On Hypergraphical Bayesian Games

This paper defines the framework of hypergraphical Bayesian games, which allows to concisely specify Bayesian games with local interactions. This framework generalizes both normal-form Bayesian games and hypergraphical games (including polymatrix games). Establishing a generalization of Howson and Rosenthal's Theorem, we show that hypergraphical Bayesian games can be transformed, in polynomial time, into equivalent complete-information hypergraphical games. This result has several consequences. It involves that finding an
$\varepsilon$
-Nash equilibrium in a hypergraphical Bayesian game or an exact mixed Nash equilibrium in a polymatrix Bayesian game is PPAD-complete, while checking the existence of a pure Nash equilibrium defines a NP-complete problem. It also allows to make use of existing solution algorithms for hypergraphical games to solve hypergraphical and standard normal form Bayesian games.