Nash Equilibria in Symmetric Games with Partial Observation

Patricia Bouyer
(LSV – CNRS & ENS Cachan)
Nicolas Markey
(LSV – CNRS & ENS Cachan)
Steen Vester
(DTU, Kgs. Lyngby)

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.

In Fabio Mogavero, Aniello Murano and Moshe Y. Vardi: Proceedings 2nd International Workshop on Strategic Reasoning (SR 2014), Grenoble, France, April 5-6, 2014, Electronic Proceedings in Theoretical Computer Science 146, pp. 49–55.
Published: 1st April 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.146.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org