Document Open Access Logo

Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability

Authors Thomas Brihaye, Véronique Bruyère, Noémie Meunier, Jean-Francois Raskin

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.504.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Brihaye
Véronique Bruyère
Noémie Meunier
Jean-Francois Raskin

Cite As Get BibTex

Thomas Brihaye, Véronique Bruyère, Noémie Meunier, and Jean-Francois Raskin. Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 504-518, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CSL.2015.504

Abstract

We study n-player turn-based games played on a finite directed graph. For each play, the players have to pay a cost that they want to minimize. Instead of the well-known notion of Nash equilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE), a refinement of NE well-suited in the framework of games played on graphs. We also study natural variants of SPE, named weak (resp. very weak) SPE, where players who deviate cannot use the full class of strategies but only a subclass with a finite number of (resp. a unique) deviation step(s).

Our results are threefold. Firstly, we characterize in the form of a Folk theorem the set of all plays that are the outcome of a weak SPE. Secondly, for the class of quantitative reachability games, we prove the existence of a finite-memory SPE and provide an algorithm for computing it (only existence was known with no information regarding the memory). Moreover, we show that the existence of a constrained SPE, i.e. an SPE such that each player pays a cost less than a given constant, can be decided. The proofs rely on our Folk theorem for weak SPEs (which coincide with SPEs in the case of quantitative reachability games) and on the decidability of MSO logic on infinite words. Finally with similar techniques, we provide a second general class of games for which the existence of a (constrained) weak SPE is decidable.

Subject Classification

Keywords
  • multi-player games on graphs
  • quantitative objectives
  • Nash equilibrium
  • subgame perfect equilibrium
  • quantitative reachability

Metrics

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

References

  1. Thomas Brihaye, Véronique Bruyère, Julie De Pril, and Hugo Gimbert. On subgame perfection in quantitative reachability games. Logical Methods in Computer Science, 9, 2012. Google Scholar
  2. Thomas Brihaye, Véronique Bruyère, Noémie Meunier, and Jean-François Raskin. Weak subgame perfect equilibria and their application to quantitative reachability. CoRR, abs/1504.01557, 2015. Google Scholar
  3. Thomas Brihaye, Julie De Pril, and Sven Schewe. Multiplayer cost games with simple Nash equilibria. In LFCS, volume 7734 of Lecture Notes in Comput. Sci., pages 59-73. Springer, 2013. Google Scholar
  4. Véronique Bruyère, Noémie Meunier, and Jean-François Raskin. Secure equilibria in weighted games. In CSL-LICS, pages 26:1-26:26. ACM, 2014. Google Scholar
  5. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Trans. Comput. Log., 11, 2010. Google Scholar
  6. János Flesch, Jeroen Kuipers, Ayala Mashiah-Yaakovi, Gijs Schoenmakers, Eilon Solan, and Koos Vrieze. Perfect-information games with lower-semicontinuous payoffs. Math. Oper. Res., 35:742-755, 2010. Google Scholar
  7. Drew Fudenberg and David Levine. Subgame-perfect equilibria of finite- and infinite-horizon games. Journal of Economic Theory, 31:251-268, 1983. Google Scholar
  8. Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991. Google Scholar
  9. Miroslav Klimos, Kim G. Larsen, Filip Stefanak, and Jeppe Thaarup. Nash equilibria in concurrent priced games. In LATA, volume 7183 of Lecture Notes in Comput. Sci., pages 363-376. Springer, 2012. Google Scholar
  10. H.W. Kuhn. Extensive games and the problem of information. Classics in Game Theory, pages 46-68, 1953. Google Scholar
  11. Jean-François Mertens. Repeated games. In Internat. Congress Mathematicians, American Mathematical Society, pages 1528-1577. Providence, RI, 1987. Google Scholar
  12. J. F. Nash. Equilibrium points in n-person games. In PNAS, volume 36, pages 48-49. National Academy of Sciences, 1950. Google Scholar
  13. Martin J. Osborne and Ariel Rubinstein. A course in Game Theory. MIT Press, Cambridge, MA, 1994. Google Scholar
  14. Amir Pnueli and Roni Rosner. On the synthesis of a reactive module. In POPL, pages 179-190. ACM Press, 1989. Google Scholar
  15. Stéphane Le Roux and Arno Pauly. Infinite sequential games with real-valued payoffs. In CSL-LICS, pages 62:1-62:10. ACM, 2014. Google Scholar
  16. Ariel Rubinstein. Comments on the interpretation of game theory. Econometrica, 59:909-924, 1991. Google Scholar
  17. Eilon Solan and Nicolas Vieille. Deterministic multi-player dynkin games. Journal of Mathematical Economics, 39:911-929, 2003. Google Scholar
  18. Wolfgang Thomas. Automata on infinite objects. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pages 133-192. Elsevier Science Publishers, Amsterdam, 1990. Google Scholar
  19. Michael Ummels. Rational behaviour and strategy construction in infinite multiplayer games. In FSTTCS, volume 4337 of Lecture Notes in Comput. Sci., pages 212-223. Springer, 2006. 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