Bounded-Memory Strategies in Partial-Information Games

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 . We show that one can decide in polynomial space if, for a given -player game, ≥ 0 and bound , there exists an -Nash equilibrium in which all strategies use at most memory modes.

For given > 0, finding an -Nash equilibrium with respect to -bounded strategies can be done in FNP NP . Similarly for 2-player zero-sum games, finding a -bounded strategy that, against allbounded 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 .

• Theory of computation → Algorithmic game theory; Exact and approximate computation of equilibria.