Game Development Reference
In-Depth Information
d/ 2 be a game parity progress measure.
Consider the positional strategy μ for player 0 that maps every vertex v
Exercise 3.17
Let ξ : V
N
V 0
to a successor w that minimises ξ [ p ( v )] ( w ).
Use Exercise 3.16 to argue that for every infinite path in the strategy
subgraph of μ , the maximum vertex priority that occurs infinitely many
times is even. Conclude that the positional strategy μ is winning for player 0
from every starting vertex.
The above exercise establishes that the existence of a game parity progress
measure in a parity game G implies that player 0 has a positional winning
strategy from every starting vertex, and hence that win 0 ( G )= V . The
following slight refinement of the concept of a game parity progress measure
gives us a more flexible tool for witnessing the existence of 0-dominion
strategies on arbitrary 0-dominions.
For every positive integer i , consider an extension of the set of i -tuples
of numbers by the top element
that is strictly bigger than every i -tuple.
Moreover, let us adopt the notational convention that if ξ : V
d/ 2
N
∪{}
implies that ξ [ q ] ( v )=
then ξ ( v )=
for every q . We say that a function
d/ 2
ξ : V
N
∪{}
is a (partial) game parity progress measure if for
every vertex v
V ,wehave:
if v ∈ V 0 and ξ ( v ) = , then ξ [ p ( v )] ( v ) min ( v,w ) ∈E ξ [ p ( v )] ( w ) ,
and if p ( v ) is odd then the inequality is strict;
(3.4)
and
max ( v,w ) ∈E ξ [ p ( v )] ( w ) ,
and if p ( v ) is odd then the inequality is strict .
, then ξ [ p ( v )] ( v )
if v
V 1 and ξ ( v )
=
(3.5)
d/ 2
For a game parity progress measure ξ : V
N
∪{}
, we write dom ( ξ )
for the domain of function ξ , i.e., the set ξ 1 (
d/ 2 ) of the vertices for which
N
the value of function ξ is not
.
d/ 2
Exercise 3.18
be a game parity progress measure.
Prove that the set dom ( ξ ) is a 0-dominion by exhibiting a positional 0-
dominion strategy on dom ( ξ ). Conclude that if ξ : V
Let ξ : V
N
∪{}
d/ 2
is a game
parity progress measure on a parity game G then dom ( ξ ) ⊆ win 0 ( G ).
N
∪{}
Exercise 3.18 implies that the existence of a game parity progress measure
with a non-empty domain is a su cient condition for the existence of a
0-dominion strategy. In the following we establish that this condition is also
necessary. Moreover, we argue that the range of a game parity progress
measure can be bounded by a function of the size of a 0-dominion for which