Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs

Parity games form an intriguing family of infinitary payoff games
whose solution is equivalent to the solution of important problems
in automatic verification and automata theory. They also form a
very natural subclass of mean and discounted payoff games, which in
turn are very natural subclasses of turn-based stochastic payoff
games. From a theoretical point of view, solving these games is one
of the few problems that belong to the complexity class NP
intersect coNP, and even more interestingly, solving has been shown
to belong to UP intersect coUP, and also to PLS. It is a major open
problem whether these game families can be solved in deterministic
polynomial time. Policy iteration is one of the most important
algorithmic schemes for solving infinitary payoff games. It is
parameterized by an improvement rule that determines how to proceed
in the iteration from one policy to the next. It is a major open
problem whether there is an improvement rule that results in a
polynomial time algorithm for solving one of the considered game
classes. Linear programming is one of the most important
computational problems studied by researchers in computer science,
mathematics and operations research. Perhaps more articles and
books are written about linear programming than on all other
computational problems combined. The simplex and the dual-simplex
algorithms are among the most widely used algorithms for solving
linear programs in practice. Simplex algorithms for solving linear
programs are closely related to policy iteration algorithms. Like
policy iteration, the simplex algorithm is parameterized by a
pivoting rule that describes how to proceed from one basic feasible
solution in the linear program to the next. It is a major open
problem whether there is a pivoting rule that results in a
(strongly) polynomial time algorithm for solving linear programs.
We contribute to both the policy iteration and the simplex
algorithm by proving exponential lower bounds for several
improvement resp. pivoting rules. For every considered improvement
rule, we start by building 2-player parity games on which the
respective policy iteration algorithm performs an exponential
number of iterations. We then transform these 2-player games into
1-player Markov decision processes ii which correspond almost
immediately to concrete linear programs on which the respective
simplex algorithm requires the same number of iterations.
Additionally, we show how to transfer the lower bound results to
more expressive game classes like payoff and turn-based stochastic
games. Particularly, we prove exponential lower bounds for the
deterministic switch all and switch best improvement rules for
solving games, for which no non-trivial lower bounds have been
known since the introduction of Howard’s policy iteration algorithm
in 1960. Moreover, we prove exponential lower bounds for the two
most natural and most studied randomized pivoting rules suggested
to date, namely the random facet and random edge rules for solving
games and linear programs, for which no non-trivial lower bounds
have been known for several decades. Furthermore, we prove an
exponential lower bound for the switch half randomized improvement
rule for solving games, which is considered to be the most
important multi-switching randomized rule. Finally, we prove an
exponential lower bound for the most natural and famous
history-based pivoting rule due to Zadeh for solving games and
linear programs, which has been an open problem for thirty years.
Last but not least, we prove exponential lower bounds for two other
classes of algorithms that solve parity games, namely for the model
checking algorithm due to Stevens and Stirling and for the
recursive algorithm by Zielonka.