Convergence method, properties and computational complexity for Lyapunov games

Julio B. Clempner; Alexander S. Poznyak

International Journal of Applied Mathematics and Computer Science (2011)

  • Volume: 21, Issue: 2, page 349-361
  • ISSN: 1641-876X

Abstract

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

How to cite

top

Julio B. Clempner, and Alexander S. Poznyak. "Convergence method, properties and computational complexity for Lyapunov games." International Journal of Applied Mathematics and Computer Science 21.2 (2011): 349-361. <http://eudml.org/doc/208052>.

@article{JulioB2011,
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.},
author = {Julio B. Clempner, Alexander S. Poznyak},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Lyapunov game; Lyapunov equilibrium point; best reply; repeated games; forward decision process},
language = {eng},
number = {2},
pages = {349-361},
title = {Convergence method, properties and computational complexity for Lyapunov games},
url = {http://eudml.org/doc/208052},
volume = {21},
year = {2011},
}

TY - JOUR
AU - Julio B. Clempner
AU - Alexander S. Poznyak
TI - Convergence method, properties and computational complexity for Lyapunov games
JO - International Journal of Applied Mathematics and Computer Science
PY - 2011
VL - 21
IS - 2
SP - 349
EP - 361
AB - 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.
LA - eng
KW - Lyapunov game; Lyapunov equilibrium point; best reply; repeated games; forward decision process
UR - http://eudml.org/doc/208052
ER -

References

top
  1. Axelrod, R. (1984). The Evolution of Cooperation, Basic Books, New York, NY. 
  2. Bernheim, B.D. (1984). Rationalizable strategic behavior, Econometrica 52(4): 1007-1028. Zbl0552.90098
  3. Chen, X. and Deng, X. (2006). Setting the complexity of 2-player Nash equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, CA, USA, pp. 261-270. 
  4. Chen, X., Deng, X. and Tengand, S.-H. (2006). Computing Nash equilibria: Approximation and smoothed complexity, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, CA, USA, pp. 603-612. 
  5. Clempner, J. (2006). Modeling shortest path games with Petri nets: A Lyapunov based theory, International Journal of Applied Mathematics and Computer Science 16(3): 387-397. Zbl1142.91375
  6. Daskalakis, C., Goldberg, P. and Papadimitriou, C. (2006a). The complexity of computing a Nash equilibrium, Proceedings of the 38th ACM Symposium on Theory of Computing, STOC 2006, Seattle, WA, USA, pp. 71-78. Zbl1301.68142
  7. Daskalakis, C., Mehta, A. and Papadimitriou, C. (2006b). A note on approximate Nash equilibria, Proceedings of the 2nd Workshop on Internet and Network Economics, WINE 06, Patras, Greece, pp. 297-306. Zbl1167.91390
  8. Fabrikant, A. and Papadimitriou, C. (2008). The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, CA, USA, pp. 844-853. Zbl1192.68357
  9. Fabrikant, A., Papadimitriou, C. and Talwar, K. (2004). The complexity of pure Nash equilibria, Proceedings of the 36th ACM Symposium on Theory of Computing, STOC 2006, Chicago, IL, USA, pp. 604-612. Zbl1192.91042
  10. Goemans, M., Mirrokni, V. and Vetta, A. (2005). Sink equilibria and convergence, Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, FOCS 2008, Pittsburgh, PA, USA, pp. 142-154. 
  11. Griffin, T.G. and Shepherd F.B. and Wilfong, G.W. (2002). The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking 10(2): 232-243. 
  12. Kakutani, S. (1941). A generalization of Brouwer's fixed point theorem, Duke Journal of Mathematics 8(3): 457-459. Zbl67.0742.03
  13. Kontogiannis, S., Panagopoulou, P. and Spirakis, P. (2006). Polynomial algorithms for approximating nash equilibria of bimatrix games, Proceedings of the 2nd Workshop on Internet and Network Economics, WINE 06, Patras, Greece, pp. 286-296. Zbl1159.91307
  14. Lakshmikantham, V., Matrosov, V. and Sivasundaram, S. (1991). Vector Lyapunov Functions and Stability Analysis of Nonlinear Systems, Kluwer Academic Publication, Dordrecht. Zbl0721.34054
  15. Lipton, R.J., Markakis, E. and Mehta, A. (2003). Playing large games using simple strategies, Proceedings of the 4th ACM Conference on Electronic Commerce, EC 2003, San Diego, CA, USA, pp. 36-41. 
  16. Mirrokni, V. and Vetta, A. (2004). Convergence issues in competitive games, Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, Cambridge, MA, USA, pp. 183-194. Zbl1105.91300
  17. Moulin, H. (1984). Dominance solvability and Cournot stability, Mathematical Social Sciences 7(1): 83-102. Zbl0541.90098
  18. Myerson, R. B. (1978). Refinements of the Nash equilibrium concept, International Journal of Game Theory 7(2): 73-80. Zbl0392.90093
  19. Nash, J. (1996). Essays on Game Theory, Elgar, Cheltenham. 
  20. Nash, J. (1951). Non-cooperative games, Annals of Mathematics 54(2): 287-295. Zbl0045.08202
  21. Nash, J. (2002). The Essential John Nash, H.W. Kuhn and S. Nasar, Princeton, NJ. Zbl1033.01024
  22. Pearce, D. (1984). Rationalizable strategic behavior and the problem of perfection, Econometrica 52(4): 1029-1050. Zbl0552.90097
  23. Poznyak, A.S. (2008). Advance Mathematical Tools for Automatic Control Engineers, Vol. 1: Deterministic Techniques, Elsevier, Amsterdam. 
  24. Poznyak, A.S., Najim, K. and Gomez-Ramirez, E. (2000). SelfLearning Control of Finite Markov Chains, Marcel Dekker, New York, NY. Zbl0960.93001
  25. Selten, R. (1975). Reexamination of the perfectness concept for equilibrium points in extensive games, International Journal of Game Theory 4(1): 25-55. Zbl0312.90072
  26. Tarapata, Z. (2007). Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms, International Journal of Applied Mathematics and Computer Science 17(2): 269-287, DOI: 10.2478/v10006-007-0023-2. Zbl1120.93051
  27. Topkis, D. (1979). Equilibrium points in nonzero-sum n-persons submodular games, SIAM Journal of Control and Optimization 17(6): 773-787. Zbl0433.90091
  28. Toth, B. and Kreinovich, V. (2009). Verified methods for computing Pareto sets: General algorithmic analysis, International Journal of Applied Mathematics and Computer Science 19(3): 369-380, DOI: 10.2478/v10006/009-0031-5. Zbl1300.90041

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.