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
.

Search Nedrilad ::

Custom Search