Research map / Learning theory and algorithms / Submodular and game algorithms
The Complexity of Correlated Equilibria in Generalized Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that computing an approximate (coarse) correlated equilibrium in generalized games with coupled linear constraints is PPAD-complete, via a reduction from two-team polymatrix zero-sum games and a QuasiVI-based membership proof.
Problem
Computing approximate Phi-equilibria (CE/CCE) in generalized games with coupled cost constraints (constrained Phi-equilibrium), where the complexity was open; prior work only showed NP-hardness of social-welfare-maximizing CE.
Approach
Reduce PolyMatrix Nash equilibrium to constrained Phi-equilibrium by creating left and right copies of each player forming a two-team zero-sum game, and use cost constraints that force the left team's marginals to equal the right team's marginals, removing terms linear in the correlated strategy so only Nash-like marginal terms remain.
Key results
- Constrained-Phi-Equilibrium (with CCE deviations) is PPAD-complete, with hardness for inverse-polynomial approximation even with 2 players or constant actions and constraints per player.
- Under the ETH for PPAD, finding a (coarse) correlated equilibrium in generalized games requires quasi-polynomial time, matching the known k^{log k} upper bound for constant players.
- Reduction yields a two-team zero-sum polymatrix game with independent teams, with epsilon' = O(epsilon/n) and nu = O(epsilon/(n k deg(G))).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add coupled constraints to correlated equilibrium computation | Constrained Φ-equilibrium in generalized games · Generalized games | computational complexity | Hurt |
| allow only a constant number of actions and constraints per player | Constrained Φ-equilibrium in generalized games · Generalized games with an arbitrary number of players | computational complexity | Hurt |
| add coupled constraints to no-regret learning | Constrained no-regret learners · Generalized games | convergence guarantee | Hurt |
Surprising findings
- Correlation does not help once coupled linear constraints are added: constrained CCE become as hard as unconstrained Nash equilibria.
- Even the restricted class with two-team zero-sum structure without constraints is polynomially solvable, yet adding cost constraints makes it PPAD-hard.
Limitations
- Hardness is for inverse-polynomial approximation in the instance size; constant-approximation hardness with arbitrary players and constant actions/constraints is left open.
- Membership relies on a safety assumption (non-empty safe deviations for every distribution) and promise problem formulation.
- Results are theoretical with no experiments.
Experimental setup
Builds on: PolyMatrix PPAD-hardness (Rubinstein; Deligkas et al.) QuasiVI PPAD membership CCE/CE no-regret framework
Closest papers by meaning
- Constrained Phi-Equilibria (ICML 2023 · similarity 0.91)
- Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games (NeurIPS 2024 · similarity 0.88)
- Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games (NeurIPS 2025 · similarity 0.87)
- On Tractable $\Phi$-Equilibria in Non-Concave Games (NeurIPS 2024 · similarity 0.87)
- On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria (AAAI 2024 · similarity 0.87)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.