The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller

arXiv:2607.10897 · cs.GT, cs.CC · Submitted 2026-07-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller".

Jane: Here's the gist of the paper. We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games

PR81, FV97: .

Tom: This paper resolves whether hardness persists when a single player controls all transitions—a setting where no such collapse occurs.

Jane: The Core Problem and Contribution In this paper, we resolve the aforementioned questions by showing that computing a stationary Markov ε-CCE in two-player stochastic games with a single controller is PPAD-complete.

Tom: In particular, hardness is shown for both the perfect notion (where the equilibrium conditions hold at every state) and the non-perfect notion (where the equilibrium conditions hold in expectation under the law of the initial state distribution).

Paper summary: Jane: We've covered what this paper says about computing stationary Markov coarse correlated equilibria in discounted single-controller stochastic games and why the complexity remains hard even with a single controller controlling all transitions.

Tom: To summarize, "The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller" establishes that finding an approximate stationary perfect Markov coarse correlated equilibrium is PPAD-complete under these constraints.

Lu: This result confirms that the computational obstruction we were looking for isn't specific to turn-based constructions where control alternates across states, but rather it's inherent to having one player exclusively control all transitions.

Meng: In simpler terms, if you have a game where one person dictates how the game moves between states, even if both players still get rewards from the outcomes, finding a good correlated equilibrium is computationally intractable unless you use an algorithm that is PPAD-complete.

Jane: And for someone who only listens to this show, it means that simplifying the structure by limiting control to one player doesn't remove the fundamental difficulty of finding these equilibria.

Tom: The paper's title and authors signal this precisely: they are studying the complexity in Markov games with a single controller, and they show that this restriction does not make the problem easier computationally.

Conclusion: Tom: So, we're wrapping up this look at "The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller." Basically, they figured out that finding these equilibria is hard even when one player controls all the transitions in a game.

Jane: That's what I was curious about. So, if you're driving and you hear something like that, what does it actually mean for how we think about games or decision-making?

Tom: It means that this isn't just a trick of setting up the rules in a specific way. The authors are showing that this computational difficulty holds up even when you restrict the control structure to having only one player dictate the game's movement between states.

Lu: What they proved is that computing an approximate stationary perfect Markov coarse correlated equilibrium is PPAD-complete under these single-controller constraints, for both the exact and non-perfect versions.

Meng: PPAD-complete... that’s a big complexity class. For someone shipping models at scale, what does that translate to in terms of actual runtime? Is this something we can ever practically tackle with current hardware limitations?

Jane: That's a fair question, Meng. So, if the problem is PPAD-complete, it suggests that finding these equilibria isn't just a matter of needing a more clever algorithm; it points to a fundamental barrier in the structure of these games themselves.

Tom: Exactly. The hard part isn't just the search space size; it’s that even with this single controller setup, the necessary correlations are still deeply buried in the problem's structure, and you can't simplify away that core difficulty easily.

Lu: What they emphasize is that this hardness is robust. It doesn't disappear if you tweak parameters like the discount factor or whether you use a perfect or non-perfect notion of equilibrium.

Meng: So, even if I try to make the game simpler by making it non-perfect, or changing how much time passes between moves, the computational hurdle stays put? That’s a strong statement for deployment scenarios.

Jane: It means that the difficulty isn't just about finding a specific parameter setting; it’s about the nature of correlation and control itself in these stochastic environments. And this has huge implications for understanding how complex decision-making systems actually work in the real world.

Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos

Massachusetts Institute of Technology · National Technical University of Athens · Archimedes, Athena Research Center, Greece · University of California, Irvine · National and Kapodistrian University of Athens

cs.GT, cs.CC

Submitted: 2026-07-12

Updated: 2026-07-12

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 99/100

The gist: We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97].

Key concepts

Stationary Markov $\epsilon$-CCE
This refers to a set of strategies where players aim for an approximate balance in their actions over time. 'Markov' means decisions depend only on the current state, and 'stationary' means the strategy repeats itself. The $\epsilon$ represents how close this approximate balance must be to a true equilibrium.
Single-Controller Restriction
This is a specific game setting where one player (the controller) has complete control over all transitions in the game, while the other player (the reward player) only affects rewards. The paper shows that even with this strong restriction, finding the CCE remains computationally hard.
PPAD-Completeness
PPAD-completeness is a complexity class used to measure problems that are computationally difficult but solvable in polynomial time if one has access to an oracle for a specific problem. Showing a problem is PPAD-complete means it's at the boundary of what is efficiently solvable, indicating inherent computational hardness.
Perfect vs. Non-Perfect CCE
A 'perfect' CCE requires that the equilibrium conditions hold exactly at every state. A 'non-perfect' CCE only requires these conditions to hold in expectation under a specific initial state distribution, allowing for some approximation ($\epsilon$) of the equilibrium.

Terminology

Summary

We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97]. p. 0

Where the paper says it

The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller Gabriele Farina1 , Andreas Kontogiannis†2,3, Ioannis Panageas4 , and Vasilis Pollatos†3,5 1Massachusetts Institute of Technology 2National Technical University of Athens 3Archimedes, Athena Research Center, Greece 4University of California, Irvine 5National and Kapodistrian University of Athens July 14, 2026 Abstract We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subclass of stochastic games in which all players may affect rewards, but only one player controls the state transitions. Prior work [DGZ23, JMS23, HN25] established PPAD-hardness for computing stationary Markov CCE in two-player general-sum stochastic games via turn-based constructions in which each state is controlled by a single player, with control alternating across states.

This paper resolves whether hardness persists when a single player controls all transitions—a setting where no such collapse occurs. p. 0
Where the paper says it

This structure forces every Markov CCE to collapse to a Nash equilibrium (NE), so hardness for NE transfers immediately to CCE. It remained open whether hardness persists when a single player controls all transitions—a setting where no such collapse occurs.

The Core Problem and Contribution

In this paper, we resolve the aforementioned questions by showing that computing a stationary Markov ε-CCE in two-player stochastic games with a single controller is PPAD-complete. In particular, hardness is shown for both the perfect notion (where the equilibrium conditions hold at every state) and the non-perfect notion (where the equilibrium conditions hold in expectation under the law of the initial state distribution). p. 3

Where the paper says it

1 Contribution and significance In this paper, we resolve the aforementioned questions by showing that computing a stationary Markov ε-CCE in two-player stochastic games with a single controller is PPAD-complete. In particular, hardness is shown for both the perfect notion (where the equilibrium conditions hold at every state) and the non-perfect notion (where the equilibrium conditions hold in expectation under the law of the initial state distribution).

We prove that this PPAD-hardness is robust to the single-controller restriction. p. 3
Where the paper says it

Since every stationary Markov perfect NE is a stationary Markov perfect CCE, the corresponding CCE search problem is in PPAD. Remarkably, our results imply that the PPAD-hardness of stationary Markov CCE is robust to the single-controller restriction.

Hardness for Perfect CCE

Theorem 4.4 states that computing a perfect stationary Markov ε-CCE in a discounted two-player single-controller Markov game is PPAD-hard, even when the discount factor γ is any fixed constant in [1/16, 1), all rewards lie in [0, 1], and accuracy ε > 0 is less than an absolute constant. p. 3

Where the paper says it

1 (Abridged version of Theorem 4. Computing a perfect stationary Markov ε-CCE in a discounted two-player single-controller Markov game is PPAD-hard, even when the discount factor γ is any fixed constant in [1/16, 1), 1 all rewards lie in [0, 1], and accuracy ε > 0 is less than an absolute constant.

The proof relies on constructing a two-player discounted Markov game Gλ(I) with players C and R. p. 0
Where the paper says it

The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller Gabriele Farina1 , Andreas Kontogiannis†2,3, Ioannis Panageas4 , and Vasilis Pollatos†3,5 1Massachusetts Institute of Technology 2National Technical University of Athens 3Archimedes, Athena Research Center, Greece 4University of California, Irvine 5National and Kapodistrian University of Athens July 14, 2026 Abstract We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subclass of stochastic games in which all players may affect rewards, but only one player controls the state transitions. Prior work [DGZ23, JMS23, HN25] established PPAD-hardness for computing stationary Markov CCE in two-player general-sum stochastic games via turn-based constructions in which each state is controlled by a single player, with control alternating across states.

Hardness for Non-Perfect CCE

Theorem 5.5 shows that assuming PCP-for-PPAD for Pure-Circuit holds, computing a non-perfect stationary Markov ε-CCE in a discounted two-player singlecontroller Markov game is PPAD-hard. p. 3

Where the paper says it

Assume that PCP-for-PPAD for Pure-Circuit holds. Then, computing a non-perfect stationary Markov ε-CCE in a discounted two-player singlecontroller Markov game is PPAD-hard, even when the discount factor γ is any fixed constant in [1/16, 1), 1 all rewards lie in [0, 1], and accuracy ε > 0 is less than an absolute constant.

Furthermore, we provide an unconditional hardness result for the non-perfect notion where the hardness holds for inverse polynomial accuracy parameter instead of constant. p. 3
Where the paper says it

Similarly to [DGZ23], we also provide an unconditional hardness result for the non-perfect notion (stated formally in Theorem 5. 6), where the hardness holds for inverse polynomial accuracy parameter instead of constant.

Technical Reduction Gadgets

The reduction starts from a circuit problem, such as Generalized-Circuit [CDT09] or Pure-Circuit [DFHM24]. We construct a two-player discounted Markov game Gλ(I) with players C (controller) and R (reward player). p. 7

Where the paper says it

An infinite-horizon discounted Markov game is a tuple Γ = (S, [m],(Ai(s))i∈[m],s∈S,(ri)i∈[m] , P, µ, γ), where S is a finite state space, [m] is a finite set of players, Ai(s) is the action set of player i at state s, and A(s) = Q i∈[m] Ai(s). The reward function of player i is ri : S s∈S{s} × A(s) → [0, 1].

The construction uses single-controller gadgets for implementing the gates, specifically the copy gadget (C) and the controller-forcing gadget (F). p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

Robustness to Equilibrium Collapse

Remarkably, our results imply that the PPAD-hardness of stationary Markov CCE is robust to the single-controller restriction. The computational obstruction is more basic than previously understood: it is enough that one player solely controls the transitions while both players affect rewards. p. 3

Where the paper says it

The computational obstruction is more basic than previously understood: the PPAD-hardness results of stationary Markov CCE shown in prior work [DGZ23, HN25, JMS23] relied on turn-based games which enforce equilibrium collapse phenomena, whereby hardness for NE immediately translated to CCE. Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards.

Conclusion on Complexity

The paper concludes that computing approximate stationary perfect Markov CCE in discounted single-controller stochastic games is PPAD-complete. The hardness of stationary Markov CCE is not an artifact of switching-controller transition setup or equilibrium collapse phenomena. p. 3

Where the paper says it

The computational obstruction is more basic than previously understood: the PPAD-hardness results of stationary Markov CCE shown in prior work [DGZ23, HN25, JMS23] relied on turn-based games which enforce equilibrium collapse phenomena, whereby hardness for NE immediately translated to CCE. Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards.

Extended Related Work

The paper notes that the results both for the perfect and non-perfect notion continue to hold for any γ ∈ [1/16, 1) due to adding an action-independent lazy self-loop in the transition model. The example illustrates that the joint policy may remain genuinely correlated at individual states, and the same stationary policy is an exact perfect Markov CCE for G0(I) and an exact non-perfect Markov CCE from the output-supported initial distribution. p. 8

Where the paper says it

4 (Non-perfect Markov ε-CCE). A stationary Markov joint policy π is a non-perfect Markov ε-coarse correlated equilibrium from µ if, for every player i and every stationary one-player deviation π ′ i , V π ′ i×π−i i (µ) − V π i (µ) ≤ ε.

Proof of Lemma 2. p. 1

Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

5

The performance-difference lemma for one-player deviations states that Vπ'i×π−i i(s0) − Vπ i(s0) = 1/ (1 − γ) X s∈S d π'i×π−i s0(s)Advπ,pi'i i(s).

Proof of Lemma 4. p. 1

Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

2

Lemma 4.2 states that if π is a perfect Markov ε-CCE of G0(I), then for every variable state s, ρπ C,s ≤ ε. p. 6

Where the paper says it

For the perfect Markov CCE hardness result, we set λ = 0, so the controller’s immediate reward at variable states is independent of its own action. Moreover, because the perfect CCE constraints hold from every initial state, each gadget condition can be proved state by state: a violation at a single variable state directly yields a profitable deviation from that state.

Proof of Lemma 5. p. 1

Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

3

Lemma 5.3 shows that if ε < ηcforce/4, then µ(Eforce) < η. p. 3

Where the paper says it

The computational obstruction is more basic than previously understood: the PPAD-hardness results of stationary Markov CCE shown in prior work [DGZ23, HN25, JMS23] relied on turn-based games which enforce equilibrium collapse phenomena, whereby hardness for NE immediately translated to CCE. Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards.

Proof of Theorem 4. p. 1

Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

4

The proof for Theorem 4.4 involves setting ε0:= γ∆/16 = 1/65536 and showing that if a polynomial-time algorithm outputs a perfect Markov ε-CCE π for some ε < ε0, then the decoded assignment solves I. p. 3

Where the paper says it

2The joint control of rewards is a necessary condition for hardness in single-controller Markov games, since the restricted setting where a single player controls the transitions, and only the other player(s) control(s) the rewards, is in P. This result is quite straightforward: the reward-controlling players compute a CCE strategy per-state, while the transition-controlling player solves a single-agent MDP problem given the CCE profile of the other players.

p. 3
Where the paper says it

2The joint control of rewards is a necessary condition for hardness in single-controller Markov games, since the restricted setting where a single player controls the transitions, and only the other player(s) control(s) the rewards, is in P. This result is quite straightforward: the reward-controlling players compute a CCE strategy per-state, while the transition-controlling player solves a single-agent MDP problem given the CCE profile of the other players.

Proof of Theorem 5. p. 1

Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

p. 1
Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

5

Theorem 5.5 proves that if a polynomial-time algorithm outputs a non-perfect Markov ε-CCE π for some ε < ε', then the assignment decoded from π satisfies at least a (1 − δ) fraction of the gates of I, solving δ-Pure-Circuit, which is PPAD-hard under Conjecture 1.

Proof of Theorem 5.6

Theorem 5.6 establishes an unconditional inverse-polynomial-accuracy result where there exists a universal constant κ > 0 such that computing a non-perfect Markov ε-CCE of a discounted two-player single-controller Markov game is PPAD-hard whenever ε < κ S2. p. 3

Where the paper says it

Then, computing a non-perfect stationary Markov ε-CCE in a discounted two-player singlecontroller Markov game is PPAD-hard, even when the discount factor γ is any fixed constant in [1/16, 1), 1 all rewards lie in [0, 1], and accuracy ε > 0 is less than an absolute constant. Similarly to [DGZ23], we also provide an unconditional hardness result for the non-perfect notion (stated formally in Theorem 5.

p. 3
Where the paper says it

Then, computing a non-perfect stationary Markov ε-CCE in a discounted two-player singlecontroller Markov game is PPAD-hard, even when the discount factor γ is any fixed constant in [1/16, 1), 1 all rewards lie in [0, 1], and accuracy ε > 0 is less than an absolute constant. Similarly to [DGZ23], we also provide an unconditional hardness result for the non-perfect notion (stated formally in Theorem 5.

Proof of Proposition 5. p. 6

Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

4

Proposition 5.4 shows that if no output state of a gate lies in Bad, then the decoded assignment satisfies that gate, and if µ(Bad) < δ/2 then the decoded assignment satisfies at least a (1 − δ) fraction of the gates. p. 5

Where the paper says it

Such a circuit is a collection of variables connected by gates, where each gate imposes a local constraint on the values of its input and output variables. The goal is to find an assignment of values to all variables that approximately satisfies every gate.

p. 5
Where the paper says it

Such a circuit is a collection of variables connected by gates, where each gate imposes a local constraint on the values of its input and output variables. The goal is to find an assignment of values to all variables that approximately satisfies every gate.

Proof of Proposition 3. p. 6

Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

2

Proposition 3.2 states that if gadget conditions (C) and (F) hold at every output state, then the decoded assignment satisfies the corresponding NOT, OR, or PURIFY constraint. p. 5

Where the paper says it

The goal is to find an assignment of values to all variables that approximately satisfies every gate. The common reduction recipe is to represent each circuit variable by a behavioral signal in the stationary policy, implement each gate by a local game gadget whose incentives enforce the corresponding constraint, and then glue the gadgets so that the output signal of one gate is used as the input signal of another.

Proof of Proposition 6. p. 6

Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

p. 6
Where the paper says it

The controller-forcing gadget uses gaps between the controller’s two continuation values4 to force the controller marginal itself to be almost Boolean. Once these two conditions hold, the decoded circuit assignment implements the NOT, OR, and PURIFY gates of the Pure-Circuit instance (see Proposition 3.

1

Proposition 6.1 shows that for λ = 0, it is an exact perfect Markov CCE of G0(I), and for every 0 < λ < 1/180, it is an exact non-perfect Markov CCE of Gλ(I) from the distribution µ that is uniform on O. p. 3

Where the paper says it

1 Contribution and significance In this paper, we resolve the aforementioned questions by showing that computing a stationary Markov ε-CCE in two-player stochastic games with a single controller is PPAD-complete. In particular, hardness is shown for both the perfect notion (where the equilibrium conditions hold at every state) and the non-perfect notion (where the equilibrium conditions hold in expectation under the law of the initial state distribution).

Proof of Proposition 3.3

Proposition 3.3 proves that if a stationary policy π of Gλ(I) satisfies conditions (C) and (F) at every output state, then the decoded assignment (8) is a valid solution of the PureCircuit instance I. p. 4

Where the paper says it

To elaborate on the above, Section 6 gives a formal example of a Pure-Circuit instance and a stationary Markov CCE of the corresponding reduced single-controller stochastic game. The decoded policy yields a valid solution of the circuit instance, but the CCE does not collapse to an approximate NE of the reduced game.

The proof for Proposition 5.4 shows that if no output state of a gate lies in Bad, then neither the copy implication nor the controllerforcing implication fails at any output of that gate. p. 3

Where the paper says it

The computational obstruction is more basic than previously understood: the PPAD-hardness results of stationary Markov CCE shown in prior work [DGZ23, HN25, JMS23] relied on turn-based games which enforce equilibrium collapse phenomena, whereby hardness for NE immediately translated to CCE. Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards.

p. 3
Where the paper says it

The computational obstruction is more basic than previously understood: the PPAD-hardness results of stationary Markov CCE shown in prior work [DGZ23, HN25, JMS23] relied on turn-based games which enforce equilibrium collapse phenomena, whereby hardness for NE immediately translated to CCE. Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards.

p. 3
Where the paper says it

The computational obstruction is more basic than previously understood: the PPAD-hardness results of stationary Markov CCE shown in prior work [DGZ23, HN25, JMS23] relied on turn-based games which enforce equilibrium collapse phenomena, whereby hardness for NE immediately translated to CCE. Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards.

Proof of Lemma 5.1

Lemma 5.1 proves the Decorrelation identity: ∆R + λ−1∆dec C = X u∈V d πµ(su) B(qu) − Mprod u. p. 7

Where the paper says it

The reward player’s best-matching deviation may gain on copy-error states but lose on well-correlated non-error states, so a gain–loss cancellation can occur when the non-perfect CCE inequality is averaged from the initial distribution. The λ-bonus supplies a controller decorrelation deviation whose gain cancels the dependence on the actual joint matching probability, replacing it by a nonnegative marginal witness of copy failure.

p. 7
Where the paper says it

The reward player’s best-matching deviation may gain on copy-error states but lose on well-correlated non-error states, so a gain–loss cancellation can occur when the non-perfect CCE inequality is averaged from the initial distribution. The λ-bonus supplies a controller decorrelation deviation whose gain cancels the dependence on the actual joint matching probability, replacing it by a nonnegative marginal witness of copy failure.

Proof of Lemma 5.2

Lemma 5.2 proves the Average copy lemma: if ε < (1 − γ)ηccopy / (1 + λ−1), then µ(Ecopy) < η. p. 1

Where the paper says it

17 5 Non-perfect Markov CCE hardness 17 5. 1 Average copy .

p. 1
Where the paper says it

17 5 Non-perfect Markov CCE hardness 17 5. 1 Average copy .

Lemma 5.3 proves the Average forcing lemma: if ε < ηcforce/4, then µ(Eforce) < η. p. 1

Where the paper says it

1 Average copy . 2 Average controller-forcing .

p. 1
Where the paper says it

1 Average copy . 2 Average controller-forcing .

Proof of Proposition 3.2 (Gates Implementation)

The proof for Proposition 3.2 verifies the three gate types as follows, using the defined value intervals and gap sizes derived from Lemma 3.1.

Proof of Example

The example illustrates that for λ = 0, it is an exact perfect Markov CCE of G0(I). For every 0 < λ < 1/180, it is an exact non-perfect Markov CCE of Gλ(I) from the distribution µ that is uniform on O. p. 3

Where the paper says it

1 Contribution and significance In this paper, we resolve the aforementioned questions by showing that computing a stationary Markov ε-CCE in two-player stochastic games with a single controller is PPAD-complete. In particular, hardness is shown for both the perfect notion (where the equilibrium conditions hold at every state) and the non-perfect notion (where the equilibrium conditions hold in expectation under the law of the initial state distribution).

Proof of Proposition 6.1 (Part iii)

The proof for part (iii) shows that for every λ > 0, deviating to action 1 from sa gives B(sa) − Vπ C (sa) = 3λ/4, proving the policy is not a perfect Markov ε-CCE.

Proof of Failure of Equilibrium Collapse

The example demonstrates that the correlation at sa is essential, as the product policy with the same one-player marginals is not even a reward-player best response at sa.

Proof of Lemma 3. p. 1

Where the paper says it

3 Non-Perfect Markov CCE is PPAD-hard . 23 6 Example: Pure-Circuit solution with no equilibrium collapse 25 7 Conclusion 29 A Extended Related Work 34 B Proof of Lemma 2.

1 (Controller value interval)

Lemma 3.1 provides a bound on the controller's value: (1 − γ)(1 − λ)pu ≤ Vπ C (su) ≤ (1 − γ)/(1 - λ)pu + λ + γ.

Proof of Lemma 4.3

Lemma 4.3 proves that if ε < γ∆/16, then every output state sv satisfies condition (F). p. 5

Where the paper says it

Such a circuit is a collection of variables connected by gates, where each gate imposes a local constraint on the values of its input and output variables. The goal is to find an assignment of values to all variables that approximately satisfies every gate.

p. 5
Where the paper says it

Such a circuit is a collection of variables connected by gates, where each gate imposes a local constraint on the values of its input and output variables. The goal is to find an assignment of values to all variables that approximately satisfies every gate.

Proof of Theorem 5.5 (Unconditional)

The proof for the unconditional result involves setting λ:= cforce/8O and showing that if ε < κ/S2, then Lemma 5.2 and Lemma 5. p. 1

Where the paper says it

2 Markov Coarse Correlated Equilibria . 3 Performance-difference lemma for one-player deviations .

p. 1
Where the paper says it

2 Markov Coarse Correlated Equilibria . 3 Performance-difference lemma for one-player deviations .

3 imply Ecopy = ∅ and Eforce = ∅, thus satisfying all gate conditions. p. 5
Where the paper says it

, action 1) provides a canonical signal, and the bipartite structure of the circuit can be used to glue gadgets while avoiding conflicts between the rewards assigned to the same player. Moreover, at a turn-based game the reward and transition depend only on the active player’s action, thus satisfying equilibrium collapse where every CCE marginalizes to a NE.

p. 5
Where the paper says it

, action 1) provides a canonical signal, and the bipartite structure of the circuit can be used to glue gadgets while avoiding conflicts between the rewards assigned to the same player. Moreover, at a turn-based game the reward and transition depend only on the active player’s action, thus satisfying equilibrium collapse where every CCE marginalizes to a NE.

Proof of Theorem 5.6 (Unconditional)

The proof for the unconditional non-perfect Markov ε-CCE hardness involves setting λ:= cforce/8O and showing that if ε < κ S2, then Lemma 5.2 and Lemma 5.3 imply Ecopy = ∅ and Eforce = ∅, thus satisfying all gate conditions.

Proof of Remark 5. p. 3

Where the paper says it

Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards. 2 1Please see also Remark 5.

p. 3
Where the paper says it

Our result shows that neither the switching-controller structure nor the equilibrium collapse property are what actually drives the hardness of stationary Markov CCE; it is enough that one player solely controls the transitions while both players affect rewards. 2 1Please see also Remark 5.

7

Remark 5.7 states that the results both for the perfect and non-perfect notion continue to hold for any γ ∈ [1/16, 1) due to adding an action-independent lazy self-loop in the transition model. p. 6

Where the paper says it

For the perfect Markov CCE hardness result, we set λ = 0, so the controller’s immediate reward at variable states is independent of its own action. Moreover, because the perfect CCE constraints hold from every initial state, each gadget condition can be proved state by state: a violation at a single variable state directly yields a profitable deviation from that state.

Proof of Remark 5.7 (Failure of equilibrium collapse)

The example demonstrates that the correlation at sa is essential, as the product policy with the same one-player marginals is not even a reward-player best response at sa.

Proof of Lemma 5.3 (Controller forcing for perfect Markov CCE)

The proof for Lemma 5.3 shows that every forcing-failure state satisfies Advπ,πF C(sv) ≥ cforce − (1 − γ)λ for every sv ∈ Eforce. p. 5

Where the paper says it

Such a circuit is a collection of variables connected by gates, where each gate imposes a local constraint on the values of its input and output variables. The goal is to find an assignment of values to all variables that approximately satisfies every gate.

Proof of Lemma 4.1 (Copy gadget for perfect Markov CCE)

Lemma 4.1 proves that if ε < 7/128, then for every variable state su, condition (C) holds. p. 6

Where the paper says it

For the perfect Markov CCE hardness result, we set λ = 0, so the controller’s immediate reward at variable states is independent of its own action. Moreover, because the perfect CCE constraints hold from every initial state, each gadget condition can be proved state by state: a violation at a single variable state directly yields a profitable deviation from that state.

Proof of Lemma 4.2 (Best local advantage under perfect Markov CCE)

Lemma 4.2 proves that if π is a perfect Markov ε-CCE of G0(I), then for every variable state s, ρπ C,s ≤ ε. p. 6

Where the paper says it

For the perfect Markov CCE hardness result, we set λ = 0, so the controller’s immediate reward at variable states is independent of its own action. Moreover, because the perfect CCE constraints hold from every initial state, each gadget condition can be proved state by state: a violation at a single variable state directly yields a profitable deviation from that state.

Proof of Theorem 4.4 (Perfect Markov CCE hardness)

The proof for Theorem 4.4 involves setting ε0:= γ∆/16 = 1/65536 and showing that if a polynomial-time algorithm outputs a perfect Markov ε-CCE π for some ε < ε0, then the decoded assignment solves I.

Proof of Theorem 5.5 (Non-perfect Markov CCE hardness under PCP-for-PPAD)

The proof for Theorem 5.5 shows that if a polynomial-time algorithm outputs a non-perfect Markov ε-CCE π for some ε < ε', then the assignment decoded from π satisfies at least a (1 − δ) fraction of the gates of I, solving δ-Pure-Circuit, which is PPAD-hard under Conjecture 1.

Proof of Theorem 5.6 (Unconditional non-perfect Markov CCE hardness)

The proof for Theorem 5.6 establishes an unconditional inverse-polynomial-accuracy result where there exists a universal constant κ > 0 such that computing a non-perfect Markov ε-CCE of a discounted two-player single-controller Markov game is PPAD-hard whenever ε < κ S2.

Proof of Proposition 5.4 (Non-perfect Markov CCE hardness under PCP)

Proposition 5.4 shows that if no output state of a gate lies in Bad, then the decoded assignment satisfies that gate, and if µ(Bad) < δ/2 then the decoded assignment satisfies at least a (1 − δ) fraction of the gates.

Proof of Lemma 5.2 (Average copy lemma)

Lemma 5.2 proves the Average copy lemma: if ε < (1 − γ)ηccopy / (1 + λ−1), then µ(Ecopy) < η.

Proof of Lemma 5.3 (Average controller-forcing)

Lemma 5.3 proves the Average forcing lemma: if ε < ηcforce/4, then µ(Eforce) < η.

The proof for Proposition 5.4 shows that if no output state of a gate lies in Bad, then neither the copy implication nor the controllerforcing implication fails at any output of that gate.

Proof of Lemma 5.1 (Decorrelation identity)

Lemma 5.1 proves the Decorrelation identity: ∆R + λ−1∆dec C = X u∈V d πµ(su) B(qu) − Mprod u.

Proof of Lemma 4.3 (Controller forcing for perfect Markov CCE)

Lemma 4.3 proves that if ε < γ∆/16, then every output state sv satisfies condition (F).

Proposition 5.4 shows that if no output state of a gate lies in Bad, then neither the copy implication nor the controllerforcing implication fails at any output of that gate.

**Proof of Lemma 4.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Hardness for computing stationary Markov CCE in single-controller stochastic games can be established by constructing single-controller gadgets whose local incentive constraints force a solution of a Pure-Circuit instance even under strongly correlated stationary policies. This allows the system to prove that the PPAD-hardness of computing CCE is robust to the single-controller restriction, moving beyond reliance on equilibrium collapse phenomena.

  2. The AI system can be designed with an oracle that efficiently solves Pure-Circuit instances, enabling it to verify if a given stationary policy satisfies complex logical constraints derived from circuit assignments. This allows for the reduction of computational problems like gap Pure-Circuit to the CCE search problem in single-controller games.

  3. The system can utilize the performance-difference lemma to analyze deviations by relating the resulting value difference directly to an average over a normalized discounted state-visitation distribution, enabling constant accuracy hardness proofs under PCP for PPAD. This capability allows the system to prove that finding an approximate stationary Markov CCE is PPAD-complete even when equilibrium collapse does not occur.

  4. The AI can implement non-perfect Markov CCE checking by leveraging the average copy lemma and average controller-forcing lemma to bound the mass of states where local incentive constraints fail, thereby proving that if the approximation error is small enough, a solution to the Pure-Circuit instance must exist. This provides a method for verifying approximate solutions without requiring perfect equilibrium conditions at every state.

  5. The system can be engineered to handle varying discount factors and reward distributions by parameterizing the construction with constants like lambda, allowing it to address both perfect and non-perfect notions of CCE hardness unconditionally across a range of fixed parameters. This ensures the complexity results hold for practical settings where exact values are not always available.

Abstract

We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subclass of stochastic games in which all players may affect rewards, but only one player controls the state transitions. Prior work [DGZ23, JMS23, HN25] established PPAD-hardness for computing stationary Markov CCE in two-player general-sum stochastic games via turn-based constructions in which each state is controlled by a single player, with control alternating across states. This structure forces every Markov CCE to collapse to a Nash equilibrium (NE), so hardness for NE transfers immediately to CCE. It remained open whether hardness persists when a single player controls all transitions--a setting where no such collapse occurs. We resolve this question: computing an approximate stationary Markov CCE in two-player single-controller stochastic games is PPAD-complete, even with a fixed discount factor and binary actions. For the perfect notion (equilibrium constraints at every state) this holds unconditionally at constant accuracy; for the non-perfect notion, we prove constant-accuracy hardness under the PCP-for-PPAD hypothesis [BPR16, DFHM26] and inverse-polynomial-accuracy hardness unconditionally. To the best of our knowledge, our result is the first to show hardness for computing CCE without relying on equilibrium collapse phenomena or other routes through Nash-like structure [FGK23, AKSZ24, PR24]. Instead, we construct single-controller gadgets whose local incentive constraints force a solution of a Pure-Circuit instance even under strongly correlated stationary policies.

Sources

Related papers