July 15, 2011

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

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.

...more

View all episodes

By Ludwig-Maximilians-Universität München

11 ratings