Game Development Reference
InDepth Information
Hence, every vertex
v
V
has its
f
value
, denoted by
val
f
(
v, G
) (or just
by
val
f
(
v
)if
G
is understood), which is defined by Equality (5.1). Note that
this result holds without any additional assumptions about the game
G
.In
particular,
G
may have infinitely many vertices and some (or all) of them
may have infinitely many outgoing transitions.
∈
Remark
It is worth noting that the result presented by Maitra and Sud
derth [1998] is even more general and holds also for
concurrent
stochastic
games (where both players make their choice simultaneously) with an
arbi
trary
(not necessarily countable) action and state spaces. The only require
ment is that
f
is a bounded
B
measurable function and both players choose
their actions at random according to finitely additive probability measures on
the power sets of their respective action sets. This can be used, e.g., to show
that vertices in various types of
timed
stochastic games have an
f
value.
An important subclass of payoff functions are
qualitative
payoffs which
simply classify each run as good or bad according to some criteria. The good
runs are assigned 1, and the bad ones are assigned 0. General (not necessarily
qualitative) payoffs are also called
quantitative
payoffs.
Note that a qualitative payoff
f
is just a characteristic function of some
Borel set
B
f
⊆
Run
(
G
). For every pair of strategies (
σ, π
)
∈
Σ
×
Π and every
initial distribution
μ
we have that
(
f
σ,π
Run
(
G
(
σ,π
)
E
)=
P
μ
(
{
w
∈
)

w
G
∈
B
f
}
)
.
μ
μ
Hence, player
in fact try to maximise and minimise the
probability
of all runs in
B
f
, respectively.
Observe that Equality (5.1) does not guarantee the existence of
optimal
strategies for player
and player
♦
which would achieve the yield
val
f
(
v
)
or better against every strategy of the opponent. As we shall see, optimal
strategies do
not
exist in general, but they may exist in some restricted cases.
On the other hand, Equality (5.1)
does
imply the existence of
ε
optimal
strategies for an arbitrarily small
ε>
0.
and player
♦
Definition 5.3
Let
ε ≥
0. A strategy
σ ∈
Σisan
ε
optimal maximising
strategy
in a vertex
v ∈ V
if inf
π∈
Π
E(
f
σ,
v
)
≥ val
f
(
v
)
− ε
. Similarly, a
strategy
π ∈
Πisan
ε
optimal minimising strategy
in a vertex
v ∈ V
if
sup
σ∈
Σ
E(
f
σ,π
)
≤ val
f
(
v
)+
ε
. Strategies that are 0optimal are
optimal
.
v
Qualitative payoffs
2
C
a
valuation
.
An important and wellstudied class of qualitative payoffs are characteristic
Let
C
=
{
c
1
,...,c
n
}
be a finite set of
colours
, and
ν
:
V
→
Search Nedrilad ::
Custom Search