Document Open Access Logo

Mixed Nash Equilibria in Concurrent Terminal-Reward Games

Authors Patricia Bouyer, Nicolas Markey, Daniel Stan

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.351.pdf
  • Filesize: 471 kB
  • 13 pages

Document Identifiers

Author Details

Patricia Bouyer
Nicolas Markey
Daniel Stan

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 351-363, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.351

Abstract

We study mixed-strategy Nash equilibria in multiplayer deterministic concurrent games played on graphs, with terminal-reward payoffs (that is, absorbing states with a value for each player). We show undecidability of the existence of a constrained Nash equilibrium (the constraint requiring that one player should have maximal payoff), with only three players and 0/1-rewards (i.e., reachability objectives). This has to be compared with the undecidability result by Ummels and Wojtczak for turn-based games which requires 14 players and general rewards. Our proof has various interesting consequences: (i) the undecidability of the existence of a Nash equilibrium with a constraint on the social welfare; (ii) the undecidability of the existence of an (unconstrained) Nash equilibrium in concurrent games with terminal-reward payoffs.

Subject Classification

Keywords
  • concurrent games
  • randomized strategy
  • Nash equilibria
  • undecidability

Metrics

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

References

  1. Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Pure Nash equilibria in concurrent games. Logical Methods in Computer Science, 2014. Submitted, under revision. Google Scholar
  2. Patricia Bouyer, Nicolas Markey, and Daniel Stan. Mixed Nash equilibria in concurrent terminal-reward games. Research Report LSV-14-11, Laboratoire Spécification et Vérification, ENS Cachan, France, October 2014. Google Scholar
  3. Krishnendu Chatterjee, Marcin Jurdziński, and Rupak Majumdar. On Nash equilibria in stochastic games. In CSL'04, volume 3210 of LNCS, pages 26-40. Springer, 2004. Google Scholar
  4. Taolue Chen, Marta Kwiatkowska, David Parker, and Aistis Simaitis. Verifying team formation protocols with probabilistic model checking. In CLIMA XII, volume 6814 of LNAI, pages 190-207. Springer, 2011. Google Scholar
  5. Vincent Conitzer and Tuomas Sandholm. Complexity results about Nash equilibria. In IJCAI'03, pages 765-771, 2003. Google Scholar
  6. Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-641, 2008. Google Scholar
  7. Luca de Alfaro, Thomas Henzinger, and Orna Kupferman. Concurrent reachability games. Theoretical Computer Science, 386(3):188-217, 2007. Google Scholar
  8. Thomas A. Henzinger. Games in system design and verification. In TARK'05, pages 1-4, 2005. Google Scholar
  9. John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48-49, 1950. Google Scholar
  10. Piercesare Secchi and William D. Sudderth. Stay-in-a-set games. International Journal of Game Theory, 30:479-490, 2001. Google Scholar
  11. Wolfgang Thomas. Infinite games and verification. In CAV'02, volume 2404 of LNCS, pages 58-64. Springer, 2002. Invited Tutorial. Google Scholar
  12. Michael Ummels. The complexity of Nash equilibria in infinite multiplayer games. In FoSSaCS'08, volume 4962 of LNCS, pages 20-34. Springer, 2008. Google Scholar
  13. Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in limit-average games. In CONCUR'11, volume 6901 of LNCS, pages 482-496. Springer, 2011. Google Scholar
  14. Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in limit-average games. Technical Report abs/1109.6220, CoRR, 2011. Google Scholar
  15. Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in stochastic multiplayer games. Logical Methods in Computer Science, 7(3), 2011. Google Scholar
  16. Nicolas Vieille. Equilibrium in two-person stochastic games I: A reduction. Israel Journal of Mathematics, 119:55-91, 2000. Google Scholar
  17. Nicolas Vieille. Equilibrium in two-person stochastic games II: The case of recursive games. Israel Journal of Mathematics, 119:93-126, 2000. 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