Concurrent Games with Arbitrarily Many Players (Invited Talk)

Author Nathalie Bertrand



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.1.pdf
  • Filesize: 447 kB
  • 8 pages

Document Identifiers

Author Details

Nathalie Bertrand
  • University of Rennes, Inria, CNRS, IRISA, France

Acknowledgements

This paper is based on partly published results obtained in a collaboration with Patricia Bouyer and Anirban Majumdar.

Cite AsGet BibTex

Nathalie Bertrand. Concurrent Games with Arbitrarily Many Players (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.1

Abstract

Traditional concurrent games on graphs involve a fixed number of players, who take decisions simultaneously, determining the next state of the game. With Anirban Majumdar and Patricia Bouyer, we introduced a parameterized variant of concurrent games on graphs, where the parameter is precisely the number of players. Parameterized concurrent games are described by finite graphs, in which the transitions bear finite-word languages to describe the possible move combinations that lead from one vertex to another. We report on results on two problems for such concurrent games with arbitrary many players. To start with, we studied the problem of determining whether the first player, say Eve, has a strategy to ensure a reachability objective against any strategy profile of her opponents as a coalition. In particular Eve’s strategy should be independent of the number of opponents she actually has. We establish the precise complexities of the problem for reachability objectives. Second, we considered a synthesis problem, where one aims at designing a strategy for each of the (arbitrarily many) players so as to achieve a common objective. For safety objectives, we show that this kind of distributed synthesis problem is decidable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Verification by model checking
Keywords
  • concurrent games
  • parameterized verification

Metrics

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

References

  1. Luca de Alfaro, Thomas A. Henzinger, and Orna Kupferman. Concurrent reachability games. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS'98), pages 564-575. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/SFCS.1998.743507.
  2. Rajeev Alur, Thomas A. Henzinger, and Orna Kupferman. Alternating-time temporal logic. Journal of the ACM, 49:672-713, 2002. URL: https://doi.org/10.1145/585265.585270.
  3. Nathalie Bertrand, Patricia Bouyer, and Anirban Majumdar. Concurrent parameterized games. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'19), volume 150 of LIPIcs, pages 31:1-31:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.31.
  4. Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Pure Nash equilibria in concurrent games. Logical Methods in Computer Science, 11(2:9), 2015. URL: https://doi.org/10.2168/LMCS-11(2:9)2015.
  5. Thomas Brihaye, Véronique Bruyère, Julie De Pril, and Hugo Gimbert. On subgame perfection in quantitative reachability games. Logical Methods Computer Science, 9(1), 2012. URL: https://doi.org/10.2168/LMCS-9(1:7)2013.
  6. Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdzinski. Games with secure equilibria. Theoretical Computer Science, 365(1-2):67-82, 2006. URL: https://doi.org/10.1016/j.tcs.2006.07.032.
  7. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500 of Lecture Notes in Computer Science. Springer, 2002. URL: https://doi.org/10.1007/3-540-36387-4.
  8. Erich Grädel and Michael Ummels. Solution concepts and algorithms for infinite multiplayer games. In New perspectives on Games and Interaction, volume 4 of Texts in Logic and Games. Amsterdam University Press, 2008. Google Scholar
  9. Rohit Parikh. On context-free languages. Journal of the ACM, 13(4):570-581, 1966. URL: https://doi.org/10.1145/321356.321364.
  10. Reinhard Selten. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit. Zeitschrift für die gesamte Staatswissenschaft, 121:301–324 and 667–689, 1965. Google Scholar
  11. Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC'73), pages 1-9. ACM, 1973. URL: https://doi.org/10.1145/800125.804029.
  12. Michael Ummels and Dominik Wojtczak. The complexity of Nash equilibria in limit-average games. In Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR'11), volume 6901 of Lecture Notes in Computer Science, pages 482-496. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23217-6_32.
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