Document Open Access Logo

Nash Equilibria in Concurrent Games with Büchi Objectives

Authors Patricia Bouyer, Romain Brenguier, Nicolas Markey, Michael Ummels



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2011.375.pdf
  • Filesize: 458 kB
  • 12 pages

Document Identifiers

Author Details

Patricia Bouyer
Romain Brenguier
Nicolas Markey
Michael Ummels

Cite AsGet BibTex

Patricia Bouyer, Romain Brenguier, Nicolas Markey, and Michael Ummels. Nash Equilibria in Concurrent Games with Büchi Objectives. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 375-386, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.FSTTCS.2011.375

Abstract

We study the problem of computing pure-strategy Nash equilibria in multiplayer concurrent games with Büchi-definable objectives. First, when the objectives are Büchi conditions on the game, we prove that the existence problem can be solved in polynomial time. In a second part, we extend our technique to objectives defined by deterministic Büchi automata, and prove that the problem then becomes EXPTIME-complete. We prove PSPACE-completeness for the case where the Büchi automata are 1-weak.
Keywords
  • Concurrent games
  • Nash equilibria
  • Büchi Objectives

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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