Complexity of Pure Equilibria in Bayesian Games

Georg Gottlob, Gianluigi Greco, Toni Mancini

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.

Subjects: 7. Distributed AI; 9.2 Computational Complexity

Submitted: Oct 12, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.