Correlated Equilibria in Continuous Games: Characterization and Computation

We present several new characterizations of correlated equilibria in games with continuous utility functions. These have the advantage of being more computationally and analytically tractable than the standard definition in terms of departure functions. We use these characterizations to construct effective algorithms for approximating a single correlated equilibrium or the entire set of correlated equilibria of a game with polynomial utility functions. We then exhibit the rich structure of the set of corre- lated equilibria by analyzing the simplest of polynomial games, the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex, the structure of its extreme points can be quite complicated. In finite games there can be a superexponential separation between the number of extreme Nash and extreme correlated equilibria. In polynomial games there can exist extreme correlated equilibria which are not finitely supported we construct a large family of examples using tech- niques from ergodic theory. These examples show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many joint moments, in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments.