A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games

摘要

We suggest the first strongly subexponential and purely combinatorial algorithm for mean payoff games. It is based on solving a new "controlled" version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to maximize the shortest distances to the unique sink. Mean payoff games easily reduce to this problem. To compute the 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, making attractive switches that seem to increase shortest paths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. A careful choice of the next iterate results in a randomized algorithm of complexity min(poly(n) • W, 2~(O(n log n)~(1/2)), which is simultaneously pseudopolyno-mial (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).