Document Open Access Logo

Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games

Authors Vittorio Bilò, Marios Mavronicolas

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.13.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Vittorio Bilò
Marios Mavronicolas

Cite As Get BibTex

Vittorio Bilò and Marios Mavronicolas. Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.13

Abstract

We study the complexity of decision problems about symmetric Nash equilibria for symmetric multi-player games. These decision problems concern the existence of a symmetric Nash equilibrium with certain natural properties. We show that a handful of such decision problems are Existential-R-complete; that is, they are exactly as hard as deciding the Existential Theory of the Reals.

Subject Classification

Keywords
  • Nash equilibrium
  • complexity of equilibria
  • ExistentialR-completeness

Metrics

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

References

  1. P. Austrin, M. Braverman, and E. Chlamtac. Inapproximability of NP-complete variants of Nash equilibrium. Theory of Computing, 9:117-142, 2013. Google Scholar
  2. V. Bilò and M. Mavronicolas. The complexity of decision problems about Nash equilibria in win-lose games. In Proceedings of the 5th International Symposium on Algorithmic Game Theory, volume 7615 of LNCS, pages 37-48, 2012. Google Scholar
  3. V. Bilò and M. Mavronicolas. Complexity of rational and irrational Nash equilibria. Theory of Computing Systems, 54(3):491-527, 2014. Google Scholar
  4. V. Bilò and M. Mavronicolas. A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, volume 47, pages 17:1-17:13, 2016. Google Scholar
  5. V. Bonifaci, U. Di Orio, and L. Laura. The complexity of uniform Nash equilibria and related subgraph problems. Theoretical Computer Science, 401(1-3):144-152, 2008. Google Scholar
  6. M. Braverman, Y. Kun-Ko, and O. Weinstein. Approximating the best Nash equilibrium in O(n^o(lg n)) time breaks the exponential time hypothesis. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 970-982, 2015. Google Scholar
  7. G. W. Brown and J. von Neumann. Solutions of games by differential equations. Contributions to the Theory of Games, Annals of Mathematics Studies, (24):73-79, 1950. Google Scholar
  8. J. Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 460-467, 1988. Google Scholar
  9. X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3), 2009. Google Scholar
  10. B. Codenotti and D. Štefankovič. On the computational complexity of Nash equilibria for (0, 1) bimatrix games. Information Processing Letters, 94(3):145-150, 2005. Google Scholar
  11. V. Conitzer and T. Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-641, 2008. Google Scholar
  12. C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. Google Scholar
  13. A. Deligkas, J. Fearnley, and R. Savani. Inapproximability results of approximate Nash equilibria. In Proceedings of the 12th International Conference on Web and Internet Economics, volume 10123 of LNCS, pages 29-43, 2012. Google Scholar
  14. K. Etessami and M. Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  15. M. J. Garey and D. J. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. J. Garg, R. Mehta, V. V. Vazirani, and S. Yazdanbod. ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, volume 9134 of LNCS, pages 554-566, 2015. Google Scholar
  17. I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-93, 1989. Google Scholar
  18. E. Hazan and R. Kraugthgamer. How hard is it to approximate the best Nash equilibrium? SIAM Journal on Computing, 40(1):79-91, 2011. Google Scholar
  19. J. F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36:48-49, 1950. Google Scholar
  20. J. F. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951. Google Scholar
  21. C. H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. Google Scholar
  22. A. Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 258-265, 2016. Google Scholar
  23. M. Schaefer and D. Štefankovič. Fixed points, Nash equilibria and the existential theory of the reals. Theory of Computing Systems, First online: 04 November 2015. Google Scholar
  24. A. Tarski. A decision method for elementary algebra and geometry. RAND Corporation, 1948. 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 About DROPS Imprint Privacy Contact