Game Development Reference

In-Depth Information

The following fundamental theorem establishes that determinacy of games

on graphs holds for a rich class of payoff functions.

Theorem 3.1
(Martin [1998])
If the payoff function is bounded and Borel

measurable then the game is determined.

A game is
positionally determined
if the equality (3.1) holds for all

v ∈ V
, where
χ
on the left hand side of the equality, and
μ
on the right-hand

side of the equality, respectively, are restricted to range over the sets of

positional strategies for player 0 and player 1, respectively. In other words, if

a game is positionally determined then players can announce their positional

strategies with impunity. We say that a class of games enjoys
positional

determinacy
if all games in this class are positionally determined.

If a game is determined then we define the
game value
Val(
v
) at vertex
v

∈

V
to be the value of either side of equation (3.1). We say that a strategy
μ

of player 0 is an
optimal strategy
if sup
χ
Outcome(
v, μ, χ
)=Val(
v
) for all

v

V
. Optimal strategies of player 1 are defined analogously. If the value of

a qualitative game at a vertex
v
is 1 and player 1 has an optimal strategy

then we say that the strategy is winning for player 1 from
v
. Similarly, if the

value of a qualitative game at a vertex
v
is 0 and player 0 has an optimal

strategy then we say that the strategy is a
winning strategy
for player 0

from
v
. We define the
winning sets
win
0
(
G
) and
win
1
(
G
) to be the sets of

vertices from which players 0 and 1, respectively, have winning strategies.

All games
G
considered in this chapter are determined, the payoff functions

are Boolean, and both players have optimal strategies from every starting

vertex. It follows that game values at all vertices are well defined, and

from every vertex exactly one of the players has a winning strategy, i.e.,

win
0
(
G
)

∈

win
1
(
G
)=
V
.

The central algorithmic problem studied in this chapter is the computation

of the values and optimal strategies for both players in games on graphs. The

corresponding decision problem is, given a game graph, a starting vertex
v
,

and a number
t
, to determine whether Val(
v
)

t
. For the special case of

qualitative games, the problem of
deciding the winner
is, given a starting

vertex
v
, to determine whether
v

≥

win
1
(
G
).

In order to formalise such algorithmic problems we have to agree on finitary

representations of relevant classes of payoff functions. In this chapter we only

consider
Boolean payoff functions
that can be uniquely specified by their

indicator sets, i.e., the sets of outcomes winning for player 1.

Given a set of target vertices
T

∈

⊆

V
, we define the
reachability payoff

Search Nedrilad ::

Custom Search