Download PDFOpen PDF in browser

An Optimal Value Iteration Algorithm for Parity Games

EasyChair Preprint no. 21

17 pagesDate: March 23, 2018

Abstract

The quest for a polynomial time algorithm for solving parity games gained momentum in 2017 when two different quasipolynomial time algorithms were constructed. In this paper, we further analyse the second algorithm due to Jurdzinski and Lazic and called the succinct progress measure algorithm. It was presented as an improvement over a previous algorithm called the small progress measure algorithm, using a better data structure.

The starting point of this paper is the observation that the underlying data structure for both progress measure algorithms are (subgraph-)universal trees. We show that in fact any universal tree gives rise to a value iteration algorithm à la succinct progress measure, and the complexity of the algorithm is proportional to the size of the chosen universal tree. We extract from both algorithms the construction of a universal tree, respectively of exponential size (for small progress measure) and of quasipolynomial size (for succinct progress measure).

The technical result of this paper is to show that the latter construction is asymptotically tight: universal trees have at least quasipolynomial size. This suggests that the succinct progress measure algorithm of Jurdzinski and Lazic is in this framework optimal, and that constructing a polynomial time algorithm for parity games is hiding someplace else.

Keyphrases: game theory, Games algorithms, parity games, Universal trees, verification

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@Booklet{EasyChair:21,
  author = {Nathanaël Fijalkow},
  title = {An Optimal Value Iteration Algorithm for Parity Games},
  howpublished = {EasyChair Preprint no. 21},
  doi = {10.29007/k2nm},
  year = {EasyChair, 2018}}
Download PDFOpen PDF in browser