## Parity games: the quasipolynomial era ## Universal trees

Question: what is the smallest tree containing all trees of height $2$ with $5$ leaves? $\qquad$ Definition: A tree is $(n,h)$-universal if it contains all trees of height $h$ with $n$ leaves
Theorem:
• There exists a $(n,h)$-universal tree of size $\binom{h + \log(n)}{h}$
• This upper bound is asymptotically tight

Remark: the number $\binom{h + \log(n)}{h}$ is
• $O(n^{\log(h)})$ in general
• $n^{O(1)}$ for $h = O(\log(n))$

## Upper bounds

We construct a $(n,h)$-universal tree. Inductively
• $T_\text{middle}$ a $(n,h-1)$-universal tree
• $T_\text{left}$ a $(\lfloor n/2 \rfloor,h)$-universal tree
• $T_\text{right}$ a $(n - 1 - \lfloor n/2 \rfloor,h)$-universal tree Fact: there exists a balanced node

## Lower bounds

$$g(n,h) = \sum_{d = 1}^n g(\lfloor n / d \rfloor,h-1)$$ Let $T$ a $(n,h)$-universal tree and $\delta \in [1,n]$.
Claim: the number of nodes at depth $h-1$ of degree $\ge \delta$ is at least $g(\lfloor n / \delta \rfloor,h-1)$. Claim: $T_\delta$ is $(\lfloor n / \delta \rfloor,h-1)$-universal

## Parity games Parity: the maximal priority appearing infinitely often is even

### Solving parity games

INPUT: A parity game and initial vertex $v_0$
QUESTION: Does Eve have a winning strategy from $v_0$?

Parameters: $n$ (number of vertices), $m$ (number of edges) and $d$ (number of priorities)

Best algorithm $$O \left( m \cdot \binom{d/2 + \log(n)}{d/2} \right) = O(n^{\log(d)})$$

### Why might you care?

Parity games play a crucial role in:
• LTL synthesis
• automata and logic over infinite trees (emptiness games)
• modal mu-calculus (model-checking games)

But also complexity: in $\textrm{NP} \cap \textrm{coNP}$, not known to be in $\textrm{P}$!

Also: included in mean payoff, discounted payoff, and simple stochastic games
Positional strategy $$\sigma : V \to E$$ Theorem: If Eve has a winning strategy in a parity game, she also has a positional winning strategy. The same holds for Adam.  Definition: A graph satisfies parity if all paths in the graph satisfy parity
Remark: If $\sigma$ is a positional winning strategy, then $G_{\sigma}$ satisfies parity

## Value iteration

Büchi: parity with priorities $1$ and $2$ Lemma: A graph satisfies Büchi if and only if there exists a progress measure $\mu : V \to \mathbb{N}$: $$(v,1,v') \in E \implies \mu(v) < \mu(v')$$
A tree is the graphical representation of nested orders $\triangleleft_p$, for $p \in [1,d]$. Example:  $\qquad$ Lemma: A graph satisfies parity if and only if there exists a tree $T$ and $\mu : V \to T$: $$(v,p,v') \in E \implies \mu(v) \triangleleft_p \mu(v')$$
$G$ parity game. A progress measure is $\mu : V \to T \cup \{ \bot \}$: $$\begin{array}{c} \forall v \in V_{\text{Eve}},\ \exists (v,p,v') \in E \wedge \mu(v) \triangleleft_p \mu(v') \\ \forall v \in V_{\text{Adam}},\ \forall (v,p,v') \in E,\ \mu(v) \triangleleft_p \mu(v') \end{array}$$
Theorem: There exists a tree $T$ and a progress measure $\mu : V \to T \cup \{ \bot \}$ such that $\mu(v) \neq \bot$ if and only if Eve wins from $v$

Corollary: Let $\mathcal{T}$ a $(n,d/2)$-universal tree. There exists a progress measure $\mu : V \to \mathcal{T} \cup \{ \bot \}$ such that $\mu(v) \neq \bot$ if and only if Eve wins from $v$
Key idea: The value iteration algorithm constructs the largest progress measure ## Beyond parity

Definition: A graph satisfies W if all paths in the graph satisfy $W$
Definition: A (graph) homomorphism is $\phi : V \to V'$ st $$(v,w,v') \in E \Longrightarrow (\phi(v),w,\phi(v')) \in E$$
Definition: A graph $U$ is $(n,W)$-universal if
• it satisfies $W$
• all graphs of size $n$ satisfying $W$ can be homomorphically mapped into $U$

## Value iteration algorithm

Let $G$ game with objective $W$ and $U$ a $(n,W)$-universal graph

We construct a value iteration algorithm of time complexity $m |U|$ and space complexity $n \log |U|$.

## Happening now

with universal graphs

• New algorithms for mean payoff games (F., Gawrychowski, Ohlmann)
• Logical implications (Dawar, F., Lehtinen)
• Combining parity with other objectives (Anand, F., Leroux)
• Combination of mean payoff objectives