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