Creator:
Clempner, Julio B. ; Poznyak, Alexander S.
Contributor:
Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Title:
Convergence method, properties and computational complexity for Lyapunov games
Group publication title:
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
Date:
Resource Type:
DOI:
Pages:
Source:
AMCS, Volume 21, Number 2 (2011) ; click here to follow the link