Document Open Access Logo

Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism

Authors Patricia Bouyer , Nathan Thomasset

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.9.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Patricia Bouyer
  • LSV, CNRS, ENS Paris-Saclay, Université Paris-Saclay, France
Nathan Thomasset
  • LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, France

Funding

This work has been partly supported by ERC project EQualIS (FP7-308087).

Cite AsGet BibTex

Patricia Bouyer and Nathan Thomasset. Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.9

Abstract

We study pure Nash equilibria in infinite-duration games on graphs, with partial visibility of actions but communication (based on a graph) among the players. We show that a simple communication mechanism consisting in reporting the deviator when seeing it and propagating this information is sufficient for characterizing Nash equilibria. We propose an epistemic game construction, which conveniently records important information about the knowledge of the players. With this abstraction, we are able to characterize Nash equilibria which follow the simple communication pattern via winning strategies. We finally discuss the size of the construction, which would allow efficient algorithmic solutions to compute Nash equilibria in the original game.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Solution concepts in game theory
  • Theory of computation → Verification by model checking
Keywords
  • Multiplayer games
  • Nash equilibria
  • partial information

Metrics

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

Related Versions

References

  1. 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.
  2. Patricia Bouyer. Games on graphs with a public signal monitoring. Research report, arXiv, 2017. URL: http://arxiv.org/abs/1710.07163.
  3. Patricia Bouyer. Games on graphs with a public signal monitoring. In Proc. 21st International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'18), volume 10803 of Lecture Notes in Computer Science, pages 530-547. Springer, 2018. Google Scholar
  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. Google Scholar
  5. Patricia Bouyer, Nicolas Markey, and Daniel Stan. Mixed Nash Equilibria in Concurrent Games. In Proc. 33rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14), volume 29 of LIPIcs, pages 351-363. Leibniz-Zentrum für Informatik, 2014. Google Scholar
  6. Patricia Bouyer and Nathan Thomasset. Nash equilibria in games over graphs equipped with a communication mechanism. Research report, arXiv, 2019. URL: http://arxiv.org/abs/1906.07753.
  7. Romain Brenguier. Robust Equilibria in Mean-Payoff Games. In Proc. 19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'16), volume 9634 of Lecture Notes in Computer Science, pages 217-233. Springer, 2016. Google Scholar
  8. Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdziński. Games with Secure Equilibria. Theoretical Computer Science, 365(1-2):67-82, 2006. Google Scholar
  9. Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdziński. On Nash Equilibria in Stochastic Games. In Proc. 18th International Workshop on Computer Science Logic (CSL'04), volume 3210 of Lecture Notes in Computer Science, pages 26-40. Springer, 2004. Google Scholar
  10. Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin. The Complexity of Rational Synthesis. In Proc. 43rd International Colloquium on Automata, Languages and Programming (ICALP'16), volume 55 of LIPIcs, pages 121:1-121:15. Leibniz-Zentrum für Informatik, 2016. Google Scholar
  11. Rodica Condurache, Youssouf Oualhadj, and Nicolas Troquard. The Complexity of Rational Synthesis for Concurrent Games. In Proc. 29th International Conference on Concurrency Theory (CONCUR'18), volume 118 of LIPIcs, pages 38:1-38:15. Leibniz-Zentrum für Informatik, 2018. Google Scholar
  12. Thomas A. Henzinger. Games in system design and verification. In Proc. 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK'05), pages 1-4, 2005. Google Scholar
  13. John F. Nash. Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48-49, 1950. Google Scholar
  14. Jérôme Renault and Tristant Tomala. Repeated Proximity Games. International Journal of Game Theory, 27(4):539-559, 1998. Google Scholar
  15. Wolfgang Thomas. Infinite Games and Verification. In Proc. 14th International Conference on Computer Aided Verification (CAV'02), volume 2404 of Lecture Notes in Computer Science, pages 58-64. Springer, 2002. Invited Tutorial. Google Scholar
  16. Michael Ummels. Rational Behaviour and Strategy Construction in Infinite Multiplayer Games. In Proc. 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'06), volume 4337 of Lecture Notes in Computer Science, pages 212-223. Springer, 2006. Google Scholar
  17. Michael Ummels. The Complexity of Nash Equilibria in Infinite Multiplayer Games. In Proc. 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'08), volume 4962 of Lecture Notes in Computer Science, pages 20-34. Springer, 2008. Google Scholar
  18. Michael Ummels and Dominik Wojtczak. The Complexity of Nash Equilibria in Limit-Average Games. In Proc. 22nd International Conference on Concurrency Theory (CONCUR'11), volume 6901 of Lecture Notes in Computer Science, pages 482-496. Springer, 2011. Google Scholar
  19. Michael Ummels and Dominik Wojtczak. The Complexity of Nash Equilibria in Stochastic Multiplayer Games. Logical Methods in Computer Science, 7(3), 2011. 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 Imprint Privacy Contact