PaperlayerView exact revision on arXiv

Source-linked AI summary

Normal-Form Correlation in Markov Games

Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang

arXiv:2610.03621v1cs.GTcs.CCcs.DScs.LG

TL;DR

Existing algorithmic results for correlated equilibria in Markov games focus on relaxations weaker than NFCEs, despite the challenge of complete policy recommendations. The paper combines constant-expectation correlated equilibria with independent state sampling to make backward induction sound, establishing an efficient fixed-player algorithm alongside PPAD-hardness regimes.

  • Problem

    Existing algorithmic results for fully observable Markov games focus on relaxations weaker than NFCEs, which allow deviations conditioned on complete policy recommendations.

    Source: §1 · p. 2

  • Method

    The approach runs backward induction using constant-expectation correlated equilibria at each stage and samples recommendations independently across states.

    Source: §1.2 · p. 4

  • Results

    The paper gives an efficient fixed-player NFCE algorithm and proves constant-expectation CE computation PPAD-hard for binary-action n-player polymatrix games at constant precision.

    Source: §1.2 · p. 4, §7 · p. 13

  • Takeaways & Limitations

    Constant-expectation CEs and independent state sampling make backward induction sound even when players observe their full recommended policies.

    Source: §7 · p. 13

    The positive algorithm scales poorly with the number of players.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $\epsilon$-NFCE in time $S(AH/\epsilon)^{O(n)}$. This is the first algorithm polynomial in $1/\epsilon$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.

1 Introduction

Existing algorithms for correlated equilibria in Markov games target weaker concepts than NFCEs, although complete policy recommendations matter when players may condition deviations on unreached states. The paper gives a fixed-player efficient algorithm and shows that backward induction can be made sound using constant-expectation correlated equilibria and independent state sampling.

1 Introduction

  • NFCE computation remains open for games with exponentially many pure strategies, and it matters when players receive complete policy recommendations and may deviate based on unreached states.Such recommendations can support systems where a mediator specifies policies before deployment, without remaining involved during execution.Source: §1 · p. 2

1.1 Our results

  • For fixed n, the algorithm computes an ϵ-NFCE in time S(AH/ϵ)^O(n) poly(L), giving an FPTAS for finite-horizon Markov games.Here L is the bit complexity of the input.Source: §1.1 · p. 2
  • The result is the first FPTAS for NFCEs beyond normal-form games, improving exponentially in 1/ϵ over the cited PTAS results.The cited PTAS results are by Dagan et al. (2024) and Peng and Rubinstein (2024).Source: §1.1 · p. 2
  • The positive algorithm scales poorly with the number of players, and the paper complements it with hardness results under state-independent recommendations.The hardness cases are succinct games with many players at ϵ = Θ(1/n), or three-player games with exponentially small ϵ.Source: §1.1 · pp. 2–3

1.2 Technical overview

  • Ordinary backward induction can fail because observing a full policy lets a player condition an earlier action on continuation recommendations that signal lower payoffs.In the example, Player 1 can stop for 5/4 when recommended S rather than enter based on the continuation CE’s average payoff.Source: §1.2 · p. 3
  • A constant-expectation CE makes obedience payoffs independent of recommendations; for fixed players, it can be approximated by searching candidate payoffs and solving linear feasibility programs.Independent sampling of local recommendations across states then makes backward induction sound after conditioning on a complete recommended policy.Source: §1.2 · p. 4
  • Under independent state recommendations, reductions link constant-expectation CEs and Markov-game NFCEs, while computing those CEs is PPAD-hard in binary-action many-player polymatrix games at constant precision.The paper also establishes hardness for two-player games at exponentially small precision, connecting the problem to rank-2 bimatrix games.Source: §1.2 · p. 4

2 Further related work

Prior Markov-game algorithms address correlated-equilibrium notions weaker than NFCE, while this work’s results cover full-policy recommendations and arbitrary history-dependent deviations. The related work also distinguishes the paper’s finite-horizon, fully observable setting from discounted, partially observable, and extensive-form settings.

Markov games.

  • Existing Markov-game learning results concern weaker equilibrium notions and do not guarantee obedience when players see their full policy recommendations; this work allows history-dependent deviations conditioned on the entire policy.The paper describes its algorithm as centralized and model based, and polynomial only for a fixed number of players.Source: Markov games · p. 5
  • Prior hardness results address discounted-game equilibria or sparse mixtures, whereas this paper leverages finite-horizon backward induction.The cited discounted-game results concern stationary or nonstationary Markov coarse correlated equilibria; sparse-mixture hardness bears on independent no-regret learning.Source: Markov games · p. 5
  • For partially observable games, Liu and Zhang (2026) give quasi-polynomial guarantees under information-sharing and observability assumptions; this approach relies on full observability.The paper says it solves continuation problems separately.Source: Markov games · p. 5
  • NFCE complexity remains open in extensive-form games, where continuation problems cannot be solved independently and this paper’s approach does not directly extend.The passage specifically notes that an FPTAS remains open even for two-player imperfect-information extensive-form games.Source: Markov games · p. 5
  • The paper connects constant-expectation CEs to Nash equilibria in constant-rank bimatrix games, alongside prior exponentially-small-precision hardness for rank-3 games (Mehta, 2014).Kannan and Theobald (2010) introduced constant-rank bimatrix games; their work gives an FPTAS, while rank-1 games have a polynomial-time algorithm.Source: Markov games · pp. 5–6
  • Constant-expectation CE and IVFCE are distinct refinements: neither implies the other, though both hold at Nash equilibrium; the former is PPAD-hard at exponentially small precision even in two-player explicit games.In succinct many-player games, both are PPAD-hard at constant precision (Anagnostides and Zheng, 2026); exact IVFCE is polynomial-time computable in explicit normal-form games (Hartline et al., 2026).Source: Markov games · p. 6

3 Preliminaries

The preliminaries define correlated equilibrium and its conditional approximation, then set up finite-horizon Markov games and NFCE as correlation over policies in the induced normal-form game. NFCE requires obedience to complete policy recommendations, a stronger condition than the cited relaxations.

3.1 Normal-form games

  • A δ-correlated equilibrium constrains gains from deviation functions, while a δ-conditional CE imposes a stronger condition; every δ-conditional CE is a δ-CE, but not conversely.The paper uses conditional CE for upper bounds and CE for lower bounds.Source: §3.1 · p. 6

3.2 Markov games

  • A Markov game has finite stages, state-dependent action sets, rewards, and transitions, with policies mapping histories to actions and Markov policies depending only on stage and state.Rewards are normalized to [0,1/H], making cumulative payoffs lie in [0,1].Source: §3.2 · pp. 6–7
  • NFCE applies normal-form correlated equilibrium to the game whose actions are complete policies, requiring obedience even when recommendations are revealed before play.This is stronger than notions akin to extensive-form correlated equilibrium, where recommendations are revealed only when their information sets are reached.Source: §3.2 · p. 7

4 Computing constant-expectation correlated equilibrium

Constant-expectation CE refines correlated equilibrium by requiring conditional expected obedience payoffs to be nearly independent of recommendations. The paper approximates this condition through discretized payoff targets and linear feasibility programs.

4 Computing constant-expectation correlated equilibrium

  • Constant-expectation CE requires each player’s conditional expected payoff from obedience to be close to a player-specific value across recommended actions.The paper’s algorithm satisfies exact obedience and a stronger supported-action payoff bound, while its hardness results use the more permissive averaged condition.Source: §4 · p. 7
  • A correlated equilibrium need not be constant-expectation: the same uniform distribution over two action profiles is constant-expectation in one example game but not another, despite being a CE in both.The example contrasts the refinement with Nash equilibrium, which satisfies the constant-expectation requirement.Source: §4 · pp. 7–8
  • The algorithm discretizes payoff targets over [0,1] and tests each target tuple with a linear feasibility program over correlated equilibria.Each feasible solution is an (ϵ/2,0)-constant-expectation CE, with conditional obedience payoffs between ℓ_i and ℓ_i + ϵ for supported actions.Source: §4 · p. 8
  • The running time is (A/ϵ)^O(n) poly(L), so this procedure scales exponentially with the number of players.Here A is the maximum action count per player and L bounds payoff-tensor bit complexity.Source: §4 · p. 8

5 Efficient backward induction for NFCE in Markov games

The algorithm works backward over auxiliary stage games, constructing independently sampled policy recommendations from local correlated equilibria. Conditioning on a player’s complete policy turns its deviation problem into an MDP, yielding an ϵ-conditional NFCE guarantee.

5 Efficient backward induction for NFCE in Markov games

  • Backward induction computes a correlated equilibrium at each state and stage, then independently samples local recommendations to form a distribution over pure Markov policy profiles.The auxiliary payoffs are bounded in [0,1], and the construction uses independence of recommendations across states.Source: §5 · pp. 8–9
  • Given the player’s policy, opponents’ prescribed actions are conditionally independent across states, and their law at the current state is preserved at histories reached by deviations.This property supports the reduction from history-dependent deviations to the conditional MDP.Source: §5 · p. 9

5.1 The induced Markov decision process

  • Conditional on a player’s recommended policy, every history-dependent deviation has the same expected payoff in a conditional MDP as in the Markov game.Consequently, an optimal deviation can be chosen deterministic and Markovian.Source: §5.1 · p. 9

5.2 Main result

  • Algorithm 1 produces an ϵ-conditional NFCE represented by independently sampled state distributions, with its runtime covered by the theorem’s stated input assumptions.The supplied theorem passage specifies explicit stage games and transitions with bit complexity at most L, but does not include the complete runtime expression.Source: §5.1 · p. 10, §5.2 · p. 10

6 Hardness results

The section proves PPAD-hardness for constant-expectation correlated equilibria in many-player and two-player games, then transfers this hardness to NFCEs in Markov games. The Markov-game result assumes independent state recommendations and holds at horizon two in the stated regimes.

6.1 Succinct multi-player games

  • The reduction uses equilibrium collapse: marginals of an (ε,δ)-constant-expectation CE yield an η-Nash equilibrium, where η = ε/α + δ/(α(1 − 2α)).The argument combines this implication with a PPAD-hardness result for polymatrix Nash equilibrium.Source: §6.1 · p. 12
  • For every 0 < ε < 1/24 and 0 ≤ δ < (1 − 24ε)^2/96, computing an (ε,δ)-constant-expectation CE in degree-three normalized polymatrix games with two actions per player is PPAD-hard.The many-player construction requires an output representation whose marginal probabilities are computable in polynomial time.Source: §6.1 · pp. 11–12

6.2 Two-player games

  • Computing an (ε,δ)-constant-expectation CE in bimatrix games is PPAD-hard when ε and δ are exponentially small, via a reduction from exact Nash equilibrium in rank-2 games.The transformed game has the same set of correlated equilibria as the source game.Source: §6.2 · p. 12

6.3 Hardness for NFCE in Markov games

  • Every ε-NFCE in the constructed horizon-two Markov game yields a (16nε,16ε)-constant-expectation CE of the original n-player game.The construction uses n + 1 players and n + 1 states.Source: §6.3 · p. 13
  • With independent state recommendations, NFCE computation is PPAD-hard at horizon two for succinct many-player games at ε = 1/(3072n), and for three-player games at exponentially small ε.The many-player case has two actions per player at each state; the small-precision case uses a constant number of states.Source: §6.3 · p. 13

7 Conclusion

The paper establishes an efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players. Its approach uses constant-expectation correlated equilibria and independent sampling across states to make backward induction sound despite players observing their full recommended policies.

7 Conclusion

  • The conclusion identifies an efficient NFCE algorithm for finite-horizon Markov games with a fixed number of players.Its key idea combines constant-expectation correlated equilibria with independent sampling across states so backward induction remains sound when players observe full policies.Source: §7 · p. 13
  • The algorithm is neither decentralized nor model free, and the authors identify both as important directions for future work.The conclusion also leaves open whether correlations between states could avoid the many-player hardness result and whether NFCEs are tractable in other representations such as extensive form.Source: §7 · p. 13

AI Use Statement

The authors report using GPT versions to assist with proofs of some lower bounds, which they checked, understood, and rewrote. The appendix contains omitted proofs.

AI Use Statement

  • Various GPT versions assisted with proofs of some lower bounds; the authors checked, understood, and rewrote all proofs.The authors attribute the paper's initial idea and the main idea for the proof of Main Theorem 1 to themselves.Source: AI Use Statement · p. 13

A Omitted proofs

A.1 Proofs from Section 4

The proof discretizes conditional expected payoffs and solves induced linear programs to construct approximate constant-expectation correlated equilibria. Its running time is polynomial in the payoff description and scales as (A/ε)^O(n).

A.1 Proofs from Section 4

  • The discretization uses (1/ε)^O(n) grid points, and the resulting procedure runs in (A/ε)^O(n) poly(L) time for payoff-tensor bit complexity L.Each induced linear program is solvable in time polynomial in A^n(L + log(1/ε)).Source: §A.1 · p. 17
  • A Nash equilibrium's product distribution is feasible for a linear program induced by rounding each supported action's expected payoff down to the ε-grid.The proof uses that each supported action is a best response and its payoff lies within ε of the rounded value.Source: §A.1 · p. 17
  • Every feasible solution of the induced linear program is a correlated equilibrium whose conditional expected payoff lies within ε of its discretized level, yielding an (ε/2,0)-constant-expectation CE.The proof sets the target value to the discretized level plus ε/2 for each supported recommendation.Source: §A.1 · p. 17

A.2 Proofs from Section 5

The appendix establishes bounds and conditional-independence properties for the auxiliary games, then uses them to relate deviations in the Markov game to an induced MDP.

Lemma A.2

  • For each stage t, the auxiliary payoffs and ℓ_i,t(s) lie in [0,(H −t + 1)/H].The proof proceeds by backward induction under the normalization assumption.Source: §A.2 · p. 17

Lemma A.3

  • Conditioned on a supported pure policy π_i, the other players’ policies are independent across stage-state pairs.Their conditional law at (t,s) is given by the ith marginal of µ_t,s.Source: §A.2 · pp. 17–18

Lemma A.4

  • Conditioned on π_i, every randomized history-dependent deviation has the same expected payoff in the Markov game and the induced MDP M_i(π_i).This reduction uses the conditional transition and reward structure and iterated expectation across stages.Source: §A.2 · p. 18

Lemma A.6

  • The appendix proves by backward induction lower and upper bounds on values for supported policies at every stage and state.The induction starts at H + 1, where continuation values are zero.Source: §A.2 · p. 18

A.3 Proofs for Section 6

The appendix proves the reductions underlying hardness for constant-expectation correlated equilibria, including polymatrix games and exponentially precise two-player games.

Polymatrix reduction

  • An (ϵ,δ)-constant-expectation CE of G′ yields an η-Nash equilibrium of G, with η = ϵ/α + δ/(α(1 −2α)).This marginal-strategy implication is the equilibrium-collapse step used in the hardness reduction.Source: §A.3 · p. 20

Polymatrix hardness

  • For constants 0 < ϵ < 1/24 and 0 ≤ δ < (1 −24ϵ)2/96, computing an (ϵ,δ)-constant-expectation CE in the stated polymatrix games is PPAD-hard.The games are normalized, have maximum degree three, and give each player two actions.Source: §A.3 · pp. 19, 21

Two-player reduction

  • The two-player reduction constructs G′ with rank at most two and preserves the set of correlated equilibria, while scaling CE tolerance by 4K.A δ-CE of G′ is equivalent to a (4Kδ)-CE of G.Source: §A.3 · p. 21

Two-player hardness

  • Computing an (ϵ,δ)-constant-expectation CE is PPAD-hard in bimatrix games when ϵ and δ are exponentially small.The reduction converts the resulting marginal η-Nash equilibrium into an exact Nash equilibrium of the source game.Source: §A.3 · p. 22

B Hardness for independent state recommendations

A reduction shows that NFCEs with independent state recommendations imply approximate constant-expectation CEs in normal-form games. The construction uses a two-stage Markov game with an added tester player.

Theorem 6.11

  • Every ϵ-NFCE with independent state recommendations in the constructed game yields a (16nϵ,16ϵ)-constant-expectation CE of the original game.The original game has n players, and the constructed game has n + 1 players, horizon 2, and n + 1 states.Source: B Hardness for independent state… · p. 22

Construction

  • At stage 1, a uniformly selected player plays matching pennies against the tester; heads leads to the original game at stage 2, while tails ends play.The constructed game has n stage-1 states and one stage-2 state.Source: B Hardness for independent state… · p. 23

Reduction argument

  • The proof uses independence across states so first-stage deviations that ignore the second-stage recommendation have continuation value equal to the original game’s expected payoff.The proof states that the induced recommendation profile is a (4nϵ,4ϵ)-constant-expectation CE.Source: B Hardness for independent state… · p. 23
  • The proof bounds the probability of reaching the original game below by 1/4, yielding a 4ϵ-CE obedience bound there.The stage is selected with probability 1/n, so its conditional deviation gain is bounded by nϵ.Source: B Hardness for independent state… · p. 23
Loading 2610.03621v1…