Game Development Reference

In-Depth Information

v
are

remains unchanged when all outgoing transitions of v except for v

→

deleted from G.

v
can be chosen arbitrarily.

Proof

Let
v

∈

V
.If
v

∈

T
, the transition
v

→

Now assume that
v

Π we define the (unique)

strategy
τ
[
v
] such that
τ
[
v
](
w
)=
τ
(
w
), where
w
is the shortest su
x of
w

which is either equal to
w
or starts with
v
. Intuitively,
τ
[
v
] behaves identically

to
τ
until the vertex
v
is revisited. Then,
τ
[
v
] 'forgets' the history and behaves

as if the play just started in
v
.

Let us define two auxiliary Borel sets of runs

∈

T
. For every strategy
τ

∈

Σ

∪

¬

T
U
v
and

¬

v
U
T
where

•¬T
U
v
consists of all
w ∈ Run
(
G
) such that
w
(
j
)=
v
for some
j>
0 and

w
(
i
)
∈ T
for all 1
≤ i<j
;

•¬

v
U
T
consists of all
w

∈

Run
(
G
) such that
w
(
j
)

∈

T
for some
j>
0 and

w
(
i
)

=
v
for all 1

≤

i<j
.

(
σ,π
)

v

Observe that for all (
σ, π
)

∈

Σ

×

Π such that

P

(

¬

T
U
v
)
<
1wehave

(
σ
[
v
]
,π
[
v
])

v

that

P

(
Reach
(
T
)) is equal to

∞

v
U
T
)=
P
(
σ,π
)

P
(
σ,π
)

v

T
U
v
)
i

(

¬

v
U
T
)

v

·P
(
σ,π
)

v

T
U
v
)
.

(

¬

(

¬

−P
(
σ,π
)

1

(

¬

v

i
=0

For the moment, assume the following equality:

(
σ,π
)

v

(
σ
[
v
]
,π
)

v

sup

σ∈
Σ

π∈
Π
P

inf

(
Reach
(
T
)) = sup

σ∈
Σ

π∈
Π
MD
P

inf

(
Reach
(
T
))
.

(5.7)

Π
MD
we have that
π
=
π
[
v
]. For every
σ

Note that for every
π

∈

∈

Σ and

v
, let
σ
v→v
be the strategy which agrees with
σ
on all

arguments except for
v
where
σ
v→v
(
v
) selects the transition
v

every transition
v

→

v
with

→

probability 1. It is easy to check that for every
σ

∈

Σ there must be some

v
satisfying

σ-good
transition
v

→

(
σ
v→v
[
v
]
,π
)

v

(
σ
[
v
]
,π
)

v

π∈
Π
MD
P

inf

(
Reach
(
T
))

≤

π∈
Π
MD
P

inf

(
Reach
(
T
))
.

For every
i

≥

1, let us fix a strategy
σ
i
∈

Σ such that

1

2
i
.

(
σ
i
[
v
]
,π
)

v

π∈
Π
MD
P

inf

(
Reach
(
T
))

≥

val
(
v
)

−

v
which is
σ
i
-good

for infinitely many
i
's, and hence the value of
v
(and therefore also the value

of the other vertices of
V
) does not change if all outgoing transitions of
v

except for
v

Since
G
is finitely branching, there is a transition
v

→

v
are deleted from
G
.

So, it remains to prove Equality (5.7). We start with the '

→

≥

' direction. Let

Search Nedrilad ::

Custom Search