Nash Equilibria in Symmetric Graph Games with Partial Observation

Patricia Bouyer, Nicolas Markey, Steen Vester

Research output: Contribution to journalJournal articleResearchpeer-review

147 Downloads (Pure)

Abstract

We investigate a model for representing large multiplayer games, which satisfy strong symmetry properties. This model is made of multiple copies of an arena; each player plays in his own arena, and can partially observe what the other players do. Therefore, this game has partial information and symmetry constraints, which make the computation of Nash equilibria difficult. We show several undecidability results, and for bounded-memory strategies, we precisely characterize the complexity of computing pure Nash equilibria for qualitative objectives in this game model.
Original languageEnglish
JournalInformation and Computation
Volume254
Issue number2
Pages (from-to)238–258
ISSN0890-5401
DOIs
Publication statusPublished - 2017

Keywords

  • Games on graphs
  • Network of systems
  • Symmetry
  • Nash equilibrium

Fingerprint Dive into the research topics of 'Nash Equilibria in Symmetric Graph Games with Partial Observation'. Together they form a unique fingerprint.

Cite this