University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs

Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Felix Fischer.

Policy iteration is one of the most important algorithmic schemes for solving infinitary payoff games such as parity games, stochastic games and Markov decision processes, and many more. 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 (two-player) game classes. Simplex algorithms for solving linear programs are closely related to policy iteration algorithms. Like policy iteration, the simplex algorithm is parameterized by a so-called pivoting rule that describes how to proceed from one basic feasible solution in the linear program to the next. Also, 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 describe our recent constructions for parity games that give rise to exponential lower bounds for several improvement rules, and how to extend the lower bound to more expressive game classes like stochastic games. We show that our construction for parity games can be translated to Markov decision processes, transferring our lower bound to their domain, and finally show how the lower bounds for the MDPs can be transferred to the linear programming domain, solving problems that have been open for several decades.

This talk is part of the Optimization and Incentives Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity