Normal-Form Correlation in Markov Games

Normal-Form Correlation in Markov Games Ioannis Anagnostides1 , Constantinos Daskalakis2 , Gabriele Farina2 Noah Golowich3 , Tuomas Sandholm1∗, and Brian Hu Zhang2 1

arXiv:2610.03621v1 [cs.GT] 2 Oct 2026

2

Carnegie Mellon University Massachusetts Institute of Technology 3 University of Texas at Austin

{ianagnos,sandholm}@cs.cmu.edu {costis,gfarina,zhangbh}@mit.edu, nzg@cs.utexas.edu

Abstract 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 ϵ-NFCE in time S(AH/ϵ)O(n) . This is the first algorithm polynomial in 1/ϵ 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 complement our positive result by showing 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.

∗

Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.

1

Introduction

The correlated equilibrium, introduced by Aumann (1974), is a foundational notion in game theory. Unlike Nash equilibria (Nash, 1951), the standard solution concept in noncooperative games, the set of correlated equilibria is the feasible region of a linear program, thereby enjoying more favorable computational properties. Indeed, a seminal result by Papadimitriou and Roughgarden (2008) shows that a correlated equilibrium can be computed in polynomial time even in certain multi-player games of polynomial type, meaning that the number of pure strategies of each player is polynomial in the description of the input. However, in most realistic settings, the number of pure strategies of each player is exponentially large, since a pure strategy should prescribe how to act across a range of different contingencies. The complexity of correlated equilibria in such settings has been a long-standing open problem, first highlighted by Papadimitriou and Roughgarden (2008). An important class of games with a large number of contingency plans is Markov (aka. stochastic) games. There has been much recent work examining correlated equilibrium concepts in (fully observable) Markov games (discussed further in Section 2). However, existing algorithmic results focus on relaxations of the normal-form correlated equilibrium (NFCE), most notably notions akin to extensive-form correlated equilibrium (von Stengel and Forges, 2008), wherein recommendations are revealed only upon reaching an information set along the realized path. In the stronger normal-form notion, a mediator samples a complete policy profile beforehand and (privately) reveals to each player the entire policy recommendation. This means that a player may condition its deviation on recommendations at states that are never reached. In this paper, we focus on the following question. Are there efficient algorithms for computing normal-form correlated equilibria (NFCEs) in Markov games? NFCE is a suitable solution concept in systems where a mediator—a trusted third party—specifies complete policy prescriptions before deployment, with no need to conceal future recommendations or remain involved throughout execution. For example, a traffic coordinator could recommend complete routing policies to autonomous vehicles before departure, allowing each vehicle to inspect its full policy and decide whether to follow it without requiring further guidance during the trip. Moreover, determining whether efficient algorithms exist for NFCE calls for fundamentally new technical insights, which will deepen our understanding of correlated equilibria in dynamic environments.

1.1

Our results

Our main positive result is an efficient algorithm for this problem in finite-horizon Markov games with a fixed number of players n. Main Theorem 1. Let S be the number of states, H the horizon, and A the maximum number of actions per player. There is an algorithm that computes an ϵ-NFCE whose running time is S(AH/ϵ)O(n) poly(L), where L is the bit complexity of the input. This shows that, for a fixed number of players, there is a fully polynomial-time approximation scheme (FPTAS) for normal-form correlated equilibrium. More broadly, beyond polynomial-type games, the best known result is a PTAS (Dagan et al., 2024; Peng and Rubinstein, 2024). Main Theorem 1 gives an exponential improvement in the dependence on 1/ϵ over those results, and is the first FPTAS for computing NFCE in an interesting class of games beyond the normal-form setting. One limitation of our positive result is that it scales poorly with the number of players; the presence of multiple players is a well-known challenge in multiagent reinforcement learning (e.g. Cui 1

et al., 2023; Wang et al., 2023). We complement Main Theorem 1 by showing that, under state independent recommendations, it cannot be significantly improved. Main Theorem 2. Computing an ϵ-NFCE with independent state recommendations is PPAD-hard even with horizon H = 2, in each of the following cases: (i) (n + 1)-player succinct games, two actions per player at each state, and ϵ = Θ(1/n). (ii) Three-player games, a constant number of states, and exponentially small ϵ. That is, computing such an NFCE is as hard as finding a Nash equilibrium in general-sum games.

1.2

Technical overview

We now highlight the key technical insights of our approach. Failure of backward induction. The most natural approach that comes to mind is backward induction, whereby each continuation state is assigned its expected correlated equilibrium payoff over the local recommendations. However, the crux is that in an NFCE, each player observes its entire recommended policy in advance, so recommendations at future states may reveal conditional continuation payoffs that differ from the average over the local recommendations. This means that a player can profitably deviate by altering an earlier action to avoid a continuation state where its recommendation there signals a lower payoff. More concretely, we consider a two-stage game in which Player 1 initially chooses between a terminal payoff of 5/4 and a continuation state where the players play the game “Bach or Stravinsky,” with payoffs (2, 1) and (1, 2) on the diagonal and (0, 0) otherwise (Figure 1). Mixing equally between the profiles on the diagonal is a CE of the continuation game and gives Player 1 an expected payoff of 3/2. As a result, backward induction based on this CE prescribes entering that state, because 3/2 > 5/4. However, the full policy recommendation reveals which action profile should be played in the “Bach or Stravinsky” game. In particular, when Player 1 is recommended the action yielding payoff 2 (B), following the prescribed policy is optimal. On the other hand, when recommended the action yielding payoff 1 (S), it can instead choose the terminal payoff of 5/4, which is a profitable deviation. So, the correlated distribution resulting from backward induction is not an NFCE. Player 1 Enter

Stop

u1 = 54

B S

B (2, 1) (0, 0)

S (0, 0) (1, 2)

CE: 12 (B, B) + 12 (S, S)

Expected payoff: 23 > 54

Figure 1: Backward induction prescribes Enter using the continuation CE’s average payoff. The CE mixes equally between the two shaded profiles. Observing its full policy lets Player 1 stop whenever S is recommended, so the resulting distribution is not an NFCE.

2

Constant-expectation correlated equilibria. To address this, the key ingredient is a refinement of correlated equilibria in normal-form games, known as constant-expectation correlated equilibrium. To our knowledge, this was first examined by Sorin (1998), and subsequently used by Heller (2012).1 In a one-shot game, a constant-expectation correlated equilibrium is a correlated equilibrium for which the conditional expected payoff from obedience does not depend on the recommended action. Even though this is a natural notion, its complexity has not been examined before. For example, the correlated equilibrium constructed in Figure 1 which breaks backward induction does not satisfy this property: for Player 1, the payoff conditional on observing B is 2, whereas the payoff conditional on observing S is 1. On the other hand, a Nash equilibrium clearly satisfies this requirement. However, unlike Nash equilibria, which are hard to compute (Daskalakis et al., 2009), our key observation is that constant-expectation CEs admit an efficient algorithm (FPTAS) for a fixed number of players: we exhaustively search over each player’s constant obedience payoff and solve a linear feasibility program for each candidate (Proposition 4.3). Rectifying backward induction. We now return to Markov games. The basic idea is to run backward induction by computing in each stage a constant-expectation correlated equilibrium. Then, the final distribution results from sampling the local recommendations independently across the states, which form pure Markovian policy profiles. This independence is crucial for the argument: after conditioning on a player’s entire recommended policy, the other players’ actions remain independent across states, and the environment induced by conditioning is a usual Markov decision process. The crucial role of constant expectation is that it makes conditional obedience payoffs approximately independent of the local recommendation. Together with independent sampling, this provides continuation values that remain valid after conditioning on the entire recommended policy, making backward induction sound (Lemma 5.6). Complexity of constant-expectation CEs and implications for Markov NFCE. We finally circle back to the proof of our main hardness result, Main Theorem 2. The upshot is that, under independent state recommendations, our previous reduction goes both ways: a constant-expectation CE reduces to an NFCE of a suitable Markov game (Theorem 6.11). Moreover, and perhaps surprisingly, we show that computing a constant-expectation CE is PPAD-hard in the following cases. Main Theorem 3. Computing a constant-expectation correlated equilibrium is PPAD-hard in (i) binary-action n-player polymatrix games at constant precision, and (ii) two-player normal-form games at exponentially small precision. Together with our positive result, this fully characterizes the complexity of computing constantexpectation correlated equilibria, which is a natural solution concept in its own right. Main Theorem 3 marks a rare problem that admits an FPTAS and yet is PPAD-hard at exponentially small approximation error. Another notable example is constant-rank bimatrix games (Kannan and Theobald, 2010; Mehta, 2014). Our reduction in fact starts from a rank-2 bimatrix game, establishing an unexpected connection between constant-expectation CEs and constant-rank bimatrix games. We defer the details of our hardness results to Section 6 and additional related work to Section 2. 1

Sorin (1998) used the term “distribution equilibrium,” but we use the more descriptive nomenclature of Heller (2012). Heller (2012) examined existence in the infinite-horizon setting, whereas we focus on computation.

3

2

Further related work

Markov games. There has been much work examining correlated equilibrium concepts in Markov games. Song et al. (2022) and Jin et al. (2024) developed decentralized algorithms for learning (coarse) correlated equilibria with sample complexity that avoids an exponential dependence on the number of players. Wang et al. (2023) and Cui et al. (2023) extended such guarantees to settings with function approximation, while Cai et al. (2024) and Mao et al. (2024) obtained near-optimal convergence rates in the full-feedback setting. These results concern equilibrium notions weaker than NFCE and do not guarantee obedience when each player observes its entire recommended policy before play. Our results allow arbitrary history-dependent deviations conditioned on the entire policy recommendation. On the flip side, our algorithm is centralized and model based, and is polynomial only for a fixed number of players. A complementary line of work has established computational barriers. Daskalakis et al. (2023) showed hardness for stationary Markov coarse correlated equilibria in discounted stochastic games, while also giving efficient algorithms for nonstationary Markov coarse correlated equilibria. Farina et al. (2026) showed that hardness persists even in two-player Markov games with a single controller. These hardness results concern stationary equilibria in the discounted setting, whereas our algorithm leverages the finite horizon through backward induction. Separately, Foster et al. (2023) established hardness for computing coarse correlated equilibria represented as sparse mixtures of product policies, which rules out computationally efficient independent no-regret learning. More recently, Yorulmaz et al. (2026) obtained computational lower bounds for independent learning in discounted games. Beyond fully observable Markov games, Liu and Zhang (2026) examined partially observable games with information sharing, obtaining quasi-polynomial guarantees under suitable informationsharing and observability assumptions. Our approach relies on full observability to solve the continuation problems separately. Beyond Markov games. As discussed earlier, existing algorithmic results focus on relaxations of the normal-form correlated equilibrium. Such relaxations can be understood through the framework of Φ-equilibria (Greenwald and Jafari, 2003; Stoltz and Lugosi, 2007; Gordon et al., 2008), which has engendered much recent work (Morrill et al., 2021a,b; Arunachaleswaran et al., 2025; Daskalakis et al., 2025; Zhang et al., 2025). Anagnostides et al. (2026) showed that computing a normal-form correlated equilibrium in concave (quadratic) games is as hard as finding fixed points of contractions, which is believed to be a hard problem. The complexity, for example, in extensive-form games remains an open question. In particular, it is open whether there is an FPTAS for NFCE even in two-player (imperfect-information) extensive-form games. It is worth noting again that our approach relies crucially on full observability and does not directly extend to extensive-form games. The basic challenge in extensive-form games is that continuation problems cannot be solved independently, so there are additional obstructions in applying backward induction. Constant-rank bimatrix games. An unexpected connection we uncover in our paper is between constant-expectation CEs and Nash equilibria in constant-rank bimatrix games. This class of games was introduced by Kannan and Theobald (2010), motivated by applications in economics. Unlike general bimatrix games, where there is no FPTAS unless P = PPAD (Chen et al., 2009), Kannan and Theobald (2010) showed that constant-rank bimatrix games admit an FPTAS (cf. Alon et al., 2013). Mehta (2014) later established that, even in rank-3 bimatrix games, finding a Nash equilibrium is PPAD-complete when the precision is exponentially small. In contrast, rank-1 games admit a

4

polynomial-time algorithm (Adsul et al., 2011) and are amenable to learning dynamics (Patris and Panageas, 2024). Other refinements of correlated equilibria. A related refinement is information-value-free correlated equilibrium (IVFCE), introduced recently by Hartline et al. (2026), which requires that each player’s (unconditional) expected payoff can be matched by a fixed action chosen without observing the recommendation. In contrast, constant-expectation CE requires each player’s conditional expected payoff from obedience to be independent of its recommendation. Neither property implies the other, although both hold at any Nash equilibrium. The two notions also exhibit similarities in their computational complexity. In succinct many-player games, both are PPAD-hard to compute even at constant precision (Anagnostides and Zheng, 2026). In explicit normal-form games, however, an exact IVFCE can be computed in polynomial time (Hartline et al., 2026), whereas we show that computing a constant-expectation CE is PPAD-hard at exponentially small precision even with two players, despite admitting an FPTAS for a fixed number of players.

3

Preliminaries

We first describe the basic models of normal-form and Markov games.

3.1

Normal-form games

A finite normal-form game is specified by G = ([n], (Ai )ni=1 , (ui )ni=1 ). We make the usual normalization assumption ui ∶ A → [0, 1], where A ∶= ∏i Ai is the joint action space. For a (potentially correlated) distribution µ ∈ ∆(A), we use the shorthand notation pµi (ai ) ∶= ∑ µ(ai , a−i ) and wiµ (ai ) ∶= ∑ µ(ai , a−i )ui (ai , a−i ). a−i

a−i

Our main notion of equilibrium is the correlated equilibrium. We will be interested in two different notions of approximate correlated equilibrium, which we now define. Definition 3.1 (Correlated equilibrium; Aumann, 1974). A distribution µ ∈ ∆(A) is a δ-correlated equilibrium (CE) if, for every player i ∈ [n] and deviation function ϕi ∶ Ai → Ai , E [ui (ϕi (ai ), a−i ) − ui (a)] ≤ δ.

a∼µ

It is a δ-conditional correlated equilibrium if, for every i and every pair ai , a′i ∈ Ai with pµi (ai ) > 0, E [ui (a′i , a−i ) − ui (ai , a−i ) ∣ ai ] ≤ δ.

a∼µ

(1)

The latter notion of approximation is stronger: every δ-conditional CE is also a δ-CE, but not vice-versa. Our upper bounds will use conditional CE, and our lower bounds will use CE.

3.2

Markov games

An n-player Markov game is played over stages t = 1, . . . , H. At stage t, the state belongs to a finite set St . At state s ∈ St , player i has a finite action set Ai,t,s . The joint action set is denoted by At,s ∶= ∏ni=1 Ai,t,s . We will write at ∈ At,st . Player i receives reward ri,t (st , at ), and the next state is drawn from Pt (⋅ ∣ st , at ) ∈ ∆(St+1 ). (This randomization is independent conditioned on the current state and joint action.) The initial state is drawn from a distribution λ ∈ ∆(S1 ). 5

A history before stage t is ht = (s1 , a1 , s2 , a2 , . . . , st−1 , at−1 , st ). A pure (history-dependent) policy of player i maps every feasible history ht to an action in Ai,t,st . We will use Πi to denote the set of pure policies of player i, and Π ∶= ∏ni=1 Πi to denote the set of pure policy profiles. A policy is Markov if it ignores the history before (t, s). In particular, a Markov policy is given by a vector π i = (πi,t (s))t∈[H], s∈S , where πi,t (s) ∈ Ai,t,s . For a joint policy π = (π1 , . . . , πn ), we t

let ui (π) ∶= E[∑H t=1 ri,t (st , at )] be the expected cumulative reward. For convenience, we make the following normalization assumption. Assumption 3.2 (Normalization). For every i, t, s, a, we have 0 ≤ ri,t (s, a) ≤ 1/H. In particular, every cumulative payoff lies in [0, 1]. This normalization is without loss after rescaling. Normal-form correlation. A finite-horizon Markov game induces a finite normal-form game, in which every (possibly history-dependent) policy πi is an action. Our main solution concept for Markov games will be the normal-form correlated equilibrium (NFCE), which is simply Definition 3.1 applied to this induced normal-form game. As with normal-form games, we will use both the standard and conditional notions of approximate NFCE; our upper bounds will apply to the latter and lower bounds to the former. This equilibrium requirement is significantly stronger than those guaranteed by existing algorithms, which revolve around notions akin to extensive-form correlated equilibrium, where recommendations are revealed only when the corresponding information sets are reached (von Stengel and Forges, 2008).

4

Computing constant-expectation correlated equilibrium

We first focus on approximately computing constant-expectation correlated equilibria—a refinement of the usual notion—in normal-form games. This refinement of correlated equilibrium will be key to our results about Markov games. Definition 4.1 (Constant-expectation CE). A distribution µ is an (ϵ, δ)-constant-expectation correlated equilibrium if it is a δ-CE and, for every player i ∈ [n], there exists vi ∈ R such that ∑

ai ∈supp(pµ i)

pµi (ai ) ∣Ea∼µ [ui (a) ∣ ai ] − vi ∣ ≤ ϵ.

Equivalently, ∑ai ∈Ai ∣wiµ (ai ) − vi pµi (ai )∣ ≤ ϵ. Our algorithm will in fact satisfy exact obedience and the stronger condition ℓi ≤ Ea∼µ [ui (a) ∣ ai ] ≤ ℓi + ϵ for every supported ai , whereas our hardness results hold for the more permissive averaged condition. To clarify this concept, we next provide an illustrative example. Example 4.2. We consider the following bimatrix game G, where A1 = {U, D} and A2 = {L, R}: L

R

U

(1, 1)

(0, 0)

D

(0, 0)

(1, 1)

Let µ be the uniform distribution over the pure profiles (U, L) and (D, R). This is not a Nash equilibrium, because µ is not a product distribution. It is, however, a constant-expectation CE. On

6

the other hand, the same distribution is not a constant-expectation CE in the following bimatrix game. L R U D

(1, 1)

(0, 0)

(0, 0)

(1/2, 1/2)

Nevertheless, µ is a correlated equilibrium in both games. Linear programming-based algorithm. The basic idea is to exhaustively search over all possible values in Definition 4.1, up to some small granularity. In particular, for a rational ϵ > 0, we let Gϵ ∶= {kϵ ∶ k = 0, 1, . . . , ⌊1/ϵ⌋} be a discretization of the [0, 1] interval. For a fixed ℓ = (ℓi )ni=1 ∈ Gnϵ , we consider the following linear feasibility program in µ: µ ∈ CE(G), ℓi pµi (ai ) ≤ wiµ (ai ) ≤ (ℓi + ϵ)pµi (ai )

for every i ∈ [n] and ai ∈ Ai .

(2)

Above, CE(G) denotes the set of correlated equilibria of G. We use the notation A ∶= max1≤i≤n ∣Ai ∣. Proposition 4.3. There exists ℓ ∈ Gnϵ for which the linear program (2) is feasible, and every feasible solution is an (ϵ/2, 0)-constant-expectation correlated equilibrium. Moreover, ℓi ≤ Ea∼µ [ui (a) ∣ ai ] ≤ ℓi + ϵ for every player i and supported action ai . Therefore, if L is an upper bound on the bit complexity of the payoff tensor of G, the running time is (A/ϵ)O(n) poly(L). The running time of this algorithm scales exponentially with the number of players. In Section 6, we will show that this obstacle is fundamental.

5

Efficient backward induction for NFCE in Markov games

Let S ∶= {(t, s) ∶ t ∈ [H], s ∈ St } and S ∶= ∣S∣ = ∑t ∣St ∣. We initialize ℓi,H+1 (s) ∶= 0 for every player i and terminal state s ∈ SH+1 . We then process stages in reverse order. At a state s ∈ St , we define an auxiliary normal-form game with payoff gi,t,s (a) ∶= ri,t (s, a) + ∑ Pt (s′ ∣ s, a)ℓi,t+1 (s′ ).

(3)

s′ ∈St+1

Using Proposition 4.3, we can find a correlated equilibrium µt,s ∈ ∆(At,s ) and values ℓi,t (s) satisfying ℓi,t (s) ≤ Ea∼µt,s [gi,t,s (a) ∣ ai ] ≤ ℓi,t (s) + ϵ

(4)

for every i and every ai ∈ Ai,t,s with positive marginal probability under µt,s . After all states have been processed, we independently sample at,s = (a1,t,s , . . . , an,t,s ) ∼ µt,s

(5)

for every (t, s) ∈ S. The sampled pure Markov policy of player i is πi,t (s) ∶= ai,t,s .

(6)

We define ρ to be the resulting distribution over pure Markov policy profiles, succinctly represented through (µt,s )(t,s)∈S . 7

Lemma 5.1. For every t, s, i, 0 ≤ ℓi,t (s) ≤ (H − t + 1)/H, and the auxiliary payoffs at stage t lie in [0, (H − t + 1)/H]. This shows that the payoffs lie in [0, 1], so we can apply Proposition 4.3. Now, by virtue of independence, the constructed distribution satisfies the following key property. Lemma 5.2. Consider a player i and a pure Markov policy π i with ρi (π i ) > 0. Conditional on π i , the random vectors {π −i,t (s) ∶ (t, s) ∈ S} are independent. At (t, s), their conditional law is πi νi,t,s (a−i ) ∶= P[π −i,t (s) = a−i ∣ π i ] =

µt,s (πi,t (s), a−i ) , µi,t,s (πi,t (s))

(7)

where µi,t,s is the ith marginal of µt,s . This will allow us to argue about the deviation benefit of a player i upon receiving its recommendation. In particular, conditioning on π i , the other players’ policy components are independent πi across states. Conditioning further on the history retains the law at (t, s) as νi,t,s per (7). Corollary 5.3. For a player i, consider any possibly randomized, history-dependent deviation conditioned on π i . At any history ht at state s having positive probability under this deviation, the πi conditional distribution of the opponents’ prescribed actions at (t, s) is νi,t,s .

5.1

The induced Markov decision process

We now leverage this notion of constant-expectation correlated equilibrium for Markov games. For a player i and π i ∈ supp(ρi ), we will analyze the conditional MDP Mi (π i ) with state spaces St , action sets Ai,t,s , expected rewards πi πi r̄i,t (s, a′i ) ∶= ∑ νi,t,s (a−i )ri,t (s, a′i , a−i ),

(8)

a−i

and transition kernels

πi

πi (a−i )Pt (s′ ∣ s, a′i , a−i ). Pi,t (s′ ∣ s, a′i ) ∶= ∑ νi,t,s

(9)

a−i

Lemma 5.4 (Reduction to an MDP). Conditional on π i , the expected payoff of every possibly randomized, history-dependent deviation of player i in the Markov game equals its expected payoff in the MDP Mi (π i ). This in particular implies that an optimal deviation may be chosen as deterministic and Markovian. ∗,π i We define the Bellman values of this MDP by Vi,H+1 (s) ∶= 0, ∗,π i ′ πi ′ ′ ′ ′ i Q∗,π i,t (s, ai ) ∶= r̄i,t (s, ai ) + ∑ Pi,t (s ∣ s, ai )Vi,t+1 (s ), πi

s′

∗,π i πi ′ i and Vi,t (s) ∶= maxa′i ∈Ai,t,s Q∗,π i,t (s, ai ). Now, let Vi,t (s) denote player i’s value in Mi (π i ) when following the recommended Markov policy π i from stage t onward. We have πi πi Vi,t (s) = ∑ νi,t,s (a−i )(ri,t (s, πi,t (s), a−i ) a−i

πi + ∑ Pt (s′ ∣ s, πi,t (s), a−i )Vi,t+1 (s′ )).

(10)

s′

Having computed a constant-expectation CE in each auxiliary game, we can derive the following. 8

Algorithm 1: Backward induction for NFCE in Markov games Input: Finite-horizon Markov game satisfying Assumption 3.2; accuracy ϵ ∈ (0, 1]. Output: An ϵ-conditional NFCE represented by (µt,s )(t,s)∈S , sampled independently. 1 η ← ϵ/H 2 ℓi,H+1 (s) ← 0 for every i ∈ [n] and s ∈ SH+1 3 for t = H, H − 1, . . . , 1 do 4 foreach s ∈ St do 5 Define, for every i ∈ [n] and a ∈ At,s , gi,t,s (a) ← ri,t (s, a) + ∑ Pt (s′ ∣ s, a)ℓi,t+1 (s′ ). s′ ∈St+1

6 7 8 9

foreach ℓ ∈ Gnη do Solve (2) with payoffs (gi,t,s )ni=1 , vector ℓ, and width η if feasible, with solution µ then µt,s ← µ and ℓi,t (s) ← ℓi for every i ∈ [n] break

10 return (µt,s )(t,s)∈S , inducing ρ via (5)–(6)

Lemma 5.5. Let ai ∶= πi,t (s). For every action a′i ∈ Ai,t,s , Ea−i ∼ν πi [gi,t,s (a′i , a−i )] ≤ ℓi,t (s) + ϵ and Ea−i ∼ν πi [gi,t,s (ai , a−i )] ≥ ℓi,t (s). i,t,s

i,t,s

Lemma 5.6. For every i, every π i ∈ supp(ρi ), every stage t, and every state s ∈ St , ∗,π i πi (s) ≥ ℓi,t (s) and Vi,t (s) ≤ ℓi,t (s) + (H − t + 1)ϵ. Vi,t

5.2

Main result

We are now ready to establish our main result. Theorem 5.7 (Backward-induction conditional NFCE guarantee). The distribution ρ over pure Markov policies produced by Algorithm 1 is an ϵ-conditional NFCE. Moreover, assuming the stage games and transitions are given explicitly with bit complexity at most L, and A ∶= maxi,t,s ∣Ai,t,s ∣, it runs in time AH O(n) S( ) poly(L). ϵ Proof. We consider a player i and a recommendation π i ∈ supp(ρi ). By Lemma 5.4, the optimal ∗,π i conditional deviation value from the initial state distribution λ is Es1 ∼λ [Vi,1 (s1 )]. Following the πi recommendation yields Es1 ∼λ [Vi,1 (s1 )]. Thus, Lemma 5.6 implies ∗,π i πi Es1 ∼λ [Vi,1 (s1 ) − Vi,1 (s1 )] ≤ Hη = ϵ.

The output is represented by the S distributions µt,s , which are to be sampled independently.

9

6

Hardness results

We now turn to our hardness results. We begin by establishing PPAD-hardness for constantexpectation CEs, and then translate those results to NFCEs in Markov games.

6.1

Succinct multi-player games

We first examine succinct many-player games. Here, we require an output representation from which the marginal probabilities can be computed in polynomial time, such as a mixture of product distributions (Papadimitriou and Roughgarden, 2008). Our hardness result holds even in polymatrix games. A polymatrix game is specified by a graph ([n], E) and a payoff matrix Mii′ for every edge (i, i′ ) ∈ E. Let Ni be the neighbor set of player i. At a pure action profile a, player i receives ui (a) = ∑i′ ∈Ni Mii′ (ai , ai′ ). We say that the game is normalized if ui (a) ∈ [0, 1] for every player and action profile. Our reduction will use the hardness result of Deligkas et al. (2024), which builds on Rubinstein (2015). Theorem 6.1 (Deligkas et al., 2024). For every constant 0 < δ < 1/12, computing a δ-Nash equilibrium in a normalized polymatrix game of maximum degree three with two actions per player is PPAD-hard. Let G be such a polymatrix game with Ai = {0, 1} for every player. We may assume that the source game has no isolated players. We define the payoff difference di (a−i ) ∶= ui (1, a−i ) − ui (0, a−i ) = ∑ (Mii′ (1, ai′ ) − Mii′ (0, ai′ )). i′ ∈Ni

Normalization implies di (a−i ) ∈ [−1, 1]. For a constant 0 < ϵ < 1/24, we set α ∶= 1/4 + 6ϵ, so 12ϵ < α < 1/2. We construct a transformed game G ′ on the same graph and action sets, with payoffs u′i (0, a−i ) ∶=

1 1 1 + αdi (a−i ) and u′i (1, a−i ) ∶= + di (a−i ). 2 2 2

This game is still a polymatrix game, as we point out below. Lemma 6.2. The game G ′ is a normalized polymatrix game of maximum degree three with two actions per player. For polymatrix games, the utilities can be expressed in terms of the marginal strategies. Lemma 6.3. Let µ ∈ ∆(A), and let x be its marginal strategy profile. Then, for every player i, Ea∼µ [di (a−i )] = ui (1, x−i ) − ui (0, x−i ). The following lemma now makes crucial use of the constant expectation property. Lemma 6.4. Let µ be an (ϵ, δ)-constant-expectation CE of G ′ . For any player i, 1 ( − α) pµi (ai ) max {(1 − 2ai )Eµ [di (a−i ) ∣ ai ], 0} ≤ δ. ∑ 2 µ ai ∈supp(p ) i

If both actions have positive marginal probability, then 1 min{pµi (0), pµi (1)} ∣ Eµ [di (a−i ) ∣ ai = 1] − αEµ [di (a−i ) ∣ ai = 0]∣ ≤ ϵ. 2 10

This lemma, together with simple algebra, implies a certain equilibrium collapse: the marginals of any constant-expectation CE reveal a Nash equilibrium of the original game. Lemma 6.5. If µ is an (ϵ, δ)-constant-expectation correlated equilibrium of G ′ and x is its marginal strategy profile, then x is an η-Nash equilibrium of G, where η = ϵ/α + δ/(α(1 − 2α)). Combining with the hardness result of Deligkas et al. (2024) (Theorem 6.1), we arrive at the following. Theorem 6.6 (PPAD-hardness). For every pair of constants such that 0 < ϵ < 1/24 and 0 ≤ δ < (1 − 24ϵ)2 /96, computing an (ϵ, δ)-constant-expectation correlated equilibrium in a normalized polymatrix game of maximum degree three with two actions per player is PPAD-hard.

6.2

Two-player games

We now turn our attention to two-player (bimatrix) games. We reduce from the problem of computing an exact Nash equilibrium of a rank-2 bimatrix game, which is PPAD-hard (Chen et al., 2016). Let G be such a game, so the sum of its payoff matrices has rank at most two. We write u1 (a) + u2 (a) = f1 (a1 )g1 (a2 ) + f2 (a1 )g2 (a2 ),

(11)

where f1 , f2 ∶ A1 → [−1, 1] and g1 , g2 ∶ A2 → [−1, 1]. For a parameter K ≥ 3, we consider the game G ′ on the same action sets with payoffs u1 (a) + 2g2 (a2 ) + K(g1 (a2 ) + 2) , 4K u2 (a) + 2f1 (a1 ) + K(f2 (a1 ) + 2) u′2 (a) ∶= . 4K As we point out below, G ′ is strategically equivalent to G. u′1 (a) ∶=

(12)

Lemma 6.7. G ′ has payoffs in [0, 1], has rank at most two, and has the same set of CEs as G. Moreover, µ is a δ-CE of G ′ if and only if it is a (4Kδ)-CE of G. The role of constant expectation is to make recommendations nearly uninformative about opponent-dependent terms, on average. For Player 1, when K ≫ 1, the term Kg1 (a2 ) dominates the remaining payoff. So, we can control the expected absolute deviation of the conditional expectation of g1 (a2 ) from its unconditional expectation. Player 2 similarly controls f2 (a1 ). These are precisely the two correlations that can separate a correlated equilibrium from a Nash equilibrium, as we establish in Lemma 6.9. In what follows, we use the notation Covµ (X, Y ) ∶= Eµ [XY ] − Eµ [X]Eµ [Y ]. Lemma 6.8. If µ is an η-CE of G with marginal strategy profile x, then 2

2

′

ui (ai , x−i ) − ui (x)) ≤ 2η + ∑ Covµ (fi (a1 ), gi (a2 )). ∑ (max ′

i=1 ai ∈Ai

i=1

As discussed, the averaged constant-expectation property suffices to control the covariance terms. Lemma 6.9. If µ is an (ϵ, δ)-constant-expectation correlated equilibrium of G ′ , then, for i ∈ {1, 2}, 6 . K Combining, we arrive at the following consequence, where we assume that ϵ and δ are given as part of the input in binary, so that log(1/ϵ) and log(1/δ) are polynomial. ∣Covµ (fi (a1 ), gi (a2 ))∣ ≤ 8ϵ +

Theorem 6.10. Computing an (ϵ, δ)-constant-expectation correlated equilibrium is PPAD-hard in bimatrix games when ϵ and δ are exponentially small. 11

6.3

Hardness for NFCE in Markov games

We finally circle back to Markov games. Our main hardness result establishes that relying on constant-expectation CEs in backward induction is fundamental: Theorem 6.11. Let G be an n-player normal-form game with utilities bounded in [0, 1], and 0 ≤ ϵ ≤ 1/(16n). There is a Markov game M with n + 1 players, horizon H = 2, S = n + 1 states, and stage rewards bounded in [0, 1/2], such that every ϵ-NFCE with independent state recommendations yields a (16nϵ, 16ϵ)-constant-expectation CE of G. By independent state recommendations, we mean that the joint action recommendations are sampled independently across pairs (t, s); recommendations to different players at the same state may be correlated. Combining the above result with Theorem 6.6 and Theorem 6.10, we therefore immediately derive PPAD-hardness of computing NFCE with independent state recommendations. Corollary 6.12. Computing an ϵ-NFCE with independent state recommendations is PPAD-hard for Markov games satisfying Assumption 3.2, even with horizon H = 2, in each of the following cases: 1. (n + 1)-player succinct games, two actions per player at each state, and ϵ = 1/(3072n). 2. Three-player games, a constant number of states, and exponentially small ϵ.

7

Conclusion

We established an efficient algorithm for computing conditional normal-form correlated equilibria in finite-horizon Markov games with a fixed number of players. Our key insight is that constantexpectation correlated equilibria, combined with independent sampling across states, make backward induction sound even when players observe their entire recommended policies before play. Our results suggest several interesting questions for future research. First, our algorithm is neither decentralized nor model free. Addressing this limitation is an important challenge for future work, but we believe our work lays the groundwork for such extensions. It would also be interesting to understand whether there are efficient algorithms when the number of players is part of the input. Our PPAD-hardness rules this out under state independent recommendations, but perhaps one can circumvent that result by introducing correlation between states. Finally, the complexity of computing NFCEs in other game representations, most notably the extensive form, remains a challenging open question.

AI Use Statement The initial idea for this paper, and the main idea for the proof of Main Theorem 1, are due to the authors. Various versions of GPT were used to assist in proofs of some of the lower bounds. All proofs were checked, understood, and rewritten by the authors.

Acknowledgments I.A. and T.S. are supported by NIH award A240108S001, the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, and National Science Foundation grant RI-2312342. We are grateful to Xi Chen and Mihalis Yannakakis for sharing their manuscript (Chen et al., 2016). I.A. additionally thanks Ioannis Panageas for helpful discussions concerning constant-rank games. C.D. was supported 12

by a Simons Investigator Award, a Simons Collaboration on Algorithmic Fairness, ONR MURI grant N00014-25-1-2116, ONR grant N00014-25-1-2296. G.F. was supported in part by the National Science Foundation award CCF-2443068, the Office of Naval Research grant N000142512296, and an AI2050 Early Career Fellowship.

References Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. In Symposium on Theory of computing (STOC), 2011. Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix and its algorithmic applications: approximate rank. In Symposium on Theory of computing (STOC), 2013. Ioannis Anagnostides and Weiqiang Zheng. Algorithmic collusion and the complexity of informationvalue-free equilibria. arXiv:2609.22757, 2026. Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, and Brian Hu Zhang. On the complexity of correlated equilibria beyond normal-form games. arXiv:2605.17665, 2026. Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Swap regret and correlated equilibria beyond normal-form games. In Conference on Economics and Computation (EC), 2025. Robert J Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67–96, 1974. Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Near-optimal policy optimization for correlated equilibrium in general-sum Markov games. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2024. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3):1–57, 2009. Xi Chen, Anthi Orfanou, Dimitris Paparas, and Mihalis Yannakakis. Rank 2 bimatrix games are PPAD-hard. Unpublished manuscript, 2016. Qiwen Cui, Kaiqing Zhang, and Simon S. Du. Breaking the curse of multiagents in a large state space: RL in Markov games with independent linear function approximation. In Conference on Learning Theory (COLT), 2023. Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction for large action spaces. In Symposium on Theory of Computing (STOC), 2024. Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. Communications of the ACM, 52(2):89–97, 2009. Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of Markov equilibrium in stochastic games. In Conference on Learning Theory (COLT), 2023. 13

Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis, and Jon Schneider. Efficient learning and computation of linear correlated equilibrium in general convex games. In Symposium on Theory of Computing (STOC), 2025. Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. PureCircuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5):1–48, 2024. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531–2597, 2010. Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas, and Vasilis Pollatos. The complexity of computing coarse correlated equilibria in Markov games with a single controller. arXiv:2607.10897, 2026. Dylan J. Foster, Noah Golowich, and Sham M. Kakade. Hardness of independent learning and sparse equilibrium computation in Markov games. In International Conference on Machine Learning (ICML), 2023. Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In International Conference on Machine learning (ICML), 2008. Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game-theoretic equilibria. In Conference on Learning Theory (COLT), 2003. Jason D Hartline, Chang Wang, and Chenhao Zhang. The computable but not learnable informationvalue-free equilibria and regulation of algorithmic collusion. In Conference on Economics and Computation (EC), 2026. Yuval Heller. Sequential correlated equilibria in stopping games. Operations Research, 60(1):209–224, 2012. Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning—a simple, efficient, decentralized algorithm for multiagent reinforcement learning. Mathematics of Operations Research, 49(4): 2295–2322, 2024. Ravi Kannan and Thorsten Theobald. Games of fixed rank: A hierarchy of bimatrix games. Economic Theory, 42(1):157–173, 2010. Xiangyu Liu and Kaiqing Zhang. Partially observable multiagent reinforcement learning with information sharing. SIAM Journal on Control and Optimization, 64(2):673–697, 2026. Weichao Mao, Haoran Qiu, Chen Wang, Hubertus Franke, Zbigniew Kalbarczyk, and Tamer Başar. ̃ −1 ) convergence to (coarse) correlated equilibria in full-information general-sum Markov O(T games. In Learning for Dynamics & Control Conference (L4DC), 2024. Ruta Mehta. Constant rank bimatrix games are PPAD-hard. In Symposium on Theory of Computing (STOC), 2014. Dustin Morrill, Ryan D’Orazio, Marc Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. Efficient deviation types and learning for hindsight rationality in extensive-form games. In International Conference on Machine Learning (ICML), 2021a.

14

Dustin Morrill, Ryan D’Orazio, Reca Sarfati, Marc Lanctot, James R. Wright, Amy R. Greenwald, and Michael Bowling. Hindsight and sequential rationality of correlated play. In Conference on Artificial Intelligence (AAAI), 2021b. John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286–295, 1951. Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3):1–29, 2008. Nikolas Patris and Ioannis Panageas. Learning Nash equilibria in rank-1 games. In International Conference on Learning Representations (ICLR), 2024. Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. In Symposium on Theory of Computing (STOC), 2024. Aviad Rubinstein. Inapproximability of nash equilibrium. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Symposium on Theory of Computing (STOC), 2015. Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum Markov games with a large number of players sample-efficiently? In International Conference on Learning Representations (ICLR), 2022. Sylvain Sorin. Distribution equilibrium I: Definition and examples. Working Paper 98-35, THEMA, Université Paris X–Nanterre, 1998. Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 59(1):187–208, 2007. Bernhard von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4):1002–1022, 2008. Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably efficient decentralized multi-agent RL with function approximation. In Conference on Learning Theory (COLT), 2023. Asrin Efe Yorulmaz, Ugur Aydin, and Tamer Basar. Independent reinforcement learning in discounted Markov games. arXiv:2609.00504, 2026. Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, and Tuomas Sandholm. Learning and computation of Φ-equilibria at the frontier of tractability. In Conference on Economics and Computation (EC), 2025.

15

A

Omitted proofs

This section contains the omitted proofs.

A.1

Proofs from Section 4

We begin with Proposition 4.3. Proposition A.1. There exists ℓ ∈ Gnϵ for which the linear program (2) is feasible, and every feasible solution is an (ϵ/2, 0)-constant-expectation correlated equilibrium. Moreover, ℓi ≤ Ea∼µ [ui (a) ∣ ai ] ≤ ℓi + ϵ for every player i and supported action ai . Therefore, if L is an upper bound on the bit complexity of the payoff tensor of G, the running time is (A/ϵ)O(n) poly(L). Proof. By Nash’s theorem (Nash, 1951), G admits a Nash equilibrium x = (xi )ni=1 . Let µ = ⊗i xi be the induced product distribution, which is clearly a correlated equilibrium. Every action ai ∈ supp(xi ) is a best response to x−i , so Ea∼µ [ui (a) ∣ ai ] = ui (ai , x−i ). For ai ∉ supp(xi ), both pµi (ai ) and wiµ (ai ) are zero. For ai ∈ supp(xi ), let ℓi ∶= ϵ⌊ui (ai , x−i )/ϵ⌋. Since ui (ai , x−i ) ∈ [0, 1], we have ℓi ∈ Gϵ and ℓi ≤ ui (ai , x−i ) < ℓi + ϵ. This shows that µ must be a feasible point of the LP induced by ℓ. Conversely, every feasible solution to (2) is a correlated equilibrium. Whenever pµi (ai ) > 0, dividing the last line by pµi (ai ) gives ℓi ≤ Ea∼µ [ui (a) ∣ ai ] ≤ ℓi + ϵ. Thus, choosing vi = ℓi + ϵ/2 bounds the absolute deviation by ϵ/2 for every supported recommendation, and hence also after averaging over recommendations, giving an (ϵ/2, 0)-constant-expectation correlated equilibrium as required by Definition 4.1. Finally, the claimed running time follows because Gnϵ contains (1/ϵ)O(n) points, and each induced linear program can be solved in time polynomial in An (L + log(1/ϵ)).

A.2

Proofs from Section 5

We continue with the proofs from Section 5. Lemma A.2. For every t, s, i, 0 ≤ ℓi,t (s) ≤ (H − t + 1)/H, and the auxiliary payoffs at stage t lie in [0, (H − t + 1)/H]. Proof. At stage H + 1, the claim holds because the continuation values are zero. Suppose it holds at stage t + 1. By the assumed normalization (Assumption 3.2) and the definition of the auxiliary normal-form games, we have 0 ≤ gi,t,s (a) ≤

1 H −t H −t+1 + = . H H H

Since ℓi,t (s) ≥ 0 belongs to the grid and is bounded above by a supported action’s conditional expected auxiliary payoff, the same upper bound holds for ℓi,t (s). Lemma A.3. Consider a player i and a pure Markov policy π i with ρi (π i ) > 0. Conditional on π i , the random vectors {π −i,t (s) ∶ (t, s) ∈ S} are independent. At (t, s), their conditional law is πi νi,t,s (a−i ) ∶= P[π −i,t (s) = a−i ∣ π i ] =

where µi,t,s is the ith marginal of µt,s .

16

µt,s (πi,t (s), a−i ) , µi,t,s (πi,t (s))

(7)

Proof. Let ρi (π i ) > 0. Independence in the constructed distribution (5) gives ρi (π i ) = ∏ µi,t,s (πi,t (s)). (t,s)∈S

Moreover, for any (a−i,t,s )(t,s)∈S , P[π −i,t (s) = a−i,t,s for all (t, s) ∣ π i ] =

∏(t,s)∈S µt,s (πi,t (s), a−i,t,s ) πi = ∏ νi,t,s (a−i,t,s ), µ (π (s)) ∏(t,s)∈S i,t,s i,t (t,s)∈S

as claimed. Lemma A.4 (Reduction to an MDP). Conditional on π i , the expected payoff of every possibly randomized, history-dependent deviation of player i in the Markov game equals its expected payoff in the MDP Mi (π i ). Proof. Corollary 5.3 shows that after every history at (t, s), and for every deviating action a′i , the conditional expected immediate reward and transition probabilities are given by (8) and (9), respectively. Applying iterated expectation over the stages, the expected cumulative reward in the Markov game conditional on π i is equal to that in Mi (π i ). Lemma A.5. Let ai ∶= πi,t (s). For every action a′i ∈ Ai,t,s , Ea−i ∼ν πi [gi,t,s (a′i , a−i )] ≤ ℓi,t (s) + ϵ and Ea−i ∼ν πi [gi,t,s (ai , a−i )] ≥ ℓi,t (s). i,t,s

i,t,s

Proof. Because π i ∈ supp(ρi ), the recommendation ai has positive marginal probability under µt,s . Thus, Ea−i ∼ν πi [gi,t,s (ai , a−i )] ≥ Ea−i ∼ν πi [gi,t,s (a′i , a−i )]. i,t,s

i,t,s

Combining this with (4) gives the claim. Lemma A.6. For every i, every π i ∈ supp(ρi ), every stage t, and every state s ∈ St , ∗,π i πi (s) ≥ ℓi,t (s) and Vi,t (s) ≤ ℓi,t (s) + (H − t + 1)ϵ. Vi,t

Proof. We proceed by backward induction, starting from the lower bound. At t = H + 1, the claim is immediate. Suppose that it holds at stage t + 1, and let ai ∶= πi,t (s). Using (10), the inductive πi hypothesis Vi,t+1 (s′ ) ≥ ℓi,t+1 (s′ ), and Lemma 5.5, we obtain πi Vi,t (s) ≥ Ea−i ∼ν πi [ri,t (s, ai , a−i ) + ∑ Pt (s′ ∣ s, ai , a−i )ℓi,t+1 (s′ )] i,t,s

s′

= Ea−i ∼ν πi [gi,t,s (ai , a−i )] ≥ ℓi,t (s). i,t,s

∗,π i ′ For the upper bound, the Bellman recursion, the inductive hypothesis Vi,t+1 (s ) ≤ ℓi,t+1 (s′ ) + (H − t)ϵ, and Lemma 5.5 give ∗,π i Vi,t (s) ≤ ′max Ea−i ∼ν πi [gi,t,s (a′i , a−i ) + (H − t)ϵ] ai ∈Ai,t,s

i,t,s

≤ ℓi,t (s) + ϵ + (H − t)ϵ = ℓi,t (s) + (H − t + 1)ϵ. This completes the induction. 17

A.3

Proofs for Section 6

We conclude with the proofs from Section 6, starting from our hardness result for polymatrix games. Lemma A.7. The game G ′ is a normalized polymatrix game of maximum degree three with two actions per player. Proof. For each edge (i, i′ ), we define 1 + α(Mii′ (1, ai′ ) − Mii′ (0, ai′ )), 2∣Ni ∣ 1 1 + (Mii′ (1, ai′ ) − Mii′ (0, ai′ )). M′ii′ (1, ai′ ) ∶= 2∣Ni ∣ 2 M′ii′ (0, ai′ ) ∶=

Summing over i′ ∈ Ni gives the specified payoffs. Because di ∈ [−1, 1] and 0 < α < 1/2, both payoffs lie in [0, 1]. The interaction graph and action sets remain the same, and the construction has polynomial bit complexity. Lemma A.8. Let µ ∈ ∆(A), and let x be its marginal strategy profile. Then, for every player i, Ea∼µ [di (a−i )] = ui (1, x−i ) − ui (0, x−i ). Proof. Linearity and the polymatrix structure give Ea∼µ [di (a−i )] = ∑ Ea∼µ [Mii′ (1, ai′ ) − Mii′ (0, ai′ )] i′ ∈Ni

= ∑

∑

i′ ∈Ni ai′ ∈{0,1}

xi′ (ai′ )(Mii′ (1, ai′ ) − Mii′ (0, ai′ ))

= ui (1, x−i ) − ui (0, x−i ). Lemma A.9. Let µ be an (ϵ, δ)-constant-expectation CE of G ′ . For any player i, 1 ( − α) pµi (ai ) max {(1 − 2ai )Eµ [di (a−i ) ∣ ai ], 0} ≤ δ. ∑ 2 µ ai ∈supp(p ) i

If both actions have positive marginal probability, then 1 min{pµi (0), pµi (1)} ∣ Eµ [di (a−i ) ∣ ai = 1] − αEµ [di (a−i ) ∣ ai = 0]∣ ≤ ϵ. 2 Proof. Since 1/2 − α > 0, we consider the deviation map that switches supported recommendation 0 precisely when Eµ [di (a−i ) ∣ ai = 0] > 0, switches supported recommendation 1 precisely when Eµ [di (a−i ) ∣ ai = 1] < 0, and otherwise obeys. Its expected gain is the sum of the positive gains from the two recommendations, so δ-CE obedience gives 1 ( − α) pµi (ai ) max {(1 − 2ai )Eµ [di (a−i ) ∣ ai ], 0} ≤ δ. ∑ 2 ai ∈supp(pµ ) i

Suppose now that pµi (0), pµi (1) > 0. By Definition 4.1, there exists vi such that ϵ ≥ pµi (0) ∣Eµ [u′i (a) ∣ ai = 0] − vi ∣ + pµi (1) ∣Eµ [u′i (a) ∣ ai = 1] − vi ∣ ≥ min{pµi (0), pµi (1)} ∣Eµ [u′i (a) ∣ ai = 1] − Eµ [u′i (a) ∣ ai = 0]∣ 1 = min{pµi (0), pµi (1)} ∣ Eµ [di (a−i ) ∣ ai = 1] − αEµ [di (a−i ) ∣ ai = 0]∣ , 2 which proves the claim. 18

This lemma, together with simple calculations, establishes the claimed equilibrium collapse, as we formalize below. Lemma A.10. If µ is an (ϵ, δ)-constant-expectation correlated equilibrium of G ′ and x is its marginal strategy profile, then x is an η-Nash equilibrium of G, where η = ϵ/α + δ/(α(1 − 2α)). Proof. By Lemma 6.3, we have that for any player i, ui (1, x−i ) − ui (0, x−i ) = Eµ [di (a−i )]. If pµi (0) = 1, obedience gives max ui (a′i , x−i ) − ui (x) = max{ui (1, x−i ) − ui (0, x−i ), 0} ≤

a′i ∈{0,1}

δ . 1/2 − α

Similarly, if pµi (1) = 1, max ui (a′i , x−i ) − ui (x) = max{ui (0, x−i ) − ui (1, x−i ), 0} ≤

a′i ∈{0,1}

δ . 1/2 − α

Since 2α < 1, these bounds are at most ϵ/α + δ/(α(1 − 2α)). If both probabilities are positive, ui (1, x−i ) − ui (0, x−i ) = pµi (0)Eµ [di (a−i ) ∣ ai = 0] + pµi (1)Eµ [di (a−i ) ∣ ai = 1]. If ui (1, x−i ) ≥ ui (0, x−i ), then max ui (a′i , x−i ) − ui (x) = pµi (0)(ui (1, x−i ) − ui (0, x−i ))

a′i ∈{0,1}

1 = 2pµi (0)pµi (1) ( Eµ [di (a−i ) ∣ ai = 1] − αEµ [di (a−i ) ∣ ai = 0]) 2 + pµi (0)(pµi (0) + 2αpµi (1))Eµ [di (a−i ) ∣ ai = 0] δ ≤ 2ϵ + , 1/2 − α where we used the fact that pµi (0)pµi (1) ≤ min{pµi (0), pµi (1)}, pµi (0) + 2αpµi (1) ≤ 1, and we applied both bounds from Lemma 6.4. Similarly, if ui (1, x−i ) ≤ ui (0, x−i ), max ui (a′i , x−i ) − ui (x) = pµi (1)(ui (0, x−i ) − ui (1, x−i ))

a′i ∈{0,1}

pµi (0)pµi (1) 1 ( Eµ [di (a−i ) ∣ ai = 1] − αEµ [di (a−i ) ∣ ai = 0]) α 2 pµi (0) µ µ − pi (1) (pi (1) + ) Eµ [di (a−i ) ∣ ai = 1] 2α ϵ δ ≤ + , α α(1 − 2α) =

where we used the fact that pµi (1) + pµi (0)/(2α) ≤ 1/(2α) and Lemma 6.4. Since α < 1/2, the second upper bound also dominates the first, proving the claim. We put everything together below.

19

Theorem 6.6 (PPAD-hardness). For every pair of constants such that 0 < ϵ < 1/24 and 0 ≤ δ < (1 − 24ϵ)2 /96, computing an (ϵ, δ)-constant-expectation correlated equilibrium in a normalized polymatrix game of maximum degree three with two actions per player is PPAD-hard. Proof. We consider constants 0 < ϵ < 1/24 and 0 ≤ δ < (1 − 24ϵ)2 /96, and set α = 1/4 + 6ϵ and η = ϵ/α + δ/(α(1 − 2α)). Since α(1 − 2α) > 0, we have ϵ δ 1 + < α α(1 − 2α) 12

⇐⇒

δ < (α/12 − ϵ)(1 − 2α) =

(1 − 24ϵ)2 . 96

Given an instance G of the problem in Theorem 6.1 for this η < 1/12, construct G ′ as above. The construction is polynomial. From any (ϵ, δ)-constant-expectation correlated equilibrium of G ′ , we compute its marginals x. By Lemma 6.5, x is an η-Nash equilibrium of G, and the result follows from Theorem 6.1. Next, we provide the proofs pertaining to the two-player reduction, which starts from a rank-2 game. Lemma A.11. G ′ has payoffs in [0, 1], has rank at most two, and has the same set of CEs as G. Moreover, µ is a δ-CE of G ′ if and only if it is a (4Kδ)-CE of G. Proof. Normalization is immediate. The rank bound follows from the fact that 4K(u′1 (a) + u′2 (a)) = (f1 (a1 ) + K)(g1 (a2 ) + 2) + (f2 (a1 ) + 2)(g2 (a2 ) + K). Moreover, for every deviation map ϕi ∶ Ai → Ai , Eµ [u′i (ϕi (ai ), a−i ) − u′i (a)] =

1 Eµ [ui (ϕi (ai ), a−i ) − ui (a)], 4K

Thus, µ is a δ-CE of G ′ if and only if it is a (4Kδ)-CE of G. Lemma A.12. If µ is an η-CE of G with marginal strategy profile x, then 2

2

′

ui (ai , x−i ) − ui (x)) ≤ 2η + ∑ Covµ (fi (a1 ), gi (a2 )). ∑ (max ′

i=1 ai ∈Ai

i=1

Proof. For each player i, we have Eµ [ui (a)] ≥ maxa′i ∈Ai ui (a′i , x−i ) − η by applying η-CE obedience to constant deviation maps. Subtracting ui (x), summing over both players, and using (11) gives the upper bound 2

2

′

ui (ai , x−i ) − ui (x)) ≤ 2η + ∑ (Eµ [ui (a)] − ui (x)) ∑ (max ′

i=1

ai

i=1 2

= 2η + ∑ Covµ (fi (a1 ), gi (a2 )). i=1

In light of the previous lemma, it suffices to bound the covariance terms. This is done in the following lemma, crucially relying on the constant expectation property. Lemma A.13. If µ is an (ϵ, δ)-constant-expectation correlated equilibrium of G ′ , then, for i ∈ {1, 2}, ∣Covµ (fi (a1 ), gi (a2 ))∣ ≤ 8ϵ + 20

6 . K

Proof. We use the notation u′i (ai ) ∶= Eµ [u′i (a) ∣ ai ] for supported actions, and ūi ∶= Eµ [u′i (a)]. Since ūi = ∑ai ∈supp(pµ ) pµi (ai )u′i (ai ), Definition 4.1 gives i ∑

ai ∈supp(pµ i)

pµi (ai )∣u′i (ai ) − ūi ∣ ≤

∑

ai ∈supp(pµ i)

pµi (ai )∣u′i (ai ) − vi ∣ + ∣vi − ūi ∣ ≤ 2ϵ.

(13)

Taking conditional and unconditional expectations in (12), and using ∣u1 + 2g2 ∣ ≤ 3, gives ∣Eµ [g1 (a2 ) ∣ a1 ] − Eµ [g1 (a2 )]∣ ≤ 4∣u′1 (a1 ) − ū1 ∣ +

6 . K

Averaging over a1 and applying (13), we obtain ∑

a1 ∈supp(pµ 1)

pµ1 (a1 ) ∣Eµ [g1 (a2 ) ∣ a1 ] − Eµ [g1 (a2 )]∣ ≤ 8ϵ +

6 . K

As a result, since ∣f1 ∣ ≤ 1, ∣ Covµ (f1 (a1 ), g1 (a2 ))∣ = ∣Eµ [f1 (a1 ) (Eµ [g1 (a2 ) ∣ a1 ] − Eµ [g1 (a2 )])]∣ 6 ≤ 8ϵ + . K The bound with respect to Player 2 follows symetrically. Theorem 6.10. Computing an (ϵ, δ)-constant-expectation correlated equilibrium is PPAD-hard in bimatrix games when ϵ and δ are exponentially small. Proof. Given a game G as above, we choose η = 2−p(L) ∈ (0, 1], where L is its bit complexity and p is a polynomial, sufficiently small that any rational η-Nash equilibrium can be converted in polynomial time into an exact Nash equilibrium; for example, this can be done through an LP (Etessami and Yannakakis, 2010). We set the parameters as K ∶= 48/η, ϵ ∶= η/32, δ ∶= η 2 /1536 = η/(32K), and construct G ′ using (12). The construction is polynomial in L. Let µ be any (ϵ, δ)-constant-expectation correlated equilibrium of G ′ , and let x be its marginal strategy profile. By Lemma 6.7, µ is a (4Kδ)-CE of G. Therefore, Lemmas 6.8 and 6.9 give 2

′

ui (ai , x−i ) − ui (x)) ≤ 16ϵ + 8Kδ + ∑ (max ′

i=1

ai

12 = η, K

where the equality follows by our parameter choice. This proves that x is an η-Nash equilibrium, from which we can recover an exact Nash equilibrium of G.

B

Hardness for independent state recommendations

In this section, we show that, in a sense, constant-expectation CEs are necessary to compute NFCEs in Markov games. Thus, applying our hardness results (Theorems 6.6 and 6.10), it will follow that computing an ϵ-NFCE with independent state recommendations is PPAD-hard for games with a constant number of players when ϵ is exponentially small, and for n + 1 players when ϵ = Θ(1/n). Theorem 6.11. Let G be an n-player normal-form game with utilities bounded in [0, 1], and 0 ≤ ϵ ≤ 1/(16n). There is a Markov game M with n + 1 players, horizon H = 2, S = n + 1 states, and stage rewards bounded in [0, 1/2], such that every ϵ-NFCE with independent state recommendations yields a (16nϵ, 16ϵ)-constant-expectation CE of G. 21

Proof. Player n + 1 will be called the tester. The Markov game is constructed as follows. At the first stage, a player i ∈ [n] is selected uniformly at random. That player plays a game of matching pennies against the tester: if the pennies match, then i gets 2; else, the tester gets 2. If the player played tails, the game ends. Otherwise, at stage 2, the n players (excluding the tester) play G and gain the associated rewards. There are n states at stage 1 and one state at stage 2, for a total of n + 1 states. All unspecified rewards are zero, and inactive players have a single dummy action. Consider any ϵ-NFCE of M with independent state recommendations. (Throughout this proof, we use the ex-ante deviation inequalities of an ϵ-NFCE.) Let µ be the correlated profile recommended at G. We claim that µ is a (4nϵ, 4ϵ)-constant-expectation CE. Let vi ∶= Ea∼µ [ui (a)]. Independence across states implies that deviations affecting only the first-stage action, and ignoring the secondstage recommendation, have continuation value vi if G is reached. If Player i is selected, then Player i and the tester play a game strategically equivalent to the zero-sum game with row utility matrix H

T

H

2 + vi

vi

T

0

2

where the player is the row player and the tester is the column player. The unique Nash equilibrium has the player playing heads with probability 1/2, the tester playing heads with probability (2 − vi )/4 ∈ [1/4, 1/2], and value Vi ∶= 1 + vi /2 for i. Let Ṽi be the row player’s expected payoff conditional on reaching this state. The state is reached with probability 1/n, so a deviation confined to this state has conditional gain at most nϵ. Therefore, we have ∣Vi − Ṽi ∣ ≤ nϵ. The tester’s deviation to H gives Ṽi ≤ (2 + vi )qi + nϵ, where qi is the probability that Player i plays heads. Therefore, qi ≥

Ṽi − nϵ Vi − 2nϵ 1 1 ≥ ≥ − nϵ ≥ , 2 + vi 2Vi 2 4

where we use the inequalities Ṽi ≥ Vi − nϵ, Vi ≥ 1, and nϵ ≤ 1/4. Therefore, G is reached with probability at least 1/4, and so µ is a 4ϵ-CE. It remains to show the constant-expectation property. Let pi be the probability with which the tester is recommended to play heads against i. For every recommendation ai in the support of pµi , let ui (ai ) ∶= Ea∼µ [ui (a) ∣ ai ]. Consider a deviation that, only when i is selected, ignores its first-stage recommendation and chooses heads or tails using only ai , while obeying at G if it is reached. By independence across states, heads has expected value 2pi + ui (ai ) and tails has expected value 2(1 − pi ). Therefore, choosing the most profitable action and averaging over ai yields conditional utility Vi∗ = ∑ pµi (ai ) max{2pi + ui (ai ), 2(1 − pi )} = Vi + ai

1 µ ∑ p (ai )∣(2 − 4pi ) − ui (ai )∣. 2 ai i

This deviation cannot increase utility conditional on the selected state by more than nϵ. As a result, Vi∗ ≤ Ṽi + nϵ ≤ Vi + 2nϵ, and ∑

ai ∈supp(pµ i)

pµi (ai )∣(2 − 4pi ) − ui (ai )∣ ≤ 4nϵ.

22

Therefore, choosing vi′ ∶= 2−4pi , and dividing all rewards by 4 to satisfy the normalization assumption, completes the proof. We finally note that the construction preserves succinct payoff representations with polynomial overhead.

23

Related documents

• Correlated Perfect Equilibrium#1248297
• Normal-Form Correlation in Markov Games#1188332
• Categorization and correlation in a random-matching game#1276439
• Game Theory#702308
• Reinterpreting Nash Equilibrium and Game Theory: From Prisoners to Fluctuations#85512