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 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

← Home