An Optimal Value Iteration Algorithm for Parity Games

EasyChair Preprint 21

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: Games algorithms, Universal trees, game theory, parity games, verification

@booklet{EasyChair:21,
  author    = {Nathanaël Fijalkow},
  title     = {An Optimal Value Iteration Algorithm for Parity Games},
  doi       = {10.29007/k2nm},
  howpublished = {EasyChair Preprint 21},
  year      = {EasyChair, 2018}}