×
Brice, Léonard; Raskin, Jean-François; van den Bogaard, Marie

Subgame-perfect equilibria in mean-payoff games. (English) Zbl 07788978

Log. Methods Comput. Sci. 19, No. 4, Paper No. 6, 38 p. (2023).
Summary: In this paper, we provide an effective characterization of all the subgame-perfect equilibria in infinite duration games played on finite graphs with mean-payoff objectives. To this end, we introduce the notion of requirement, and the notion of negotiation function. We establish that the plays that are supported by SPEs are exactly those that are consistent with a fixed point of the negotiation function. Finally, we use that characterization to prove that the SPE threshold problem, who status was left open in the literature, is decidable.

Cited in 1 Document

MSC:

91A11 Equilibrium refinements
91A43 Games involving graphs
05C57 Games on graphs (graph-theoretic aspects)

Keywords:

games on graphs; subgame-perfect equilibria; mean-payoff objectives
Cite Review PDF
Full Text: DOI arXiv
OA License

References:

[1] BBG + 19] Thomas Brihaye, Véronique Bruyère, Aline Goeminne, Jean-François Raskin, and Marie van den Bogaard. The complexity of subgame perfect equilibria in quantitative reachability games. In CONCUR, volume 140 of LIPIcs, pages 13:1-13:16. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2019. · Zbl 1519.91051
[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. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, volume 41 of LIPIcs, pages 504-518. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2015. [BCH + 16] Romain Brenguier, Lorenzo Clemente, Paul Hunter, Guillermo A. Pérez, Mickael Randour, Jean-François Raskin, Ocan Sankur, and Mathieu Sassolas. Non-zero sum games for reactive synthesis. In Language and Automata Theory and Applications -10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings, volume 9618 of Lecture Notes in Computer Science, pages 3-23. Springer, 2016.
[3] Thomas Brihaye, Julie De Pril, and Sven Schewe. Multiplayer cost games with simple Nash equilibria. In Logical Foundations of Computer Science, International Symposium, LFCS 2013, San Diego, CA, USA, January 6-8, 2013. Proceedings, volume 7734 of Lecture Notes in Computer Science, pages 59-73. Springer, 2013. · Zbl 1422.91043
[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. · Zbl 1401.91012
[5] Romain Brenguier and Jean-François Raskin. Pareto curves of multidimensional mean-payoff games. In Daniel Kroening and Corina S. Pasareanu, editors, Computer Aided Verification -27th International Conference, CAV 2015, San Francisco, CA, USA, July 18-24, 2015, Proceedings, Part II, volume 9207 of Lecture Notes in Computer Science, pages 251-267. Springer, 2015. doi:10.1007/978-3-319-21668-3_15. · Zbl 1382.91012 · doi:10.1007/978-3-319-21668-3_15
[6] Véronique Bruyère, Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. On the existence of weak subgame perfect equilibria. CoRR, abs/1612.01402, 2016.
[7] Véronique Bruyère, Stéphane Le Roux, Arno Pauly, and Jean-François Raskin. On the existence of weak subgame perfect equilibria. In Foundations of Software Science and Computation Structures -20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, volume 10203 of Lecture Notes in Computer Science, pages 145-161, 2017. · Zbl 1486.91016
[8] Véronique Bruyère. Computer aided synthesis: A game-theoretic approach. In Developments in Language Theory -21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings, volume 10396 of Lecture Notes in Computer Science, pages 3-35. Springer, 2017. · Zbl 1494.91033
[9] Léonard Brice, Jean-François Raskin, and Marie van den Bogaard. Subgame-perfect equilibria in mean-payoff games. CoRR, 2021. [CDE + 10] Krishnendu Chatterjee, Laurent Doyen, Herbert Edelsbrunner, Thomas A. Henzinger, and Philippe Rannou. Mean-payoff automaton expressions. In Paul Gastin and François Laroussinie, editors, CONCUR 2010 -Concurrency Theory, 21th International Conference, CONCUR 2010, Paris, France, August 31-September 3, 2010. Proceedings, volume 6269 of Lecture Notes in Computer Science, pages 269-283. Springer, 2010. · Zbl 1287.68093
[10] Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Strategy logic. Inf. Comput., 208(6):677-693, 2010. doi:10.1016/j.ic.2009.07.004. · Zbl 1205.68197 · doi:10.1016/j.ic.2009.07.004
[11] [FKM + 10] 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(4):742-755, 2010. · Zbl 1232.91014
[12] János Flesch and Arkadi Predtetchinski. On refinements of subgame perfect \(\epsilon \) -equilibrium. Int. J. Game Theory, 45(3):523-542, 2016. doi:10.1007/s00182-015-0468-8. · Zbl 1388.91040 · doi:10.1007/s00182-015-0468-8
[13] János Flesch and Arkadi Predtetchinski. A characterization of subgame-perfect equilibrium plays in Borel games of perfect information. Math. Oper. Res., 42(4):1162-1179, 2017. doi: 10.1287/moor.2016.0843. · Zbl 1376.91030 · doi:10.1287/moor.2016.0843
[14] Eryk Kopczynski. Half-positional determinacy of infinite games. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd
[15] Vol. 19:4 SUBGAME-PERFECT EQUILIBRIA IN MEAN-PAYOFF GAMES 6:31 · Zbl 07788978
[16] International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 336-347. Springer, 2006. · Zbl 1133.91334
[17] Orna Kupferman, Giuseppe Perelli, and Moshe Y. Vardi. Synthesis with rational environments. Ann. Math. Artif. Intell., 78(1):3-20, 2016. doi:10.1007/s10472-016-9508-8. · Zbl 1372.68173 · doi:10.1007/s10472-016-9508-8
[18] Donald A. Martin. Borel determinacy. Annals of Mathematics, pages 363-371, 1975. · Zbl 0336.02049
[19] Noémie Meunier. Multi-Player Quantitative Games: Equilibria and Algorithms. PhD thesis, Université de Mons, 2016.
[20] Martin J. Osborne. An introduction to game theory. Oxford Univ. Press, 2004.
[21] Eilon Solan and Nicolas Vieille. Deterministic multi-player Dynkin games. Journal of Mathematical Economics, 39(8):911-929, 2003. · Zbl 1081.91004
[22] Michael Ummels. Rational behaviour and strategy construction in infinite multiplayer games. In FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings, volume 4337 of Lecture Notes in Computer Science, pages 212-223. Springer, 2006. · Zbl 1177.91060
[23] Michael Ummels. The complexity of Nash equilibria in infinite multiplayer games. In Roberto M. Amadio, editor, Foundations of Software Science and Computational Structures, 11th Inter-national Conference, FOSSACS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 -April 6, 2008. Proceedings, volume 4962 of Lecture Notes in Computer Science, pages 20-34. Springer, 2008. doi:10.1007/978-3-540-78499-9_3. · Zbl 1138.91359 · doi:10.1007/978-3-540-78499-9_3
[24] + 15] Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander Moshe Rabinovich, and Jean-François Raskin. The complexity of multi-mean-payoff and multi-energy games. Inf. Comput., 241:177-196, 2015. · Zbl 1309.68082
[25] Nicolas Vieille and Eilon Solan. Deterministic multi-player Dynkin games. Journal of Mathematical Economics, Vol.39,num. 8:pp.911-929, November 2003. doi:10.1016/S0304-4068(03)00021-1. · Zbl 1081.91004 · doi:10.1016/S0304-4068(03)00021-1
[26] C , ν C (⟨τ ⟩) < α;
[27] there exists a λ-rational strategy profileσ −i in the game G ↾v 0 such that for every strategy σ i , we have µ i (⟨σ⟩) < α.
[28] • (1) implies (2). Let τ P be such that for every strategy τ C , ν C (⟨τ ⟩) < α. In what follows, any history h compatible with an already defined strategy profileσ −i in G ↾v 0 will be decomposed in: h = v 0 h (0) v 1 h (1) . . . h (n−1) v n h (n) ,
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.