The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller
2026-07-12 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how hard it is to find certain stable strategies called stationary Markov coarse correlated equilibria (CCE) in a specific type of game where one player controls how the game changes over time. Previous work showed this problem is hard in games where control switches between players, but it was unclear if it remains hard when just one player controls everything. They prove it is still very hard (PPAD-complete) to find these strategies even in this simpler setup. Their work is the first to show this difficulty without relying on simpler connections to another equilibrium concept called Nash equilibrium.
stationary Markov CCEsingle-controller stochastic gamesPPAD-completenessdiscounted gamesNash equilibriumcoarse correlated equilibriumgame theorycomplexity theory
Authors
Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos
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.