University of Twente Student Theses


Instances with exponential running time for strategy iteration

Maat, M.T. (2022) Instances with exponential running time for strategy iteration.

[img] PDF
Abstract:A parity game is a game played by two players on the nodes of a directed graph. Solving a parity game consists of finding out who can win and what the winning strategy is. Solving parity games is linked to many other mathematical problems, and so far there is no polynomial-time algorithm for this problem. A currently often used algorithm is strategy iteration, which iteratively improves a strategy, where decisions are taken by a so-called improvement rule. It has been shown previously that in some cases improvement rules for strategy iteration can be linked to pivot rules for the simplex algorithm. This reduction is via mean payoff games and Markov decision processes and only works for specific cases. In this thesis, an alternative relation between strategy iteration and the simplex algorithm is presented. This relation works for a broader class of parity games. Moreover, a framework for constructing examples with exponential running time for strategy iteration is presented and illustrated with some examples. Finally, a family of graphs with exponential running time for the symmetric strategy iteration algorithm is presented. For this algorithm no class of graphs was known before with superpolynomial running time.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page