Research map / Learning theory and algorithms / Submodular and game algorithms

Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games

NeurIPS 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Correlated equilibria in sequential games · 1 citations (OpenAlex)

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.

Generalizes the Ellipsoid Against Hope to bilinear zero-sum games with a good-enough-response oracle, and uses it to compute exact linear-deviation correlated equilibria (LCE) in extensive-form games in polynomial time.

Problem

Computing exact Phi-equilibria (in particular exact linear-deviation correlated equilibria) in polyhedral games such as extensive-form games, where the Ellipsoid Against Hope does not directly apply because the polynomial-type property fails and best-response oracles may be NP-hard.

Approach

Replaces the best-response oracle with a weaker good-enough-response (GER) oracle that returns a strategy with nonnegative payoff against a given y; for linear Phi, GER is built from fixed points of linear deviations, yielding product distributions that are purified via Caratheodory into pure profiles, and the ellipsoid method on the dual with GER separation gives an exact sparse solution.

Key results

• Gives the first polynomial-time algorithm for computing exact linear-deviation correlated equilibria (LCE) in extensive-form games, running in poly(N, log u) time.
• Shows that computing a best-response oracle for the Correlator in the Correlator-Deviator game for CCE in extensive-form games is NP-hard, motivating the GER oracle.
• The framework recovers exact CE in normal-form games under polynomial type and expectation properties and yields EFCE as a special case.

Surprising findings

• Constructing a best-response oracle for the Correlator is NP-hard even though a good-enough-response oracle is efficient.

Limitations

• Ellipsoid-based framework has a polynomial of large degree and is likely impractical.
• Results restricted to polytopes; extension to general convex strategy sets is open.
• Only linear transformations are handled; non-linear Phi is left open.

Experimental setup

Metrics: polynomial running time

Baselines: Ellipsoid Against Hope (Papadimitriou and Roughgarden 2008) Farina and Gatti 2017 EFCE exact computation

Builds on: Ellipsoid Against Hope Phi-regret minimization framework linear-deviation correlated equilibrium Papadimitriou-Roughgarden Ellipsoid Against Hope

Closest papers by meaning

• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond (NeurIPS 2020 · similarity 0.92)
• On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria (AAAI 2024 · similarity 0.90)
• The Complexity of Correlated Equilibria in Generalized Games (NeurIPS 2025 · similarity 0.88)
• Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games (NeurIPS 2025 · similarity 0.88)
• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.87)
• Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games (NeurIPS 2025 · similarity 0.87)