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

  Browse A-Z

Log in

Cambridge users (raven)details Other usersdetails No account?details

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

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.

Other lists

Visual Rhetoric and modern South Asian history (2015-16) Critical Theory and Practice Seminar CU Truth Movement Society

Other talks

An approach to the four colour theorem via Donaldson- Floer theory Disease Migration Intrinsically Motivating Teachers;STIR's use of Data Driven Insight to Iterate, Pivot and (where necessary) Fail Fast Modeling and understanding of Quaternary climate cycles Chemical convection and stratification at the top of the Earth's outer core Practical Steps to Addressing Unconscious / Implicit Bias An SU(3) variant of instanton homology for webs Cambridge - Corporate Finance Theory Symposium September 2017 - Day 1 The role of myosin VI in connexin 43 gap junction accretion 100 Problems around Scalar Curvature 'The Japanese Mingei Movement and the art of Katazome' Develop a tool for inferring symptoms from prescriptions histories for cancer patients
 

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