Game Development Reference

In-Depth Information

parity-win-dominion
†
(
G
) can be characterised by the recurrence:

n
2
/
3

,d
)+
O
(
n
d/
3+
O
(1)
)
,

T
(
n, d
)

≤

T
(
n, d

−

1) +
T
(
n

−

T
(
n,
1) =
O
(
n
)
,

and hence also by the recurrence:

T
(
n, d
)
≤ n
1
/
3

· T
(
n, d −
1) +
O
(
n
d/
3+
O
(1)
)
,

T
(
n,
1) =
O
(
n
)
.

Prove that
T
(
n, d
)=
O
(
n
d/
3+
O
(1)
).

Theorem 3.10
(Schewe [2007])
The winning sets and positional win-

ning strategies of both players in parity games can be computed in time

O
(
n
d/
3+
O
(1)
)
.

3.4 Related work

This survey of algorithms for solving parity games is not exhaustive. In

particular, an important class of
local search algorithms
has not been

included here. This class includes
strategy improvement algorithms
,

inspired by policy iteration algorithms for
Markov decision processes

(Howard [1960], Puterman [2005]) and
stochastic games
(Filar and Vrieze

[1997]), and various
pivoting algorithms
adapted from the theory of the

linear complementarity problem
(Cottle et al. [2009]).

The initial impulse for exploring applications of such local search algorithms

to parity games has been the observation by Puri [1995] and Stirling [1995]

that there is a polynomial time reduction from parity games to
mean-

payoff games
and to
simple stochastic games
. The reduction has also

been exploited by Jurdzinski [1998] to show that the problems of deciding

the winner in parity, mean-payoff, discounted, and simple stochastic games

are in UP and in co-UP.

Voge and Jurdzinski [2000] have been inspired by the reduction from parity

games to discounted games to devise a
discrete strategy improvement

algorithm for parity games. This algorithm has been conjectured to have

worst-case polynomial running time, but in a recent breakthrough Friedmann

[2009] has dashed those hopes by exhibiting a family of parity games with

O
(
n
) vertices on which the algorithm performs Ω(2
n
) iterations. Intriguingly,

working with parity games and the discrete strategy improvement algorithm

has enabled Friedmann to devise examples of mean-payoff, discounted, and

simple stochastic games that make the strategy improvement algorithm

Search Nedrilad ::

Custom Search