Characterization and computation of correlated equilibria in infinite games

Abstract—Motivated by recent work on computing Nash equilibria in two-player zero-sum games with polynomial pay-offs by semidefinite programming and in arbitrary polynomial-like games by discretization techniques, we consider the prob-lems of characterizing and computing correlated equilibria in games with infinite strategy sets. We prove several character-izations of correlated equilibria in continuous games which are more analytically tractable than the standard definition and may be of independent interest. Then we use these to construct algorithms for approximating correlated equilibria of polynomial games with arbitrary accuracy, including a sequence of semidefinite programming relaxation algorithms and discretization algorithms. I