Complexity of pure equilibria in Bayesian games

In this paper we make a comprehensive study of the complexity of the problem of deciding the ex-istence of equilibria in strategic games with incom-plete information, in case of pure strategies. In par-ticular, we show that this is NP-complete in gen-eral Bayesian Games in Standard Normal Form, and that it becomes PP-hard (and, in fixed-precision scenarios, PP-complete), when the game is repre-sented succinctly in General Normal Form. Suit-able restrictions in case of graphical games that make the problem tractable are also discussed.