Vincenzo Auletta
ABSTRACT
We present the first general bounds on the mixing time of logit dynamics for wide classes of strategic games. The logit dynamics describes the behaviour of a complex system whose individual components act "selfishly" and keep responding according to some partial ("noisy") knowledge of the system. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that, for potential games, the mixing time is upper and lower bounded by an "exponential" in the inverse of the noise and in the maximum potential difference. Instead, for games with dominant strategies, the mixing time cannot grow arbitrarily with the inverse of the noise. Finally, we refine our analysis for a subclass of potential games called "graphical" coordination games and we give evidence that the mixing time strongly depends on the structure of the underlying graph. Games in this class have been previously studied in Physics and, more recently, in Computer Science in the context of diffusion of new technologies.
- Arash Asadpour and Amin Saberi. On the inefficiency ratio of stable equilibria in congestion games. In Proc. of the 5th International Workshop on Internet and Network Economics (WINE'09), volume 5929 of LNCS, pages 545--552. Springer, 2009. Google Scholar
Digital Library
- Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, and Giuseppe Persiano. Mixing time and stationary expected social welfare of logit dynamics. In 3rd Int. Symp. on Algorithmic Game Theory (SAGT), volume 6386 of LNCS, pages 54--65. Springer, 2010. Google ScholarDigital Library
- Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres. Glauber dynamics on trees and hyperbolic graphs. Probability Theory and Related Fields, 131:311--340, 2005.Google ScholarCross Ref
- Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5:387--424, 1993.Google ScholarCross Ref
- Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):1047--1071, 1993.Google Scholar
- John C. Harsanyi and Reinhard Selten. A General Theory of Equilibrium Selection in Games. MIT Press, 1988.Google Scholar
- David Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.Google Scholar
- Jason R. Marden, H. Peyton Young, Gürdal Arslan, and Jeff S. Shamma. Payoff-based dynamics for multiplayer weakly acyclic games. SIAM Journal on Control and Optimization, 48(1):373--396, 2009. Google ScholarDigital Library
- Fabio Martinelli. Lectures on Glauber dynamics for discrete spin models. In Lectures on Probability Theory and Statistics (Saint-Flour, 1997), volume 1717 of Lecture Notes in Math., pages 93--191. Springer, 1999.Google Scholar
- Panayotis Mertikopoulos and Aris L. Moustakas. The emergence of rational behavior in the presence of stochastic perturbations. The Annals of Applied Probability, 20(4):1359--1388, 2010.Google ScholarCross Ref
- Andrea Montanari and Amin Saberi. Convergence to equilibrium in local interaction games. In Proc. of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pages 303--312. IEEE, 2009. Google ScholarDigital Library
- Noam Nisan, Michael Schapira, and Aviv Zohar. Asynchronous best-reply dynamics. In 4th International Workshop on Internet and Network Economics (WINE), volume 5385 of LNCS, pages 531--538. Springer, 2008. Google ScholarDigital Library
- H. Peyton Young. Adaptive learning in systems of interacting agents. In Internet and Network Economics, volume 5929 of LNCS, pages 13--16. Springer Berlin / Heidelberg, 2009. Google ScholarDigital Library
- H. Peyton Young. The diffusion of innovations in social networks, chapter in "The Economy as a Complex Evolving System", vol. III, Lawrence E. Blume and Steven N. Durlauf, eds. Oxford University Press, 2003.Google Scholar
Index Terms
- Convergence to equilibrium of logit dynamics for strategic games
Recommendations
Convergence to Equilibrium of Logit Dynamics for Strategic Games
We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise $$\beta $$β describes the behavior of a complex system whose ...
Strategic Reasoning in Digital Zero-Sum Games
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent SystemsDigital zero-sum games are a challenging domain for artificial intelligence techniques. In such games, human players often resort to strategies, i.e., memorized sequences of low-level actions that guide their behavior. In this research we model this way ...
Double-oracle algorithm for computing an exact nash equilibrium in zero-sum extensive-form games
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systemsWe investigate an iterative algorithm for computing an exact Nash equilibrium in two-player zero-sum extensive-form games with imperfect information. The approach uses the sequence-form representation of extensive-form games and the double-oracle ...
Comments