Strategy recovery for mean-payoff games is as hard as solving them
Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch
Computer Science and Game TheoryData Structures and Algorithms
Summary
Mean-Payoff Games are mathematical challenges where two players pick paths through a graph trying to maximize or minimize the long-term average cost of edges they travel. Usually, solving these games means finding both the value of each position and the best strategy for each player. The authors show that even if you already know the value of every position, figuring out the best strategy for one or both players is just as hard as solving the whole game from scratch. This finding closes a gap in the understanding of these games' complexity and answers a previously open question.
What this means in practice
- •For game algorithm designers: Avoid relying on known vertex values when developing algorithms since finding optimal strategies given values is as complex as solving the entire game.
- •For automated verification engineers: Recognize that extracting explicit optimal strategies remains computationally difficult, even when system state values are already computed.
A theory result. No direct application yet.
Authors
Dani Dorfman, Uri Zwick
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.