Document Open Access Logo

Subgame-Perfect Equilibria in Mean-Payoff Games

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

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2021.8.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Léonard Brice
  • LIGM, Univ. Gustave Eiffel, CNRS, F-77454 Marne-la-Vallée, France
Jean-François Raskin
  • Université libre de Bruxelles, Brussels, Belgium
Marie van den Bogaard
  • LIGM, Univ. Gustave Eiffel, CNRS, F-77454 Marne-la-Vallée, France

Funding

This work is partially supported by the ARC project Non-Zero Sum Game Graphs: Applications to Reactive Synthesis and Beyond (Fédération Wallonie-Bruxelles), the EOS project Verifying Learning Artificial Intelligence Systems (F.R.S.-FNRS & FWO), the COST Action 16228 GAMENET (European Cooperation in Science and Technology), and by the PDR project Subgame perfection in graph games (F.R.S.- FNRS).

Cite AsGet BibTex

Léonard Brice, Jean-François Raskin, and Marie van den Bogaard. Subgame-Perfect Equilibria in Mean-Payoff Games. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CONCUR.2021.8

Abstract

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 the least fixed point of the negotiation function. Finally, we show that the negotiation function is piecewise linear, and can be analyzed using the linear algebraic tool box. As a corollary, we prove the decidability of the SPE constrained existence problem, whose status was left open in the literature.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Formal methods
  • Theory of computation → Logic and verification
  • Theory of computation → Solution concepts in game theory
Keywords
  • Games on graphs
  • subgame-perfect equilibria
  • mean-payoff objectives.

Metrics

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

Related Versions

References

  1. Rajeev Alur, Aldric Degorre, Oded Maler, and Gera Weiss. On omega-languages defined by mean-payoff conditions. In Luca de Alfaro, editor, Foundations of Software Science and Computational Structures, 12th International Conference, FOSSACS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedings, volume 5504 of Lecture Notes in Computer Science, pages 333-347. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-00596-1_24.
  2. 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. Google Scholar
  3. Léonard Brice, Jean-François Raskin, and Marie van den Bogaard. Subgame-perfect equilibria in mean-payoff games. CoRR, abs/2101.10685, 2021. URL: http://arxiv.org/abs/2101.10685.
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. 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. Google Scholar
  7. 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. Google Scholar
  8. 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
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. 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. URL: https://doi.org/10.1007/978-3-642-15375-4_19.
  12. Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Strategy logic. Inf. Comput., 208(6):677-693, 2010. URL: https://doi.org/10.1016/j.ic.2009.07.004.
  13. 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. Google Scholar
  14. 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. URL: https://doi.org/10.1287/moor.2016.0843.
  15. Orna Kupferman, Giuseppe Perelli, and Moshe Y. Vardi. Synthesis with rational environments. Ann. Math. Artif. Intell., 78(1):3-20, 2016. URL: https://doi.org/10.1007/s10472-016-9508-8.
  16. Donald A. Martin. Borel determinacy. Annals of Mathematics, pages 363-371, 1975. Google Scholar
  17. Noémie Meunier. Multi-Player Quantitative Games: Equilibria and Algorithms. PhD thesis, Université de Mons, 2016. Google Scholar
  18. Martin J. Osborne. An introduction to game theory. Oxford Univ. Press, 2004. Google Scholar
  19. Eilon Solan and Nicolas Vieille. Deterministic multi-player dynkin games. Journal of Mathematical Economics, 39(8):911-929, 2003. Google Scholar
  20. 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. Google Scholar
  21. Nicolas Vieille and Eilon Solan. Deterministic multi-player Dynkin games. Journal of Mathematical Economics, Vol.39,num. 8:pp.911-929, 2003. URL: https://doi.org/10.1016/S0304-4068(03)00021-1.
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 Imprint Privacy Contact