Object structure

Title:

Convergence method, properties and computational complexity for Lyapunov games

Group publication title:

AMCS, Volume 21 (2011)

Creator:

Clempner, Julio B. ; Poznyak, Alexander S.

Subject and Keywords:

Lyapunov game ; Lyapunov equilibrium point ; best reply ; repeated games ; forward decision process

Abstract:

We introduce the concept of a Lyapunov game as a subclass of strictly dominated games and potential games. The advantage of this approach is that every ergodic system (repeated game) can be represented by a Lyapunov-like function. A direct acyclic graph is associated with a game. The graph structure represents the dependencies existing between the strategy profiles. By definition, a Lyapunov-like function monotonically decreases and converges to a single Lyapunov equilibrium point identified by the sink of the game graph. ; It is important to note that in previous works this convergence has not been guaranteed even if the Nash equilibrium point exists. The best reply dynamics result in a natural implementation of the behavior of a Lyapunov-like function. Therefore, a Lyapunov game has also the benefit that it is common knowledge of the players that only best replies are chosen. By the natural evolution of a Lyapunov-like function, no matter what, a strategy played once is not played again. ; As a construction example, we show that, for repeated games with bounded nonnegative cost functions within the class of differentiable vector functions whose derivatives satisfy the Lipschitz condition, a complex vector-function can be built, where each component is a function of the corresponding cost value and satisfies the condition of the Lyapunov-like function. The resulting vector Lyapunov-like function is a monotonic function which can only decrease over time. Then, a repeated game can be represented by a one-shot game. The functionality of the suggested method is successfully demonstrated by a simulated experiment.

Publisher:

Zielona Góra: Uniwersytet Zielonogórski

Contributor:

Korbicz, Józef - red. ; Uciński, Dariusz - red.

Date:

2011

Resource Type:

artykuł

DOI:

10.2478/v10006-011-0026-x

Pages:

349-361

Source:

AMCS, Volume 21, Number 2 (2011)

Language:

eng

Rights:

Biblioteka Uniwersytetu Zielonogórskiego