arXiv preprint ·
Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Mean-Payoff Games (MPGs) form an interesting family of deterministic, infinite-duration, zero-sum, turn-based games played by two players on a finite weighted directed graph. The goal of the players is to minimize, respectively maximize, the $\textit{limiting average}$ of the costs of the edges on an infinite path constructed by the two players. The complexity of solving MPGs is a long-standing open question. The decision problem associated with these games is known to be in $\text{NP}\cap \text{co-NP}$, and even $\text{UP}\cap \text{co-UP}$, yet the problem is not known to be in $\text{P}$. This is one of the simplest combinatorial problems with such a status. A full solution of an MPG gives the $\textit{value}$ of each vertex of the game, along with a pair of $\textit{optimal strategies}$ for the two players. (Each player has a succinct $\textit{positional}$ optimal strategy.) The problem of finding optimal strategies for the players given the values of all vertices is known as the $\textit{strategy recovery}$ problem. We describe a simple reduction from the problem of solving MPGs to the strategy recovery problem for MPGs. This shows that the strategy recovery problem for MPGs is essentially as hard as solving MPGs from scratch, i.e., without knowing the values. The reduction uses simple $\textit{game transformations}$ and simple $\textit{self-reducibility}$ and $\textit{peeling}$ arguments. This answers a question of Andersson and Miltersen. Mamino obtained a similar result for $\textit{stochastic}$ games with a limiting average objective, but his technique does not extend to deterministic games such as MPGs. We go one step further and show that finding an optimal strategy for one of the players of an MPG remains hard even if an optimal strategy of the second player, and hence all the values, are known.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Game of Phones: Harnessing Game Theory and LLMs in 'Bot Wars' to Counteract Phone Scams
How Far Can an Agent Push? Trust-Safety Margins in Live Language-Based Economic Games
Fundamental Impossibility Results in AI Safety: Trading Off between Desiderata
Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
Splitting Planar Necklaces with Few Straight Cuts
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.