Game Development Reference
In-Depth Information
For zero-sum games, it su ces to specify just yield , which is denoted simply
by yield . Then, the objective of player
and player
is to maximise and
minimise the value of yield , respectively.
There are two major classes of zero-sum turn-based stochastic games,
which can be characterised as follows:
(1) Games with Borel measurable payoffs. Every
-measurable func-
tion over Run ( G ) determines a unique random variable over the runs of
a given play of G . The yield assigned to the play is the expected value
of this random variable.
(2) Win-lose games. A win-lose yield is either 1 or 0 for every play of
G , depending of whether the play satisfies a certain property or not,
respectively. Typically, the property is encoded as a formula of some
probabilistic temporal logic.
B
These two classes of games are formally introduced and discussed in the next
subsections.
Let us note that there are also results about non-zero-sum turned-based
stochastic games, where the objectives of the (two or more) players are
not necessarily conflicting. The main question is the existence and effective
computability of Nash equilibria for various classes of players' objectives. The
problem has been considered also in the more general setting of simultaneous-
choice stochastic games. We refer to Secchi and Sudderth [2001], Chatterjee
et al. [2004c, 2006] and Ummels and Wojtczak [2009] for more details.
5.2.1 Games with Borel measurable payoffs
A payoff is a bounded 1
B
-measurable function f : Run ( G )
R
. Observe
that for every pair of strategies ( σ, π )
Σ
×
Π and every initial probabil-
: Run ( G ( σ,π )
ity distribution μ on V , the function f σ,π
defined by
f σ, μ ( w )= f ( w G ) is a random variable. Thus, every payoff f determines the
associated yield defined by
yield f ( G ( σ,π )
)
R
μ
μ
( f σ,π
)=
E
) .
μ
μ
As observed by Maitra and Sudderth [1998], the determinacy result for
Blackwell games achieved by Martin [1998] implies that for every vertex
v
V we have the following:
( f σ,π
( f σ,π
sup
σ∈ Σ
inf
π∈ Π
E
) = inf
π∈ Π
sup
σ∈ Σ E
) .
(5.1)
v
v
1 A real-valued function f is bounded if there is b ∈ R such that −b ≤ f ( x ) ≤ b for every x in the
domain of f .