Correlated equilibria in continuous games: Characterization and computation

Noah D. Stein, Pablo A. Parrilo, Asuman E. OzdaglarGames Econ. Behav 2011 · DOI

Abstract

Finding stable outcomes in games with infinite choice sets remains a significant challenge in game theory. This work addresses the computation of Correlated Equilibria (CE) in continuous games, specifically those with polynomial utility functions. The authors introduce tractable characterizations and two primary algorithms—adaptive discretization and moment relaxation—that leverage semidefinite programming (SDP) and Sum of Squares (SOS) techniques. These methods transform complex functional analysis problems into manageable optimization tasks, providing a powerful toolkit for approximating equilibria in non-zero-sum scenarios that were previously computationally out of reach.

Introduction

In game theory, the Nash Equilibrium (NE) is the most famous solution concept but is notoriously difficult to compute. Correlated Equilibrium (CE) offers a more general and computationally "friendly" alternative; in finite games, finding a CE is a matter of solving a Linear Program (LP). However, many real-world problems—such as auctions, resource allocation, or control systems—are continuous games where players choose from a range of moves rather than a fixed list. In these settings, the standard definition of CE involves "departure functions" that are mathematically complex and nearly impossible to solve directly. This paper fills a critical gap by providing a way to describe and compute CE for games with continuous, specifically polynomial, utility functions.

Comparison of equilibrium characterizations across game types. The table highlights the research gap for correlated equilibria in polynomial games that this paper addresses.

Methods

The paper introduces three major contributions to the field of algorithmic game theory:

  1. New Characterizations (Theorem 2.10): The authors prove that instead of checking every possible way a player could deviate (the "departure function"), one only needs to check if the equilibrium holds against a specific class of "test functions," such as continuous functions or squares of polynomials. This turns a functional analysis problem into a manageable optimization task.
  2. Adaptive Discretization: Rather than using a static grid of points, which is often slow and inaccurate, this algorithm starts with a few points and "intelligently" adds new strategies where players are most likely to deviate. This allows the algorithm to home in on the equilibrium much faster than traditional methods.
  3. Moment Relaxation: For games with polynomial utilities, the authors show that the full probability distribution of players' moves is not required—only its moments (e.g., mean and variance). They use Sum of Squares (SOS) techniques to transform equilibrium conditions into a Semidefinite Program (SDP), which can be solved efficiently using standard convex optimization software.

Key Results and Insights

  • Superior Convergence: In experimental tests (e.g., Example 3.1), the adaptive discretization method reached an exact equilibrium in just 3 iterations, whereas standard static grid methods remained far from convergence after 50 iterations.
  • Uniqueness Proofs: Using the moment relaxation method, the authors were able to prove that specific games had a unique correlated equilibrium payoff by showing the relaxation converged to a single point (a "singleton").
  • Convexity is King: Unlike the set of Nash Equilibria, which can be disconnected and non-convex, the set of Correlated Equilibria is always convex. This allows the use of powerful convex optimization tools (like SDP) that guarantee global optima.
  • Theoretical Soundness: The authors provided formal proofs that their approximations (both discretization and moments) are guaranteed to converge to the true set of correlated equilibria as the degree of the approximation increases.

Limitations and Future Work

While the algorithms work well in practice, the authors acknowledge that a theoretical bound on the rate of convergence is not yet established. Additionally, while SDPs are efficient, they still face the "curse of dimensionality" as the number of players or the degree of the polynomials grows very large. Future research aims to find a purely constructive proof of existence for CE that does not rely on Nash's theorem, which could lead to even faster algorithmic implementations.

Summary updated

BibTeX
@article{stein2011correlated,
  author = {Noah D. Stein and Pablo A. Parrilo and Asuman E. Ozdaglar},
  title = {{Correlated equilibria in continuous games: Characterization and computation}},
  journal = {Games Econ. Behav.},
  year = {2011},
  doi = {10.1016/j.geb.2010.04.004},
}
Figure