A Sufficient Condition for Weakly Acyclic games with Applications

zhao, guo and Chai, Yingming (2024): A Sufficient Condition for Weakly Acyclic games with Applications.

Abstract

The class of weakly acyclic games captures many practical application domains, and is particularly relevant for multi-agent distributed control problems. However, reliably checking weak acyclicity is extremely computationally intractable (PSPACE-complete) in the worst case. The present paper identifies sufficient conditions for weak acyclicity by means of the transitive closure of individual conditional preference, which can be constructed in terms of better-reply improvement paths. This pure-ordinal approach leads to a novel connection between weak acyclic games and better-reply secure games. Specifically, a better-reply secure game is weakly acyclic if the better reply dynamics does not possess a dense orbit (in addition to the quasi-concavity of individual preferences as well as the usual convexity and compactness assumptions on strategy sets). These results give a partial answer to an open problem of finding applicable and tractable conditions for weak acyclicity, posed by Fabrikant, Jaggard, and Schapira in 2013.

• Item Type: MPRA Paper
• Language: English
• Keywords: pure-strategy Nash equilibrium, weakly acyclicity, better reply dynamics, better-reply security
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; D - Microeconomics > D0 - General > D01 - Microeconomic Behavior: Underlying Principles

References

B. Swenson, C. Eksin, S. Kar and A. Ribeiro. 2018. "Distributed Inertial Best-Response Dynamics," IEEE Transactions on Automatic Control, vol. 63, no. 12, pp. 4294-4300, doi: 10.1109/TAC.2018.2817161.

Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo, Alex Scott, Bassel Tarbush & Samuel Wiese. Best-response dynamics, playing sequences, and convergence to equilibrium in random games. Int J Game Theory (2023). Volume 52, pages 703–735. https://doi.org/10.1007/s00182-023-00837-4

D. Fudenberg, D. Levine. The Theory of Learning in Games. Cambridge, MA: MIT Press; 1998.

N. Nisan, T. Roughgarden, È. Tardos, V. Vazirani (Eds.). Algorithmic Game Theory, Cambridge University Press (2007)

HART, S., AND A. MAS-COLELL (2003): “Uncoupled Dynamics Do Not Lead to Nash Equilibrium,” American Economic Review, 93, 1830–1836

Young, H.P. (1993): The evolution of conventions. Econometrica 61(1), 57–84

Jason R. Marden, H. Peyton Young, Gürdal Arslan, and Jeff S. Shamma. 2009. Payoff-Based Dynamics for Multiplayer Weakly Acyclic Games, SIAM Journal on Control and Optimization Vol. 48, Iss. 1 pp373-396 https://doi.org/10.1137/070680199

Itai Arieli & H. Peyton Young, 2016. "Stochastic Learning Dynamics and Speed of Convergence in Population Games," Econometrica, vol. 84, pages 627-676, March.

Roee Engelberg, Michael Schapira. Weakly-Acyclic (Internet) Routing Games. Theory Comput Syst. Volume 54 Issue 3April 2014 pp 431–452. https://doi.org/10.1007/s00224-013-9474-z

Jason R. Marden, Gürdal Arslan, and Jeff S. Shamma. 2010. Cooperative Control and Potential Games. IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics 39(6):1393 – 1407

Fabrikant, A., Jaggard, A.D. & Schapira, M. On the Structure of Weakly Acyclic Games. Theory Comput Syst 53, 107–122 (2013). https://doi.org/10.1007/s00224-013-9457-0

Mirrokni, V.S., Skopalik, A.: On the complexity of Nash dynamics and sink equilibria. In: ACM Conference on Electronic Commerce, pp. 1–10 (2009)

James W. Friedman,Claudio Mezzetti.2001. Learning in Games by Random Sampling. Journal of Economic Theory. 98(1):55-84

Kukushkin, N., Takahashi, S. & Yamamori, T. Improvement dynamics in games with strategic complementarities. Int J Game Theory 33, 229–238 (2005). https://doi.org/10.1007/s001820400195

Antonio Cabrales, Roberto Serrano. Implementation in adaptive better-response dynamics: Towards a general theory of bounded rationality in mechanisms. Games and Economic Behavior, 2011, vol. 73, issue 2, 360-374

Nikolai S. Kukushkin. 2018. Better response dynamics and Nash equilibrium in discontinuous games. Journal of Mathematical Economics 74. 68–78

Kenneth H. Rosen. Discrete Mathematics and Its Applications (8Th Edition). McGraw-Hill Higher Education, 2018

Davey B. and Priestley H. Introduction to Lattices and Order (2nd Edition). Cambridge University Press, Cambridge, 2002.

Jech, Thomas (2002). Set theory, third millennium edition (revised and expanded). Springer. ISBN 3-540-44085-2.

Philip J. Reny (1999) On the existence of pure and mixed equilibria in discontinuous games. Econometrica 67(5):1029–1056

Philip J. Reny (2020). "Nash Equilibrium in Discontinuous Games," Annual Review of Economics, vol. 12(1), pages 439-470, August.

Gierz, G., Hofmann K., Keimel K., Lawson J., Mislove M. and Scott D., Continuous Lattices and Domains. Cambridge University Press, Cambridge, 2003.

Gibbard A (1974) A pareto-consistent libertarian claim. Journal of Economic Theory 7: 617–631.

Boutilier C, Brafman RI, Domshlak C, Hoos HH, Poole D (2004) Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research 21: 135–191.

Stirling WC, Felin T (2013) Game Theory, Conditional Preferences, and Social Influence. PLoS ONE 8(2): e56751. https://doi.org/10.1371/journal.pone.0056751

Simon, Herbert A. 1955. “A Behavioral Model of Rational Choice’’, Quart. J. Econ. 69(1): 99-118.

Kukushkin, Nikolai S., 1999. "Potential games: a purely ordinal approach," Economics Letters, vol. 64(3), pages 279-283, September.

Morris W. Hirsch, Stephen Smale, Robert L. Devaney, Differential equations, dynamical systems, and an introduction to chaos (3rd Edition), Academic Press, 2012