×

The complexity of subgame perfect equilibria in quantitative reachability games. (English) Zbl 1519.91050

Summary: We study multiplayer quantitative reachability games played on a finite directed graph, where the objective of each player is to reach his target set of vertices as quickly as possible. 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. It is known that there always exists an SPE in quantitative reachability games and that the constrained existence problem is decidable. We here prove that this problem is PSPACE-complete. To obtain this result, we propose a new algorithm that iteratively builds a set of constraints characterizing the set of SPE outcomes in quantitative reachability games. This set of constraints is obtained by iterating an operator that reinforces the constraints up to obtaining a fixpoint. With this fixpoint, the set of SPE outcomes can be represented by a finite graph of size at most exponential. A careful inspection of the computation allows us to establish PSPACE membership.
For the conference paper see [Fokkink, Wan (ed.) et al., 30th international conference on concurrency theory, CONCUR 2019, Amsterdam, the Netherlands, August 27–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 140, Article 13, 16 p. (2019; Zbl 1519.91051)].

MSC:

91A43 Games involving graphs
91A11 Equilibrium refinements
91A68 Algorithmic game theory and complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1519.91051
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Thomas Brihaye, V´eronique Bruy‘ere, Julie De Pril, and Hugo Gimbert. On subgame perfection in quantitative reachability games.Logical Methods in Computer Science, 9(1), 2012. · Zbl 1352.68146
[2] Thomas Brihaye, V´eronique Bruy‘ere, Aline Goeminne, and Jean-Fran¸cois Raskin. Constrained existence problem for weak subgame perfect equilibria withω-regular boolean objectives. In
[3] Thomas Brihaye, V´eronique Bruy‘ere, Aline Goeminne, and Jean-Fran¸cois Raskin. Constrained existence problem for weak subgame perfect equilibria with omega-regular boolean objectives. · Zbl 1501.91028
[4] Thomas Brihaye, V´eronique Bruy‘ere, Aline Goeminne, and Nathan Thomasset. On relevant equilibria in reachability games. InRP 2019, pages 48-62, 2019. · Zbl 1455.91055
[5] Thomas Brihaye, V´eronique Bruy‘ere, No´emie Meunier, and Jean-Fran¸cois Raskin. Weak subgame perfect equilibria and their application to quantitative reachability. InCSL, volume 41 ofLIPIcs, pages 504-518. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. · Zbl 1375.91042
[6] Thomas Brihaye, Julie De Pril, and Sven Schewe. Multiplayer cost games with simple nash equilibria. InLFCS, volume 7734 ofLNCS, pages 59-73. Springer, 2013. · Zbl 1422.91043
[7] Dietmar Berwanger. Admissibility in infinite games. InSTACS, volume 4393 ofLNCS, pages 188-199. Springer, 2007. · Zbl 1186.68278
[8] Romain Brenguier, Guillermo A. P´erez, Jean-Francois Raskin, and Ocan Sankur. Admissibility in Quantitative Graph Games. InFSTTCS, volume 65 ofLIPIcs, pages 42:1-42:14, 2016. · Zbl 1394.91058
[9] Romain Brenguier, Arno Pauly, Jean-Fran¸cois Raskin, and Ocan Sankur. Admissibility in Games with Imperfect Information (Invited Talk). InCONCUR, volume 85 ofLIPIcs, pages 2:1-2:23. · Zbl 1394.91058
[10] V´eronique Bruy‘ere, St´ephane Le Roux, Arno Pauly, and Jean-Fran¸cois Raskin. On the existence of weak subgame perfect equilibria. InFOSSACS, volume 10203 ofLNCS, pages 145-161, 2017. · Zbl 1486.91016
[11] Romain Brenguier, Jean-Fran¸cois Raskin, and Mathieu Sassolas. The complexity of admissibility in omega-regular games. InCSL-LICS, pages 23:1-23:10. ACM, 2014. · Zbl 1401.68110
[12] Romain Brenguier, Jean-Fran¸cois Raskin, and Ocan Sankur. Assume-admissible synthesis. In CONCUR, LIPIcs 42, pages 100-113. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. · Zbl 1374.68322
[13] V´eronique Bruy‘ere. Computer aided synthesis: A game-theoretic approach. InDLT, volume 10396 ofLNCS, pages 3-35. Springer, 2017. · Zbl 1494.91033
[14] Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and Jean-Fran¸cois Raskin. The complexity of rational synthesis. InICALP, volume 55 ofLIPIcs, pages 121:1-121:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. · Zbl 1388.68163
[15] K. Chatterjee, T. A. Henzinger, and M. Jurdzinski. Games with secure equilibria.Theoretical Computer Science, 365:67-82, 2006. · Zbl 1108.91007
[16] Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Strategy logic.Inf. Comput., 208(6):677-693, 2010. · Zbl 1205.68197
[17] Emmanuel Filiot, Raffaella Gentilini, and Jean-Fran¸cois Raskin. Rational synthesis under imperfect information. InLICS, pages 422-431. ACM, 2018. · Zbl 1452.91014
[18] Dana Fisman, Orna Kupferman, and Yoad Lustig. Rational synthesis. InTACAS, volume 6015 ofLNCS, pages 190-204. Springer, 2010. · Zbl 1284.68396
[19] Drew Fudenberg and David Levine. Subgame-perfect equilibria of finite- and infinite-horizon games.Journal of Economic Theory, 31:251-268, 1983. · Zbl 0521.90106
[20] Erich Gr¨adel and Michael Ummels. Solution Concepts and Algorithms for Infinite Multiplayer Games. InNew Perspectives on Games and Interaction, volume 4, pages 151-178. Amsterdam University Press, 2008. · Zbl 1377.91014
[21] Orna Kupferman, Giuseppe Perelli, and Moshe Y. Vardi. Synthesis with rational environments. InEUMAS, LNCS 8953, pages 219-235. Springer, 2014. · Zbl 1372.68173
[22] H.W. Kuhn. Extensive games and the problem of information. InClassics in Game Theory, pages 46-68. Princeton University Press, 1953.
[23] Fabio Mogavero, Aniello Murano, and Moshe Y. Vardi. Reasoning About Strategies. InFSTTCS 2010, volume 8 ofLIPIcs, pages 133-144. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010. · Zbl 1245.68138
[24] J. F. Nash. Equilibrium points inn-person games. InPNAS, volume 36, pages 48-49. National Academy of Sciences, 1950. · Zbl 0036.01104
[25] Martin J. Osborne.An introduction to game theory. Oxford Univ. Press, 2004.
[26] A. Pnueli and R. Rosner. On the synthesis of a reactive module. InPOPL, pages 179-190. ACM Press, 1989. · Zbl 0686.68015
[27] Eilon Solan and Nicolas Vieille. Deterministic multi-player Dynkin games.Journal of Mathematical Economics, 39:911-929, 2003. · Zbl 1081.91004
[28] Michael Ummels. Rational behaviour and strategy construction in infinite multiplayer games. In FSTTCS, volume 4337 ofLNCS, pages 212-223. Springer, 2006. · Zbl 1177.91060
[29] Michael Ummels. The complexity of nash equilibria in infinite multiplayer games. InFOSSACS, volume 4962 ofLNCS, pages 20-34. Springer, 2008. · Zbl 1138.91359
[30] Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in limit-average games. InCONCUR, volume 6901 ofLecture Notes in Comput. Sci., pages 482-496. Springer, · Zbl 1343.68177
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.