<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

Convergence method, properties and computational complexity for Lyapunov games

Center for Computing Research, National Polytechnic Institute, Av. Juan de Dios Batiz s/n, Edificio CIC, Col. Nueva Industrial Valleys, 07738 Mexico City, Mexico

Department of Automatic Control, Center for Research and Advanced Studies, Av. IPN 2508, Col. San Pedro Zacatenco, 07360 Mexico City, Mexico

International Journal of Applied Mathematics and Computer Science

{"article-title":"Convergence method, properties and computational complexity for Lyapunov games"}

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...

Convergence method, properties and computational complexity for Lyapunov games

Published Online: Jun 22, 2011

Page range: 349 - 361

DOI: https://doi.org/10.2478/v10006-011-0026-x

Keywords
Lyapunov game, Lyapunov equilibrium point, best reply, repeated games, forward decision process

This content is open access.

Convergence method, properties and computational complexity for Lyapunov games

Published Online: Jun 22, 2011

Page range: 349 - 361

DOI: https://doi.org/10.2478/v10006-011-0026-x

KeywordsLyapunov game, Lyapunov equilibrium point, best reply, repeated games, forward decision process

This content is open access.

Keywords
Lyapunov game, Lyapunov equilibrium point, best reply, repeated games, forward decision process