Document Open Access Logo

∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games

Authors Kristoffer Arnsfelt Hansen , Steffan Christ Sølvsten

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.45.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Kristoffer Arnsfelt Hansen
  • Aarhus University, Denmark
Steffan Christ Sølvsten
  • Aarhus University, Denmark

Funding

  • Hansen, Kristoffer Arnsfelt: Supported by the Independent Research Fund Denmark under grant no. 9040-00433B.

Cite AsGet BibTex

Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten. ∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.45

Abstract

We show that the problem of deciding whether in a multi-player perfect information recursive game (i.e. a stochastic game with terminal rewards) there exists a stationary Nash equilibrium ensuring each player a certain payoff is ∃ℝ-complete. Our result holds for acyclic games, where a Nash equilibrium may be computed efficiently by backward induction, and even for deterministic acyclic games with non-negative terminal rewards. We further extend our results to the existence of Nash equilibria where a single player is surely winning. Combining our result with known gadget games without any stationary Nash equilibrium, we obtain that for cyclic games, just deciding existence of any stationary Nash equilibrium is ∃ℝ-complete. This holds for reach-a-set games, stay-in-a-set games, and for deterministic recursive games.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Exact and approximate computation of equilibria
Keywords
  • Existential Theory of the Reals
  • Stationary Nash Equilibrium
  • Perfect Information Stochastic Games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marie Louisa Tølbøll Berthelsen and Kristoffer Arnsfelt Hansen. On the computational complexity of decision problems about multi-player nash equilibria. In Dimitris Fotakis and Evangelos Markakis, editors, SAGT, volume 11801 of Lecture Notes in Computer Science, pages 153-167. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-30473-7_11.
  2. Vittorio Bilò and Marios Mavronicolas. A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games. In Nicolas Ollinger and Heribert Vollmer, editors, STACS 2016, volume 47 of LIPIcs, pages 17:1-17:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.17.
  3. Vittorio Biló and Marios Mavronicolas. ∃ℝ-complete decision problems about symmetric Nash equilibria in symmetric multi-player games. In Heribert Vollmer and Brigitte Vallé, editors, STACS 2017, volume 66 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.13.
  4. Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc., 21(1):1-46, 1989. URL: https://doi.org/10.1090/S0273-0979-1989-15750-9.
  5. E. Boros and V. Gurvich. On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles. Mathematical Social Sciences, 46(2):207-241, 2003. URL: https://doi.org/10.1016/S0165-4896(03)00077-5.
  6. Endre Boros, Vladimir Gurvich, Martin Milanič, Vladimir Oudalov, and Jernej Vičič. A three-person deterministic graphical game without nash equilibria. Discrete Applied Mathematics, 243:21-38, 2018. URL: https://doi.org/10.1016/j.dam.2018.01.008.
  7. Patricia Bouyer, Nicolas Markey, and Daniel Stan. Mixed nash equilibria in concurrent terminal-reward games. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of Leibniz International Proceedings in Informatics (LIPIcs), pages 351-363, 2014. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2014.351.
  8. Peter Bürgisser and Felipe Cucker. Exotic quantifiers, complexity classes, and complete problems. Foundations of Computational Mathematics, 9(2):135-170, 2009. URL: https://doi.org/10.1007/s10208-007-9006-9.
  9. John Canny. Some algebraic and geometric computations in pspace. Proceedings of the Annual ACM Symposium on Theory of Computing, pages 460-467, January 1988. URL: https://doi.org/10.1145/62212.62257.
  10. Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdzinski. On Nash equilibria in stochastic games. In Jerzy Marcinkowski and Andrzej Tarlecki, editors, CSL 2004, volume 3210 of Lecture Notes in Computer Science, pages 26-40. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30124-0_6.
  11. Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 261-272. IEEE Computer Society Press, 2006. URL: https://doi.org/10.1109/FOCS.2006.69.
  12. Ankush Das, Shankara Narayanan Krishna, Lakshmi Manasa, Ashutosh Trivedi, and Dominik Wojtczak. On pure nash equilibria in stochastic games. In Theory and Applications of Models of Computation, pages 359-371. Springer International Publishing, 2015. Google Scholar
  13. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195-259, 2009. URL: https://doi.org/10.1137/070699652.
  14. A. Ehrenfeucht and J. Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8(2):109-113, 1979. URL: https://doi.org/10.1007/BF01768705.
  15. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM J. Comput., 39(6):2531-2597, 2010. URL: https://doi.org/10.1137/080720826.
  16. H. Everett. Recursive games. In Contributions to the Theory of Games Vol. III, volume 39 of Ann. Math. Studies, pages 67-78. Princeton University Press, 1957. URL: https://doi.org/10.1515/9781400882151-004.
  17. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. ∃ℝ-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput., 6(1):1:1-1:23, 2018. URL: https://doi.org/10.1145/3175494.
  18. Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-93, 1989. URL: https://doi.org/10.1016/0899-8256(89)90006-7.
  19. D. Gillette. Stochastic games with zero stop probabilities. In Contributions to the Theory of Games III, volume 39 of Ann. Math. Studies, pages 179-187. Princeton University Press, 1957. URL: https://doi.org/10.1515/9781400882151-011.
  20. Hugo Gimbert, Soumyajit Paul, and B. Srivathsan. A bridge between polynomial optimization and games with imperfect recall. In AAMAS 2020. International Foundation for Autonomous Agents and Multiagent Systems, 2020. URL: https://dl.acm.org/doi/abs/10.5555/3398761.3398818.
  21. Kristoffer Arnsfelt Hansen. The real computational complexity of minmax value and equilibrium refinements in multi-player games. Theor. Comput. Syst., 63:1554-1571, 2019. URL: https://doi.org/10.1007/s00224-018-9887-9.
  22. Kristoffer Arnsfelt Hansen and Mikhail Raskin. A stay-in-a-set game without a stationary equilibrium. Electronic Proceedings in Theoretical Computer Science, 305:83-90, 2019. URL: https://doi.org/10.4204/EPTCS.305.6.
  23. Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten. Existential theory of the reals completeness of stationary nash equilibria in perfect information stochastic games, 2020. URL: http://arxiv.org/abs/2006.08314.
  24. Jeroen Kuipers, János Flesch, Gijs Schoenmakers, and Koos Vrieze. Pure subgame-perfect equilibria in free transition games. European Journal of Operational Research, 199(2):442-447, 2009. URL: https://doi.org/10.1016/j.ejor.2008.11.038.
  25. Michael Littman, Nishkam Ravi, Arjun Talwar, and Martin Zinkevich. An efficient optimal-equilibrium algorithm for two-player game trees. In Proceedings of the Twenty-Second Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-06), pages 298-30, Arlington, Virginia, 2006. AUAI Press. Google Scholar
  26. John Nash. Non-cooperative games. Annals of Mathematics, 2(54):286-295, 1951. URL: https://doi.org/10.2307/1969529.
  27. Marcus Schaefer. Realizability of graphs and linkages. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pages 461-482. Springer New York, 2013. Google Scholar
  28. Marcus Schaefer and Daniel Štefankovič. Fixed points, Nash equilibria, and the existential theory of the reals. Theor. Comput. Syst., 60:172-193, 2017. URL: https://doi.org/10.1007/s00224-015-9662-0.
  29. Piercesare Secchi and William D. Sudderth. Stay-in-a-set games. Int. J. Game Theory, 30(4):479-490, 2002. URL: https://doi.org/10.1007/s001820200092.
  30. Michael Ummels. Stochastic Multiplayer Games: Theory and Algorithms. PhD thesis, RWTH Aachen University, 2011. URL: http://darwin.bth.rwth-aachen.de/opus3/volltexte/2011/3451/pdf/3451.pdf.
  31. Michael Ummels and Dominik Wojtczak. The complexity of nash equilibria in limit-average games. In Joost-Pieter Katoen and Barbara König, editors, CONCUR 2011, volume 6901 of LNCS, pages 482-496. Springer, 2011. Google Scholar
  32. Michael Ummels and Dominik Wojtczak. The complexity of nash equilibria in limit-average games. CoRR, abs/1109.6220, 2011. Google Scholar
  33. Michael Ummels and Dominik Wojtczak. The complexity of nash equilibria in stochastic multiplayer games. Log. Meth. Comput Sci., 7(3), 2011. URL: https://doi.org/10.2168/LMCS-7(3:20)2011.
  34. J. von Neumann and O. Morgenstern. Theory of Games and Economic Behaviour. Princeton University Press, 3rd edition, 1953. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact