Complexity of Pure Equilibria in Bayesian Games
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.
Cite
Text
Gottlob et al. "Complexity of Pure Equilibria in Bayesian Games." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Gottlob et al. "Complexity of Pure Equilibria in Bayesian Games." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/gottlob2007ijcai-complexity/)BibTeX
@inproceedings{gottlob2007ijcai-complexity,
title = {{Complexity of Pure Equilibria in Bayesian Games}},
author = {Gottlob, Georg and Greco, Gianluigi and Mancini, Toni},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {1294-1299},
url = {https://mlanthology.org/ijcai/2007/gottlob2007ijcai-complexity/}
}