The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller
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 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
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.Where the paper says it
Where the paper says it
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 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). 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.Where the paper says it
Where the paper says it
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 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 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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
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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 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
(µ) ≤ ε.Where the paper says it
Proof of Lemma 2. p. 1 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.Where the paper says it
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 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 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 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 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 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 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Lemma 4.2 states that if π is a perfect Markov ε-CCE of G0(I), then for every variable state s, ρπ C,s ≤ ε. p. 6 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.Where the paper says it
Proof of Lemma 5. p. 1 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 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 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 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 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 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 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 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Lemma 5.3 shows that if ε < ηcforce/4, then µ(Eforce) < η. p. 3 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.Where the paper says it
Proof of Theorem 4. p. 1 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 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Proof of Theorem 5. p. 1 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 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 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 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 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 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Proof of Proposition 5. p. 6 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Proof of Proposition 3. p. 6 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
Proof of Proposition 6. p. 6 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. 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.Where the paper says it
Where the paper says it
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 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).Where the paper says it
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 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.Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Proof of Lemma 5.2
Lemma 5.2 proves the Average copy lemma: if ε < (1 − γ)ηccopy / (1 + λ−1), then µ(Ecopy) < η. p. 1 17
5 Non-perfect Markov CCE hardness 17
5. 1 Average copy . 17
5 Non-perfect Markov CCE hardness 17
5. 1 Average copy .Where the paper says it
Where the paper says it
Lemma 5.3 proves the Average forcing lemma: if ε < ηcforce/4, then µ(Eforce) < η. p. 1 1 Average copy . 2 Average controller-forcing . 1 Average copy . 2 Average controller-forcing .Where the paper says it
Where the paper says it
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 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).Where the paper says it
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 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 2 Markov Coarse Correlated Equilibria . 3 Performance-difference lemma for one-player deviations . 2 Markov Coarse Correlated Equilibria . 3 Performance-difference lemma for one-player deviations . , 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. , 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments