Bounded-Memory Strategies in Partial-Information Games

Bose, Sougata, Ibsen-Jensen, Rasmus ORCID: 0000-0003-4783-0389 and Totzke, Patrick ORCID: 0000-0001-5274-8190 (2024) Bounded-Memory Strategies in Partial-Information Games In: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science.

Access the full-text of this item by clicking on the Open Access link.

PDF BIT2024.pdf - Author Accepted Manuscript Download (825kB) | Preview

Abstract

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 FNP^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.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Finite-memory strategies, Equilibria, Approximation, Imperfect information games
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	20 Sep 2024 10:30
Last Modified:	23 May 2026 08:56
DOI:	10.1145/3661814.3662096
Open Access URL:	https://dl.acm.org/doi/10.1145/3661814.3662096
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3184639
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.