Improved Complexity Analysisof Quasi-Polynomial Algorithms
Solving Parity Games

Paweł Parys, Aleksander Wiącek
University of Warsaw

CiE 2023, Batumi

Parity games
1

3

2

Priorities on vertices●
Player owning the current vertex choses the next vertex●
Player  wins if the biggest priority seen infinitely often is even.
●

Parity games
1

3

2

Priorities on vertices●
Player owning the current vertex choses the next vertex●
Player  wins if the biggest priority seen infinitely often is even.
●

Algorithmic problem:

Given a game graph, decide which player has a winning strategy.

Long standing open problem:
Can we solve parity games in PTIME?

Parity games

Recent results
Long standing open problem:
Decide in PTIME which player has a winning strategy.
Recent result:This can be decided in quasi-polynomial time, i.e. nO(log n)
A few algorithms achieving this:●play summaries - Calude, Jain, Khoussainov, Li, Stephan 2017●
antagonistic play summaries Fearnley, Jain, Schewe, Stephan, Wojtczak 2017●
succinct progress measures - Jurdziński, Lazić 2018●
register games - Lehtinen 2018
●recursive à la Zielonka - Parys 2019●improved recursive à la Zielonka Lehtinen, Schewe, Wojtczak 2019●
symmetric progress measures Jurdziński, Morvan, Ohlmann, Thejaswini 2020●
strategy iteration - Koh, Loho 2021

This paper:
Small improvement in the complexity analysis of the algorithms
Previous: O(mdn log2e+log2(d/log2n) )New:

1 log2e+log2(d/log2n)O(m–n)
dwheren – number of nodesm – number of edges
d – number of priorities(we skip polylogarithmic factors)

Universal trees
A tree U (of height h) is (n,h)-universal if every tree of height h with n leaves
embeds in U.

(2,2)-universal

Universal trees
A tree U (of height h) is (n,h)-universal if every tree of height h with n leaves
embeds in U.

(2,2)-universal

Examples:Cn,h =
Cn,h-1 Cn,h-1...

Pn,h =
Cn,h-1nP⌊n/2⌋,h-1⌊n/2⌋

Sn,h =
S⌊n/2⌋,hP⌊n/2⌋,h-1...

Sn,h-1S⌊n/2⌋,hPn,h-1

P⌊n/2⌋,h-1...

P⌊n/2⌋,h-1⌊n/2⌋

Universal trees
A tree U (of height h) is (n,h)-universal if every tree of height h with n leaves
embeds in U.

(2,2)-universalExamples:Cn,h =Cn,h-1 Cn,h-1...

Pn,h =
Cn,h-1nP⌊n/2⌋,h-1...

Pn,h-1P⌊n/2⌋,h-1⌊n/2⌋

P⌊n/2⌋,h-1...

P⌊n/2⌋,h-1⌊n/2⌋

size nhsize nlg n + lg(h/lg n)+O(1)size nlg(h/lg n)+O(1)Sn,h =
S⌊n/2⌋,hSn,h-1

S⌊n/2⌋,hUniversal trees
A tree U (of height h) is (n,h)-universal if every tree of height h with n leaves
embeds in U.
Sn,h =
S⌊n/2⌋,hSn,h-1

S⌊n/2⌋,hWhy is it (n,h)-universal?

Universal trees
A tree U (of height h) is (n,h)-universal if every tree of height h with n leaves
embeds in U.
Sn,h =S⌊n/2⌋,hSn,h-1S⌊(n-1)/2⌋,h

Why is it (n,h)-universal?
Take any tree T of height h with n leaves.

≤⌊n/2⌋ leaves≤⌊(n-1)/2⌋ leaves

Subtree with the middle leaf goes to Sn,h-1.
Left and right part have at most ⌊n/2⌋ or ⌊(n-1)/2⌋ leaves.

Why universal trees?
1) It is enough to consider positional strategies: given a node, player chooses
some fixed successor, no matter what was the history of the play.
If a player can win, then he can win positionally.
Consequence: the problem is in NP∩coNP.
In fact it is also in UP∩coUP (Jurdziński 1998)
The search variant is in PLS, PPAD, CLS (Daskalakis, Papadimitriou 2011)

1

3

2

Why universal trees?
1) It is enough to consider positional strategies: given a node, player choses
some fixed successor, no matter what was the history of the play.
If a player can win, then he can win positionally.
2) After fixing a positional strategy, a game graph defines a treeof height d/2 with n leaves (game node = tree leaf)

24221311Why universal trees?
1) It is enough to consider positional strategies: given a node, player choses
some fixed successor, no matter what was the history of the play.
If a player can win, then he can win positionally.
2) After fixing a positional strategy, a game graph defines a treeof height d/2 with n leaves (game node = tree leaf)

242213113) Idea: checking a universal tree = checking all positional strategies

Why universal trees?
All known quasipolynomial algorithms solving parity games use (explicitly orimplicitly) universal trees.
Is this necessary?
PapersCzerwiński, Daviaud, Fijalkow, Jurdziński, Lazić, Parys 2019
Arnold, Niwiński, Parys 2021
define two general approaches such that●all known quasipolynomial algorithms follow these approaches●
every algorithm following this approach has to use a universal tree

Why universal trees?
All known quasipolynomial algorithms solving parity games use (explicitly orimplicitly) universal trees.
Is this necessary?
PapersCzerwiński, Daviaud, Fijalkow, Jurdziński, Lazić, Parys 2019
Arnold, Niwiński, Parys 2021
define two general approaches such that●all known quasipolynomial algorithms follow these approaches●every algorithm following this approach has to use a universal tree
Complexity of the (best) algorithms?

O(m.|Sn,d/2|)

Improvement 1: this can be changed toO(m.|Sn/2,d/2|)

i.e., we can use universal trees for n/2 leaves(not really new – already observed in some older papers,
but not present in papers with the best complexity)

Why universal trees?
Complexity of the (best) algorithms?

O(m.|Sn,d/2|)

Improvement 1: this can be changed toO(m.|Sn/2,d/2|)
i.e., we can use universal trees for n/2 leaves(not really new – already observed in some older papers,
but not present in papers with the best complexity)

Idea: map only nodes of odd priority (or only nodes of even priority)
to leaves of the universal tree.
There are at most n/2 of them.

Why universal trees?
Complexity of the (best) algorithms?

O(m.|Sn,d/2|)

Improvement 1: this can be changed toO(m.|Sn/2,d/2|)
i.e., we can use universal trees for n/2 leaves(not really new – already observed in some older papers,
but not present in papers with the best complexity)

Idea: map only nodes of odd priority (or only nodes of even priority)
to leaves of the universal tree.
There are at most n/2 of them.

Anyway: it is essential to bound the size of universal trees.

What is the size?
Recursive formula:|S0,h|=0|Sn,0|=1|Sn,h|=|Sn,h-1|+|S⌊n/2⌋,h|+|S⌊(n-1)/2⌋,h|Sn,h =S⌊n/2⌋,hSn,h-1S⌊(n-1)/2⌋,hTheorem

h–1+⌊log2n⌋1+log2e+log2(1+h/log2n).
|Sn,h|≤n≤n⌊log n⌋(2)(we did better analysis – previous bound was greater h times)

What is the size?
Recursive formula:|S0,h|=0|Sn,0|=1|Sn,h|=|Sn,h-1|+|S⌊n/2⌋,h|+|S⌊(n-1)/2⌋,h|Sn,h =
S⌊n/2⌋,hSn,h-1S⌊(n-1)/2⌋,hTheorem

h–1+⌊log2n⌋1+log2e+log2(1+h/log2n).
|Sn,h|≤n≤n⌊log n⌋()

2(we did better analysis – previous bound was greater h times)

Lower bound?
Every (n,h)-universal tree satisfiesh+⌊log2n⌋|Un,h|≥( ⌊log n⌋
2n log2(1+h/log2n)≥(–)2)(Czerwiński, Daviaud, Fijalkow, Jurdziński, Lazić, Parys 2019 + our improvements)

What is the size?
Upper bound:h–1+⌊log2n⌋1+log2e+log2(1+h/log2n).
|Sn,h|≤n≤n⌊log n⌋()2Lower bound:h+⌊log2n⌋|Un,h|≥( ⌊log2n⌋upper bound≤nlower boundn log2(1+h/log2n)≥(–)2)

What is the size?
Upper bound:h–1+⌊log2n⌋1+log2e+log2(1+h/log2n).
|Sn,h|≤n≤n⌊log n⌋()2Lower bound:h+⌊log2n⌋|Un,h|≥( ⌊log2n⌋n log2(1+h/log2n)≥(–)2)

upper bound≤nlower boundOpen questions:●Can this be improved?
● Is there any universal tree smaller than Sn,h?

What is the size?
Open questions:●Can the bounds be improved?
● Is there any universal tree smaller than Sn,h?
Partial answers:● For h=2 the tree S
n,2 is optimal.
● There is exists a “strange” (5,3)-universal tree of the same size as S5,3

Summary
Small improvement in the complexity of solving parity games:
Previous: O(mdn log2e+log2(d/log2n) )1 log2e+log2(d/log2n)
New: O(m–n)
dSmall improvement in bounds for size of (n,h)-universal tree:
upper bound≤nlower bound(previously: nh)

Thank you!