Bose, Sougata 
ORCID: 0000-0003-3662-3915, 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: LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science.
|
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<sup>NP</sup>. 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<sup>NP</sup>. 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<sup>NP</sup>.
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | 3801 Applied Economics, 3803 Economic Theory, 38 Economics, 4901 Applied Mathematics, 49 Mathematical Sciences |
| Divisions: | Faculty of Science and Engineering Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 20 Sep 2024 10:30 |
| Last Modified: | 05 Jun 2025 17:07 |
| DOI: | 10.1145/3661814.3662096 |
| Open Access URL: | https://dl.acm.org/doi/10.1145/3661814.3662096 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3184639 |
Altmetric
Altmetric