An Introduction to Dynamic Games

March 28, 2000

18 CHAPTER 2. DECISION ANALYSIS WITH MANY AGENTS

s [payoffs]
1/3
*
a12
E
H - s [payoffs]
HH
1/3 HH
j s [payoffs]

D2

@
@
a11 @ * s [payoffs]


1/3
@ -
R E
@ s [payoffs]
H H
a22 H
1/3 HH
j s [payoffs]

D1
A
A s [payoffs]
A 1/3
*
A a12
A E
H - s [payoffs]
A H
H
A 1/3 HH
j s [payoffs]
a21 A
A
U D2
A
@
@
@ 1/3 * s [payoffs]

@

R E
@ H
- s [payoffs]
a22 H
H
1/3 HH j s [payoffs]

Figure 2.1: A game in extensive form

ferent mathematical tools are used for the representation of the game dynamics. In
particular, differential and/or difference equations are utilized for this purpose.

2.2.2 Comparing Random Perspectives

Due to Nature’s randomness, the players will have to compare and choose among
different random perspectives in their decision making. The fundamental decision
structure is described in Figure 2.2. If the player chooses action a1 he faces a random
perspective of expected value 100. If he chooses action a2 he faces a sure gain of 100.
If the player is risk neutral he will be indifferent between the two actions. If he is risk
2.2. GAMES IN EXTENSIVE FORM 19

averse he will choose action a2 , if he is risk lover he will choose action a1 . In order to

0

1/3

e.v.=100
1/3

E - 100

@
a1 @
@
@
1/3 @@
@
@
D @ R
@
200
@
@
@
@
@
@
a2 @
R
@
100

Figure 2.2: Decision in uncertainty

represent the attitude toward risk of a decision maker Von Neumann and Morgenstern
introduced the concept of cardinal utility [Von Neumann & Morgenstern 1944]. If one
accepts the axioms of utility theory then a rational player should take the action which
leads toward the random perspective with the highest expected utility .

This solves the problem of comparing random perspectives. However this also
introduces a new way to play the game. A player can set a random experiment in order
to generate his decision. Since he uses utility functions the principle of maximization
of expected utility permits him to compare deterministic action choices with random
ones.

As a final reminder of the foundations of utility theory let’s recall that the Von Neumann-
Morgenstern utility function is defined up to an affine transformation. This says that
the player choices will not be affected if the utilities are modified through an affine
transformation.
20 CHAPTER 2. DECISION ANALYSIS WITH MANY AGENTS

2.3 Additional concepts about information

What is known by the players who interact in a game is of paramount importance. We

refer briefly to the concepts of complete and perfect information.

2.3.1 Complete and perfect information

The information structure of a game indicates what is known by each player at the time
the game starts and at each of his moves.

Complete vs Incomplete Information

Let us consider first the information available to the players when they enter a game
play. A player has complete information if he knows

• who the players are

• the set of actions available to all players

• all possible outcomes to all players.

A game with complete information and common knowledge is a game where all play-
ers have complete information and all players know that the other players have com-
plete information.

Perfect vs Imperfect Information

We consider now the information available to a player when he decides about specific
move. In a game defined in its extensive form, if each information set consists of just
one node, then we say that the players have perfect information . If that is not the case
the game is one of imperfect information .

Example 2.3.1 A game with simultaneous moves, as e.g. the one shown in Figure 2.1,
is of imperfect information.
2.4. GAMES IN NORMAL FORM 21

Perfect recall

If the information structure is such that a player can always remember all past moves
he has selected, and the information he has received, then the game is one of perfect
recall . Otherwise it is one of imperfect recall .

2.3.2 Commitment

A commitment is an action taken by a player that is binding on him and that is known
to the other players. In making a commitment a player can persuade the other players
to take actions that are favorable to him. To be effective commitments have to be
credible . A particular class of commitments are threats .

2.3.3 Binding agreement

Binding agreements are restrictions on the possible actions decided by two or more
players, with a binding contract that forces the implementation of the agreement. Usu-
ally, to be binding an agreement requires an outside authority that can monitor the
agreement at no cost and impose on violators sanctions so severe that cheating is pre-
vented.

2.4 Games in Normal Form

2.4.1 Playing games through strategies

Let M = {1, . . . , m} be the set of players. A pure strategy γj for Player j is a mapping
which transforms the information available to Player j at a decision node where he is
making a move into his set of admissible actions. We call strategy vector the m-tuple
γ = (γ)j=1,...m . Once a strategy is selected by each player, the strategy vector γ is
defined and the game is played as it were controlled by an automaton4 .

An outcome (expressed in terms of expected utility to each player if the game

includes chance nodes) is associated with a strategy vector γ. We denote by Γj the set
4
This idea of playing games through the use of automata will be discussed in more details when we
present the folk theorem for repeated games in Part II
22 CHAPTER 2. DECISION ANALYSIS WITH MANY AGENTS

of strategies for Player j. Then the game can be represented by the m mappings

Vj : Γ1 × · · · Γj × · · · Γm → IR, j∈M

that associate a unique (expected utility) outcome Vj (γ) for each player j ∈ M with
a given strategy vector in γ ∈ Γ1 × · · · Γj × · · · Γm . One then says that the game is
defined in its normal form .

2.4.2 From the extensive form to the strategic or normal form

We consider a simple two-player game, called “matching pennies”. The rules of the
game are as follows:

The game is played over two stages. At first stage each player chooses
head (H) or tail (T) without knowing the other player’s choice. Then they
reveal their choices to one another. If the coins do not match, Player 1
wins $5 and Payer 2 wins -$5. If the coins match, Player 2 wins $5 and
Payer 1 wins -$5. At the second stage, the player who lost at stage 1 has
the choice of either stopping the game or playing another penny matching
with the same type of payoffs as in the first stage (Q, H, T).

The extensive form tree

This game is represented in its extensive form in Figure 2.3. The terminal payoffs rep-
resent what Player 1 wins; Player 2 receives the opposite values. We have represented
the information structure in a slightly different way here. A dotted line connects the
different nodes forming an information set for a player. The player who has the move
is indicated on top of the graph.

Listing all strategies

In Table 2.1 we have identified the 12 different strategies that can be used by each of
the two players in the game of Matching pennies. Each player moves twice. In the
first move the players have no information; in the second move they know what have
been the choices made at first stage. We can easily identify the whole set of possible
strategies.
2.4. GAMES IN NORMAL FORM 23

Figure 2.3: The extensive form tree of the matching pennies game

P1 P2 P1 P2 P1

* 5



H
*
10

Q
T : 0
tXX


H 3Q XXX H H : 0
zt

Q
Q p
p
Q p T-
H t
TQst p 10
pPP

p p P PP :


ppp PP Q -5
T PP

pp P
qtX H 1 0

pp Q X XXX
Q H z tp - -10

pp Q p T

p Q p
pp TQ sptP - 10

t p PPH
J pp P q
P
J p T 0
pp : -5
J p Q
J pp
1t 1 0
J pp X
QXXX H
H Q H p z
X t
-
J pp
Q p
-10
T
T JJ^
H
pt
p TQQstpP
p - -10
HH PPH
PPq
HHjtXX
Q T- 0
T Q XX 5
Q ztX
X - 10
QH pp XXXX
Q p XXXH
TQsXtpHX XXz
HX X
HHXXXXT 0
H XXz
HH H 0
HH
TH j
10

Payoff matrix

In Table 2.2 we have represented the payoffs that are obtained by Player 1 when both
players choose one of the 12 possible strategies.
24 CHAPTER 2. DECISION ANALYSIS WITH MANY AGENTS

Strategies of Player 1 Strategies of Player 2

1st scnd move 1st scnd move
move if player 2 move if player 1
has played move has played
H T H T
1 H Q H H H Q
2 H Q T H T Q
3 H H H H H H
4 H H T H T H
5 H T H H H T
6 H T T H T T
7 T H Q T Q H
8 T T Q T Q T
9 T H H T H H
10 T T H T H T
11 T H T T T H
12 T T T T T T
Table 2.1: List of strategies

2.4.3 Mixed and Behavior Strategies

Mixing strategies

Since a player evaluates outcomes according to his VNM-utility functions he can envi-
sion to “mix” strategies by selecting one of them randomly, according to a lottery that
he will define. This introduces one supplementary chance move in the game descrip-
tion.

For example, if Player j has p pure strategies γjk , k = 1, . . . , p he can select the
strategy he will play through a lottery which gives a probability xjk to the pure strategy
γjk , k = 1, . . . , p. Now the possible choices of action by Player j are elements of the
set of all the probability distributions

X
p
Xj = {xj = (xjk )k=1,...,p |xjk ≥ 0, xjk = 1.
k=1

We note that the set Xj is compact and convex in IRp .

2.4. GAMES IN NORMAL FORM 25

1 2 3 4 5 6 7 8 9 10 11 12
1 -5 -5 -5 -5 -5 -5 -5 -5 0 0 10 10
2 -5 -5 -5 -5 -5 -5 5 5 10 10 0 0
3 0 -10 0 -10 -10 0 5 5 0 0 10 10
4 -10 0 -10 0 -10 0 5 5 10 10 0 0
5 0 -10 0 -10 0 -10 5 5 0 0 10 10
6 0 -10 0 -10 0 -10 5 5 10 10 0 0
7 5 5 0 0 10 10 -5 -5 -5 -5 -5 -5
8 5 5 10 10 0 0 -5 -5 -5 5 5 5
9 5 5 0 0 10 10 -10 0 -10 0 -10 0
10 5 5 10 10 0 0 -10 0 -10 0 -10 0
11 5 5 0 0 10 10 0 -10 0 -10 0 -10
12 5 5 10 10 0 0 0 -10 0 -10 0 -10
Table 2.2: Payoff matrix

Behavior strategies

A behavior strategy is defined as a mapping which associates with the information

available to Player j at a decision node where he is making a move a probability dis-
tribution over his set of actions.

The difference between mixed and behavior strategies is subtle. In a mixed strat-
egy, the player considers the set of possible strategies and picks one, at random, ac-
cording to a carefully designed lottery. In a behavior strategy the player designs a
strategy that consists in deciding at each decision node, according to a carefully de-
signed lottery, this design being contingent to the information available at this node.
In summary we can say that a behavior strategy is a strategy that includes randomness
at each decision node. A famous theorem [Kuhn, 1953], that we give without proof,
establishes that these two ways of introding randomness in the choice of actions are
equivalent in a large class of games.

Theorem 2.4.1 In an extensive game of perfect recall all mixed strategies can be rep-
resented as behavior strategies.