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

On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria

AAAI 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.

Shows that every extensive-form correlated equilibrium (EFCE) can be converted in polynomial time into an outcome-equivalent behavioral correlated equilibrium (BCE), yielding the first polynomial-time algorithm for computing a BCE.

Problem

Whether the stronger behavioral correlated equilibrium (BCE) in extensive-form games, which lacks known polynomial-time algorithms (no-regret methods are exponential in depth/branching), can be reached from the polynomially computable EFCE.

Approach

Replace recommendations at off-path infosets with counterfactual best-response recommendations (conditioned on the player's deviation point) so that deviators receive no useful information; this preserves outcome distributions while making the EFCE a BCE, and the transformation runs in polynomial time on mixtures of small-support products.

Key results

• Proves every eps-EFCE is outcome-equivalent to an eps-BCE (main theorem).
• Gives a poly(|H|, T, K)-time algorithm converting an EFCE in mixture-of-small-support-products form into a BCE, yielding the first polynomial-time exact BCE computation.
• Shows the EFCE-to-BCE map cannot be surjective and fails under counterfactual outcome-equivalence.

Surprising findings

• BCE is outcome-equivalent to EFCE even though BCE appears strictly stronger, but the conversion may require non-behavioral strategies.
• The conversion does not yield uncoupled learning dynamics converging to BCE in poly(|H|, 1/eps) rounds, since it depends on future opponent strategies.

Limitations

• Outcome equivalence only on the equilibrium path; stronger counterfactual equivalence fails.
• Map from EFCE to BCE is not surjective, and converted BCE may not be a behavioral strategy.
• No polynomial-time uncoupled learning dynamics for BCE follow from the result.

Experimental setup

Baselines: EFCE polynomial-time algorithm (Huang and von Stengel) no-regret BCE algorithms (Morrill et al., Farina et al.) K-EFCE

Builds on: extensive-form correlated equilibrium behavioral correlated equilibrium counterfactual regret minimization Phi-regret

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.93)
• Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks (NeurIPS 2019 · similarity 0.92)
• Coarse Correlation in Extensive-Form Games (AAAI 2020 · similarity 0.92)
• Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games (NeurIPS 2024 · similarity 0.90)
• The Complexity of Correlated Equilibria in Generalized Games (NeurIPS 2025 · similarity 0.87)
• Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.86)