A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games

Authors: Henrik Bjorklund, Sven Sandberg and Sergei Vorobyov

ABSTRACT

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem based on iteratively improving the longest shortest distances to a sink in a possibly cyclic graph.

We identify a new controlled'' version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. Under reasonable assumptions the problem belongs to the complexity class \textsc{NP}$\cap$\textsc{coNP}. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player Max selects a strategy (one edge in each controlled vertex) and player Min responds by evaluating shortest paths to the sink in the remaining graph. Then Max locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths (under the current evaluation). We show that this is a monotonic strategy improvement, and any locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity $\min(poly\cdot W,\;2^{O(\sqrt{n\log n})}),$ which is simultaneously pseudopolynomial ($W$ is the maximal absolute edge weight) and subexponential in the number of vertices $n$. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-05.ps.gz