Game Development Reference
In-Depth 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 turn-based 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 turn-based 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 component-wise ordering, we can apply the Knaster-Tarski Theorem
(see Tarski [1955]) and conclude that Γ has the least fixed-point μ Γ. 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
fixed-point of Γ, which is also straightforward. So, it remains to show that