Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games

1 Introduction

• The CE feasibility program can be exponential in the size of a compact game representation, and a CE may itself require exponential space to specify.Source: §1 · p. 2

1.1 Recent uncertainty about the complexity of exact CE

• Stein, Parrilo and Ozdaglar showed that the original algorithm can fail to find an exact CE, while a modified version computes approximate CEs in polynomial time.Their example implies exact rational CE algorithms must violate either the rational convex-combination-of-product-distributions condition or its symmetric-game counterpart.Source: §1.1 · pp. 2–3
• Whether Ellipsoid Against Hope could be modified to compute an exact rational CE remained unresolved.The original analysis also mishandled numerical precision: oracle cuts can require more bits than constraints in the original dual LP, so infeasibility of the cut LP is not guaranteed.Source: §1.1 · pp. 2–3

1.2 Our results

• The proposed variant computes an exact rational CE in polynomial time by using pure-strategy-profile cuts, which are actual dual constraints rather than convex combinations of constraints.The algorithm and its analysis are simpler, and standard ellipsoid techniques establish correctness with polynomially many oracle queries.Source: §1.2 · p. 3
• The oracle derandomizes the original approach with conditional probabilities, fixing players’ strategies sequentially while maintaining a nonnegative conditional expectation.The resulting equilibria have polynomial-sized supports; unlike the existence result, no tractable algorithm for identifying such equilibria had previously been proposed.Source: §1.2 · p. 4

2 Preliminaries

• A game has n players, each with a pure-strategy set S_p; a pure-strategy profile selects one strategy per player, and utilities are assumed to be nonnegative integers.The results can be adapted to rational utilities.Source: §2 · p. 4
• A correlated distribution assigns probabilities to pure-strategy profiles, while a product distribution results when players randomize independently.Source: §2 · pp. 4–5
• The game representation must have polynomial type: the player count and each player’s action count are polynomially bounded in representation size.Source: §2 · p. 5
• The representation must also support polynomial-time computation of each player’s expected utility under any product distribution.Source: §2 · p. 5
• A correlated equilibrium satisfies incentive constraints for every player and pair of that player’s actions; together with probability-distribution constraints, these form a linear feasibility program.The incentive constraints are written as Ux ≥ 0.Source: §2 · p. 5
• Every game has a CE with support size at most 1 + Σ_p |S_p|(|S_p|−1), and rational payoffs yield rational basic feasible solutions.The bound follows from the number of nonredundant incentive constraints.Source: §2 · p. 5

3 The Ellipsoid Against Hope Algorithm

• The approach replaces the CE program’s probability-normalization constraint with an objective; the resulting primal is either zero-optimal or unbounded, and unboundedness implies a CE.The method establishes existence by showing infeasibility of the dual.Source: §3 · p. 6
• For each nonnegative dual vector y, a polynomial-time procedure finds a product distribution x with xU^T y = 0.This product distribution is used as the separation oracle’s response.Source: §3 · p. 6
• The ellipsoid method collects oracle cuts until it declares the dual infeasible; solving the dual of the resulting polynomial-size LP gives a CE as a mixture of the generated product distributions.The mixture can be represented in polynomial space and sampled efficiently.Source: §3 · pp. 6–7
• The oracle’s matrix of expected-utility differences can be computed in polynomial time under the polynomial expectation property.Source: §3 · p. 7

4 Our Algorithm

• Pure-strategy-profile cuts let the modified Ellipsoid Against Hope algorithm compute exact correlated equilibria while avoiding its original numerical-precision mechanism.Each cut is directly a row of the dual constraint matrix.Source: §4 · p. 7

4.1 The Purified Separation Oracle

• A polynomial-time oracle derandomizes the existence of a profile with nonnegative expected value by choosing each player's action while preserving nonnegative conditional expectation.Its conditional expectations are computed using the polynomial-time expected-utility subroutine.Source: §4.1 · pp. 8–9

4.2 The Simplified Ellipsoid Against Hope Algorithm

• Because each generated cut is already a constraint of the original dual, the ellipsoid run avoids the bit-growth precision issue caused by convex-combination cuts.The method uses standard ellipsoid radius and volume bounds, with perturbation to handle a feasible set that is not full dimensional.Source: §4.2 · pp. 10–11
• The algorithm computes an exact rational correlated equilibrium with support at most 1 + Σ_p |S_p|(|S_p| − 1) in polynomial time.A basic feasible solution supplies the support bound and has polynomially representable rational probabilities.Source: §4.2 · pp. 10, 12, 13
• Its guarantee applies to game representations with polynomial type and the polynomial expectation property.The latter provides polynomial-time expected-utility computation needed by the purified oracle.Source: §4.1 · p. 8, §4.2 · p. 10

• The algorithm computes exact correlated equilibria in polynomial time for games with polynomial type and the polynomial expectation property.Source: §5 · p. 13
• Derandomizing the original separation oracle with conditional probabilities yields a polynomial-time oracle whose cuts correspond to pure-strategy profiles.Source: §5 · p. 13
• The returned equilibria have polynomial-sized supports, and the pure-profile cuts avoid the numerical precision issues emphasized by earlier approaches.Source: §5 · p. 13
• Deeper cuts can reduce iterations but require more work per iteration; choosing profiles with good social welfare offers a heuristic, while optimal-welfare CE is generally NP-hard for many representations.Source: §5 · p. 13