Document Open Access Logo

On the Computation of Nash Equilibria in Games on Graphs (Invited Talk)

Author Patricia Bouyer

PDF
Thumbnail PDF

File

LIPIcs.TIME.2019.3.pdf
  • Filesize: 362 kB
  • 3 pages

Document Identifiers

Author Details

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

Funding

Work supported by ERC project EQualIS between 2013 and 2019.

Acknowledgements

I would like to thank all my co-authors since I started working on multiplayer games played on graphs, that is, Nicolas Markey, Romain Brenguier [Romain Brenguier, 2012], Daniel Stan [Stan, 2017], Michael Ummels and Nathan Thomasset.

Cite As Get BibTex

Patricia Bouyer. On the Computation of Nash Equilibria in Games on Graphs (Invited Talk). In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.TIME.2019.3

Abstract

In this talk, I will show how one can characterize and compute Nash equilibria in multiplayer games played on graphs. I will present in particular a construction, called the suspect game construction, which allows to reduce the computation of Nash equilibria to the computation of winning strategies in a two-player zero-sum 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

Metrics

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

References

  1. Patricia Bouyer. A Note on Game Theory and Verification. In Proc. 17th International Symposium on Automated Technology for Verification and Analysis (ATVA'19), Lecture Notes in Computer Science. Springer, 2019. To appear. Google Scholar
  2. 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
  3. Romain Brenguier. Nash Equilibria in Concurrent Games - Application to Timed Games. PhD thesis, ENS Cachan, France, 2012. Google Scholar
  4. Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdziński. Games with Secure Equilibria. Theoretical Computer Science, 365(1-2):67-82, 2006. Google Scholar
  5. 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
  6. 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, pages 151-178. Amsterdam University Press, 2008. Google Scholar
  7. 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
  8. 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
  9. Daniel Stan. Randomized Strategies in Concurrent Games. PhD thesis, Université Paris-Saclay, France, 2017. Google Scholar
  10. 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
  11. 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
  12. 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
  13. Michael Ummels. Stochastic Multiplayer Games - Theory and Algorithms. PhD thesis, RWTH Aachen, Germany, 2010. 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 About DROPS Imprint Privacy Contact