---
title: "Complexity of Pure Equilibria in Bayesian Games"
authors:
  - "Georg Gottlob"
  - "Gianluigi Greco"
  - "Toni Mancini"
doi: ""
url: "https://ijcai.org/proceedings/2007/209"
pdf: "https://ijcai.org/proceedings/2007/0209.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "1294-1298"
track: ""
keywords:
---

# Complexity of Pure Equilibria in Bayesian Games

Georg Gottlob, Gianluigi Greco, Toni Mancini

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