Friedmann, Oliver (2011): Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics 

PDF
Friedmann_Oliver.pdf 1954Kb 
Abstract
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 turnbased 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 dualsimplex 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 2player parity games on which the respective policy iteration algorithm performs an exponential number of iterations. We then transform these 2player games into 1player 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 turnbased stochastic games. Particularly, we prove exponential lower bounds for the deterministic switch all and switch best improvement rules for solving games, for which no nontrivial 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 nontrivial 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 multiswitching randomized rule. Finally, we prove an exponential lower bound for the most natural and famous historybased 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.
Item Type:  Thesis (Dissertation, LMU Munich) 

Subjects:  000 Computers, Information and General Reference > 004 Data processing computer science 000 Computers, Information and General Reference 
Faculties:  Faculty of Mathematics, Computer Science and Statistics 
Language:  English 
Date Accepted:  15. July 2011 
1. Referee:  Lange, Martin 
Persistent Identifier (URN):  urn:nbn:de:bvb:19132940 
MD5 Checksum of the PDFfile:  96edb437b03cdc9e78c78b459debcca2 
Signature of the printed copy:  0001/UMC 19633 
ID Code:  13294 
Deposited On:  23. Aug 2011 08:48 
Last Modified:  16. Oct 2012 08:52 