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

Custom Search