Nash Equilibria in Symmetric Games with Partial Observation

Patricia Bouyer; Nicolas Markey; Steen Vester

doi:10.4204/EPTCS.146.7

Nash Equilibria in Symmetric Games with Partial Observation

Patricia Bouyer, Nicolas Markey, Steen Vester

Department of Applied Mathematics and Computer Science

CNRS

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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 language	English
Title of host publication	Proceedings of 2nd International Workshop on Strategic Reasoning
Editors	F. Mogavero, A. Murano, M. Y. Vardi
Publication date	2014
Pages	49-55
DOIs	https://doi.org/10.4204/EPTCS.146.7
Publication status	Published - 2014
Event	2nd International Workshop on Strategic Reasoning - Grenoble, France Duration: 5 Apr 2014 → 6 Apr 2014 Conference number: 2 http://www.strategicreasoning.net/

Conference

Conference	2nd International Workshop on Strategic Reasoning
Number	2
Country/Territory	France
City	Grenoble
Period	05/04/2014 → 06/04/2014
Internet address	http://www.strategicreasoning.net/

Access to Document

10.4204/EPTCS.146.7

OpenUrl availability

Full text

Cite this

@inproceedings{5aee3dc095f74025a00e1120c696ff7c,

title = "Nash Equilibria in Symmetric Games with Partial Observation",

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.",

author = "Patricia Bouyer and Nicolas Markey and Steen Vester",

year = "2014",

doi = "10.4204/EPTCS.146.7",

language = "English",

pages = "49--55",

editor = "Mogavero, \{F. \} and A. Murano and Vardi, \{M. Y.\}",

booktitle = "Proceedings of 2nd International Workshop on Strategic Reasoning",

note = "2nd International Workshop on Strategic Reasoning, SR 14 ; Conference date: 05-04-2014 Through 06-04-2014",

url = "http://www.strategicreasoning.net/",

}

TY - GEN

T1 - Nash Equilibria in Symmetric Games with Partial Observation

AU - Bouyer, Patricia

AU - Markey, Nicolas

AU - Vester, Steen

N1 - Conference code: 2

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.4204/EPTCS.146.7

DO - 10.4204/EPTCS.146.7

M3 - Article in proceedings

SP - 49

EP - 55

BT - Proceedings of 2nd International Workshop on Strategic Reasoning

A2 - Mogavero, F.

A2 - Murano, A.

A2 - Vardi, M. Y.

T2 - 2nd International Workshop on Strategic Reasoning

Y2 - 5 April 2014 through 6 April 2014

ER -

Nash Equilibria in Symmetric Games with Partial Observation

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this