The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller
summary
The gist
We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97].
In short
The study investigates how hard it is to compute stationary Markov coarse correlated equilibria (CCE) in discounted games where a single player controls all transitions. The authors prove that computing these equilibria is PPAD-complete, showing that this computational difficulty persists even with the single-controller restriction, regardless of whether the equilibrium notion is perfect or non-perfect.
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 used across episodes
This episode discusses
- The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller · Paper Radio
- Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games
The paper
The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller · Read on arXiv
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
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.
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game