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 epsilon-optimally, or form epsilon-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, epsilon >= 0 and bound b, there exists an epsilon-Nash equilibrium in which all strategies use at most b memory modes. For given epsilon > 0, finding an epsilon-Nash equilibrium with respect to b-bounded strategies can be done in FNPNP. 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 FNPNP. 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 FNPNP.