2024/05/15 by Sougata Bose, Bose, Sougata, Rasmus Ibsen-Jensen +3 · 1 citation
Computer Science · Decision Sciences · #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2405.09406
openalex publication_date 2024/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the computational complexity of solving stochastic games with mean-payoff objectives. Instead of identifying special classes in which simple strategies are sufficient to play ε-optimally, or form ε-Nash equilibria, we consider general partial-information multiplayer games and ask what can be achieved with (and against) finite-memory strategies up to a given bound on the memory. We show NP-hardness for approximating zero-sum values, already with respect to memoryless strategies and for 1-player reachability games. On the other hand, we provide upper bounds for solving games of any fixed number of players k. We show that one can decide in polynomial space if, for a given k-player game, ε≥ 0 and bound b, there exists an ε-Nash equilibrium in which all strategies use at most b memory modes. For given ε>0, finding an ε-Nash equilibrium with respect to b-bounded strategies can be done in FN[NP]. Similarly for 2-player zero-sum games, finding a b-bounded strategy that, against all b-bounded opponent strategies, guarantees an outcome within ε of a given value, can be done in FNP[NP]. Our constructions apply to parity objectives with minimal simplifications. Our results improve the status quo in several well-known special cases of games. In particular, for 2-player zero-sum concurrent mean-payoff games, one can approximate ordinary zero-sum values (without restricting admissible strategies) in FNP[NP].