Game Development Reference
In-Depth Information
enemy is unaware of (and thus being able to make moves that the enemy is
unaware of) can be critical; in financial markets, some investors may not be
aware of certain investment strategies (complicated hedging strategies, for
example, or tax-avoidance strategies).
To understand the impact of adding the possibility of unawareness to the
analysis of games, consider the game shown in Figure 8.1 (this example, and
all the discussion in this section, is taken from [Halpern and Rego, 2006]).
One Nash equilibrium of this game has A playing across A and B playing
down B . However, suppose that A is not aware that B can play down B .In
that case, if A is rational, A will play down A . Although A would play across A
if A knew that B were going to play down B , A cannot even contemplate this
possibility, let alone know it. Therefore, Nash equilibrium does not seem to
be the appropriate solution concept here.
A
across A
B
across B
(0,2)
down A
down B
(1,1)
(2,3)
Figure 8.1 A simple game
To find an appropriate analogue of Nash equilibrium in games where players
may be unaware of some possible moves, we must first find an appropriate
representation for such games. The first step in doing so is to explicitly
represent what players are aware of at each node. We do this by using what
we call an augmented game .
Recall that an extensive game is described by a game tree. Each node
in the tree describes a partial history of the game - the sequence of moves
that led to that node. Associated with each node is the player that moves at
that node. Some nodes where a player i moves are grouped together into an
information set for player i . Intuitively, if player i is at some node in an
information set I , then i does not know which node of I describes the true
situation; thus, at all nodes in I , i must make the same move. An augmented
game is an extensive game with one more feature: associated with each node
in the game tree where player i moves is the level of awareness of player
i - the set of histories that player i is aware of. (The formal definition of an
augmented game can be found in [Halpern and Rego, 2006].)