Complexity of Pure Equilibria in Bayesian Games

Gottlob, Georg; Greco, Gianluigi; Mancini, Toni

Complexity of Pure Equilibria in Bayesian Games

Georg Gottlob, Gianluigi Greco, Toni Mancini

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1294-1298.

Abstract

In this paper we make a comprehensive study of the complexity of the problem of deciding the existence of equilibria in strategic games with incomplete information, in case of pure strategies. In particular, we show that this is NP-complete in general Bayesian Games in Standard Normal Form, and that it becomes PP-hard (and, in fixed-precision scenarios, PP-complete), when the game is represented succinctly in General Normal Form. Suitable restrictions in case of graphical games that make the problem tractable are also discussed.

Georg Gottlob, Gianluigi Greco, and Toni Mancini. 2007. Complexity of Pure Equilibria in Bayesian Games. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 1294–1298. https://ijcai.org/proceedings/2007/209

@inproceedings{ijcai2007p209,
  title     = {Complexity of Pure Equilibria in Bayesian Games},
  author    = {Gottlob, Georg and Greco, Gianluigi and Mancini, Toni},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {1294--1298},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/209},
}

TY  - CPAPER
TI  - Complexity of Pure Equilibria in Bayesian Games
AU  - Gottlob, Georg
AU  - Greco, Gianluigi
AU  - Mancini, Toni
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 1294
EP  - 1298
UR  - https://ijcai.org/proceedings/2007/209
ER  -