Game Development Reference
InDepth Information
5.3 Reachability objectives in games with finitely and
infinitely many vertices
As we have already mentioned, the properties of stochastic games with finitely
and infinitely many vertices are different in many respects. To illustrate this,
we examine the properties of turnbased stochastic games with
reachability
objectives in greater detail. Most of the negative results presented in this
section are valid also for the other objectives introduced in Section 5.2.
For the rest of this section, we fix a turnbased stochastic game
G
=(
V,
→
,
(
V
,V
♦
,V
)
, Prob
) and a set
T
⊆
V
of
target
vertices. The
set of all
w
Run
(
G
) which visit a vertex of
T
is denoted by
Reach
(
T
).
Further, for every pair of strategies (
σ, π
)
∈
∈
Σ
×
Π and every initial vertex
v
,
(
σ,π
)
v
Run
(
G
(
σ,π
)
we use
P
(
Reach
(
T
)) to denote the probability
P
v
(
{
w
∈
)

v
w
G
∈
Reach
(
T
)
}
).
5.3.1 The existence of a value revisited
Recall that every vertex
v
of
G
has a value
val
(
v
) defined by Equality 5.1
which now takes the following simple form:
(
σ,π
)
v
(
σ,π
)
v
sup
σ∈
Σ
π∈
Π
P
inf
(
Reach
(
T
)) = inf
π∈
Π
sup
σ∈
Σ
P
(
Reach
(
T
))
.
(5.5)
A direct proof of Equality (5.5) is actually simple and instructive. Consider
the following (Bellman) functional Γ : [0
,
1]
V 
→
[0
,
1]
V 
defined as follows:
⎨
1
if
v
∈
T
;
α
(
v
)
v
}
sup
{

v
→
if
v
∈
T
and
v
∈
V
;
Γ(
α
)(
v
)=
⎩
α
(
v
)
v
}
inf
{

v
→
if
v
∈
T
and
v
∈
V
♦
;
v
x
α
(
v
)
→v
x
·
if
v
∈
T
and
v
∈
V
.
Since Γ is a monotonic function over a complete lattice ([0
,
1]
V 
,
), where
is a componentwise ordering, we can apply the KnasterTarski Theorem
(see Tarski [1955]) and conclude that Γ has the least fixedpoint
μ
Γ. Observe
that for every
v
∈
V
we have that
(
σ,π
)
v
(
σ,π
)
v
μ
Γ(
v
)
≤
sup
σ∈
Σ
π∈
Π
P
inf
(
Reach
(
T
))
≤
inf
π∈
Π
sup
σ∈
Σ
P
(
Reach
(
T
))
.
The second inequality follows directly from definitions and it is actually valid
for
arbitrary
Borel measurable payoffs. The first inequality is obtained by
demonstrating that the tuple of all sup
σ∈
Σ
inf
π∈
Π
P
(
σ,π
)
v
(
Reach
(
T
)) is a
fixedpoint of Γ, which is also straightforward. So, it remains to show that
Search Nedrilad ::
Custom Search