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.
|
PDF
2MB |
| 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: | https://purl.utwente.nl/essays/92502 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page