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

Search Nedrilad ::

Custom Search