Lecture I-II: Motivation and Decision Theory

Markus M. Möbius
February 4, 2003

1 Motivating Experiment: Guess the average

Setup: Each of you (the students in this course) have to declare an integer
between 0 and 100 to guess ”2/3 of the average of all the responses”. More
precisely, each student who guesses the highest integer which is not higher
than 2/3 of the average of all responses, will receive a prize of 10 Dollars.
This game can be solved by iterated dominance. However, being smart
is not enough. Those who bid 0 typically lose badly. You have to guess how
’dumn’ all the other students in the class are. Even if everyone is supersmart,
but has low confidence in the smartness of others, the winning value can be
quite high. In our class we got a winning bid of 17 and 1 person walked away
with 10 Dollars.

2 What is game theory?

Definition 1 Game theory is a formal way to analyze interaction among a
group of rational agents who behave strategically.

This definition contains a number of important concepts which are dis-

cussed in order:
Group: In any game there is more than one decision maker who is
referred to as player. If there is a single player the game becomes a decision
problem.
Interaction: What one individual player does directly affects at least
one other player in the group. Otherwise the game is simple a series of
independent decision problems.

1
 Strategic: Individual players account for this interdependence.
Rational: While accounting for this interdependence each player chooses
her best action. This condition can be weakened and we can assume that
agents are boundedly rational. Behavioral economics analyzes decision prob-
lems in which agents behave boundedly rational. Evolutionary game theory
is game theory with boundedly rational agents.

Example 1 Assume that 10 people go into a restaurant. Every person pays

for her own meal. This is a decision problem. Now assume that everyone
agrees before the meal to split the bill evenly amongst all 10 participants. Now
we have a game.

Game theory has found numerous applications in all fields of economics:

1. Trade: Levels of imports, exports, prices depend not only on your own
tariffs but also on tariffs of other countries.
2. Labor: Internal labor market promotions like tournaments: your chances
depend not only on effort but also on efforts of others.
3. IO: Price depends not only on your output but also on the output of
your competitor (market structure ...).
4. PF: My benefits from contributing to a public good depend on what
everyone else contributes.
5. Political Economy: Who/what I vote for depends on what everyone
else is voting for.

3 Decision Theory under Certainty

It makes sense to start by discussing trivial games - those we play against
ourselves, e.g. decision problems. Agents face situations in which they have
to make a choice. The actions of other agents do not influence my preference
ordering over those choices - therefore there is no strategic interaction going
on. Proper games will be discussed in the next lectures.
A decision problem (A, ¹) consists of a finite set of outcomes A = {a1 , a2 , .., an }
and a preference relation ¹. The expression a ¹ b should be interpreted as
”b is at least as good as a”. We expect the preference relation to fulfill two
simple axioms:

2
Axiom 1 Completeness. Any two outcomes can be ranked, e.g. a ¹ b or
b ¹ a.

Axiom 2 Transitivity implies that if a ≥ b and b ≥ c then a ≥ c.

Both axioms ensure that all choices can be ordered in a single chain without
gaps (axiom 1) and without cycles (axiom 2).
Although the preference relation is the basic primitive of any decision
problem (and generally observable) it is much easier to work with a consistent
utility function u : A → < because we only have to remember n real numbers
{u1 , u2 , .., un }.
Definition 2 A utility function u : A → < is consist with the preference
relationship of a decision problem (A, ¹) if for all a, b ∈ A:

a¹b if and only if u (a) ≤ u (b)

Theorem 1 Assume the set of outcomes is finite. Then there exists a utility
function u which is consistent.

Proof: The proof is very simple. Simple collect all equivalent outcomes in
equivalence classes. There are finitely many of those equivalence classes
since there are only finitely many outcomes. Then we can order these
equivalence classes in a strictly increasing chain due to completeness
and transitivity.

Note that the utility function is not unique. In fact, any monotonic
transformation of a consistent utility function gives another utility function
which is also consistent.
We can now define what a rational decision maker is.
Definition 3 A rational decision maker who faces a decision problem (A, ¹)
chooses an outcome a∗ ∈ A which maximizes his utility (or, equivalently, for
each a ∈ A we have a ¹ a∗ ).

Remark 1 When there are infinitely many choices we want to make sure
that there is a continuous utility function. This requires one more axiom
which makes sure that preferences are continuous. For that purpose, one has
to define topology on the set of outcomes. We won’t deal with that since we
won’t gain much insight from it.

3
4 Decision Theory under Uncertainty
Lotteries are defined over the of outcomes A (which is again assumed to be
finite to keep things simple).
DefinitionP4 A simple lottery is defined as the set {(a1 , p1 ) , (a2 , p2 ) , .. (an , pn )}
such that ni=1 pi = 1 and 0 ≤ pi ≤ 1. In a simple lottery the outcome ai
occurs with probability pi .
When there are up to three outcomes we can conveniently describe the
set of lotteries in a graphical way (see triangle).
Under certainty the preference relationship can still be written down ex-
plicitly for finite A (simply write down all of the n(n+1) 2
rankings). Under
uncertainty there are suddenly infinitely many lotteries. This poses two
problems. First of all, it’s impractical to write a large number of lottery
comparisons down. A second (and deeper) point is the observation that the
preference relationship is in principle unobservable because of the infinite
number of necessary comparisons.
John von Neumann and Oscar Morgenstern showed that under some ad-
ditional restrictions on preferences over lotteries there exists a utility function
over outcomes such that the expected utility of a lottery provides a consistent
ranking of all lotteries.
Definition 5 Assume a utility function u over the outcomes A. The expected
utility of the lottery L = {(a1 , p1 ) , (a2 , p2 ) , .. (an , pn )} is defined as
n
X
u (L) = u (ai ) pi
i=1

Before we introduce the additional axioms we discuss the notion of com-

pound (two stage) lotteries.
Definition 6 The compound lottery L̃ is expressed as L̃ = {(L1 , q1 ) , (L2 , 1 − q1 )}.
With probability q1 the simple lottery L1 is chosen and with probability 1 − q1
the simple lottery L2 is chosen.
Note, that we implicitly distinguish between simple and compound lotteries.
Therefore, we allow that a simple lottery L might have the same outcome
distribution as the compound lottery L̃ but L ≺ L̃.
The first axiom assumes that only outcomes matter - the process which
generates those outcomes is irrelevant.

4
Axiom 3 Each compound lottery is equivalent to a simple lottery with the
same distribution over final outcomes.

In some books the equivalence of simple and compound lotteries is assumed

in the definition of a lottery. However, it is useful to keep those types of
lotteries separate because we know that the framing of a decision problem
influences how people make choices (i.e. both the process and the final out-
come distribution matter).
The next axiom is fairly uncontroversial.

Axiom 4 Monotonicity. Assume that the lottery L1 is preferred to lot-

tery L2 . Then the compound lottery {(L1 , α) , (L2 , 1 − α)} is preferred to
{(L1 , β) , (L2 , 1 − β)} if α > β.

Axiom 5 Archimedian. For any outcomes a < b < c there is some lottery
L = {(a, α) , (c, 1 − α)} such that the agent is indifferent between L and b.

The substitution axiom (also know as independence of irrelevant alterna-

tives) is the most critical axiom.

Axiom 6 Substitution. If lottery L1 is preferred to lottery L2 then any mix-

ture of these lotteries with any other lottery L3 preserves this ordering:

{(L1 , α) , (L3 , 1 − α)} ≥ {(L2 , α) , (L3 , 1 − α)}

This axiom is also known as independence of irrelevant alternatives.

Under these axioms we obtain the celebrated result due to John von
Neumann and Oskar Morgenstern.

Theorem 2 Under the above axioms an expected utility function exists.

Proof: First of all we find the best and worst outcome b and w (possible be-
cause there are only finitely many outcomes). Because of the Archime-
dian axiom we can find a number αa for each outcome a such that L =
{(b, α) , (w, 1 − α)}. We can define a utility function over each outcome
a such that u (a) = α. Using the monotonicity axiom it can be shown
that this number is unique. For each lottery we can now calculate its ex-
pected utility. It remains to be shown that this expected utility function
is consistent with the original preferences. So take two lotteries L1 and
L2 such that L1 ¹ L2 . We can write L1 = {(a1 , p1 ) , (a2 , p2 ) , .. (an , pn )}

5
 and L2 = {(a1 , q1 ) , (a2 , q2 ) , .. (an , qn )}. Now replace each outcome
ai by the above
Pn lotteries. The compound Pn lottery can be rewritten
as L1 = {(b,
Pn i=1 i p u (a i )) , (w, 1
Pn i=1 i (ai ))}. Similarly, we get
− p u
L2 = {(b, i=1 qi u (ai )) , (w,
P 1 − i=1 qi u P (ai ))}. By the monotonicity
axiom we can deduce that ni=1 pi u (ai ) ≤ ni=1 qi u (ai ), e.g. EU (L1 ) ≤
EU (L2 ). QED

From now on all payoffs in our course will be assumed to represent vNM
utility values. The expected payoff will be the expected utility.

4.1 Puzzles
EUT forms the basis of modern micro economics. Despite its success there
are important behavioral inconsistencies related to it. Some of those we are
going to discuss briefly before we turn our attention to proper games.

4.2 Allais Paradox

Consider the following choice situation (A) among two lotteries:

• Lottery A1 promises a sure win of 3000,

• Lottery A2 is a 80 percent chance to win 4000 (and zero in 20 percent

of the cases).

Typically, A1 is strictly preferred to A2. Now, consider two further choice

pairs (B) and (C):

• Lottery B1 promises a 90 percent chance of winning 3000,

• Lottery B2 is a 72 percent chance to win 4000.

This choice is included to see if there is a certainty effect.

• Lottery C1 promises a 25 percent chance of winning 3000,

• Lottery C2 is a 20 percent chance to win 4000.

6
Most people in our class now preferred C2 over C1.
It can be checked that the lotteries Bi and Ci are derived from Ai just
by mixing the original lotteries with an irrelevant alternative - in the case of
(B) there is a 10 percent chance of getting nothing and a 90 percent chance
of getting (A), and in case of (C), there is a 75 percent chance of getting
nothing.
The Allais paradox is the most prominent example for behavioral incon-
sistencies related to the von Neumann Morgenstern axiomatic model of choice
under uncertainty. The Allais paradox shows that the significant majority of
real decision makers orders uncertain prospects in a way that is inconsistent
with the postulate that choices are independent of irrelevant alternatives.
There is an alternative explanation for the failure of EUT in this case.
Assume, that agents face the compound lottery instead of the simple lotteries
(B) and (C). Now the relationship to (A) is much more transparent - in fact,
one could tell a story such as: ”with 75 percent probability you are not invited
to choose between these two outcomes, and with 25 percent probability you
can choose either A1 or A2”. It’s likely that choices would be much more
consistent now.
The standard explanation for the failure of EUT is peoples’ inability to
keep small probability differences apart. 80 percent and 100 percent ’looks’
quite different and people focus on the probabilities. 20 percent and 25 per-
cent ’looks’ the same - so people focus on the values instead. Prospect theory
(Kahnemann and Tversky) can deal with the Allais paradox by weighting
probabilities accordingly.

4.3 Framing effects

Framing effects are preference reversals induced by changes in reference
points.
Consider the following choice situation (A):
Pair 1: 600 people are struck with a disease that could kill. Vaccine 1
will save 400 lives for sure while the second one will either save no one (1/3)
or will save everyone (with probability 2/3).
Pair 2: 600 people are struck with a disease that could kill. Vaccine 1
will kill 200 people for sure while the second one implies a 2/3 chance that
no one will die and a 1/3 chance that everyone will die.
Note that both situations are identical because save is equal to not kill.
However, people tend to be risk averse in saving lives and risk loving if it is

7
 Table 1: McNeil, Pauker and Tversky (1988)
Survival Mortality Both
Radiation Surgery Radiation Surgery Radiation Surgery
immediate 100 90 0 10
1 year 77 68 23 32
5 year 22 34 78 66
US 16 84 50 50 44 56
Israeli 20 80 45 56 34 66

phrased in terms of losses (kills).

Preference reversals have real effects and do not just appear in cute ex-
amples. McNeil, Pauker and Tversky (1988) asked American doctors and
Israeli medical students about how they would choose between two cancer
treatments (surgery and radiation) - they presented one group with survival
statistics, a second group with mortality statistics and a third group with
both. Table 1 sums up their choices.

8
Lecture III: Normal Form Games, Rationality
and Iterated Deletion of Dominated Strategies
Markus M. Möbius
February 7, 2003

1 Definition of Normal Form Game

Game theory can be regarded as a multi-agent decision problem. It’s useful
to define first exactly what we mean by a game.
Every normal form (strategic form) game has the following ingredients.

1. There is a list of players D = {1, 2, .., I}. We mostly consider games

with just two players. As an example consider two people who want to
meet in New York.

2. Each player i can choose actions from a strategy set Si . To continue

our example, each of the players has the option to go the Empire State
building or meet at the old oak tree in Central Park (where ever that
is ...). So the strategy sets of both players are S1 = S2 = {E, C}.

3. The outcome of the game is defined by the ’strategy profile’ which

consists of all strategies chosen by the individual players. For example,
in our game there are four possible outcomes - both players meet at the
Empire state building (E, E), they miscoordinate, (E, C) and (C, E), or
they meet in Central Park (C, C). Mathematically, the set of strategy
profiles (or outcomes of the game) is defined as

S = S1 × S2

In our case, S has order 4. If player 1 can take 5 possible actions, and
player 2 can take 10 possible actions, the set of profiles has order 50.

1
 Figure 1: General 2 by 2 game
E C

E 1,1 0,0

C 0,0 1,1

4. Players have preferences over the outcomes of the play. You should
realize that players cannot have preferences over the actions. In a game
my payoff depends on your action. In our New York game players just
want to be able to meet at the same spot. They don’t care if they
meet at the Empire State building or at Central Park. If they choose
E and the other player does so, too, fine! If they choose E but the
other player chooses C, then they are unhappy. So what matters to
players are outcomes, not actions (of course their actions influence the
outcome - but for each action there might be many possible outcomes -
in our example there are two possible outcomes per action). Recall, that
we can represent preferences over outcomes through a utility function.
Mathematically, preferences over outcomes are defined as:

ui : S → R

In our example, ui = 1 if both agents choose the same action, and 0

otherwise.
All this information can be conveniently expressed in a game matrix as
shown in figure 1:
A more formal definition of a game is given below:
Definition 1 A normal (strategic) form game G consists of
• A finite set of agents D = {1, 2, .., I}.
• Strategy sets S1 , S2 , .., SI
• Payoff functions ui : S1 × S2 × ..SI → R (i = 1, 2, .., n)

2
 We’ll write S = S1 × S2 × .. × SI and we call s ∈ S a strategy profile
(s = (s1 , s2 , .., sI )). We denote the strategy choices of all players except
player i with s−i for (s1 , s2 , .., si−1 , si+1 , ..sI ).

2 Some Important Games

We already discussed coordination games. These are interesting games, be-
cause players have an incentive to work together rather than against each
other. The first games analyzed by game theorists were just the opposite -
zero sum games, where the sum of agents’ utilities in each outcome sums up
to zero (or a constant).

2.1 Zero-Sum Games

Zero-sum games are true games of conflict. Any gain on my side comes at
the expense of my opponents. Think of dividing up a pie. The size of the
pie doesn’t change - it’s all about redistribution of the pieces between the
players (tax policy is a good example).
The simplest zero sum game is matching pennies. This is a two player
game where player 1 get a Dollar from player 2 if both choose the same
action, and otherwise loses a Dollar:

H T

H 1,−1 −1,1

T −1,1 1,−1

2.2 Battle of the Sexes

This game is interesting because it is a coordination game with some elements
of conflict. The idea is that a couple want to spend the evening together. The
wife wants to go to the Opera, while the husband wants to go to a football
game. Each get at least some utility from going together to at least one of

3
the venues, but each wants to go their favorite one (the husband is player 1
- the column player).

F O

F 2,1 0,0

O 0,0 1,2

2.3 Chicken or Hawk versus Dove

This game is an anti-coordination game. The story is that two teenagers
drive home on a narrow road with their bikes, and in opposite directions.
None of them wants to go out of the way - whoever ’chickens’ out loses his
pride, while the tough guy wins. But if both stay tough, then they break
their bones. If both go out of the way, none of the them is too happy or
unhappy.

t c

t −1,−1 10,0

c 0,10 5,5

2.4 Prisoner’s Dilemma

This game might be the most famous of all. It’s the mother of all cooperation
games. The story is that two prisoners are interrogated. If both cooperate
with the prosecution they get of with 1 year in prison. If both give each
other away (defect) they get 3 years in prison each. If one cooperates and
the other guy defects, then the cooperating guy is thrown into prison for 10
years, and the defecting guy walks free.

4
 C D

C 3,3 −1,4

D 4,−1 0,0

Note, that the best outcome in terms of welfare is if both cooperate. The
outcome (D, D) is worst in welfare terms, and is also Pareto dominated by
(C, C) because both players can do better. So clearly, (D, D) seems to be a
terrible outcome overall.
Some examples of Prisoner’s dilemmas are the following:

• Arms races. Two countries engage in an expensive arms race (corre-

sponds to outcome D,D). They both would like to spend their money
on (say) healthcare, but if one spends the money on healthcare and
the other country engages in arms build-up, the weak country will get
invaded.

• Missile defence. The missile defence initiative proposed by the ad-

ministration is interpreted by some observers as a Prisoner’s dilemma.
Country 1 (the US) can either not build a missile defence system (strat-
egy C) or build one (strategy D). Country 2 (Russia) can either not
build any more missiles (strategy C) or build lots more (strategy D).
If the US does not build a missile system, and Russia does not build
more missiles then both countries are fairly well off. If Russia builds
more missiles and the US has no defence then the US feels very unsafe.
If the US builds a missile shield, and Russia does not missiles then the
US is happy but Russia feels unsafe. If the US builds missile defence
and Russia builds more missiles then they are equally unsafe as in the
(C,C) case, but they are much less well off because they both have to
increase their defence budget.

• Driving a big SUV is a Prisoner’s Dilemma. I want my car to be as

safe as possible and buy an SUV. However, my neighbors who has a
Volkswagen Beetle suddenly is much worse off. If she also buys an SUV

5
2.5 Cournot Competition
This game has an infinite strategy space. Two firms choose output levels qi
and have cost function ci (qi ). The products are undifferentiated and market
demand determines a price p (q1 + q2 ). Note, that this specification assumes
that the products of both firms are perfect substitutes, i.e. they are homoge-
nous products.

D = {1, 2}
S1 = S2 = R+
u1 (q1 , q2 ) = q1 p (q1 + q2 ) − c1 (q1 )
u2 (q1 , q2 ) = q2 p (q1 + q2 ) − c2 (q2 )

2.6 Bertrand Competition

Bertrand competition is in some ways the opposite of Cournot competition.
Firms compete in a homogenous product market but they set prices. Con-
sumers buy from the lowest cost firm.

Remark 1 It is interesting to compare Bertrand and Cournot competition

with perfect competition analyzed in standard micro theory. Under perfect
competition firms are price takers i.e. they cannot influence the market. In
this case there is not strategic interaction between firms - each firm solves a
simple profit maximization problem (decision problem). This is of course not
quite true since the auctioneer does determine prices such that demand and
supply equalize.

3 Experiment: Prisoner’s Dilemma

Students are asked which strategy they would play in the Prisoner’s dilemma.
The class was roughly divided in half - we calculated the expected payoff from
both strategies if people in the class would be randomly matched against each
other. We found that strategy D was better - this is unsurprising as we will
see later since strategy C is strictly dominated by strategy D.

6
4 Experiment: Iterated Deletion Game
Students play the game given below and are asked to choose a strategy for
player 1.

A B C D

A 5,2 2,6 1,4 0,4

B 0,0 3,2 2,1 1,1

C 7,0 2,2 1,5 5,1

D 9,5 1,3 0,2 4,8

In class no student chooses strategy A which is weakly dominated by C. 2

students chose B, 9 students chose C because it looked ’safe’ and 16 students
chose D because of the high payoffs in that row. It turns out that only (B,B)
survives iterated deletion (see below).

5 Iterated Deletion of Dominated Strategies

How do agents play games? We can learn a lot by exploiting the assumption
that players are rational and that each player knows that other players are
rational. Sometimes this reasoning allows us to ’solve’ a game.

5.1 Rational Behavior

Assume that agent i has belief µi about the play of her opponents. A belief
is a probability distribution over the strategy set S−i . Since we are only
considering pure strategies right now this probability distribution is a point
distribution (i.e. puts all its weight on a single s−i .

7
Definition 2 Player i is rational with beliefs µi if
si ∈ arg max
0
Eµi (s−i ) ui (s0i , s−i ) ,
si

or alternatively X
si maximizes ui (s0i , s−i ) µi (s−i ) .
s−i

Note, that player i faces a simple decision problem as soon as she has
formed her belief µi .
Definition 3 Strategy si is stricttly dominated for player i if there is some
s0i ∈ Si such that
ui (s0i , s−i ) > ui (si , s−i )
for all s−i ∈ S−i .
Note that the inequality is strict for all s−i . A strategy is weakly domi-
nated if the inequality is weak for all s−i and strict for at least one s−i .
Proposition 1 If player i is rational he will not play a strictly dominated
strategy.
Proof: If strategy si is strictly dominated by strategy s0i we can deduce that
for any belief of player i we have Eµi (s−i ) ui (s0i , s−i ) > Eµi (s−i ) ui (si , s−i ).

5.2 Iterated Dominance

The hardest task in solving a game is to determine players’ beliefs. A lot of
games can be simplified by rationality and the knowledge that my opponent
is rational. To see that look at the Prisoner’s Dilemma.
Cooperating is a dominated strategy. A rational player would therefore
never cooperate. This solves the game since every player will defect. Notice
that I don’t have to know anything about the other player. This prediction
is interesting because it is the worst outcome in terms of joint surplus and
it would be Pareto improving if both players would cooperate. This result
highlights the value of commitment in the Prisoner’s dilemma - commitment
consists of credibly playing strategy C. For example, in the missile defence
example the ABM treaty (prohibits missile defence) and the START II agree-
ment (prohibits building of new missiles) effectively restrict both country’s
strategy sets to strategy C.
Now look at the next game.

8
 L M R

U 2,2 1,1 4,0

D 1,2 4,1 3,5

1. If the column player is rational he shouldn’t play M

2. Row player should realize this if he know that the other player is ra-
tional. Thus he won’t play D.

3. Column player should realize that R knows that C is rational. If he

knows that R is rational he knows that R won’t play D. Hence he won’t
play R. This leaves (U,L) as only outcome for rational players.

It’s worth while to discuss the level of knowledge required by players.

R has to know that C is rational. C has to know that R knows that C is
rational. This latter knowledge is a ’higher order’ form of knowledge. It’s
not enough to know that my opponent is rational - I also have to be sure
that my opponent knows that I am rational. There are even higher order
types of knowledge. I might know that my opponent is rational and that he
knows that I am. But maybe he doesn’t know that I know that he knows.
The higher the order of knowledge the more often the process of elimi-
nation can be repeated. For example, the game in section 4 of our second
experiment can be solved by the iterated deletion of dominated strategies.
An important concept in game theory is common knowledge (see next
lecture). We will assume throughout the course that rationality is common
knowledge between both players. Therefore, the iteration process can be
repeated arbitrarily often. However, the experiment showed that this as-
sumption might be too strong.

5.3 Formal Definition Of Iterated Dominance

• Step I: Define Si0 = Si

9
 • Step II: Define
© ¯ ª
Si1 = si ∈ Si0 ¯6 ∃s0i ∈ Si0 ui (s0i , s−i ) > ui (si , s−i ) ∀s−i ∈ S−i
0

• Step k+1: Define

© ¯ ª
Sik+1 = si ∈ Sik ¯6 ∃s0i ∈ Sik ui (s0i , s−i ) > ui (si , s−i ) ∀s−i ∈ S−i
k

Sik+1 is the set still not strictly dominated when you know your oppo-
k
nent uses some strategy in S−i .
0 1
Note restrictions S−i , S−i , ..
Players know that opponents are rational, know that opponents know
that they are rational ..., e.g. rationality is common knowledge.
T
• Step ∞: Let Si∞ = ∞ k
k=1 Si .
Note, that the process must stop after finitely many steps if the strategy
set is finite because the sets can only get smaller after each iteration.

Definition 4 G is solvable by pure strategy iterated strict dominance if S ∞

contains a single strategy profile.

Most games are not dominance solvable (coordination game, zero sum
game).
We have not specified the order in which strategies are eliminated. You
will show in the problem set that the speed and order of elimination does
not matter.
The same is not true for the elimination of weakly dominated strategies
as the next example shows.

L R

T 1,1 0,0

M 1,1 2,1

B 0,0 2,1

10
 We can first eliminate T and then L in which case we know that (2,1) is
played for sure. However, if we eliminate B first and then R we know that
(1,1) is being played for sure. So weak elimination does not deliver consistent
results and is therefore generally a less attractive option than the deletion of
strictly dominated strategies.

6 Example: Cournot Competition

Remark 2 For the mathematically inclined: With finite strategy sets the set
S ∞ is clearly non-empty because after each stage there must be some domi-
nant strategy left. For infinite strategy sets this is not as obvious. However,
one can show that for compact strategy sets each nested subset Sik is closed
and non-empty. Therefore the intersection of all nested subsets cannot be
empty.

Cournot competition with two firms can be solved by iterated deletion

in some cases. Specifically, we look at a linear demand function p = α −
β (qi + qj ) and constant marginal cost c such that the total cost of producing
qi units is cqi . It will be usefull to calculate the ’best-response’ function
BR (qj ) of each firm i to the quantity choice qj of the other firm. By taking
the first-order condition of the profit function you can easily show that the
best-response function for both firms (there is symmetry!) is
½ α−c qj
2β
− 2 if qj ≤ α−cβ
BRi (qj ) =
0 otherwise

The best-response function is decreasing in my belief of the other firm’s

action. Note, that for qj > α−c β
firm i makes negative profits even if it
chooses the profit maximizing output. It therefore is better off to stay out of
the market and choose qi = 0.
Initially, firms can set any quantity, i.e. S10 = S20 = <+ . However,
£ ¤ the
best-responses of each firm to any belief has to lie in the interval q, q with
q = 0 and q = α−c 2β
. All other strategies make negative profits, are therefore
dominated by some strategy inside this interval, and eliminated. ¡ ¢
In the second stage only the strategies S12 = S22 = [BR1 (q) , BR1 q ]
¡ ¡ ¢¢
survive, and in the third stage S13 = S23 = [BR2 BR1 q , BR2 (BR1 (q))]
(note, that the BR function is decreasing!).

11
 2k+1
Therefore
¡ ¡ in¢¢ the 2k + 1th stage only strategies in S1 = S22k+1 =
[BR2 ..BR1 q , BR2 (..BR1 (q))] survive.
It’s easy to show graphically that this interval shrinks in each iteration
and that the two limits converge to the intersection q1∗ = q2∗ of both best
response functions where q2∗ = BR2 (q1∗ ). Therefore, the Cournot game is
solvable through the iterated deletion of strictly dominated strategies.

Remark 3 It can be shown that the same game with three firms is NOT
dominance solvable. You have to show that on the problem set!

12
 Lecture IV: Nash Equilibrium
Markus M. Möbius
March 3, 2003

Readings for this class: Osborne and Rubinstein, Chapter 2.1-

2.3; FT has a good section on the connection to IDSDS.
Iterated dominance is an attractive solution concept because it only as-
sumes that all players are rational and that it is common knowledge that
every player is rational (although this might be too strong an assumption as
our experiments showed). It is essentially a constructive concept - the idea
is to restrict my assumptions about the strategy choices of other players by
eliminating strategies one by one.
For a large class of games iterated deletion of strictly dominated strategies
significantly reduces the strategy set. However, only a small class of games
are solvable in this way (such as Counot competition with linear demand
curve).
Today we introduce the most important concept for solving games: Nash
equilibrium. We will later show that all finite games have at least one Nash
equilibrium, and that the set of Nash equilibria is a subset of the strategy pro-
files which survive iterated deletion. In that sense, Nash equilibrium makes
stronger predictions than iterated deletion would but it is not excessively
strong in the sense that it does not rule out any equilibrium play for some
games.
Definition 1 A strategy profile s∗ is a pure strategy Nash equilibrium of G
if and only if ¡ ¢ ¡ ¢
ui s∗i , s∗−i ≥ ui si , s∗−i
for all players i and all si ∈ Si .
Definition 2 A pure strategy NE is strict if
¡ ¢ ¡ ¢
ui s∗i , s∗−i > ui si , s∗−i

1
 A Nash equilibrium captures the idea of equilibrium. Both players know
what strategy the other player is going to choose, and no player has an
incentive to deviate from equilibrium play because her strategy is a best
response to her belief about the other player’s strategy.

1 Games with Unique NE

1.1 Prisoner’s Dilemma
C D

C 3,3 −1,4

D 4,−1 0,0

This game has the unique Nash equilibrium (D,D). It is easy to check
that each player can profitably deviate from every other strategy profile. For,
example (C,C) cannot be a NE because player 1 would gain from playing D
instead (as would player 2).

1.2 Example II
L M R

U 2,2 1,1 4,0

D 1,2 4,1 3,5

In this game the unique Nash equilibrium is (U,L). It is easy to see that
(U,L) is a NE because both players would lose from deviating to any other
strategy.

2
 To show hat there are no other Nash equilibria we could check each other
strategy profile, or note that S1∞ = {U } and S2∞ = {L} and use:

Proposition 1 If s∗ is a pure strategy Nash equilibrium of G then s∗ ∈ S ∞ .

Proof: Suppose not. Then there exists T such that s∗ ∈ S1T × ... × SIT
but s∗ 6∈ S1T +1 × ... × SIT +1 . The definition of ISD implies that there
exists s0i ∈ SiT ⊆ Si such that ui (s0i , s−i ) > ui (s∗i¡, s−i ) for
¢ all s−i
¡∈
T
S−i¢.
0 0 ∗ ∗ ∗
Therefore there exists a si ∈ Si such that ui si , s−i > ui si , s−i
which contradicts that s∗ was a NE.

1.3 Cournot Competition

Using our new result it is easy to see that the unique Nash equilibrium of
the Cournot game with linear demand and constant marginal cost is the
intersection of the two BR functions since this was the only profile which
survived IDSDS.
A more direct proof notes that any Nash equilibrium has to lie on the
best response function of both players by the definition of NE:

Lemma 1 (q1∗ , q2∗ ) is a NE if and only if qi∗ ∈ BRi (q−i ) for all i.

We have derived the best response functions of both firms in previous

lectures (see figure 1).
½ α−c qj
2β
− 2 if qj ≤ α−c
β
BRi (qj ) =
0 otherwise

The NE is the solution to q1 = BR1 (q2 ) and q2 = BR2 (q1 ). This system
has exactly one solution. This can be shown algebraically or simply by
looking at the intersections of the BR graphs in figure 1. Because of symmetry
we know that q1 = q2 = q ∗ . Hence we obtain:
α − c q∗
q∗ = −
β 2

This gives us the solution q ∗ = 2(α−c)

3β
.
If both firms are not symmetric you have to solve a system of two equa-
tions with two unknowns (q1 and q2 ).

3
 Figure 1: BR functions of two firm Cournot game

BR1(q2)
2
q

(q*1,q*2)

BR2(q1)

(α−c)/2β (α−c)/β
q1

1.4 Bertrand Competition

Recall the Bertrand price setting game between two firms that sell a homoge-
nous product to consumers.
Two firms can simultaneously set any positive price pi (i = 1, 2) and
produce output at constant marginal cost c. They face a downward sloping
demand curve q = D (p) and consumers always buy from the lowest price
firm (this would not be true if the goods weren’t homogenous!). Therefore,
each firm faces demand

 D (pi ) if pi < pj
Di (p1 , p2 ) = D (pi ) /2 if pi = pj

0 if pi > pj

We also assume that D (c) > 0, i.e. firms can sell a positive quantity if
they price at marginal cost (otherwise a market would not be viable - firms
couldn’t sell any output, or would have to accumulate losses to do so).

Lemma 2 The Bertrand game has the unique NE (p∗1 , p∗2 ) = (c, c).

Proof: First we must show that (c,c) is a NE. It is easy to see that each firm
makes zero profits. Deviating to a price below c would cause losses to
the deviating firm. If any firm sets a higher price it does not sell any

4
 output and also makes zero profits. Therefore, there is no incentive to
deviate.
To show uniqueness we must show that any other strategy profile
(p1 , p2 ) is not a NE. It’s easiest to distinguish lots of cases.
Case I: p1 < c or p2 < c In this case one (or both players) makes
negative losses. This player should set a price above his rival’s price
and cut his losses by not selling any output.
Case II: c ≤ p1 < p2 or c ≤ p2 < p1 Assume first that c < p1 < p2
or c < p2 < p1 . In this case the firm with the higher price makes zero
profits. It could profitably deviate by setting a price equal to the rival’s
price and thus capture at least half of his market, and make strictly
positive profits. Now consider the case c = p1 < p2 or c = p2 < p1 .
Now the lower price firm can charge a price slightly above marginal
cost (but still below the price of the rival) and make strictly positive
profits.
Case III: c < p1 = p2 Firm 1 could profitably deviate by setting a
price p1 = p2 − ² > c. The firm’s profits before and after the deviation
are:
D (p2 )
πB = (p2 − c)
2
πA = D (p2 − ²) (p2 − ² − c)

Note, that the demand function is decreasing. We can therefore deduce:

D (p2 )
∆π = πA − πB ≥= (p2 − c) − ²D (p2 )
2

This expression (the gain from deviating) is strictly positive for suffi-
ciently small ². Therefore, (p1 , p2 ) cannot be a NE.

Remark 1 In problem 11 of problem set 1 you had to solve for the unique
Nash equilibrium when one firm (say 2) has higher marginal cost c2 > c1 .
Intuitively the price in the unique NE should be just below c2 - this would
keep firm 2 out of the market and firm 1 has no incentive to cut prices any
further. However, if firms can set any real positive price there is no pure NE.
Assume c2 = 10. If firm 1 sets prices at 9.99 it can do better by setting them
at 9.999 etc. Therefore, we have to assume that the pricing is discrete, i.e.

5
can only be done in multiples of pennies say. In this way, the unique NE has
firm 1 setting a price p1 = c2 minus one penny.

Food for Thought: How would you modify the Bertrand game to make
it solvable through IDSDS? Hint: You have to (a) discretize the strategy
space, and (b) assume that D (p) = 0 for some sufficiently high price.

6
 Lecture IV: Nash Equilibrium II - Multiple
Equilibria
Markus M. Möbius
March 3, 2003

Readings for this class: Osborne and Rubinstein, Chapter 2.1-

2.3

1 Multiple Equilibria I - Coordination

Lots of games have multiple Nash equilibria. In this case the problem arises
how to select between different equilibria.

1.1 New-York Game

Look at this simple coordination game:

E C

E 1,1 0,0

C 0,0 1,1

This game has two Nash equilibria - (E,E) and (C,C). In both cases no
player can profitably deviate. (E,C) and (C,E) cannot be NE because both
players would have an incentive to deviate.

1
1.2 Voting Game
Three players simultaneously cast ballots for one of three alternatives A,B
or C. If a majority chooses any policy that policy is implemented. If the
votes split 1-1-1 we assume that the status quo A is retained. Suppose the
preferences are:

u1 (A) > u1 (B) > u1 (C)

u2 (B) > u2 (C) > u2 (A)
u3 (C) > u3 (A) > u3 (B)

Claim 1 The game has several Nash equilibria including (A, A, A), (B, B, B),
(C, C, C),(A, B, A), and (A, C, C).

Informal Proof: In the first three cases no single player can change the
outcome. Therefore there is no profitable deviation. In the last two
equilibria each of the two A and two C players, respectively, is pivotal
but still would not deviate because it would lead to a less desirable
result.

1.3 Focal Points

In the New York game there is no sense in which one of the two equilibria is
’better’ than the other one.
For certain games Schelling’s (1961) concept of a tipping point can be a
useful way to select between different Nash equilibria. A focal point is a NE
which stands out from the set of NE - in games which are played frequently
social norms can develop. In one-shot games strategies which ’stand out’ are
frequently played. In both cases, players can coordinate by using knowledge
and information which is not part of the formal description of our game.
An example of a social norm is the fact that Americans drive on the right
hand side of the road. Consider the following game. Tom and Jerry drive in
two cars on a two lane road and in opposite directions. They can drive on
the right or on the left, but if they mis-coordinate they cause a traffic crash.
The game can be represented as follows:

2
 R L

R 1,1 0,0

L 0,0 1,1

We expect both drivers to choose (R,R) which is the social norm in this
game.
Next, let’s conduct a class experiment.

Class Experiment 1 You have to coordinate on what of the following four

actions - coordinating with your partner gives you a joint payoff of 1 Dollar.
Otherwise you both get zero Dollars. The actions are
{Fiat95, Fiat97, Saab98, Fiat98}.

We played the game with four pairs of students - three pairs coordinated
on SAAB98, one pair did not coordinate.
This experiment is meant to illustrate that a strategy which looks quite
distinct from the set of other available strategies (here, Fiats) can be a focal
point in a one-shot game (when no social norm can guide us).

2 Multiple Equilibria II - Battle of the Sexes

The payoffs in the Battle of the Sexes are assumed to be Dollars.

F O

F 2,1 0,0

O 0,0 1,2

3
 (F,F) and (O,O) are both Nash equilibria of the game. The Battle of the
Sexes is an interesting coordination game because players are not indifferent
on which strategy to coordinate. Men want to watch Football, while Women
want to go to the Opera.

Class Experiment 2 You are playing the battle of the sexes. You are player
2. Player 1 will make his choice first but you will not know what that move
was until you make your own. What will you play?

Last year: We divided the class up into men and women. 18 out of 25
men (i.e. 72 percent) chose the action which in case of coordination would
give them the higher payoff. In contrast, only 6 out of 11 women did the
same. These results replicate similar experiments by Rubinstein at Princeton
and Tel Aviv University. Men are simply more aggressive creatures...
When we aggregate up we found that 24 out of 36 people (66 percent)
play the preferred strategy in BoS.
Because there is an element of conflict in the BoS players use the framing
of the game in order to infer the strategies of their opponent. In the follow-
ing experiments the underlying game is always the above BoS. However, in
each case the results differ significantly from the basic experiment we just
conducted. This tells us that players signal their intention to each other, and
that the normal strategic form does not capture this belief formation process.

Class Experiment 3 You are player 1 in the Battle of the sexes. Player 2
makes the first move and chooses an action. You cannot observe her action
until you have chosen your own action. Which action will you choose.

Last year: Now a significantly higher number of students (17 instead of 12)
choose the less desirable action (O). Note, that the game is still the same
simultaneous move game as before. However, players seem to believe that
player 1 has an advantage by moving first, and they are more likely to ’cave
in’.

Class Experiment 4 You are player 1 in the Battle of the sexes. Before
actually playing the game, your opponent (player 2) had an opportunity to
make an announcement. Her announcement was ”I will play O”. You could
not make a counter-announcement. What will you play ?

4
Now 35 out of 36 students chose the less desirable action. The announcement
seems to strengthen beliefs that the other player will choose O.
This kind of communication is called cheap talk because this type of
message is costless to the sender. For exactly this reason, it should not
matter for the analysis of the game. To see that, simply expand the strategy
set of player 2. Instead of strategies F and O she now has 4 strategies - Ff,
Fo, Of, Oo - where strategy Ff means that player 2 plays F and announces
to play f, while Of means that player 2 announces O and plays f. Clearly,
the strategies Of and Oo yield exactly the same payoffs when played against
any strategy of player 1. Therefore, the game has exactly the same NE as
before. However, the announcement seems to have successfully signalled to
player 1 that player 2 will choose her preferred strategy.

Class Experiment 5 Two players are playing the Battle of the Sexes. You
are player 1. Before actually playing the game, player 2 (the wife) had an
opportunity to make a short announcement. Player 2 choose to remain silent.
What is your prediction about the outcome of the game?

Less than 12 people choose the less desirable action in this case. Apparently,
silence is interpreted as weakness.

3 Multiple Equilibria III - Coordination and

Risk Dominance
The following symmetric coordination game is given.

A B

A 9,9 −15,8

B 8,−15 7,7

5
Class Experiment 6 Ask class how many would choose strategy A in this
coordination game.

Observations:

1. This game has the two Nash equilibria, namely (A,A) and (B,B). Co-
ordinating on A Pareto dominates coordination on B. Unlike the New
York and the Battle of the Sexes game, one of equilibria is clearly ’bet-
ter’ for both players. We might therefore be tempted to regard (A,A)
as the more likely equilibrium.

2. However, lots of people typically choose strategy B in most experimen-

tal settings. Playing A seems too ’risky’ for many players.

3. Harsanyi-Selten developed the notion of risk-dominance. Assume that

you don’t know much about the other player and assign 50-50 prob-
ability to him playing A or B. Then playing A gives you utility -3 in
expectation while playing B gives you 7.5. Therefore, B risk-dominates
A.

4 Interpretations of NE
IDSDS is a constructive algorithm to predict play and does not assume that
players know the strategy choices of other players. In contrast, in a Nash
equilibrium players have precise beliefs about the play of other players, and
these beliefs are self-fulfilling. However, where do these beliefs come from?
There are several interpretations:

1. Play Prescription: Some outside party proposes a prescription of

how to play the game. This prescription is stable, i.e. no player has
an incentive to deviate from if she thinks the other players follow that
prescription.

2. Preplay communication: There is a preplay phase in which players

can communicate and agree on how to play the game. These agreements
are self-enforcing.

3. Rational Introspection: A NE seems a reasonable way to play a

game because my beliefs of what other players do are consistent with

6
 them being rational. This is a good explanation for explaining NE in
games with a unique NE. However, it is less compelling for games with
multiple NE.

4. Focal Point: Social norms, or some distinctive characteristic can in-

duce players to prefer certain strategies over others.

5. Learning Agents learn other players’ strategies by playing the same

game many time over.

6. Evolution: Agents are programmed to play a certain strategy and

are randomly matched against each other. Assume that agents do not
play NE initially. Occasionally ’mutations’ are born, i.e. players who
deviate from the majority play. If this deviation is profitable, these
agents will ’multiply’ at a faster rate than other agents and eventually
take over. Under certain conditions, this system converges to a state
where all agents play a Nash equilibrium, and mutating agents cannot
benefit from deviation anymore.

Remark 1 Each of these interpretations makes different assumptions about

the knowledge of players. For a play prescription it is sufficient that every
player is rational, and simply trusts the outside party. For rational introspec-
tion it has to be common knowledge that players are rational. For evolution
players do not even have to be rational.

Remark 2 Some interpretations have less problems in dealing with multi-

plicity of equilibria. If we believe that NE arises because an outside party
prescribes play for both players, then we don’t have to worry about multiplic-
ity - as long as the outside party suggests some Nash equilibrium, players
have no reason to deviate. Rational introspection is much more problematic:
each player can rationalize any of the multiple equilibria and therefore has
no clear way to choose amongst them.

7
 Lecture V: Mixed Strategies
Markus M. Möbius
March 3, 2003

Readings for this class: Osborne and Rubinstein, section 3.1

and 3.2

1 The Advantage of Mixed Strategies

Consider the following Rock-Paper-Scissors game: Note that RPS is a zero-
sum game.

R P S

R 0,0 −1,1 1,−1

P 1,−1 0,0 −1,1

S −1,1 1,−1 0,0

This game has no pure-strategy Nash equilibrium. Whatever pure strategy

player 1 chooses, player 2 can beat him. A natural solution for player 1 might
be to randomize amongst his strategies.
Another example of a game without pure-strategy NE is matching pen-
nies. As in RPS the opponent can exploit his knowledge of the other player’s
action.

1
 H T

H 1,−1 −1,1

T −1,1 1,−1

Fearing this what might the opponent do? One solution is to randomize
and play a mixed strategy. Each player could flip a coin and play H with
probability 12 and T with probability 12 .
Note that each player cannot be taken advantage of.

Definition 1 Let G be a game with strategy spaces S1 ,S2 ,..,SI . A mixed

strategy σi for player i is a probability distribution on
P Si i.e. for Si finite a
+
mixed strategy is a function σi : Si → < such that si ∈Si σi (si ) = 1.

Several notations are commonly used for describing mixed strategies.

1 1
1. Function (measure): σ1 (H) = 2
and σ1 (T ) = 2

2. Vector:
¡ If¢ the pure strategies are si1 ,..siNi write (σi (si1 ) , .., σi (siNi ))
e.g. 21 , 12 .
1
3. 2
H + 12 T

Class Experiment 1 Three groups of two people. Play RPS with each other
30 times. Calculate frequency with which each strategy is being played.

• Players are indifferent between strategies if opponent mixes equally

between all three strategies.

• In games such as matching pennies, poker bluffing, football run/pass

etc you want to make the opponent guess and you worry about being
found out.

2
2 Mixed Strategy Nash Equilibrium
Write Σi (also ∆ (Si )) for the set of probability distributions on Si .
Write Σ for Σ1 × .. × ΣI . A mixed strategy profile σ ∈ Σ is an I-tuple
(σ1 , .., σI ) with σi ∈ Σi .
We write ui (σi , σ−i ) for player i’s expected payoff when he uses mixed
strategy σi and all other players play as in σ−i .
X
ui (σi , σ−i ) = (1)
si ,s−i ui (si ,s−i )σi (si )σ−i (si )

Remark 1 For the definition of a mixed strategy payoff we have to assume

that the utility function fulfills the VNM axioms. Mixed strategies induce
lotteries over the outcomes (strategy profiles) and the expected utility of a
lottery allows a consistent ranking only if the preference relation satisfies
these axioms.
Definition 2 A mixed strategy NE of G is a mixed profile σ ∗ ∈ Σ such that
¡ ¢ ¡ ¢
ui σi∗ , σ−i
∗ ∗
≥ ui σi , σ−i
for all i and all σi ∈ Σi .

3 Testing for MSNE

The definition of MSNE makes it cumbersome to check that a mixed profile
is a NE. The next result shows that it is sufficient to check against pure
strategy alternatives.
Proposition 1 σ ∗ is a Nash equilibrium if and only if
¡ ¢ ¡ ¢
ui σi∗ , σ−i
∗ ∗
≥ ui si , σ−i
for all i and si ∈ Si .
Example 1 The strategy profile σ1∗ = σ2∗ = 12 H + 21 T is a NE of Matching
Pennies.
Because of symmetry is it sufficient to check that player 1 would not
deviate. If he plays his mixed strategy he gets expected payoff 0. Playing
his two pure strategies gives him payoff 0 as well. Therefore, there is no
incentive to deviate.
Note: Mixed strategies can help us to find MSNE when no pure strategy
NE exist.

3
4 Finding Mixed Strategy Equilibria I
Definition 3 In a finite game, the support of a mixed strategy σi , supp (σi ),
is the set of pure strategies to which σi assigns positive probability

supp (σi ) = {si ∈ Si |σi (si ) > 0}

Proposition 2 If σ ∗ is a mixed strategy Nash equilibrium and s0i ,s00i ∈ supp (σi∗ )
then ¡ ¢ ¡ ¢
ui s0i , σ−i
∗
= ui s00i , σ−i
∗

Proof: Suppose not. Assume WLOG that

¡ ¢ ¡ ¢
∗
ui s0i , σ−i ∗
> ui s00i , σ−i

with s0i ,s00i ∈ supp (σi∗ ).

Define a new mixed strategy σ̂i for player i by
 ∗ 0
 σi (si ) + σi∗ (s00i ) if si = s0i
σ̂i (si ) = 0 if si = s00i
 ∗
σi (si ) otherwise

We can calculate the gain from playing the modified stratgey:

¡ ∗
¢ ¡ ¢
ui σ̂i , σ−i − ui σi∗ , σ−i
∗
X ¡ ¢ X ¡ ¢ ∗
∗ ∗
= ui si , σ−i σ̂i (si ) − ui si , σ−i σi (si )
si ∈Si si ∈Si
X ¡ ¢
∗
= ui si , σ−i [σ̂i (si ) − σi∗ (si )]
si ∈Si
¡ ¢ ∗ 00 ¡ ¢ ∗ 00
= ui s0i , σ−i
∗
σi (si ) − ui s00i , σ−i
∗
σi (si )
> 0

Note that a mixed strategy NE is never strict.

The proposition suggests a process of finding MSNE.

1. Look at all possible supports for mixed equilibria.

2. Solve for probabilities and check if it works.

4
Example 2 Find all the Nash equilibria of the game below.

L R

U 1,1 0,4

D 0,2 2,1

It is easy to see that this game has no pure strategy Nash equilibria. For
a mixed strategy Nash equilibrium to exist player 1 has to be indifferent
between strategies U and D and player 2 has to be indifferent between L and
R. Assume player 1 plays U with probability α and player 2 plays L with
probability β.

u1 (U, σ2∗ ) = u1 (D, σ2∗ )

β = 2 (1 − β)
u2 (L, σ1∗ ) = u2 (R, σ1∗ )
α + 2 (1 − α) = 4α + (1 − α)

We can deduce that α = 14 and β = 23 . There is a unique mixed Nash

equilibrium with σ1∗ = 14 U + 34 D and σ2∗ = 23 L + 13 R

Remark 2 Recall the Battle of the Sexes experiments from last class. It
can be shown that the game has a mixed NE where each agent plays her
favorite strategy with probability 23 . This was not quite the proportion of
people playing it in class (but pretty close to the proportion of people choosing
it in the previous year)! In many instances of this experiment one finds that
men and women differed in their ’aggressiveness’. Does that imply that they
were irrational? No. In a mixed NE players are indifferent between their
strategies. As long as men and women are matched completely randomly
(i.e. woman-woman and man-man pairs are also possible) it only matters
how players mix in the aggregate! It does NOT matter if subgroups (i.e.
’men’ and ’women’) mix at different states, although it would matter if they

5
would play only against players within their subgroup. Interestingly, that
suggests that letting women ’segregate’ into their own communities should
make them more aggressive, and men less aggressive. The term ’aggressive’
is a bit misleading because it does not result in bigger payoffs. However, you
could come up with a story of lexicographic preferences - people care first of
all about payoffs, but everything else equal they want to fit gender stereotypes
- so playing ’football’ is good for men’s ego.

5 Finding Mixed Strategy Equilibria II

Finding mixed NE in 2 by 2 games is relatively easy. It becomes harder
if players have more than two strategies because we have to start worrying
about supports. In many cases it is useful to exploit iterated deletion in
order to narrow down possible supports.
Proposition 3 Let σ ∗ be a NE of G and suppose that σ ∗ (si ) > 0 then
si ∈ Si∞ , i.e. strategy si is not removed by ISD.
Proof: see problem set 2
Having introduced mixed strategies we can even define a tighter notion of
IDSDS. Consider the next game. No player has a strategy which is strictly
dominated by another pure strategy. However, C for player 2 is strictly
dominated by 12 L + 12 R. Thus we would think that C won’t be used.

L C R

U 1,1 0,2 0,4

M 0,2 5,0 1,6

D 0,2 1,1 2,1

6
After we delete C we note that M is dominated by 23 D + 13 U . Using the above
proposition we can conclude that the only Nash equilibria are the NE of the
2 by 2 game analyzed in the previous section. Since that game had a unique
mixed strategy equilibrium we can conclude that the only NE of the 3 by 3
game is σ1∗ = 41 U + 34 D and σ2∗ = 23 L + 13 R.
It is useful to adjust the formal definition of IDSDS and allow for mixed
strategy domination:

Definition 4 The set of strategy profiles surviving iterated strict dominance

is S ∞ = S1∞ × S2∞ × .. × SI∞ where
∞
\
Si∞ = Sik
k=1
Si0 = Si
© ¡ ¢ ª
Sik+1 = si ∈ Sik | 6 ∃σi ∈ ∆ Sik |ui (σi , s−i ) > ui (si , s−i ) ∀s−i ∈ S−i
k

Remark 3 Recall the above 3 by 3 game. If we would look for possible mixed
NE with supports (U,M) and (L,C) respectively, we would find a potential NE
2
3
U + 13 M, 56 L + 16 C. However, this is NOT a NE because player 2 would play
R instead.

Remark 4 In the RPS game we cannot reduce the set of strategies through
IDSDS. Therefore we have to check all possible supports and check if it works.

6 Finding Mixed Strategy Equilibria III

Definition 5 A correspondence F : A → B is a mapping which associates
to every element of a ∈ A a subset F (a) ⊂ B.

The mixed strategy best response correspondence for player i BRi :

Σ−i → Σi is defined by

BRi (σ−i ) = arg max ui (σi , σ−i )

σi ∈Σi

¡ ∗ ¢
Proposition 4 σ ∗ is a Nash equilibrium if and only if σi∗ ∈ BRi σ−i for
all i.

7
 In the 2 by 2 game we have:
 2
 U if β > 3
2
BR1 (βL + (1 − β) R) = {αU + (1 − α) D|α ∈ [0, 1]} if β = 3
 2
D if β < 3
 1
 L if α < 4
1
BR2 (αU + (1 − α) D) = {βL + (1 − β) R|β ∈ [0, 1]} if α = 4
 1
R if α > 4

We can graph both correspondences to find the set of Nash equilibria.

7 Interpretation of Mixed NE
1. Sometimes players explicitly flip coins. That fits games like Poker,
soccer etc., where players have to randomize credibly.

2. Large populations of players with each player playing a fixed strategy

and random matching. That’s very related to the social norm expla-
nation of pure Nash equilibrium.

3. Payoff uncertainty (Harsanyi, purification). Roughly their argument

goes as follows in the matching penny game. There are two types of
players - those who get slightly higher payoff from playing heads, and
those who get higher payoff from getting tails (their preferences are
almost the same - think of one guy getting 1 dollar and the other guy
getting 1 + ² = 1.01 dollars from playing head). Also, we assume that
there is an equal probability that my opponent is of type 1 or type
2. In this circumstances no player loses from just playing her favorite
strategy (i.e. a pure strategy) because it will do best on average. To
show that this is a NE we have to introduce the notion of incomplete
information which we don’t do just yet. Harsanyi-Selten then let the
payoff uncertainty ² go to 0 such that the game in the limit approaches
the standard matching pennies. Players’ ’average’ strategies converge
to the mixed equilibrium.

8
 Lecture VI: Existence of Nash equilibrium
Markus M. Möbius
March 3, 2003

Readings for this class: Osborne and Rubinstein, section 2.4

and Fudenberg and Tirole, chapter 1.3

1 Nash’s Existence Theorem

When we introduced the notion of Nash equilibrium the idea was to come
up with a solution concept which is stronger than IDSDS. Today we show
that NE is not too strong in the sense that it guarantees the existence of at
least one mixed Nash equilibrium in most games (for sure in all finite games).
This is reassuring because it tells that there is at least one way to play most
games.1
Let’s start by stating the main theorem we will prove:
Theorem 1 (Nash Existence)Every finite strategic-form game has a mixed-
strategy Nash equilibrium.
Many game theorists therefore regard the set of NE for this reason as the
lower bound for the set of reasonably solution concept. A lot of research has
gone into refining the notion of NE in order to retain the existence result
but get more precise predictions in games with multiple equilibria (such as
coordination games).
However, we have already discussed games which are solvable by IDSDS
and hence have a unique Nash equilibrium as well (for example, the two
thirds of the average game), but subjects in an experiment will not follow
those equilibrium prescription. Therefore, if we want to describe and predict
the behavior of real-world people rather than come up with an explanation
1
Note, that a pure Nash equilibrium is a (degenerate) mixed equilibrium, too.

1
of how they should play a game, then the notion of NE and even even IDSDS
can be too restricting.
Behavioral game theory has tried to weaken the joint assumptions of
rationality and common knowledge in order to come up with better theories
of how real people play real games. Anyone interested should take David
Laibson’s course next year.
Despite these reservation about Nash equilibrium it is still a very useful
benchmark and a starting point for any game analysis.
In the following we will go through three proofs of the Existence Theorem
using various levels of mathematical sophistication:
• existence in 2 × 2 games using elementary techniques

• existence in 2 × 2 games using a fixed point approach

• general existence theorem in finite games

You are only required to understand the simplest approach. The rest is for
the intellectually curious.

2 Nash Existence in 2 × 2 Games

Let us consider the simple 2 × 2 game which we discussed in the previous
lecture on mixed Nash equilibria:

L R

U 1,1 0,4

D 0,2 2,1

We next draw the best-response curves of both players. Recall that player
1’s strategy can be represented by a single number α such that σ1 = αU +
(1 − α)D while player 2’s strategy is σ2 = βL + (1 − β)R.

2
 Let’s find the best-response of player 2 to player 1 playing strategy α:

u2 (L, αU + (1 − α)D) = 2 − α
u2 (R, αU + (1 − α)D) = 1 + 3α (1)

Therefore, player 2 will strictly prefer strategy L iff 2 − α > 1 + 3α which

implies α < 14 . The best-response correspondence of player 2 is therefore:

 1 if α < 14
BR2 (α) = [0, 1] if α = 14 (2)

0 if α > 14

We can similarly find the best-response correspondence of player 1:


 0 if β < 23
BR1 (β) = [0, 1] if β = 23 (3)

1 if β > 23

We draw both best-response correspondences in a single graph (the graph is

in color - so looking at it on the computer screen might help you):

BR2(α) BR1(β)

2/3

1/4 α 1

We immediately see, that both correspondences intersect in the single point

α = 14 and β = 23 which is therefore the unique (mixed) Nash equilibrium of
the game.

3
 What’s useful about this approach is that it generalizes to a proof that
any two by two game has at least one Nash equilibriu, i.e. its two best
response correspondences have to intersect in at least one point.
An informal argument runs as follows:

1. The best response correspondence for player 2 maps each α into at

least one β. The graph of the correspondence connects the left and
right side of the square [0, 1] × [0, 1]. This connection is continuous
- the only discontinuity could happen when player 2’s best response
switches from L to R or vice versa at some α∗ . But at this switching
point player 2 has to be exactly indifferent between both strategies -
hence the graph has the value BR2 (α∗ ) = [0, 1] at this point and there
cannot be a discontinuity. Note, that this is precisely why we need
mixed strategies - with pure strategies the BR graph would generally
be discontinuous at some point.

2. By an analogous argument the BR graph of player 1 connects the upper

and lower side of the square [0, 1] × [0, 1].

3. Two lines which connect the left/right side and the upper/lower side
of the square respectively have to intersect in at least one point. Hence
each 2 by 2 game has a mixed Nash equilibrium.

3 Nash Existence in 2 × 2 Games using Fixed

Point Argument
There is a different way to prove existence of NE on 2 × 2 games. The
advantage of this new approach is that it generalizes easily to general finite
games.
Consider any strategy profile (αU + (1 − α)D, βL + (1 − β)R) represented
by the point (α, β) inside the square [0, 1]×[0, 1]. Now imagine the following:
player 1 assumes that player 2 follows strategy β and player 2 assumes that
player 1 follows strategy α. What should they do? They should play their
BR to their beliefs - i.e. player 1 should play BR1 (β) and player 2 should
play BR2 (α). So we can imagine that the strategy profile (α, β) is mapped
onto (BR1 (β), BR2 (α)). This would describe the actual play of both players
if their beliefs would be summarizes by (α, β). We can therefore define a

4
giant correspondence BR : [0, 1] × [0, 1] → [0, 1] × [0, 1] in the following way:
BR(α, β) = BR1 (β) × BR2 (α) (4)
The following figure illustrates the properties of the combined best-response
map BR:

BR2(α) BR1(β)

(α2,β2)

2/3

(α1,β1)
β

(BR1(β1),BR2(α1))
1/4 α 1 (BR1(β2),BR2(α2))

The neat fact about BR is that the Nash equilibria σ ∗ are precisely the
fixed points of BR, i.e. σ ∗ ∈ BR(σ ∗ ). In other words, if players have beliefs
σ ∗ then σ ∗ should also be a best response by them. The next lemma follows
directly from the definition of mixed Nash equilibrium:
Lemma 1 A mixed strategy profile σ ∗ is a Nash equilibrium if and only if it
is a fixed point of the BR correspondence, i.e. σ ∗ ∈ BR (σ ∗ ).
We therefore look precisely for the fixed points of the correspondence
BR which maps the square [0, 1] × [0, 1] onto itself. There is well developed
mathematical theory for these types of maps which we utilize to prove Nash
existence (i.e. that BR has at least one fixed point).

3.1 Kakutani’s Fixed Point Theorem

The key result we need is Kakutani’s fixed point theorem. You might have
used Brower’s fixed point theorem in some mathematics class. This is not

5
sufficient for proving the existence of nash equilibria because it only applies
to functions but not to correspondences.
Theorem 2 Kakutani A correspondence r : X → X has a fixed point
x ∈ X such that x ∈ r (x) if
1. X is a compact, convex and non-empty subset of <n .

2. r (x) is non-empty for all x.

3. r (x) is convex for all x.

4. r has a closed graph.

There are a few concepts in this definition which have to be defined:
Convex Set: A set A ⊆ <n is convex if for any two points x, y ∈ A the
straight line connecting these two points lies inside the set as well. Formally,
λx + (1 − λ) y ∈ A for all λ ∈ [0, 1].
Closed Set: A set A ⊆ <n is closed if for any converging sequence
{xn }∞ ∗ ∗
n=1 with xn → x as n → ∞ we have x ∈ A. Closed intervals such
as [0, 1] are closed sets but open or half-open intervals are not. For example
(0, 1] cannot be closed because the sequence n1 converges to 0 which is not in
the set.
Compact Set: A set A ⊆ <n is compact if it is both closed and bounded.
For example, the set [0, 1] is compact but the set [0, ∞) is only closed but
unbounded, and hence not compact.
Graph: The graph of a correspondence r : X → Y is the set {(x, y) |y ∈ r (x)}.
If r is a real function the graph is simply the plot of the function.
Closed Graph: A correspondence has a closed graph if the graph of the
correspondence is a closed set. Formally, this implies that for a sequence of
point on the graph {(xn , yn )}∞ ∗ ∗
n=1 such that xn → x and yn → y as n → ∞
∗ ∗ 2
we have y ∈ r (x ).
It is useful to understand exactly why we need each of the conditions in
Kakutani’s fixed point theorem to be fulfilled. We discuss the conditions by
looking correspondences on the real line, i.e. r : < → <. In this case, a fixed
point simply lies on the intersection between the graph of the correspondence
and the diagonal y = x. Hence Kakutani’s fixed point theorem tells us that
2
If the correspondence is a function then the closed graph requirement is equivalent to
assuming that the function is continuous. It’s easy to see that a continuous function has
a closed graph. For the reverse, you’ll need Baire’s category theorem.

6
a correspondence r : [0, 1] → [0, 1] which fulfills the conditions above always
intersects with the diagonal.

3.1.1 Kakutani Condition I: X is compact, convex and non-empty.

Assume X is not compact because it is not closed - for example X = (0, 1).
Now consider the correspondence r(x) = x2 which maps X into X. However,
it has no fixed point. Now consider X non-compact because it is unbounded
such as X = [0, ∞) and consider the correspondence r(x) = 1 + x which
maps X into X but has again no fixed point.
If X is empty there is clearly no fixed point. For convexity of X look at
the example X = [0, 13 ] ∪ [ 32 , 1] which is not convex because the set has a hole.
Now consider the following correspondence (see figure below):
½ 3
if x ∈ [0, 31 ]
r(x) = 4
1 (5)
4
if x ∈ [ 23 , 1]

This correspondence maps X into X but has no fixed point again.

3/4

1/4

1/3 x 2/3 1

From now on we focus on correspondences r : [0, 1] → [0, 1] - note that [0, 1]

is closed and bounded and hence compact, and is also convex.

7
3.1.2 Kakutani Condition II: r(x) is non-empty.
If r(x) could be empty we could define a correspondence r : [0, 1] → [0, 1]
such as the following:
 3
 4 if x ∈ [0, 13 ]
r(x) = ∅ if x ∈ [ 31 , 32 ] (6)
 1
4
if x ∈ [ 23 , 1]
As before, this correspondence has no fixed point because of the hole in the
middle.

3.1.3 Kakutani Condition III: r(x) is convex.

If r(x) is not convex, then the graph does not have to have a fixed point as
the following example of a correspondence r : [0, 1] → [0, 1] shows:

 1£ ¤ £ ¤ if x < 12
r(x) = 0, 13 ∪ 23 , 1 if x = 21 (7)

0 if x > 12

x 1/2 1

The graph is non-convex because r( 12 ) is not convex. It also does not have a
fixed point.

8
3.1.4 Kakutani Condition IV: r(x) has a closed graph.
This condition ensures that the graph cannot have holes. Consider the follow-
ing correspondence r : [0, 1] → [0, 1] which fulfills all conditions of Kakutani
except (4):  1
 £2 ¢ if x < 12
1 1
r(x) = , if x = 21 (8)
 14 2 1
4
if x > 2

x 1/2 1

£ ¢
Note, that r( 12 ) is the convex set 14 , 12 but that this set is not closed. Hence
the graph is not closed. For example, consider the sequence xn = 21 and
yn = 12 − n+2
1
for n ≥ 1. Clearly, we have yn ∈ r(xn ). However, xn → x∗ = 12
and yn → y ∗ = 12 but y ∗ ∈ / r(x∗ ). Hence the graph is not closed.

3.2 Applying Kakutani

We now apply Kakutani to prove that 2 × 2 games have a Nash equilibrium,
i.e. the giant best-response correspondence BR has a fixed point. We denote
the strategies of player 1 with U and D and the strategies of player 2 with
L and R.

9
 We have to check (a) that BR is a map from some compact and convex
set X into itself, and (b) conditions (1) to (4) of Kakutani.
• First note, that BR : [0, 1] × [0, 1] → [0, 1] × [0, 1]. The square X =
[0, 1] × [0, 1] is convex and compact because it is bounded and closed.
• Now check condition (2) of Kakutani - BR(σ) is non-empty. This is
true if BR1 (σ2 ) and BR2 (σ1 ) are non-empty. Let’s prove it for BR1 -
the proof for BR2 is analogous. Player 1 will get the following payoff
u1,β (α) from playing strategy α if the other player plays β:
u1,β (α) = αβu1 (U, L) + α(1 − β)u1 (U, R) +
+ (1 − α)βu1 (D, L) + (1 − α)(1 − β)u1 (D, R) (9)
The function u1,β is continuous in α. We also know that α ∈ [0, 1] which
is a closed interval. Therefore, we know that the continuous function
u1,β reaches its maximum over that interval (standard min-max result
from real analysis - continuous functions reach their minimum and max-
imum over closed intervals). Hence there is at least one best response
α∗ which maximizes player 1’s payoff.
• Condition (3) requires that if player 1 has tow best responses α1∗ U +
(1 − α1∗ )D and α2∗ U + (1 − α2∗ )D to player 2 playing βL + (1 − β)R then
the strategy where player 1 chooses U with probability λα1∗ + (1 − λ)α2∗
for some 0 < λ < 1 is also a best response (i.e. BR1 (β) is convex).
But since both the α1 and the α2 strategy are best responses of player
1 to the same β strategy of player 2 they also have to provide the same
payoffs to player 1. But this implies that if player 1 plays strategy α1
with probability λ and α2 with probability 1 − λ she will get exactly
the same payoff as well. Hence the strategy where she plays U with
probability λα1∗ +(1−λ)α2∗ is also a best response and her best response
set BR1 (β) is convex.
• The final condition (4) requires that BR has a closed graph. To show
this consider a sequence σ n = (αn , β n ) of (mixed) strategy profiles and
σ̃ n = (α̃n , β̃ n ) ∈ BR (σ n ). Both sequences are assumed to converge to
σ ∗ = (α∗ , β ∗ ) and σ̃ ∗ = (α̃∗ , β̃ ∗ ), respectively. We now want to show
that σ̃ ∈ BR (σ) to prove that BR has a closed graph.
We know that for player 1, for example, we have
u1 (α̃n , β n ) ≥ u1 (α0 , β n )

10
 for any α0 ∈ [0, 1]. Note, that the utility function is continuous in both
arguments because it is linear in α and β. Therefore, we can take the
limit on both sides while preserving the inequality sign:
u1 (α̃∗ , β ∗ ) ≥ u2 (α0 , β)
for all α0 ∈ [0, 1]. This shows that α˜∗ ∈ BR1 (β) and therefore σ̃ ∗ ∈
BR (σ ∗ ). Hence the graph of the BR correspondence is closed.
Therefore, all four Kakutani conditions apply and the giant best-response
correspondence BR has a fixed point, and each 2 × 2 game has a Nash
equilibrium.

4 Nash Existence Proof for General Finite

Case
Using the fixed point method it is now relatively easy to extend the proof
for the 2 × 2 case to general finite games.The biggest difference is that we
cannot represent a mixed strategy any longer with a single number such as α.
If player 1 has three pure strategies A1 ,A2 and A3 , for example, then his set
of mixed strategies is represented by two probabilities - for example, (α1 , α2 )
which are the probabilities that A1 and A2 are chosen. The set of admissible
α1 and α2 is described by:
Σ1 = {(α1 , α2 )|0 ≤ α1 , α2 ≤ 1 and α1 + α2 ≤ 1} (10)
The definition of the set of mixed strategies can be straightforwardly ex-
tended to games where player 1 has a strategy set consisting of n pure
strategies A1 ,..,An . Then we need n − 1 probabilities α1 ,..,αn−1 such that:
Σ1 = {(α1 , .., αn−1 )|0 ≤ α1 , .., αn−1 ≤ 1 and α1 + .. + αn−1 ≤ 1} (11)
So instead of representing strategies on the unit interval [0, 1] we have to
represent as elements of the simplex Σ1 .
Lemma 2 The set Σ1 is compact and convex.
Proof: It is clearly convex - if you mix between two mixed strategies you get
another mixed strategy. The set is also compact because it is bounded
i
(all |αi | ≤ 1) and closed. To see closedness take a sequence (α1i , .., αn−1 )
∗ ∗
of elements of Σ1 which converges to (α1 , ..). Then we have αi ≥ 0 and
Pn−1 ∗
i=1 αi ≤ 1 because the limit preserves weak inequalities. QED

11
 We can now check that all conditions of Kakutani are fulfilled in the gen-
eral finite case. Checking them is almost 1-1 identical to checking Kakutani’s
condition for 2 × 2 games.
Condition 1: The individual mixed strategy sets Σi are clearly non-
empty because every player has at least one strategy. Since Σi is compact
Σ = Σ1 ×...×ΣI is also compact. Hence the BR correspondence BR : Σ → Σ
acts on a compact and convex non-empty set.
Condition 2: For each player i we can calculate his utiltiy ui,σ−i (σi ) for
σi ∈ Σi . Since Σi is compact and ui,σ−i is continuous the set of payoffs is also
compact and hence has a maximum. Therefore, BRi (Σi ) is non-empty.
Condition 3: Assume that σi1 and σi2 are both BR of player i to σ−i .
Both strategies have to give player i equal payoffs then and any linear com-
bination of these two strategies has to be a BR for player i, too.
Condition 4: Assume that σ n is a sequence of strategy profiles and
σ̃ ∈ BR (σ n ). Both sequences converge to σ ∗ and σ̃ ∗ , respectively. We
n

know that for each player i we have

¡ ¢ ¡ ¢
ui σ̃in , σ−i
n
≥ ui σi0 , σ−i
n

for all σi0 ∈ Σi . Note, that the utility function is continuous in both arguments
because it is linear.3 Therefore, we can take the limit on both sides while
preserving the inequality sign:
¡ ¢ ¡ ¢
ui σ̃i∗ , σ−i
∗
≥ ui σi0 , σ−i
∗

¡ ∗ ¢
for all σi0 ∈ Σi . This shows that σ̃i∗ ∈ BRi σ−i and therefore σ̃ ∗ ∈ BR (σ ∗ ).
Hence the graph of the BR correspondence is closed.
So Kakutani’s theorem applies and the giant best-response map BR has
a fixed point.

3
It is crucial here that the set of pure strategies is finite.

12
 Lecture VII: Common Knowledge
Markus M. Möbius
March 4, 2003

Readings for this class: Osborne and Rubinstein, sections 5.1,5.2,5.4

Today we formally introduce the notion of common knowledge and discuss
the assumptions underlying players’ knowledge in the two solution concepts
we discussed so far - IDSDS and Nash equilibrium.

1 A Model of Knowledge
There is a set of states of nature Ω = {ω1 , ω2 , .., ωn } which represent the
uncertainty which an agent faces when making a decision.

Example 1 Agents 1, 2 have a prior over the states of nature

Ω = {ω1 = It will rain today, ω2 = It will be cloudy today,

ω3 = It will be sunny today }

where each of the three events is equally likely ex ante.

The knowledge of every agent i is represented by an information partition

Hi of the set Ω.

Definition 1 An information partition Hi is a collection {hi (ω) |ω ∈ Ω} of

disjoint subsets of Ω such that

• (P1) ω ∈ hi (ω),

• (P2) If ω 0 ∈ hi (ω) then hi (ω 0 ) = hi (ω).

1
Note, that the subsets hi (ω) span Ω. We can think of hi (ω) as the knowledge
of agent i if the state of nature is in fact ω. Property P1 ensures that the true
state of nature ω is an element of an agent’s information set (or knowledge) -
this is called the axiom of knowledge. Property P2 is a consistency criterion.
Assume for example, that ω 0 ∈ hi (ω) and that there is a state ω 00 ∈ hi (ω 0 )
but ω 00 6∈ hi (ω). Then in the state of nature is ω the decision-maker could
argue that because ω 00 is inconsistent with his information the true state can
not be ω 0 .

Example 1 (cont.) Agent 1 has the information partition

H1 = {{ω1 , ω2 } , {ω3 }}

So the agent has good information if the weather is going to be sunny but
cannot distinguish between bad weather.

We next define a knowledge function K.

Definition 2 For any event E (a subset of Ω) we have

K (E) = {ω ∈ Ω|hi (ω) ⊆ E} .

So the set K (E) is the collection of all states in which the decision maker
knows E.
We are now ready to define common knowledge (for simplicity we only
consider two players).

Definition 3 Let K1 and K2 be the knowledge functions of both players. An

event E ⊆ Ω is common knowledge between 1 and 2 in the state ω ∈ Ω if ω if
a member of every set in the infinite sequence K1 (E), K2 (E), K1 (K2 (E)),
K2 (K1 (E)) and so on.

This definition implies that player 1 and 2 knows E, they know that the
other player knows it, and so on.
There is an equivalent definition of common knowledge which is frequently
easier to work with.

Definition 4 An event F ⊆ Ω is self-evident between both players if for

all ω ∈ F we have hi (ω) ⊆ F for i = 1, 2. An event E ⊆ Ω is common
knowledge between both players in the state ω ∈ Ω if there is a self-evident
event F for which ω ∈ F ⊆ E.

2
Example 1 (cont.) Agent 2 has information function

H2 = {{ω1 } , {ω2 } , {ω3 }}

In this case the event E = {ω1 , ω2 } is common knowledge if the state of nature
is ω1 or ω2 . Both definition can be applied - E survives iterated deletion, but
is also self-evident.

We finally show that both definitions of common knowledge are equiva-

lent. We need the next proposition first.

Proposition 1 The following are equivalent:

1. Ki (E) = E for i = 1, 2

2. E is self evident between 1 and 2.

3. E is a union of members of the partition induced by Hi for i = 1, 2.

Proof: Assume a). Then for every ω ∈ E we have hi (ω) ⊆ E and b) follows.
c) follows because immediately. c) implies a).

We can now prove the following theorem.

Theorem 1 Definitions 3 and 4 are equivalent.

Proof: Assume that the event E is common knowledge in state ω according

to definition 3. First note, that

E ⊇ Ki (E) ⊇ Kj (Ki (E)) ...

Because Ω is finite and ω is a member of those subsets the infinite

regression must eventually produce a set F such that Ki (F ) = F .
Therefore, F is self-evident and we are done.
Next assume that the event E is common knowledge in state ω accord-
ing to definition 4. Then F ⊆ E, Ki (F ) = F ⊆ Ki (E) etc, and F is a
member of every of the regressive subsets Ki (Kj (...E...)) and so is ω.
This proves the theorem.

3
2 Dirty Faces
We have played the game in class. Now we are going to analyze it by using
the mathematical language we just developed. Recall, that any agent can
only see the faces of all n − 1 other agents but not her own. Furthermore, at
least one face is dirty.
First of all we define the states of nature Ω. If there are n players there
are 2n − 1 possible states (since all faces clean cannot be a state of nature).
It’s convenient to denote the states by the n-tuples ω = (C, C, D, .., C). We
also denote the number of dirty faces with |ω| and note that |ω| ≥ 1 by
assumption (there is at least one dirty face).
The initial information set of each agent in some state of nature ω has at
most two elements. The agent knows the faces of all other agents ω (−i) but
does not know if she has a clean or dirty face, i.e. hi (ω) = {(C, ω (−i)) , (D, ω (−i))}.
Initially, all agents information set has two elements except in the case |ω| = 1
and one agent sees only clean faces - then she know for sure that she has a
dirty face because all clean is excluded. You can easily show that the event
”There is at least one dirty face” is common knowledge as you would expect.
The game ends when at least player knows the state of the world for sure,
i.e. her knowledge partition hi (ω) consists of a single element. In the first
this will only be the case if the state of world is such that only a single player
has a dirt face.
What happens if no agent raises her hand in the first period? All agents
update their information partition and exclude all states of nature with just
one dirty face. All agents who see just one dirty face now know for sure the
state of nature (they have a dirty face!). They raise their hand and the game
is over. Otherwise, all agents can exclude states of nature with at most two
dirty faces. Agents who see two dirty faces now know the state of nature for
sure (they have a dirty face!). etc.
The state of nature with k dirty faces therefore gets revealed at stage k
of the game. At that point all guys with dirty faces know the state of nature
for sure.
Question: What happens if it is common knowledge that neither all faces
are clean, nor all faces are dirty?

Remark 1 The game crucially depends on the fact that it is common knowl-
edge that at least one agent has a dirty face. Assume no such information
would be known - so the state of the world where all faces are clean would

4
be a possible outcome. Then no agent in the first round would ever know for
sure if she had a dirty face. Hence the information partition would never get
refined after any number of rounds.

3 Coordinated Attack
This story shows that ’almost common knowledge’ can be very different from
common knowledge.
Two divisions of an army are camped on two hilltops overlooking a com-
mon valley. In the valley waits the enemy. If both divisions attack simultane-
ously they will win the battle, whereas if only one division attacks it will be
defeated. Neither general will attack unless he is sure that other will attack
with him.
Commander A is in peace negotiations with the enemy. The generals
agreed that if the negotiations fail, commander A will send a message to
commander B with an attack plan. However, there is a small probability ²
that the messenger gets intercepted and the message does not arrive. The
messenger takes one hour normally. How long will it take to coordinate on
the attack?
The answer is: never! Once commander B receives the message he has to
confirm it - otherwise A is not sure that he received it and will not attack.
But B cannot be sure that A receives his confirmation and will not attack
until he receives another confirmation from A. etc. The messenger can run
back and forth countless times before he is intercepted but the generals can
never coordinate with certainty.
Let’s define the state of nature to be (n, m) if commander A sent n
messages and received n−1 confirmation from commander B, and commander
B sent m messages and received m − 1 confirmations. We also introduce the
state of nature (0, 0). In that state the peace negotiations have succeeded,
and no attack is scheduled.1
The information partition of commander A is

HA = {{(0, 0)} , {(1, 0), (1, 1)} , {(2, 1), (2, 2)} , ..} . (1)
1
As was pointed out by an alert student in class this state is necessary to make this
exercise interesting. Otherwise, the generals could agree on an attack plan in advance,
and no communication would be necessary at all - the attack would be common knowledge
already.

5
The information partition of commander B is

HB = {{(0, 0), (1, 0)} , {(1, 1), (2, 1)} , ..} . (2)

Both commanders only attack in some state of the world ω if it is common

knowledge that commander B has sent a message, i.e. n ≥ 1 (the negotiations
have failed and an attack should occur). However, this event can never
be common knowledge for any state of nature (i.e. after any sequence of
messages) because there is no self-evident set F contained in the event E.
This is easy to verify: take the union of any collection of information sets of
commander A (only those can be candidates for a self-evident F ). Then ask
yourself whether such a set can be also the union of a collection of information
sets of commander B. The answer is no - there will always some information
set of B which ’stick out’ at either ’end’ of the candidate set F.

4 Knowledge and Solution Concepts

We finally apply our formal definition of knowledge to redefine IDSDS and
Nash equilibrium for 2-player games. We first have to define what we mean
with a ’state of the world’. Formally, the set Ω is the environment in which
the game is played. In each state we have:
• The action ai (ω) taken by agent i in state ω.

• µi (ω) is agent i’s belief about the actions taken by his opponent.

• Some information partition hi (ω) which describes player i’s knowledge

in state ω.
One way to generate the state of the world would be to take each possible
action profile s ∈ S and combine it with each possible belief µ ∈ Σ1 × Σ2 and
call this combination (s, µ) a ’state’.

4.1 Nash Equilibrium

Nash equilibrium restricts the information partition of players very strongly.
Basically, players (i) need to know other players’ actions, (ii) have beliefs
which are consistent with their knowledge, (iii) be rational.
Proposition 2 Suppose that in the state ω ∈ Ω each player i

6
 • knows the other players’ actions: hi (ω) ⊆ {ω 0 ∈ Ω|a−i (ω 0 ) = a−i (ω)}

• has a belief which is consistent with his knowledge: the support µi (ω)
is a subset of {a−i (ω 0 ) ∈ A−i : ω 0 ∈ hi (ω)}

• is rational: ai (ω) is a best-response of player i to µi (ω)

Then (ai (ω)) is a Nash equilibrium of G.

The proof is not difficult. The action of player i is a best-response to his

beliefs which in turn put probability 1 on the other players playing strategy
a−i .

4.2 IDSDS
For applying iterated deletion of strictly dominated strategies we can use a
less restrictive information partition.

Proposition 3 Suppose that in state ω in a two-player game it is com-

mon knowledge between players that each player’s belief is consistent with
his knowledge and that each player is rational. That is, suppose that there is
a self-evident event ω ∈ F such that for every ω 0 ∈ F and each player i we
have:

• the support µi (ω 0 ) is a subset of {a−i (ω 00 ) ∈ A−i : ω 00 ∈ hi (ω 0 )}

• is rational: ai (ω 0 ) is a best-response of player i to µi (ω 0 )

Then the action ai (ω) is an element of Si∞ .

7
 Lecture VIII: Learning
Markus M. Möbius
March 6, 2003

Readings: Fudenberg and Levine (1998), The Theory of Learn-

ing in Games, Chapter 1 and 2

1 Introduction
What are the problems with Nash equilibrium? It has been argued that Nash
equilibrium are a reasonable minimum requirement for how people should
play games (although this is debatable as some of our experiments have
shown). It has been suggested that players should be able to figure out
Nash equilibria starting from the assumption that the rules of the game, the
players’ rationality and the payoff functions are all common knowledge.1 As
Fudenberg and Levine (1998) have pointed out, there are some important
conceptual and empirical problems associated with this line of reasoning:

1. If there are multiple equilibria it is not clear how agents can coordinate
their beliefs about each other’s play by pure introspection.

2. Common knowledge of rationality and about the game itself can be

difficult to establish.
1
We haven’t discussed the connection between knowledge and Nash equilibrium. As-
sume that there is a Nash equilibrium σ ∗ in a two player game and that each player’s
best-response is unique. In this case player 1 knows that player 2 will play σ2∗ in response
to σ1∗ , player 2 knows that player 1 knows this etc. Common knowledge is important for
the same reason that it matters in the coordinated attack game we discussed earlier. Each
player might be unwilling to play her prescribed strategy if she is not absolutely certain
that the other play will do the same.

1
 3. Equilibrium theory does a poor job explaining play in early rounds of
most experiments, although it does much better in later rounds. This
shift from non-equilibrium to equilibrium play is difficult to reconcile
with a purely introspective theory.

1.1 Learning or Evolution?

There are two main ways to model the processes according to which players
change their strategies they are using to play a game. A learning model is
any model that specifies the learning rules used by individual players and
examines their interaction when the game (or games) is played repeatedly.
These types of models will be the subject of today’s lecture.
Learning models quickly become very complex when there are many play-
ers involved. Evolutionary models do not specifically model the learning
process at the individual level. The basic assumption there is that some un-
specified process at the individual level leads the population as a whole to
adopt strategies that yield improved payoffs. These type of models will the
subject of the next few lectures.

1.2 Population Size and Matching

The natural starting point for any learning (or evolutionary) model is the
case of fixed players. Typically, we will only look at 2 by 2 games which
are played repeatedly between these two fixed players. Each player faces the
task of inferring future play from the past behavior of agents.
There is a serious drawback from working with fixed agents. Due to
the repeated interaction in every game players might have an incentive to
influence the future play of their opponent. For example, in most learning
models players will defect in a Prisoner’s dilemma because cooperation is
strictly dominated for any beliefs I might hold about my opponent. However,
if I interact frequently with the same opponent, I might try to cooperate in
order to ’teach’ the opponent that I am a cooperator. We will see in a future
lecture that such behavior can be in deed a Nash equilibrium in a repeated
game.
There are several ways in which repeated play considerations can be as-
sumed away.

1. We can imagine that players are locked into their actions for quite

2
 a while (they invest infrequently, can’t build a new factory overnight
etc.) and that their discount factors (the factor by which they weight
the future) is small compared that lock-in length. It them makes sense
to treat agents as approximately myopic when making their decisions.

2. An alternative is to dispense with the fixed player assumption, and

instead assume that agents are drawn from a large population and are
randomly matched against each other to play games. In this case, it is
very unlikely that I encounter a recent opponent in a round in the near
future. This breaks the strategic links between the rounds and allows
us to treat agents as approximately myopic again (i.e. they maximize
their short-term payoffs).

2 Cournot Adjustment
In the Cournot adjustment model two fixed players move sequentially and
choose a best response to the play of their opponent in the last period.
The model was originally developed to explain learning in the Cournot
model. Firms start from some initial output combination (q10 , q20 ). In the
first round both firms adapt their output to be the best response to q20 . They
therefore play (BR1 (q20 ) , BR2 (q10 )).
This process is repeated and it can be easily seen that in the case of linear
demand and constant marginal costs the process converges to the unique
Nash equilibrium. If there are several Nash equilibria the initial conditions
will determine which equilibrium is selected.

2.1 Problem with Cournot Learning

There are two main problems:

• Firms are pretty dim-witted. They adjust their strategies today as if

they expect firms to play the same strategy as yesterday.

• In each period play can actually change quite a lot. Intelligent firms
should anticipate their opponents play in the future and react accord-
ingly. Intuitively, this should speed up the adjustment process.

3
 BR1(q2)
q2

0 0 1 0
(q1,q2) (q1,q2)

(q1,q2)
1 2

(q* ,q* )
1 2

BR2(q1)

(α−c)/2β (α−c)/β
q1

Cournot adjustment can be made more realistic by assuming that firms

are ’locked in’ for some time and that they move alternately. Firms 1 moves
in period 1,3,5,... and firm 2 moves in periods 2,4,6,.. Starting from some
initial play (q10 , q20 ), firms will play (q11 , q20 ) in round 1 and (q11 , q22 ) in round 2.
Clearly, the Cournot dynamics with alternate moves has the same long-run
behavior as the Cournot dynamics with simultaneous moves.
Cournot adjustment will be approximately optimal for firms if the lock-
in period is large compared to the discount rate of firms. The less locked-in
firms are the smaller the discount rate (the discount rate is the weight on
next period’s profits).
Of course, the problem with the lock-in interpretation is the fact that it is
not really a model of learning anymore. Learning is irrelevant because firms
choose their optimal action in each period.

3 Fictitious Play
In the process of fictitious play players assume that their opponents strategies
are drawn from some stationary but unknown distribution. As in the Cournot
adjustment model we restrict attention to a fixed two-player setting. We also
assume that the strategy sets of both players are finite.

4
 In fictitious play players choose the best response to their assessment of
their opponent’s strategy. Each player has some exogenously given weighting
function κ0i : S−i → <+ . After each period the weights are updated by adding
1 to each opponent strategy each time is has been played:
½ t−1
t κi (s−i ) if s−i 6= st−1
−i
κi (s−i ) =
κt−1
i (s−i ) + 1 if s −i = st−1
−i

Player i assigns probability γit (s−i ) to strategy profile s−i :

κti (s−i )
γit (s−i ) = P t
s̃−i ∈S−i κi (s̃−i )

The player then chooses a pure strategy which is a best response to his
assessment of other players’ strategy profiles. Note that there is not neces-
sarily a unique best-response to every assessment - hence fictitious play is
not always unique.
We also define the empirical distribution dti (si ) of each player’s strategies
as Pt
t I t̃ (si )
di (si ) = t̃=0
t
The indicator function is set to 1 if the strategy has been played in period t̃
and 0 otherwise. Note, that as t → ∞ the empirical distribution dtj of player
j’s strategies approximate the weighting function κti (since in a two player
game we have j = −i).
Remark 1 The updating of the weighting function looks intuitive but also
somewhat arbitrary. It can be made more rigorous in the following way.
Assume, that there are n strategy profiles in S−i and that each profile is
played by player i’s opponents’ with probability p (s−i ). Agent i has a prior
belief according to which these probabilities are distributed. This prior is
a Dirichlet distribution whose parameters depend on the weighting function.
After each round agents update their prior: it can be shown that the posterior
belief is again Dirichlet and the parameters of the posterior depend now on
the updated weighting function.

3.1 Asymptotic Behavior

Will fictitious play converge to a Nash equilibrium? The next proposition
gives a partial answer.

5
Proposition 1 If s is a strict Nash equilibrium, and s is played at date t in
the process of fictitious play, s is played at all subsequent dates. That is, strict
Nash equilibria are absorbing for the process of fictitious play. Furthermore,
any pure-strategy steady state of fictitious play must be a Nash equilibrium.

Proof : Assume that s = (si , sj ) is played at time t. This implies that si is

a best-response to player i’s assessment at time t. But his next period
assessment will put higher relative weight on strategy sj . Because si is
a BR to sj and the old assessment it will be also a best-response to the
updated assessment. Conversely, if fictitious play gets stuck in some
pure steady state then players’ assessment converge to the empirical
distribution. If the steady state is not Nash players would eventually
deviate.

A corollary of the above result is that fictitious play cannot converge to

a pure steady state in a game which has only mixed Nash equilibria such as
matching pennies.

H T

H 1,−1 −1,1

T −1,1 1,−1

Assume that both players have initial weights weights (1.5,2) and (2,1.5).
Then fictitious play cycles as follows: In the first period, 1 and 2 play T, so
the weights the next period are (1.5,3) and (2, 2.5). Then 1 plays T and 2
plays H for the next two periods, after which 1’s weights are (3.5,3) and 2’s
are (2,4.5). At this point 1 switches to H, and both players play H for the
next three periods, at which point 2 switches to T, and so on. It may not be
obvious, but although the actual play in this example cycles, the empirical

6
 ¡1 ¢
distribution over each player’s strategies are converging to ,1
2 2
- this is
precisely the unique mixed Nash equilibrium.
This observation leads to a general result.

Proposition 2 Under fictitious play, if the empirical distributions over each

player’s choices converge, the strategy profile corresponding to the product of
these distributions is a Nash equilibrium.

Proof : Assume that there is a profitable deviation. Then in the limit at

least one player should deviate - but this contradicts the assumption
that strategies converge.

These results don’t tell us when fictitious play converges. The next the-
orem does precisely that.

Theorem 1 Under fictitious play the empirical distributions converge if the

stage has generic payoffs and is 2 2, or zero sum, or is solvable by iterated
strict dominance.

We won’t prove this theorem in this lecture. However, it is intuitively clear

why fictitious play observes IDSDS. A strictly dominated strategy can never
be a best response. Therefore, in the limit fictitious play should put zero
relative weight on it. But then all strategies deleted in the second step can
never be best responses and should have zero weight as well etc.

3.2 Non-Convergence is Possible

Fictitious play does not have to converge at all. An example for that is due
to Shapley.

7
 L M R

T 0,0 1,0 0,1

M 0,1 0,0 1,0

D 1,0 0,1 0,0

¡ ¢
The unique mixed NE of the game is s1 = s2 = 31 , 13 , 13 .
If the initial play is (T, M ) then the sequence becomes (T, M ), (T, R),
(M, R), (M, L), (D, L), (D, M ), (T, M ).
One can show that the number of time each profile is played increases at
a fast enough rate such that the play never converges. Also note, that the
diagonal entries are never played.

3.3 Pathological Convergence

Convergence in the empirical distribution of strategy choices can be mis-
leading even though the process converges to a Nash equilibrium. Take the
following game:

8
 A B

A 0,0 1,1

B 1,1 0,0

¡ √ ¢
Assume that the initial weights are 1, 2 for both players. In the first
period both players think
¡ √ the¢ other will play B, so both play A. The next pe-
riod the weights are 2, 2 , and both play B; the outcome is the alternating
sequence (B, B), (A, A), (B, B), and so on. The empirical frequencies of each
player’s choices converge to 1/2, 1/2, which is the Nash equilibrium. The
realized play is always on the diagonal, however, and both players receive
payoff 0 each period. Another way of putting this is that the empirical joint
distribution on pairs of actions does not equal the product of the two marginal
distributions, so the empirical joint distribution corresponds to correlated as
opposed to independent play.
This type of correlation is very appealing. In particular, agents don’t seem
to be smart enough to recognize cycles which they could exploit. Hence the
attractive property of convergence to a Nash equilibrium can be misleading
if the equilibrium is mixed.

9
 Lecture IX: Evolution
Markus M. Möbius
March 15, 2003

Readings: Fudenberg and Levine (1998), The Theory of Learn-

ing in Games, Chapter 3

1 Introduction
For models of learning we typically assume a fixed number of players who
find out about each other’s intentions over time. In evolutionary models the
process of learning is not explicitly modeled. Instead, we assume that strate-
gies which do better on average are played more often in the population over
time. The biological explanation for this is that individuals are genetically
programmed to play one strategy and their reproduction rate depends on
their fitness, i.e. the average payoff they obtain in the game. The economic
explanation is that there is social learning going on in the background -
people find out gradually which strategies do better and adjust accordingly.
However, that adjustment process is slower than the rate at which agents
play the game.
We will focus initially on models with random matching: there are N
agents who are randomly matched against each other over time to play a
certain game. Frequently, we assume that N as infinite. We have discussed
in the last lecture that random matching gives rise to myopic play because
there are no repeated game concerns (I’m unlikely to ever encounter my
current opponent again).
We will focus on symmetric n by n games for the purpose of this course.
In a symmetric game each player has the same strategy set and the payoff
matrix satisfies ui (si , sj ) = uj (sj , si ) for each player i and j and strategies
si , sj ∈ Si = Sj = {s1 , .., sn }. Many games we encountered so far in the

1
course are symmetric such as the Prisoner’s Dilemma, Battle of the Sexes,
Chicken and all coordination games. In symmetric games both players face
exactly the same problem and their optimal strategies do not depend on
whether they play the role of player 1 or player 2.
An important assumption in evolutionary models is that each agent plays
a fixed pure strategy until she dies, or has an opportunity to learn and about
her belief. The game is fully specified if we know the fraction of agents
who play strategy s1 , s2 , .., sn which we denote with x1 , x2 , .., xn such that
P n
i=1 xi = 1.

2 Mutations and Selection

Every model of evolution relies on two key concepts - a mutation mechanism
and a selection mechanism. We have already discussed selection - strategies
spread if they give above average payoffs. This captures social learning in a
reduced form.
Mutations are important to add ’noise’ to the system (i.e. ensure that
xi > 0 at all times) and prevent it from getting ’stuck’. For example, in
a world where players are randomly matched to play a Prisoner’s Dilemma
mutations make sure that it will never be the case that all agents cooperate or
all agents defect because there will be random mutations pushing the system
away from the two extremes.1

3 Replicator Dynamics
The replicator dynamics is one particular selection mechanism which captures
the notion that strategies with above average payoff should spread in the
population. Typically, the replicator dynamics is modelled without allowing
for mutations - the dynamics therefore becomes deterministic.
Since the stage game is symmetric we know that u (si , sj ) = u1 (si , sj ) =
u2 (sj , si ) . The average payoff of strategy si for a player is u (si , x) since he
is randomly matched with probability xj against agents playing sj (x =
1
If we start from an all-cooperating state, mutating agents will defect and do better.
Hence they spread, and finally take over. Without mutations the system might be ’stuck’
in the all-cooperating state.

2
 Pn
(x1 , x2 , .., xn )). The average payoff of all strategies is i=1 xi u (si , x) =
u (x, x).
Strategy si does better than the average strategy if u (si , x) > u (x, x),
and worse otherwise. A minimum requirement for a selection mechanism is
that sgn (ẋi (t)) = sgn [u (si , x) − u (x, x)]. The share xi increases over time
if and only if strategy si does better than average. The replicator dynamics
is one particular example:
Definition 1 In the replicator dynamics the share xi of the population play-
ing strategy si evolves over time according to:
ẋi
= u (si , x) − u (x, x)
xi
If xi = 0 at time 0 then we have xi = 0 at all subsequent time periods: if
nobody plays strategy si then the share of population playing it can neither
decrease not increase.
The next proposition makes sure that the definition is consistent (i.e.
population share always sum up to 1).
Proposition 1 The population shares always sum up to 1.

Proof: We can write:

X X X
ẋi = xi u (si , x) − xi u (x, x) = u (x, x) − u (x, x) = 0
P
This establishes that xi = const. The constant has to be 1 because
the population shares sum up to 1 initially.

3.1 Steady States and Nash Equilibria

Definition 2 The strategy σ is a steady state if for xi = σi (si ) we have
dx
dt
= 0.

Proposition 2 If σ is the strategy played by each player in a symmatric

mixed NE then it is a steady state.

Proof: In a NE each player has to be indifferent between the strategies in

her support. Therefore, we have u (si , x) = u (x, x).

Note, that the reverse is NOT true. If all players cooperate in a Prisoner’s
Dilemma this will be a steady state (since there are no mutations).

3
3.1.1 Example I
In 2 by 2 games the replicator dynamics is easily understood. Look at the
following game:
A B

A 0,0 1,1

B 1,1 0,0

There are only two types in the population and x = (xA , xB ). It’s enough to
keep track of xA .
ẋA
= xB − 2xA xB = (1 − xA ) (1 − 2xA ) (1)
xA

It’s easy to see that ẋA > 0 for 0 < xA < 12 and ẋA < 0 for 1 > xA > 21 . This
makes xA = 1/2 a ’stable’ equilibrium (see below for a precise definition).

3.1.2 Example II
Now look at the New York game.

4
 E C

E 1,1 0,0

C 0,0 1,1

We can show:
ẋE
= xE − (xE xE + xC xC ) = (1 − xE ) (2xE − 1) (2)
xE
1
Now the steady state xE = 2
is ’unstable’.

3.2 Stability
Definition 3 A steady state σ is stable if for all ² > 0 there exists δ > 0
such that if the process starts a distance δ away from the steady state it will
never get further away than ².

The mixed equilibrium is stable in example I and unstable in example II.

Definition 4 A steady state σ is asymptotically stable if there exists some

δ > 0 such that the process converges to σ if it starts from a distance at most
δ away from the steady state.

The mixed equilibrium in example I is asymptotically stable.

Definition 5 A steady state σ is globally stable if the process converges to

the steady state from any initial state where xi > 0 for all si .

Stability can be interpreted as a form of equilibrium selection.

Theorem 1 If the steady state σ is stable then it is a NE.

5
Proof: Assume not. Then there exists a profitable deviation si such that
u (si , σ) − u (σ, σ) = b > 0. Because the linear utility function is uni-
formly continuous there exists some ² such that for all x a distance less
than ² away we have |u (si , x) − u (si , σ)| < 4b and |u (x, x) − u (σ, σ)| <
b
4
. This implies that |u (si , x0 ) − u (x, x)| > 2b . Because σ is stable
we know that for x close enough to σ (less ¡ than ¢a distance δ the dy-
1 1
namics converges to σ. So take x (0) = 1 − 2 δ x + 2 δsi . Then we
δ
b
have dxdt
i
= xi (u (si , x) − u (x, x)) ≥ xi 2b ≥ 2
2
. But this implies that
x (t) → ∞ which is a contradiction.

3.2.1 Example III

This part is harder and is NOT required for the exam.
The mixed equilibrium in the RPS game is stable but not asymptotically
stable. The RPS game is harder to analyze because each player has three
possible strategies. This implies that there are two differential equations to
keep track of.

R P S

R 0,0 −1,1 1,−1

P 1,−1 0,0 −1,1

S −1,1 1,−1 0,0

We can concentrate on xR and xP . The average payoff is

u (x, x) = xR [−xP + xS ] + xP [xR − xS ] + xS [−xR + xP ] (3)

= 0 (4)

6
We then get:
ẋR
= −xP + xS (5)
xR
ẋP
= xR − xS (6)
xP
¡ ¢
The unique mixed equilibrium 13 , 13 , 13 is the only steady state of the system.
To see whether it is stable we have to linearize the system around the
steady state. We define x̃i = xi − 13 and obtain:

3x̃˙ R = −x̃R − 2x̃P (7)

3x̃˙ P = 2x̃R + x̃P (8)
√
We have to find the eigenvalues of the system which are λ = ± 3i. This
implies that the population shares ’circle’ around the steady state.

4 ESS-Evolutionary Stable States

The ESS concept concentrates on the role of mutations. Intuitively, the
stability notion in the replicator dynamics is already a selection criterion
because if the system is disturbed a little bit, it moves away from unstable
steady states. The ESS concept expands on this intuition.

Definition 6 The state x is ESS if for all y 6= x there exists ² such that
u (x, (1 − ²) x + ²y) > u (y, (1 − ²) x + ²y) for all 0 < ² < ².

This definition captures the idea that a stable state is impervious to muta-
tions since they do worse than the original strategy.

Proposition 3 x is ESS iff for all y 6= x either (a) u (x, x) > u (y, x) or (b)
u (x, x) = u (y, x) and u (x, y) > u (y, y).

The following results establish the link between Nash equilibrium and
ESS.

Proposition 4 If x is ESS then it is a NE.

Proposition 5 If x is a strict NE then it is an ESS.

7
Proposition 6 If x is a totally mixed ESS then it is the unique ESS.

The next theorem establishes the link between ESS and stability under
the replicator dynamics.

Theorem 2 If x is an ESS then it is asymptotically stable under the Repli-

cator Dynamics.

5 Stochastic Stability
Stochastic stability combines both mutations and a selection mechanism. It
provides a much more powerful selection mechanism for Nash equilibria than
ESS and the replicator dynamics.
The ESS concept gives us some guidance as to which Nash equilibria are
stable under perturbations or ’experimentation’ by agents. The replicator
dynamics tells us how a group of agents can converge to some steady state
starting from initial conditions. However, selection relies in many cases on the
initial conditions (take the coordination game, for example). In particular,
we cannot select between multiple strict equilibria.
For this section we concentrate on generic coordination games:

A B

A a,a b,c

B c,b d,d

We assume, that a > c and d > b such that both (A, A) and (B, B) are NE
of the game. We assume that a + b > c + d such that A is the risk-dominant

8
strategy for each player. Note, that the risk-dominant NE is not necessarily
the Pareto optimal NE.
We have seen in experiments that agents tend to choose A. Can we justify
this with an evolutionary story?
YES!
Assume that there is a finite number n of agents who are randomly
matched against each other in each round. Assume that agents choose the
best response to whatever strategy did better in the population in the last
period. This is called the BR dynamics. Clearly, all agents will choose A if
d−b
xA > q ∗ = a−b+d−c . Because A is risk-dominant we have q ∗ < 21 .
There are also mutations in each period. Specifically, with probability ²
each agent randomizes between both strategies.
We define the basin of attraction of xA = 1 (everybody plays A) to be
BA = [q ∗ , 1] and the basin of attraction of xA = 0 to be [0, q ∗ ]. Whenever
the initial state of the system is within the basin of attraction it converges
to all A/ all B for sure if there are no mutations. We define the radius of the
basin BA to be the number of mutations it takes to ’jump out’ of the state
all A. We get RA = (1 − q ∗ ) n. Similarly, we define the co-radius CRA as the
number of mutations it takes at most to ’jump into’ the basin BA . We get
CRA = q ∗ n.

Theorem 3 If CRA < RA then the state ’all A’ is stochastically stable. The
waiting time to reach the state ’all A’ is of the order ²CRA .

Therefore, the risk-dominant equilibrium is stochastically stable as q ∗ < 12 .

5.1 The Power Local Interaction

Local interaction can significantly speed up the evolution of the system. As-
sume, that agents are located on the circle and play the BR to average play of
their direct neighbors in the previous period. It can be shown that CRA = 2
and CRA = n2 . The convergence is a lot faster than under global interaction.

9
 Lecture X: Extensive Form Games
Markus M. Möbius
April 9, 2003

Readings for this class: OR (section 6.1), FT (sections 3.2.1 and

3.3.1), Gibbons (Chapter 2), Dutta (Chapter 11).

1 Introduction
While models presented so far are fairly general in some ways it should be
noted that they have one main limitation as far as accuracy of modeling goes
- in each game each player moves once and moves simultaneously.
This misses common features both of many classic games (bridge, chess)
and of many economic models.1 A few examples are:

• auctions (sealed bid versus oral)

• executive compensation (contract signed; then executive works)

• patent race (firms continually update resources based on where oppo-

nent are)

• price competition: firms repeatedly charge prices

• monetary authority and firms (continually observe and learn actions)

Topic today is how to represent and analyze such games.

1
Gibbons is a good reference for economic applications of extensive form games.

1
2 Extensive Form Games
The extensive form of a game is a complete description of

1. The set of players.

2. Who moves when and what their choices are.

3. The players’ payoffs as a function of the choices that are made.

4. What players know when they move.

2.1 Example I: Model of Entry

Currently firm 1 is an incumbent monopolist. A second firm 2 has the oppor-
tunity to enter. After firm 2 makes the decision to enter, firm 1 will have the
chance to choose a pricing strategy. It can choose either to fight the entrant
or to accommodate it with higher prices.

In Out

1 2
0
F A

−1 1
−1 1

2.2 Example II: Stackelberg Competition

Suppose firm 1 develops a new technology before firm 2 and as a result has
the opportunity to build a factory and commit to an output level q1 before
firm 2 starts. Firm 2 then observes firm 1 before picking its output level q2 .
For concreteness suppose qi ∈ {0, 1, 2} and market demand is p (Q) = 3 − Q.
The marginal cost of production is 0.

2
 1

q1=0 q1=2
q1=1

2 2 2

0 1 2 0 1 2 0 1 2

0 0 0 2 1 0 2 0 −2

0 2 2 0 1 0 0 0 −2

2.3 Example III: Matching Pennies

So far we assumed that players can observe all previous moves. In order
to model the standard matching pennies game in extensive form we have to
assume that the second player cannot observe the first player’s move.
Sequential matching pennies is represented as follows:

H T

2 2

H T H T

1 −1 −1 1

−1 1 1 −1

If we want to indicate that player 2 cannot observe the move of player 1 we

depict the game as follows:

3
 1

H T

2 2

H T H T

1 −1 −1 1

−1 1 1 −1

The extensive form representation allows that players can ’forget’ infor-
mation. For example we can assume that in a game with 4 rounds player 2
can observe player 1’s move in round 1, but in round 4 he has forgotten the
move of player 1. In most cases, we assume perfect recall which rules out
that players have such ’bad memory’.2

3 Definition of an Extensive Form Game

Formally a finite extensive form game consists of

1. A finite set of players.

2. A finite set T of nodes which form a tree along with functions giving
for each non-terminal node t 6∈ Z (Z is the set of terminal nodes)

• the player i (t) who moves

• the set of possible actions A (t)
• the successor node resulting from each possible action N (t, a)
2
It becomes difficult to think of a solution concept of a game where players are for-
getful. Forgetfulness and rational behavior don’t go well together, and concepts like Nash
equilibrium assume that players are rational.

4
 3. Payoff functions ui : Z → < giving the players payoffs as a function of
the terminal node reached (the terminal nodes are the outcomes of the
game).

4. An information partition: for each node x, h (x) is the set of nodes

which are possible given what player i (x) knows. This partition must
satisfy

x0 ∈ h (x) ⇒ i (x0 ) = i (x) , A (x0 ) = A (x) , and h (x0 ) = h (x)

We sometimes write i (h) and A (h) since the action set is the same for
each node in the same information set.
It is useful to go over the definition in detail in the matching pennies game
where player 2 can’t observe player 1’s move. Let’s number the non-terminal
nodes x1 , x2 and x3 (top to bottom).

1. There are two players.

2. S1 = S2 = {H, T } at each node.

3. The tree defines clearly the terminal nodes, and shows that x2 and x3
are successors to x1 .

4. h (x1 ) = {x1 } and h (x2 ) = h (x3 ) = {x2 , x3 }

4 Normal Form Analysis

In an extensive form game write Hi for the set of information sets at which
player i moves.

Hi = {S ⊂ T |S = h (t) for some t ∈ T with i (t) = i}

Write Ai for the set of actions available to player i at any of his information
sets.

Definition 1 A pure strategy for player i in an extensive form game is a

function si : Hi → Ai such that si (h) ∈ A (h) for all h ∈ Hi .

5
 Note that a strategy is a complete contingent plan explaining what a
player will do in any situation that arises. At first, a strategy looks overspec-
ified: earlier action might make it impossible to reach certain sections of a
tree. Why do we have to specify how players would play at nodes which can
never be reached if a player follows his strategy early on? The reason is that
play off the equilibrium path is crucial to determine if a set of strategies form
a Nash equilibrium. Off-equilibrium threats are crucial. This will become
clearer shortly.

Definition 2 A mixed behavior strategy for player i is a function σi : Hi →

∆ (Ai ) such that supp (σi (h)) ⊂ A (h) for all h ∈ Ai .

Note that we specify an independent randomization at each information

set!3

4.1 Example I: Entry Game

We can find the pure strategy sets S1 = {Fight, Accomodate} and S2 =
{Out, In}. We can represent the game in normal form as:

Out In

F 2,0 −1,−1

A 2,0 1,1

3
You might think that a more natural definition would simply define mixed strategies
as a randomization over a set of pure strategies (just as in simultaneous move games). It
can be shown that for games with perfect recall this definition is equivalent to the one
given here, i.e. a mixed strategy is a mixed behavior strategy and vice versa. In games
without perfect recall this is no longer true - it is instructive to convince yourself that in
such games each mixed behavior strategy is a mixed strategy but not vice versa.

6
4.2 Example II: Stackelberg Competition
Firm 1 chooses q1 and firm 2 chooses a quantity q2 (q1 ). With three possible
output levels, firm 1 has three strategies, while firm 2 has 33 = 9 different
strategies because it can choose three strategies at its three information sets.

4.3 Example III: Sequential Matching Pennies

We have S1 = {H, T }. Firm 2 has four strategies as it can choose two actions
at two information sets. Strategy HH implies that firm 2 chooses H at both
nodes, while HT implies that it chooses H in the left node (after having
observed H) and T in the right node (after having observed T).

HH HT TH TT

H 1,−1 1,−1 −1,1 −1,1

T −1,1 1,−1 −1,1 1,−1

4.4 Example IV
Look at the following extensive form game:

7
 1

L R

1 2

L R

0 1

a b

4 3

0 3

One might be tempted to say that player 1 has three strategies because there
are only three terminal nodes which can be reached. However, there are 4
because La and Lb are two distinct strategies. After player 1 plays L it
is irrelevant for the final outcome what he would play in the bottom node.
However, this off equilibrium pay is important for player 2’s decision process
which in turn makes 1 decide whether to play L or R.

L R

La 1,0 1,0

Lb 1,0 1,0

Ra 0,1 4,0

Rb 0,1 3,3

8
5 Nash Equilibrium in Extensive Form Games
We can apply NE in extensive form games simply by looking at the normal
form representation. It turns out that this is not an appealing solution
concept because it allows for too many profiles to be equilibria.
Look at the entry game. There are two pure strategy equilibria: (A,In)
and (F,Out) as well as mixed equilibria (αF + (1 − α) A, Out) for α ≥ 12 .
Why is (F,Out) a Nash equilibrium? Firm 2 stays out because he thinks
that player 2 will fight entry. In other words, the threat to fight entry is
sufficient to keep firm 2 out. Note, that in equilibrium this threat is never
played since firm 2 stays out in the first place.
The problem with this equilibrium is that firm 2 could call firm 1’s bluff
and enter. Once firm 2 has entered it is in the interest of firm 1 to accom-
modate. Therefore, firm 1’s threat is not credible. This suggests that only
(A,In) is a reasonable equilibrium for the game since it does not rely on non-
credible threats. The concept of subgame perfection which we will introduce
in the next lecture rules out non-credible threats.

5.1 Example II: Stackelberg

We next look at a Stackelberg game where each firm can choose qi ∈ [0, 1]
and p = 1 − q1 − q2 and c = 0.
Claim: For any q10 ∈ [0, 1] the game has a NE in which firm 1
produces q10 .
Consider the following strategies:

s1 = q10
½ 1−q10
if q1 = q10
s2 = 2
1 − q10 6 q10
if q1 =

In words: firm 2 floods the market such that the price drops to zero if firm
1 does not choose q10 . It is easy to see that these strategies form a NE. Firm
1 can only do worse by deviating since profits are zero if firm 2 floods the
market. Firm 2 plays a BR to q10 and therefore won’t deviate either.
Note, that in this game things are even worse. Unlike the Cournot game
where we got a unique equilibrium we now have a continuum of equilibria.
Second, we have even more disturbing non-credible threats. For instance, in
the equilibrium where q10 = 1 firm 2’s threat is ”if you don’t flood the market

9
and destroy the market I will”. Not only won’t the threat be carried out -
it’s also hard to see why it would be made in the first place.

10
 Lecture XI: Subgame Perfect Equilibrium
Markus M. Möbius
April 9, 2003

Readings for this class: OR (section 6.2), FT (section 3.2.2),

Gibbons (Chapter 2), Dutta (Chapter 13).

1 Introduction
Last time we discussed extensive form representation and showed that there
are typically lots of Nash equilibria. Many of them look unreasonable because
they are based on out of equilibrium threats. For example, in the entry
game the incumbent can deter entry by threatening to flood the market. In
equilibrium this threat is never carried out. However, it seems unreasonable
because the incumbent would do better accommodating the entrant if entry
in fact occurs. In other words, the entrant can call the incumbent’s bluff by
entering anyway.
Subgame perfection is a refinement of Nash equilibrium. It rules out
non-credible threats.

2 Subgames
Definition 1 A subgame G0 of an extensive form game G consists of

1. A subset T 0 of the nodes of G consisting of a single node x and all of

its successors which has the property that t ∈ T 0 , t0 ∈ h (t) then t0 ∈ T 0 .

2. Information sets, feasible moves and payoffs at terminal nodes as in G.

1
2.1 Example I: Entry Game
2

In Out

1 2
0
F A

−1 1
−1 1

This game has two subgames. The entire game (which is always a sub-
game) and the subgame which is played after player 2 has entered the market:

F A

−1 1

−1 1

2.2 Example II
1

L R

2 2

L R L R

a b

2 2

a b a b

2
 This game has also two subgames. The entire game and the subgame (a
simultaneous move game) played after round 2:

a b

2 2

a b a b

This subgame has no further subgames: otherwise the information set of

player 2 would be separated which is not allowed under our definition.

3 Subgame Perfect Equilibrium

Definition 2 A strategy profile s∗ is a subgame perfect equilibrium of G if
it is a Nash equilibrium of every subgame of G.

Note, that a SPE is also a NE because the game itself is a (degenerate)

subgame of the entire game.
Look at the entry game again. We can show that s1 = A and s2 = Entry
is the unique SPE. Accomodation is the unique best response in the subgame
after entry has occurred. Knowing that, firm 2’s best response is to enter.

3.1 Example: Stackelberg

We next continue the Stackelberg example from the last lecture. We claim
that the unique SPE is q2∗ = 12 and q1∗ (q2 ) = 1−q2
2
.
The proof is as follows. A SPE must be a NE in the subgame after firm
1 has chosen q1 . This is a one player game so NE is equivalent to firm 1
maximizing its payoff, i.e. q1∗ (q1 ) ∈ arg max q1 [1 − (q1 + q2 )]. This implies
that q1∗ (q2 ) = 1−q
2
2
. Equivalently, firm 1 plays on its BR curve.
A SPE must also be a NE in the whole game, so q2∗ is a BR to q1∗ :
1 − q1
u2 (q1 , q2∗ ) = q2 (1 − (q2 + q1∗ (q2 ))) = q1
2

3
The FOC for maximizing u2 is q2∗ = 21 .
Note that firm 2 (the first mover) produces more than in Cournot.
There are many games which fit the Stackelberg paradigm such as mon-
etary policy setting by the central bank, performance pay for managers etc.
We will discuss general results for this class of games in the next lecture.

4 Backward Induction
The previous example illustrates the most common technique for finding and
verifying that you have found the SPE of a game. Start at the end of the
game and work your way from the start.
We will focus for the moment on extensive form games where each infor-
mation set is a single node (i.e. players can perfectly observe all previous
moves).

Definition 3 An extensive form is said to have perfect information if each

information set contains a single node.

Proposition 1 Any finite game of perfect information has a pure strategy

SPE. For generic payoffs in a finite extensive form game with perfect infor-
mation the SPE is unique.

What does generic mean? With generic payoffs players are never indiffer-
ent between two strategies. If payoffs are randomly selected at the terminal
nodes then indifference between two actions is a zero probability event. More
mathematically, we can say that the results holds for almost all games.

Proof: I did it in class, and I do a more general proof in the next section
for games with imperfect information. Intuitively, you solve the last
rounds of the game, then replace these subgames with the (unique)
outcome of the NE and repeat the procedure.

What happens if players are indifferent between two strategies at some

point? Then there is more than one SPE, and you have to complete the
backward induction for each possible outcome of the subgame.
Consider the following game:

4
 1

L R

2 2

A B C D

3 0 1 1

2 0 1 1

After player 1 played R player 2 is indifferent between C and D. It is

easy to see that there are infinitely many SPE such that s∗1 = L and s∗2 =
(A, αC + (1 − α) D) for 0 ≤ α ≤ 1.
Note however, that each of these SPE yields the same equilibrium out-
come in which the left terminal node is reached. Hence equilibrium play is
identical but off equilibrium pay differs. There are several SPE in this perfect
information game because it is not generic.

5 Existence of SPE
The next theorem shows that the logic of backward induction can be extended
to games with imperfect information.

Theorem 1 Every finite extensive form game has a SPE.

This theorem is the equivalent of the Nash existence theorem for extensive
form games. It establishes that SPE is not too strong in the sense that a
SPE exists for each extensive form game. We have seen that NE is too weak
in extensive form games because there are too many equilibria.
The proof of the theorem is a generalization of backward induction. In
backward induction we solve the game from the back by solving node after
node. Now we solve it backwards subgame for subgame.
Formally, define the set Γ of subgames of the game G. Γ is never empty
because G itself is a member. We can define a partial order on the set Γ such
that for two subgames G1 and G2 we have G1 ≥ G2 if G2 is a subgame of
G1 .
Look at the following example.

5
 1

A B C

1 1 1
−1

H T H T

2 2 2 2

H T H T H T H T

1 −1 −1 1 1 −1 −1 1
−1 1 1 −1 −1 1 1 −1

This game has three subgames: the whole game G1 and two matching pennies
subgames G2 and G3 . We have G1 ≥ G2 and G1 ≥ G3 but G2 and G3 are
not comparable.
Step I Identify the terminal subgames. Terminal subgames are those
which do not dominate another subgame (G0 is terminal if there is no G00
such that G0 > G00 .
Step II Solve the terminal subgames These subgames have no further
subgames. They have a Nash equilibrium by the Nash existence result (they
are finite!).
In our example the matching pennies subgames have the unique NE 12 H +
1
2
T for each player.
Step III Calculate the Nash payoffs of the terminal subgames and replace
these subgames with the Nash payoffs.
In our example the matching pennies payoffs are 0 for each player. We
get:
1

A C
B

1 0 0

−1 0 0

6
 Step IV Goto step I. Repeat this procedure until all subgames have been
exhausted. In this way we construct ’from the back’ a SPE. In many cases
the procedure does not produce a unique SPE if a subgame has multiple NE.
In our example we are lucky because matching pennies just has one NE. In
the reduced game¡ player 1 plays A which¢ is his unique
¡ 1 BR.1The1 unique SPE
¢
∗ 1 1 1 1 ∗ 1
is therefore s1 = A, 2 H + 2 T, 2 H + 2 T and s2 = 2 H + 2 T, 2 H + 2 T .

6 Application of SPE to Behavioral Economics

In the first two lectures of the course we analyzed decision problems and later
contrasted them to proper games where agents have to think strategically.
Our decision problems were essentially static - people one action out of a
number of alternatives.
In reality many decision problems involve taking decision over time: re-
tirement decision, savings, when to finish a paper for class etc. are standard
examples. Intertemporal decision making is different from static decision
making because agents might want to revise past decisions in the future
(they never have a chance to do so under static decision making). If agents
revise decisions we say that they are time-inconsistent. In most economics
classes you will never hear about such behavior - the decision making pro-
cess of agents is assumed to be time-consistent. This reduces intertemporal
decision making essentially to static decision making.

6.1 Time-Consistent Preferences

How do we model intertemporal decision making? Economists assume that
the future counts less than the present - agents discount. Typically we assume
that the utility in different time periods can be added up. So getting x1 now
and x2 in the next period has total utility:

U = u (x1 ) + δu (x2 ) (1)

For concreteness assume that agents want to spend 100 Dollars over two
time periods. Their discount factor for next period’s
√ utility is 0.5. Their
utility function is the square root function u (x) = x. You can check that
the agent would allocate 80 Dollar to today’s consumption and the rest to
tomorrow’s consumption.

7
 The agent is necessarily time-consistent in a two-period model because
she cannot reallocate any resources in period 2. However this is no longer
true in a 3-period model.
Let’s first look at exponential discounting where consumption in period t
is discounted by δ t :

U1 = u (x1 ) + δu (x2 ) + δ 2 u (x3 ) (2)

Let’s assume the same parameters as above. It’s easy to check that the agent
would want to allocate 2100
16
≈ 76 Dollars to the first period, 19 Dollars to
the second and 5 to the third.
Now the agent could potentially change her allocation in period 2. Would
she do so? The answer is no. Her decision problem in period 2 can be written
as maximizing U2 given that x2 + x3 = 100 − 76:

U2 = u (x2 ) + δu (x3 ) (3)

Note, that:
U1 = u (x1 ) + δU2 (4)
Therefore, if an agent would just a different consumption plan in period 2
she would have done so in period 1 as well.
We say that there is no conflict between different selves in games
with exponential discounting. Agents are time-consistent. Time-
consistent preferences are assumed in most of micro and macro economics.

6.2 Time-Inconsistent Preferences

Let’s now look at a difference discounting rule for future consumption which
we refer to as hyperbolic discounting. Agents discount at rate δ between all
future time periods. However, they use an additional discount factor β < 1 to
discount future versus present consumption. The idea here is, that consumers
discount more strongly between period 1 and 2 than between period 2 and
3:
U = u (x1 ) + βδu (x2 ) + βδ 2 u (x3 ) (5)
For simplicity we assume δ = 1 from now on.
Let’s assume β = 12 . In this case a period 1 agent would allocate 50 Dollars
to today and 25 Dollars to both tomorrow and the day after tomorrow.

8
 What would the period 2 agent do with her remaining 50 Dollars? Her
decision problem would look as follows:
U = u (x2 ) + βu (x3 ) (6)
So she would allocate 40 Dollars to period 2 and only 10 Dollars to the third
period.
Therefore there is conflict between agent 1’s and agent 2’s preferences!
Agent 1 would like agent 2 to save more, but agent 2 can’t help herself and
splurges!

6.3 Naive and Sophisticated Agents

There are two ways to deal with the self-control problem of agents. First,
agents might not be aware of their future self’s self-control problem - we say
that they are naive. In this case you solve a different decision problem in
each period and the consumption plans of agents get continuously revised.
If agents are aware of their self-control problem we call them sophisti-
cated. Sophisticated agents play a game with their future self, are aware that
they do so, and use SPE to solve for a consumption plan.
Let’s return to our previous problem. A period 2 agent would always
spend four times as much on this period than on period 3 (sophisticated or
naive). Period 1 agent realizes this behavior of agent 2 and therefore takes
the constraint x2 = 4x3 into account when allocating her own consumption.
She maximizes:
"r r #
√ 1 4 1
U 1 = x1 + (1 − x1 ) + (1 − x1 ) (7)
2 5 5
She would now spend 68 Dollars in the first period and predict that her
future self spends 24 Dollars in the second period such that there are 6 left
in the last period.
What has happened? Effectively, self 1 has taken away resources from
self 2 by spending more in period 1. Self 1 predicts that self 2 would splurge
- so self 1 might as well splurge immediately.

6.4 The Value of Commitment

If agents are time-inconsistent they can benefit from commitment devices
which effectively constrain future selves. For example, a sophisticated hy-

9
perbolic agent could invest 50 Dollars in a 401k from which he can’t with-
draw more than 25 Dollars in the second period. While a time-consistent
agent would never enter such a bargain (unexpected things might happen
- so why should he constrain his future choices), a time-inconsistent agent
might benefit.

7 Doing it Now or Later (Matt Rabin, AER,

1999)
This is a nice little paper which analyzes procrastination.

7.1 Salient Costs

Example 1 Assume you go to the cinema on Saturdays. The schedule con-
sists of a mediocre movie this week, a good movie next week, a great movie
in two weeks and (best of all) a Johnny Depp movie in three weeks. Also
assume that you must complete a report during the next four weeks so that
you have to skip one of the movies. The benefit of writing the report is the
same in each period (call it (v, v, v, v). The cost of not seeing a movie is
(c1 , c2 , c3 , c4 ) = (3, 5, 8, 13). When do you write the report?

Let’s assume that there are three types of agents. Time consistent agents
(TC) have δ = 1 and β = 1. Naive agents have β = 12 and sophisticated
agents are aware of their self-control problem.
TC agents will write the report immediately and skip the mediocre movie.
Generally, TC agents will maximize v − c.
Naive agents will write the report in the last period. They believe that
they will write the report in the second period. In the second period, they
assume to write it in the third period (cost 4 versus 5 now). In the third
period they again procrastinate.
Sophisticated agents use backward induction. They know that period 3
agent would procrastinate. Period 2 agent would predict period 3’s procras-
tination and write the report. Period 1 agent knows that period 2 agent will
write the report and can therefore safely procrastinate.
This example captures the idea that sophistication can somehow help
to overcome procrastination because agents are aware of their future selfs
tendencies to procrastinate.

10
7.2 Salient Rewards
Example 2 Assume you can go to the cinema on Saturdays. The schedule
consists of a mediocre movie this week, a good movie next week, a great movie
in two weeks and (best of all) a Johnny Depp movie in three weeks. You have
no money but a coupon to spend on exactly one movie. The benefit of seeing
the movies are (v1 , v2 , v3 , v4 ) = (3, 5, 8, 13). Which movie do you see?

The TC agent would wait and see the Depp movie which gives the highest
benefit.
The naive agent would see the third movie. He would not the mediocre
one because he would expect to see either the Depp movie later. He would
also not see the week 2 movie for the same reason. But in week 3 he caves
in to his impatience and spends the coupon.
The sophisticated agent would see the mediocre movie! She would expect
that period 3 self caves in to her desires. Period 2 self would then go to the
movies expecting period 3 self to cave in. But then period 1 self should go
immediately because 3 > 2.5.
The result is the opposite of the result we got for the procrastination
example. Sophistication hurts agents! The intuition is that naive agents
can pretend that they see the Depp movie and therefore are willing to wait.
Sophisticated agents know about their weakness and therefore don’t have the
same time horizon. This makes them cave in even earlier.
A sophisticated agent would not be able to withstand a jar of cookies
because she knows that she would cave in too early anyway, so she might as
well cave in right away.

7.3 Choice and Procrastination: The Perfect as the

Enemy of the Good
In a related paper (Choice and Procrastination, QJE 2002, forthcoming)
Rabin points out that greater choice can lead to more procrastination. In
the previous example, there was just procrastination on a single action. Now
assume, that agents have the choice between two actions.
Example 3 Assume you are a naive hyperbolic discounter (β = 12 ). You
can invest 1,000 Dollar in your 401k plan which gives you a yearly return of
5 percent. Once the money is invested it is out of reach for the next 30 years.
Just when you want to sign the forms your friend tells you that he has invested

11
his 1,000 Dollars at a rate of 6 percent. You make ca quick calculation and
decide that you should do more research before signing on because research
only causes you a disutility of 30 Dollars and the compounded interest gain
over 30 years far exceed this amount. What will you do?

You won’t do anything and still have your 1000 Dollars after 30 years. Wait-
ing a year has a cost of 50 Dollars (lost interest) which is discounted by β = 12
and thus is below the salient cost of doing research. So you wait. and wait.
and wait.
This is a nice example of why the perfect can be the enemy of the good:
more choice can lead to procrastination. For a naive decision maker choices
are determined by long-term benefits (just as for TC decision maker). How-
ever, procrastination is caused by small period to period costs of waiting
which exceed salient costs of doing research.

12
 Lecture XIII: Analysis of Infinite Games
Markus M. Möbius
April 9, 2003

Readings for this class: OR (sections 6.5, 8.1 and 8.2) Fudenberg
and Tirole, chapters 4.2 and 4.3 are most useful; Dutta, chapter 15

1 Introduction - Critique of SPE

The SPE concept eliminates non-credible threats but it’s worth to step back
for am minute and ask whether we think SPE is reasonable or in throwing
out threats we have been overzealous.
Practically, for this course the answer will be that SPE restrictions are
OK and we’ll always use them in extensive form games. However, it’s worth
looking at situations where it has been criticized. Some of the worst anoma-
lies disappear in infinite horizon games which we study next.

1.1 Rationality off the Equilibrium Path

Is it reasonable to play NE off the equilibrium path? After all, if a player
does not follow the equilibrium he is probably as stupid as a broomstick.
Why should we trust him to play NE in the subgame? Let’s look at the
following game to illustrate that concern:

1
 1

L R

10 1

0
A B

2 2

x y x y

1 5 0 4

1 0 −100 0

Here (L, A, x) is the unique SPE. However, player 2 has to put a lot of
trust into player 1’s rationality in order to play x. He must believe that
player 1 is smart enough to figure out that A is a dominant strategy in the
subgame following R. However, player 2 might have serious doubts about
player 1’s marbles after the guy has just foregone 5 utils by not playing L.1

Remark 1 The main reason for the breakdown of cooperation in the finitely
repeated Prisoner’s Dilemma is not so much SPE by itself by the fact that
there is a final period in which agents would certainly defect. This raises the
question whether an infinitely repeated PD game would allow us to cooperate.
Essentially, we could cooperate as long as the other player does, and if there
is defection, we defect from then on. This still looks like a SPE - in any
subgame in which I have defected before, I might as well defect forever. If I
haven’t defected yet, I can jeopardize cooperation by defection, and therefore
should not do it as long as I care about the future sufficiently.

1.2 Multi-Stage Games

Lemma 1 The unique SPE of the finitely repeated Prisoner’s Dilemma game
in which players get the sum of their payoffs from each stage game has every
player defecting at each information set.
1
After all any strategy in which L is played strictly dominates any strategy in which R
is played in the normal form.

2
The proof proceeds by analyzing the last stage game where we would see
defection for sure. But then we would see defection in the second to last
stage game etc. In the same way we can show that the finitely repeated
Bertrand game results in pricing at marginal cost all the time.
These results should make us suspicious. Axelrod’s experiments (see fu-
ture lecture) showed that in the finitely repeated Prisoner’s Dilemma people
tend to cooperate until the last few periods when the ’endgame effect’ kicks
in. Similarly, there are indications that rival firms can learn to collude if they
interact repeatedly and set prices above marginal cost.
This criticisms of SPE is reminiscent of our criticism of IDSDS. In both
cases we use an iterative procedure to find equilibrium. We might have doubts
where real-world subjects are able (and inclined) to do this calculation.
A famous example for the perils of backward induction is Rosenthal’s
centipede game:
1

L R

1 2
0
L R

0 1
2
L R

3 2
1
L R

2 1
4
L R

5 2
3
L R

4 7
6 5

The game can be extended to even more periods. The unique SPE of the
game is to drop out immediately (play L) at each stage. However, in experi-

3
ments people typically continue until almost the last period before they drop
out.

2 Infinite Horizon Games

Of the criticism of SPE the one we will take most seriously is that long finite
horizon models do not give reasonable answers. Recall that the problem
was that the backward induction procedure tended to unravel ’reasonably’
looking strategies from the end. It turns out that many of the anomalies
go away once we model these games as infinite games because there is not
endgame to be played.
The prototypical model is what Fudenberg and Tirole call an infinite
horizon multistage game with observed actions.

• At times t = 0, 1, 2, .. some subset of the set of players simultaneously

chooses actions.

• All players observe the period t actions before choosing period t + 1

actions.

• Players payoffs maybe any function of the infinite sequence of actions

(play does not end in terminal nodes necessarily any longer)

2.1 Infinite Games with Discounting

Often we assume that player i’s payoffs are of the form:

ui (si , s−i ) = ui0 (si , s−i ) + δui1 (si , s−i ) + δ 2 ui2 (si , s−i ) + .. (1)

where uit (si , s−i ) is a payoff received at t when the strategies are followed.

2.1.1 Interpretation of δ
1
1. Interest rate δ = 1+r . Having two dollars today or two dollars tomor-
row makes a difference to you: your two dollars today are worth more,
because you can take them to the bank and get 2 (1 + r) Dollars to-
morrow where r is the interest rate. By discounting future payoffs with
1
δ = 1+r we correct for the fact that future payoffs are worth less to us
than present payoffs.

4
 2. Probabilistic end of game: suppose the game is really finite, but that
the end of the game is not deterministic. Instead given that stage t is
reached there is probability δ that the game continues and probability
1 − δ that the game ends after this stage. Note, that the expected
1
number of periods is then 1−δ and finite. However, we can’t apply
backward induction directly because we can never be sure that any
round is the last one. The probabilistic interpretation is particularly
attractive for interpreting bargaining games with many rounds.

2.2 Example I: Repeated Games

Let G be a simultaneous move game with finite action spaces A1 ,..,AI . The
infinitely repeated game G∞ is the game where in periods t = 0, 1, 2, .. the
players simultaneously choose actions (at1 , .., atI ) after observing all previous
actions. We define payoffs in this game by
∞
X ¡ ¢
ui (si , s−i ) = δ t ũi at1 , .., atI (2)
t=0

where (at1 , .., atI )

is the action profile taken in period t when players follow
strategies s1 , .., sI , and ũi are the utilities of players in each stage game.
For example, in the infinitely repeated Prisoner’s Dilemma game the ũi are
simply the payoffs in the ’boxes’ of the normal form representation.

2.3 Example II: Bargaining

Suppose there is a one Dollar to be divided up between two players. The
following alternate offer procedure is used:
I. In periods 0,2,4,... player 1 offers the division (x1 , 1 − x1 ). Player 2
then accepts and the game ends, or he rejects and play continues.
II. In period 1,3,5,... player 2 offers the division (1 − x2 , x2 ). Player 1 then
accepts or rejects.
Assume that if the division (y, 1 − y) is agreed to in period t then the payoffs
are δ t y and δ t (1 − y).2
2
Note that this is not a repeated game. First of all, the stage games are not identical
(alternate players make offers). Second, there is no per period payoff. Instead, players
only get payoffs when one of them has agreed to an offer. Waiting to divide the pie is
costly.

5
Remark 2 There are finite versions of this game in which play end after
period T . One has to make some assumption what happens if there is no
agreement at time T - typically, one assumes that the pie simply disappears.
If T = 1 then we get the simple ultimatum game.

3 Continuity at Infinity
None of the tools we’ve discussed so far are easy to apply for infinite games.
First, backward induction isn’t feasible because there is no end to work back-
ward from. Second, using the definition of SPE alone isn’t very easy. There
are infinitely many subgames and uncountably many strategies that might
do better.
We will discuss a theorem which makes the analysis quite tractable in
most infinite horizon games. To do so, we must first discuss what continuity
at infinity means.

Definition 1 An infinite extensive form game G is continuous at ∞ if

lim sup |ui (σ) − ui (σ 0 )| = 0

T →∞ 0
i,σ,σ s. th. σ (h) =
σ 0 (h) for all h in peri-
ods t ≤ T

In words: compare the payoffs of two strategies which are identical for all
information sets up to time T and might differ thereafter. As T becomes large
the maximal difference between any two such strategies becomes arbitrarily
small. Essentially, this means that distant future events have a very small
payoff effect.

3.1 Example I: Repeated Games

If σ and σ 0 agree in the first T periods then:
¯∞ ¯
¯X ¡ ¡ ¢ ¢ ¯
0 ¯ t t 0 ¯
|ui (σ) − ui (σ )| = ¯ δ ũi a − ũi (at ) ¯
¯ ¯
t=T
∞
X
≤ δ t max0 |ũi (a) − ũi (a0 )|
i,a,a
t=T

6
For finite stage games we know that M = maxi,a,a0 |ũi (a) − ũi (a0 )| is finite.
This implies that
∞
X δT
lim |ui (σ) − ui (σ 0 )| ≤ lim δ t M = lim M = 0.
T →∞ T →∞ T →∞ 1 − δ
t=T

3.2 Example II: Bargaining

It’s easy to check that the bargaining game is also continuous.

3.3 Example III: Non-discounted war of attrition

This is an example for an infinite game which is NOT continuous at infinity.
Players 1 and 2 choose ati ∈ {Out, Fight} at time t = 0, 1, 2, ... The game
ends whenever one player quits with the other being the ’winner’. Assume
the payoffs are
½
1 − ct if player i ’wins’ in period t
ui (si , s−i ) =
−ct if player i quits in period t

Note, that players in this game can win a price of 1 by staying in the game
longer than the other player. However, staying in the game is costly for both
players. Each player wants the game to finish as quickly as possible, but also
wants the other player to drop out first.
This game is not continuous at ∞. Let

σ T = Both fight for T periods and then 1 quits

σ 0T = Both fight for T periods and then 2 quits.

Then we have ¯ ¡ T¢ ¡ ¢¯
¯ui σ − ui σ 0T ¯ = 1.

This expression does not go to zero as T → ∞.

4 The Single-Period Deviation Principle

The next theorem makes the analysis of infinite games which are continuous
at ∞ possible.

7
Theorem 1 Let G be an infinite horizon multistage game with observed ac-
tions which is continuous at ∞. A strategy profile (σ1 , .., σI ) is a SPE if and
only if there is no player i and strategy σ̂i that agrees with σi except at a sin-
gle information set hti and which gives a higher payoff to player i conditional
on hti being reached.

We write ui (σi , σ−i |x) for the payoff conditional on x being reached. For
example, in the entry game below we have u2 (Accomodate, Out|node 1 is reached) =
1.
2

In Out

1 2
0
F A

−1 1
−1 1

Recall, that we can condition on nodes which are not on the equilibrium path
because the strategy of each player defines play at each node.

4.1 Proof of SPDP for Finite Games

I start by proving the result for finite-horizon games with observed actions.
Step I: By the definition of SPE there cannot be a profitable deviation
for any player at some information set in games with observed actions.3
Step II: The reverse is a bit harder to show. We want to show that
ui (σ̂i , σ−i |xt ) ≤ ui (σi , σ−i |xt ) for all initial nodes xt of a subgame (subgame
at some round t).
We prove this by induction on T which is the number of periods in which
σi and σ̂i differ.
3
We have to very careful at this point. We have defined SPE as NE in every subgame.
Subgames can only originate at nodes and not information sets. However, in games with
observed actions all players play simultaneous move games in each round t. Therefore any
deviation by a player at an information set at round t which is not a singleton is on the
equilibrium path of some subgame at round t.

8
 T=1: In this case the result is clear. Suppose σi and σ̂i differ only in
the information set in period t0 . If t > t0 it is clear that ui (σ̂i , σ−i |xt ) =
ui (σi , σ−i |xt ) because the two strategies are identical at all the relevant in-
formation sets. If t ≤ t0 then:
X
ui (σ̂i , σ−i |xt ) = ui (σ̂i , σ−i |hit0 ) P rob {hit0 |σ̂i , σ−i , xt }
hit0
X
≤ ui (σi , σ−i |hit0 ) P rob {hit0 |σi , σ−i , xt }
| {z } | {z }
hit0
follows from one follows from σi
stage deviation and σ̂i having
criterion same play be-
tween t and t0
= ui (σi , σ−i |xt )

T → T+1:Assuming that the result holds for T let σ̂i be any strategy
differing from σi in T + 1 periods. Let t0 be the last period at which they
differ and define σ̃i by:
½
σ̂i (hit ) if t < t0
σ̃i (hit ) =
σi (hit ) if t ≥ t0

In other words, σ̃i differs from σi only at T periods. Therefore we have for
any xt
ui (σ̃i , σ−i |xt ) ≤ ui (σi , σ−i |xt )
by the inductive hypothesis since we assumed that the claim holds for T .
However, we also know that σ̃ and σ̂ only differ in a single deviation at
round t0 . Therefore, we can use exactly the same argument as in the previous
step to show that
ui (σ̂i , σ−i |xt ) ≤ ui (σ̃i , σ−i |xt )
for any xt .4
Combining both inequalities we get the desires result:

ui (σ̂i , σ−i |xt ) ≤ ui (σi , σ−i |xt )

This proves the result for finite games with observed actions.
4
It is important that we have defined σ̃i in differing only in the last period deviation.
Therefore, after time t0 strategy σ̃i follows σi . This allows us to use the SPDP.

9
4.2 Proof for infinite horizon games
Note, that the proof for finite-horizon games also establishes that we for a
profile σ which satisfies SPDP player i cannot improve on σi in some subgame
xt by considering a new strategy σ̂i with finitely many deviations from σi .
However, it is still possible that deviations at infinitely many periods might
be an improvement for player i.
Assume this would be the case for some σ̂i . Let’s denote the gain from
using this strategy with ²:

² = ui (σ̂i , σ−i |xt ) − ui (σi , σ−i |xt )

Because the game is continuous at ∞ this implies that if we choose T large

enough we can define some strategy σ̃i which agrees with σ̂i up to period T
and then follows strategy σi such that:
²
|ui (σ̂i , σ−i |xt ) − ui (σ̃i , σ−i xt )| <
2
This implies that the new strategy σ̃i gives player i strictly more utility than
σi . However, it can only differ from σi for at most T periods. But this is a
contradiction as we have shown above. QED

Remark 3 Games which are at continuous at ∞ are in some sense ’the next
best thing’ to finite games.

5 Analysis of Rubinstein’s Bargaining Game

To illustrate the use of the single period deviation principle and to show
the power of SPE in one interesting model we now return to the Rubinstein
bargaining game introduced before.
First, note that the game has many Nash equilibria. For example, player
2 can implement any division by adopting a strategy in which he only accepts
and proposes a share x2 and rejects anything else.

Proposition 1 The bargaining game has a unique SPE. In each period of

1
the SPE the player i who proposes picks xi = 1+δ and the other player accepts
δ
any division giving him at least 1+δ and rejects any offer giving him less.

Several observations are in order:

10
 1. We get a roughly even split for δ close to 1 (little discounting). The
proposer can increase his share the more impatient the other player is.

2. Agreement is immediate and bargaining is therefore efficient. Players

can perfectly predict play in the next period and will therefore choose a
division which makes the other player just indifferent between accepting
and making her own proposal. There is no reason to delay agreement
because it just shrinks the pie. Immediate agreement is in fact not
observed in most experiments - last year in a two stage bargaining game
in class we observed that only 2 out of 14 bargains ended in agreement
after the first period. There are extensions of the Rubinstein model
which do not give immediate agreement.5

3. The division becomes less equal for finite bargaining games. Essentially,
the last proposer at period T can take everything for himself. Therefore,
he will tend to get the greatest share of the pie in period 1 as well
- otherwise he would continue to reject and take everything in the
last period. In our two-period experiments we have in deed observed
greater payoffs to the last proposer (ratio of 2 to 1). However, half
of all bargains resulted in disagreement after the second period and so
zero payoffs for everyone. Apparently, people care about fairness as
well as payoffs which makes one wonder whether monetary payoffs are
the right way to describe the utility of players in this game.

5.1 Useful Shortcuts

The hard part is to show that the Rubinstein game has a unique SPE. If we
know that it is much easier to calculate the actual strategies.

5.1.1 Backward Induction in infinite game

You can solve the game by assuming that random payoff after rejection of
offer at period T . The game then becomes a finite game of perfect information
which can be solved through backward induction. It turns out that as T → ∞
5
For example, when there is uncertainty about a players discount factor the proposer
might start with a low offer in order to weed out player 2 types with low discount factor.
Players with high δ will reject low offers and therefore agreement is not immediate. To
analyze these extension we have to first develop the notion of incomplete information
games.

11
 the backward solution converges to the Rubinstein solution. This technique
also provides an alternative proof for uniqueness.

5.1.2 Using the Recursive Structure of Game

The game has a recursive structure. Each player faces essentially the same
game, just with interchanged roles. Therefore, in the unique SPE player
1 should proposes some (x, 1 − x) and player 2 should propose (1 − x, x).
Player 1’s proposal to 2 should make 2 indifferent between accepting imme-
diately or waiting to make her own offer (otherwise player 1 would bid higher
or lower). This implies:

1| {z
− x} = δx
|{z}
2’s payoff at period 1 2’s discounted payoff from period 2
1
x =
1+δ

5.2 Proof of Rubinstein’s Solution

5.2.1 Existence
We show that there is no profitable single history deviation.
1
Proposer: If he conforms at period t the continuation payoff is δ t 1+δ . If he deviates
t+1 δ
and asks for more he gets δ 1+δ . If he deviates and asks for less he
gets less. Either way he loses.

Recipient: Look at payoffs conditional on y being proposes in period t.

1
– If he rejects he gets δ t+1 1+δ .
– If he accepts he gets δ t y.
δ
– If y ≥ 1+δ
the strategy says accept and this is better than reject-
ing.
δ
– If y < 1+δ the strategy says reject and accepting is not a profitable
deviation.

12
5.2.2 Uniqueness
This proof illustrates a number of techniques which enable us to prove prop-
erties about equilibrium without actually constructing it.
Let v and v be the highest and lowest payoffs received by a proposer in
any SPE. We first observe:
1 − v ≥ δv (3)
If this equation would not be true then no proposer could propose v because
the recipient could always get more in any subgame. We also find:

v ≥ 1 − δv (4)

If not then no proposer would propose v - she would rather wait for the other
player to make her proposal because she would get a higher payoff this way.
We can use both inequalities to derive bounds on v and v:

v ≥ 1 − δv ≥ 1 − δ (1 − δv) (5)
¡ 2
¢
1−δ v ≥ 1−δ (6)
1
v ≥ (7)
1+δ
Similarly, we find:

1 − v ≥ δv ≥ δ (1 − δv) (8)
1
v ≤ (9)
1+δ
1
Hence v = v = 1+δ . Clearly, no other strategies can generate this payoff in
6
every subgame.

6
While being a nice result it does not necessarily hold anymore when we change the
game. For example, if both players make simultaneous proposals then any division is a
SPE. Also, it no longer holds when there are several players.

13
 Lecture XIII: Repeated Games
Markus M. Möbius
April 23, 2003

Readings for this class: Fudenberg and Tirole, page 146-154;

Dutta, chapter 15

1 Introduction
So far one might get a somewhat misleading impression about SPE. When
we first introduced dynamic games we noted that they often have a large
number of (unreasonable) Nash equilibria. In the models we’ve looked at so
far SPE has ’solved’ this problem and given us a unique NE. In fact, this is
not really the norm. We’ll see today that many dynamic games still have a
very large number of SPE.

2 Credible Threats
We introduced SPE to rule out non-credible threats. In many finite horizon
games though credible threats are common and cause a multiplicity of SPE.
Consider the following game:

1
 L C R

T 3,1 0,0 5,0

M 2,1 1,2 3,1

B 1,2 0,1 4,4

¡ ¢
The game has three NE: (T,L), (M,C) and 12 T + 12 M, 12 L + 12 C
Suppose that the players play the game twice and observe first period
actions before choosing the second period actions. Now one way to get a
SPE is to play any of the three profiles above followed by another of them
(or same one). We can also, however, use credible threats to get other actions
played in period 1, such as:

• Play (B,R) in period 1.

• If player 1 plays B in period 1 play (T,L) in period 2 - otherwise play

(M,C) in period 2.

It is easy to see that no single period deviation helps here. In period 2 a

NE is played so obviously doesn’t help.

• In period 1 player 1 gets 4 + 3 if he follows strategy and at most 5 + 1

if he doesn’t.

• Player 2 gets 4 + 1 if he follows and at most 2+1 if he doesn’t.

Therefore switching to the (M,C) equilibrium in period 2 is a credible threat.

2
3 Repeated Prisoner’s Dilemma
Note, that the PD doesn’t have multiple NE so in a finite horizon we don’t
have the same easy threats to use. Therefore, the finitely repeated PD has a
unique SPE in which every player defects in each period.
C D

C 1,1 −1,2

D 2,−1 0,0

In infinite horizon, however, we do get many SPE because other types of

threats are credible.

Proposition 1 In the infinitely repeated PD with δ ≥ 12 there exists a SPE

in which the outcome is that both players cooperate in every period.

Proof: Consider the following symmetric profile:

(
If both players have played C in every
C
si (ht ) = period along the path leading to ht .
D If either player has ever played D.

To see that there is no profitable single deviation note that at any ht

such that si (ht ) = D player i gets:

0 + δ0 + δ 2 0 + ..

if he follows his strategy and

−1 + δ0 + δ 2 0 + ..

if he plays C instead and then follows si .

At any ht such that si (ht ) = C player i gets:
1
1 + δ1 + δ 2 1 + .. =
1−δ

3
 if he follows his strategy and

2 + δ0 + δ 2 0 + .. = 2

if he plays D instead and then follows si .

Neither of these deviations is worth while if δ ≥ 12 . QED

Remark 1 While people sometimes tend to think of this as showing that

people will cooperate in they repeatedly interact if does not show this. All it
shows is that there is one SPE in which they do. The correct moral to draw
is that there many possible outcomes.

3.1 Other SPE of repeated PD

1. For any δ it is a SPE to play D every period.

2. For δ ≥ 12 there is a SPE where the players play D in the first period
and then C in all future periods.

3. For δ > √12 there is a SPE where the players play D in every even
period and C in every odd period.

4. For δ ≥ 12 there is a SPE where the players play (C,D) in every even
period and (D,C) in every odd period.

3.2 Recipe for Checking for SPE

Whenever you are supposed to check that a strategy profile is an SPE you
should first try to classify all histories (i.e. all information sets) on and
off the equilibrium path. Then you have to apply the SPDP for each class
separately.

• Assume you want to check that the cooperation with grim trigger pun-
ishment is SPE. There are two types of histories you have to check.
Along the equilibrium path there is just one history: everybody coop-
erated so far. Off the equilibrium path, there is again only one class:
one person has defected.

4
 • Assume you want to check that cooperating in even periods and defect-
ing in odd periods plus grim trigger punishment in case of deviation
by any player from above pattern is SPE. There are three types of his-
tories: even and odd periods along the equilibrium path, and off the
equilibrium path histories.
• Assume you want to check that TFT (’Tit for Tat’) is SPE (which it
isn’t - see next lecture). Then you have you check four histories: only
the play of both players in the last period matters for future play - so
there are four relevant histories such as player 1 and 2 both cooperated
in the last period, player 1 defected and player 2 cooperated etc.1

Sometimes the following result comes in handy.

Lemma 1 If players play Nash equilibria of the stage game in each period
in such a way that the particular equilibrium being played in a period is a
function of time only and does not depend on previous play, then this strategy
is a Nash equilibrium.
The proof is immediate: we check for the SPDP. Assume that there is a
profitable deviation. Such a deviation will not affect future play by assump-
tion: if the stage game has two NE, for example, and NE1 is played in even
periods and NE2 in odd periods, then a deviation will not affect future play.1
Therefore, the deviation has to be profitable in the current stage game - but
since a NE is being played no such profitable deviation can exist.

Corollary 1 A strategy which has players play the same NE in each period
is always SPE.

In particular, the grim trigger strategy is SPE if the punishment strategy in

each stage game is a NE (as is the case in the PD).

4 Folk Theorem
The examples in 3.1 suggest that the repeated PD has a tremendous number
of equilibria when δ is large. Essentially, this means that game theory tells
us we can’t really tell what is going to happen. This turns out to be an
accurate description of most infinitely repeated games.
1
If a deviation triggers a switch to only NE1 this statement would no longer be true.

5
 Let G be a simultaneous move game with action sets A1 , A2 , .., AI and
mixed strategy spaces Σ1 , Σ2 ,.., ΣI and payoff function ũi .

Definition 1 A payoff vector v = (v1 , v2 , .., vI ) ⊂ <I is feasible if there exists

action profiles a1 , a2 , ..,ak ∈ A and non-negative weights ω1 ,..,ωI which sum
up to 1 such that
¡ ¢ ¡ ¢ ¡ ¢
vi = ω1 ũi a1 + ω2 ũi a2 + .. + ωk ũi ak +

Definition 2 A payoff vector v is strictly individually rational if

vi > v i = min max ũi (σi (σ−i ) , σ−i ) (1)

σ−i ∈Σ−i σi (σ−i )∈Σi

We can think of this as the lowest payoff a rational player could ever get
in equilibrium if he anticipates his opponents’ (possibly non-rational) play.
Intuitively, the minmax payoff v i is the payoff player 1 can guarantee to
herself even if the other players try to punish her as badly as they can. The
minmax payoff is a measure of the punishment other players can inflict.

Theorem 1 Folk Theorem. Suppose that the set of feasible payoffs of G is

I-dimensional. Then for any feasible and strictly individually rational payoff
vector v there exists δ < 1 such that for all δ > δ there exists a SPE x∗ of
G∞ such that the average payoff to s∗ is v, i.e.
vi
ui (s∗ ) =
1−δ

The normalized (or average) payoff is defined as P = (1 − δ) ui (s∗ ). It is the

payoff which a stage game would have to generate in each period such that
we are indifferent between that payoff stream and the one generates by s∗ :

P + δP + δ 2 P + ... = ui (s∗ )

4.1 Example: Prisoner’s Dilemma

• The feasible payoff set is the diamond bounded by (0,0), (2,-1), (-1,2)
and (1,1). Every point inside can be generated as a convex combina-
tions of these payoff vectors.

6
 • The minmax payoff for each player is 0 as you can easily check. The
other player can at most punish his rival by defecting, and each player
can secure herself 0 in this case.
2

1.5

1
(1−δ)u2

0.5

−0.5

−1
−1 −0.5 0 0.5 1 1.5 2
(1−δ)u1

Hence the theorem says that anything in this trapezoid is possible. Note,
that the equilibria I showed before generate payoffs inside this area.

4.2 Example: BOS

Consider the Battle of the Sexes game instead.
F O

F 2,1 0,0

O 0,0 1,2

7
Here each player can guarantee herself at least payoff 23 which is the pay-
off from playing the mixed strategy Nash equilibrium. You can check that
whenever player 2 mixes with different probabilities, player 1 can guarantee
herself more than this payoff by playing either F or O all the time.

4.3 Idea behind the Proof

1. Have players on the equilibrium path play an action with payoff v (or
alternate if necessary to generate this payoff).2

2. If some player deviates punish him by having the other players for T
periods choose σ−i such that player i gets v i .

3. After the end of the punishment phase reward all players (other than i)
for having carried out the punishment by switching to an action profile
where player i gets viP < vi and all other players get vjP + ².

¡ ¢
2
For example, in the BoS it is not possible to generate 32 , 32 in the stage game even
with mixing. However, if players alternate and play (O,F) and then (F,O) the players can
get arbitrarily close for large δ.

8
 Lecture XV: Axelrod Tournaments
Markus M. Möbius
April 23, 2003

Readings for this class: Axelrod, chapters 1-3.

1 Introduction
In 1983 Axelrod solicited computer programs from game theorists and psy-
chologists - each program was essentially a strategy of how to play a repeated
Prisoner’s Dilemma stage game 200 times:

C D

C 3,3 0,5

D 5,0 1,1

All 40 entries were matched against each other, and the score of each bilateral
match was calculated as the sum of all stage payoffs (i.e. δ = 1). All payoffs
were between 200 and 600 since a player can always guarantee at least a payoff

1
of 1 in a stage game. The average score of each strategy was calculated, and
the strategies ranked according to overall success.1
Perhaps surprisingly, the winner was the simple TIT FOR TAT rule - a
player starts to cooperate and then does whatever the last player did in the
previous period.
The reason that TFT did so well was the following:
1. TFT is ’nice’ because it never defects first. In fact, all of the best eight
strategies were nice. Nice strategies did primarily well because so many
of the entries were nice - hence they did particularly well against other
nice strategies (getting the maximum payoff of 600).
2. TFT is discriminating enough not to be exploited too badly. For ex-
ample, ’all C’ is easily exploited by ’all D’, but TFT can’t be as easily
duped.
3. TFT is forgiving - bygones are bygones, and one period cooperation can
lead to continued cooperation in the future. Many strategies did badly
because they were unforgiving. Forgiveness was the main criterion for
success amongst the set of ’nice’ strategies.
It’s ironic that the example on the solicitation letter would have done
even better than TFT. This was essentially a TIT for two TATs strategy - a
player will only defect if he sees two defections in a row. What’s nice about
TF2T is that it avoids ’echo effects’ where players are caught in an alternate
(C, D) and (D, C) cycle.
Most submissions were in some way or another variations of TFT. How-
ever, rather than making TFT more forgiving (as TF2T) participants devised
less nice rules which turned out to do worse on average.

2 The Evolutionary Approach

Axelrod uses evolutionary game theory to analyze cooperation in repeated
games. This approach is useful because his main interest lies in the question
1
Note, that we wouldn’t necessarily expect a strategy to be a NE - after all we know
from the folk theorem that there are many SPE implementing a continuum of outcomes.
Hence, there is no obvious way to select NE strategies. A winning strategy has to do
well on average against other strategies and therefore doesn’t have to be Nash (just as
in the 2/3 of the average game the winning strategy is typically never part of a Nash
equilibrium).

2
how does cooperation arise in populations?
Ideally, evolutionary forces should select equilibria with more cooperation
over those with less cooperation, and provide some mechanism through which
the transition can be accomplished. This mechanism are typically ’mutations’
of agents who do better than non-cooperating agents.
In order to analyze evolution in repeated PD games we go through the
following steps:

1. Define a suitable evolutionary environment such that our evolutionary

concepts (ESS, replicator dynamics etc.) continue to apply in repeated
game setting.

2. Show that TFT is evolutionary stable. For simplicity, we use a slightly

less demanding concept called collective stability.

3. Realize that lots of strategies are collectively stable, in particular ’All

D’.

4. Define the concept of q-clusters and cluster-invasions and show that

TFT is cluster-stable while ’All D’ is not. The concept of ’coordinated
mutations’ is powerful, and has many analogies in real life.

3 Evolution and Repeated Games

Our standard evolutionary setting was a mass 1 of agents who are randomly
matched all the time and play a stage game against each other. In this
case agents will act myopically, even if they have a positive discount factor
because the probability of running into the same agent twice is essentially
zero (if matching in random and the population is large).
We want to keep the random matching assumption but weaken the re-
quirement that agents’ matches break up for sure after each period. Formally,
we assume that agents have discount factors δ and that there is a probability
p that a match breaks up in every time period (or it breaks up at rate p
if time is continuous). The expected match length is then p1 - for the Ax-
elrod tournament we would choose p = 0.005 in order to get T = 200 on
average. Each agent then discounts payoffs within the same match at rate
δ̃ = δ (1 − p). After a match breaks up, agents are instantly rematched. Each
period a share p of agents are rematched.

3
 Previously, agents were labelled by the strategy set (e.g. xi was the share
of agents using strategy si ). Now, the strategy set is the set of extensive form
strategies, i.e. s : H → {C, D}.2
Now we can define ESS, replicator dynamics etc. exactly as before. To
make life easier, we will use a slightly weaker form of ESS, namely collective
stability which is essentially NE:

Definition 1 A strategy s is collectively stable if any other strategy s0 (of

the infinite extensive form game) does not do better, i.e.:3

U (s0 , s) ≤ U (s, s)

Collective stability (like NE) captures the idea that no mutation will do
better than the original strategy does against itself.4

4 TFT and Collective Stability

Note, that TFT is NOT a SPE. This can be easily shown using the SPDP.
Assume we are in a subgame where both players defected. TFT would lead
to continual defection. However, if one player deviates and cooperates, it
will lead to an ’echo’ of alternating (C, D) and (D, C) moves. For sufficiently
high discount factor players will do better as a result. Hence TFT is not
SPE. However, it is NE and hence collectively stable as the next proposition
shows.
Note, that the SPE is hard to translate into an evolutionary setting be-
cause after all people are assumed to play fixed rules and hence don’t have
commitment problems. However, in the repeated PD the NE concept does
not allow ’non-credible’ threats as NE in the entry game does, for example.
The reason is that the only threat players have in PD is in fact playing Nash.

Proposition 1 TFT is collectively stable for δ > 32 .

2
There are some potential technical problems because the set of strategies is now infinite
(in fact uncountable) whereas before we had to deal only with xc and xD . Typically, we
restrict attention to two strategies - some dominant strategy, and an entrant ’mutant’.
3
Capital utility is the discounted sum of stage game utilities.
4
Note, that ESS is stronger because it imposes a second condition.

4
Proof: ’All C’ clearly doesn’t do better than TFT since TFT is nice. We
have to check that ’all D’ doesn’t do better, and also ’alternate D and
C’. Are there any other strategies? NO.
Look at a strategy s0 which contains both C and D along the equilib-
rium path. Assume there is a string of at least two D’s somewhere in
that strategy s0 =(...DDXXX..). Note, that TFT defects after the first
defection. Consider the modified strategy s00 =(...DXXXX). If s00 does
better s0 against T F T then it does not pay to include an additional D
in the string of strategy s0 . Hence we can eliminate all double D’s from
s0 and get a better strategy against TFT. If s00 does not do better than
s0 against TFT then we can continue to insert defections to get suc-
cessively better strategies until we get back to ’all D’. This argument
implies that we only have to consider ’all D’ or mixed strategies with
no consecutive D’s.
In the same way we can exclude consecutive C’s. This shows that we
only have to consider ’all D’, and ’alternate D and C’.
3
u (TFT, TFT) =
1−δ
δ
u (all D, TFT) = 5 +
1−δ
5
u (alternate D and C , TFT) =
1 − δ2
We just have to make that none of the ¡two mutations
¢ does better than
TFT. This will be the case if δ > max 12 , 23 . QED

5 What About Other Strategies?

Any NE is collectively stable. By the folk theorem there is a continuum of
SPE (which are obviously NE) and guarantee any IR, feasible payoff (check
this area for yourself). In particular:

Proposition 2 ’All D’ is SPE and collectively stable.

This look like horrible news - how can cooperation ever arise if everything
including ’All D’ is collectively stable?

5
6 Cluster-stability
For this section assume that δ = .9 such that TFT is collectively stable. The
standard ESS concept of a mutation assumes that mutations are ’small’ and
hence it’s unlikely that a mutant interacts with other mutants.
Axelrod’s idea is to consider mutations which are ’small’ compared to
the population, but whose members nonetheless interact. For example, the
senate is pretty large, but two freshmen senators from California might in-
teract sufficiently so that they don’t influence the payoffs of other senators
very much (just as individual mutations do), but they do affect each other
directly a lot.
Formally, we say that agents in a q-cluster mutation interact with each
other with probability q and interact with everyone else with probability
1 − q.
Recall, that a mutant agent playing TFT gets payoff U (TFT, All D) in
an ’All D’ equilibrium. However, mutants in a q-cluster get:

qU (TFT, TFT) + (1 − q) U (TFT, All D)

It can be easily checked that q-cluster mutants do better than the ’All D’
1
incumbents for q > 21 ≈ 5 percent. Hence, cluster mutants don’t have to
interact a lot to do a lot better than the ’meanies’ who are the majority of
the population.
1
Proposition 3 TFT is q-cluster stable for q > 21
while ’All D’ is not q-
cluster stable for any q.

6.1 Real-World Implications

Hence, a group of meanies is vulnerable to invasion by groups of ’nice’ agents
such as those playing TFT. In contrast, TFT cannot be invaded neither by
individual nor by group mutations. This last theorem is Axelrod’s basic
insight, and a lot of the examples in the book (senators, World War I trench
warfare) revolve around applications of this principle.
Cooperation can arise quickly and naturally as long as group
mutations are possible.5

5
Note, that the intuition is very similar to stochastic stability with local interaction.

6
 Lecture XV: Games with Incomplete
Information
Markus M. Möbius
April 23, 2003

Readings for this class: Fudenberg and Tirole, pages 209-215;

Dutta chapter 20.

1 Introduction
Informally, a game with incomplete information is a game where the game
being played is not common knowledge. This idea is tremendously important
in practice where its almost always a good idea to assume that something
about the game is unknown to some players. What could be unknown?

1. Payoffs: In a price or quantity competition model you may know that

your rival maximizes profits but now what his costs are (and hence his
profits).

2. Identity of other players: R&D race between drug companies - who

else will come up with the same drug?

3. What moves are possible: What levels of quality can rivals in a

quality competition choose?

4. How does the outcome depend on action: Workers work/shirk

don’t know probability of getting caught because product fails.

1
2 Examples
2.1 Example I: Crazy Incumbent
Think of a standard entry game where the incumbent is ’crazy’ with proba-
bility 1 − p and rational with probability p. The normal incumbent faces the
standard entry game from lecture 11:

In Out

1 2
0
F A

−1 1
−1 1

If the incumbent is crazy he will always want to fight because is is facing

a different subgame:

In Out

1 2
0
F A

1 −1
−1 1

2
2.2 Example II: Auction
Two bidders are trying to purchase the same item at a sealed bid auction.
The players simultaneously choose b1 and b2 and the good is sold to the
highest bidder at his bid price (assume coin flip if b1 = b2 ). Suppose that the
players’ utilities are

 vi − bi if bi > b−i
1
ui (bi , b−i ) = (v i − b i ) if bi = b−i
 2
0 if bi < b−i

The crucial incomplete information is that while each player knows his own
valuation, he does not know his rival’s. Assume, each has a prior that his
rival’s valuation is uniform on [0, 1] and that this is common knowledge.

2.3 Example III: Public Good

Two advisors of a graduate student each want the student to get a job at
school X. Each can ensure this by calling someone on the phone and lying
about how good the student is. Suppose the payoffs are as shown because
each advisor gets utility 1 from the student being employed but has a cost
of making the phone call.

Call Dont

Call 1−c1,1−c2 1−c1,1

Dont 1,1−c2 0,0

Assume that the actions are chosen simultaneously and that players know
only their own costs. They have prior that c−i ∈ U [c, c].

3
 Alternatively, we could have player 1’s cost known to all (c1 = 21 ) but
c2 ∈ {c, c} known only to player 2.
Or, player 1 is a senior faculty member who knows from experience the
cost of such phone calls (c1 = 12 ,c2 = 23 ). Player 2 is new assistant professor
who has priors c1 , c2 ∈ U [0, 2].

3 Definitions
Definition 1 A game with incomplete information G = (Φ, S, P, u) consists
of

1. A set Φ = Φ1 × ... × ΦI where Φi is the (finite) set of possible types for

player i.1

2. A set S = S1 × ... × SI giving possible strategies for each player.

3. A joint probability distribution p (φ1 , .., φI ) over the types. For finite
type space assume p (φi ) > 0 for all φi ∈ Φi .

4. A payoff function ui : S × Φ → <.

It’s useful to discuss the types in each of our examples.

• Example I: Φ1 = normal, Φ2 ∈ {π maximizer, crazy}

• Example II:Φ1 = Φ2 = (0, 1)

• Example III:Φ1 = Φ2 = [c, c]

Note that payoffs can depend not only on your type but also on your rival’s
type as well.
Players know their own types but not the other players’ types.
To analyze games of incomplete information we rely on the following
observation (Harsanyi):
Observation: Games of incomplete information can be thought of as
games of complete but imperfect information where nature makes the first
move and not everyone is informed about nature’s move, i.e. nature chooses
Φ but only reveals φi to player i.
1
Note, that the player i knows his type.

4
 N
Rational p Crazy 1−p

2 2

In Out In Out

1 2 1 2
0 0
F A F A

−1 1 1 −1
−1 1 −1 1

Think of nature simply as another player who rather than maximizing

chooses a fixed mixed strategy.
This observation should make all of the following definitions seem com-
pletely obvious. They just say that to analyze these games we may look at
NE of the game with Nature as another player.
Definition 2 A Bayesian strategy for player i in G is a function fi : Φi →
Σi . Write S Φi for the set of Bayesian strategies.2
Definition 3 A Bayesian strategy profile (f1∗ , .., fI∗ ) is a Bayesian Nash equi-
librium if
X ¡ ¢
fi∗ ∈ arg max ∗
ui fi (φi ) , f−i (φ−i ) ; φi , φ−i p (φi , φ−i )
Φi
fi ∈Si φi ,φ−i

for all i or equivalently if for all i,φi ,si

X ¡ ¢ X ¡ ¢
ui fi∗ (φi ) , f−i
∗
(φ−i ) ; φi , φ−i p (φi , φ−i ) ≥ ∗
ui si , f−i (φ−i ) ; φi , φ−i p (φi , φ−i )
φ−i φ−i

This just says that your maximize expected payoff, and given that you
know your type (that all have positive probability) this is equivalent to saying
you maximize conditional on each possible type.
Remark 1 A Bayesian Nash equilibrium is simply a Nash equilibrium of
the game where Nature moves first, chooses φ ∈ Φ from a distribution with
probability p (φ) and reveals φi to player i.
2
Note, that a Bayesian strategy is simply an extensive form strategy where each type
is treated as a distinct information set.

5
4 Solved examples
4.1 Public good I
Suppose player 1 is known to have cost c1 < 21 . Player 2 has cost c with
probability p, c with probability 1 − p. Assume that 0 < c < 1 < c and
p < 12 .

Call Dont

Call 1−c1,1−c2 1−c1,1

Dont 1,1−c2 0,0

Then the unique BNE is:

• f1∗ = Call

• f2∗ (c) = Don’t Call for all c.

Proof: In a BNE each type of player must play a BR so for the type c of
player 2 calling is strictly dominated:

u2 (s1 , call; c) < u2 (s1 , Dont; c)

for all s1 .
So f2∗ (c) = Dont.
For player 1:

u1 (Call, f2∗ ; c1 ) = 1 − c1
u1 (Dont, f2∗ ; c1 ) = pu1 (Dont, f2∗ (c) ; c1 ) + (1 − p) u1 (Dont, Dont; c1 )
≤ p + (1 − p) 0 = p

6
 Because 1 − c1 > p we know f1∗ (c1 ) = Call.
For the type c of player 2 we have:

u2 (f1∗ , Call; c) = 1 − c
u2 (f1∗ , Dont; c) = 1

because f1∗ = Call. So f2∗ (c) = Dont.

This indicates this is the only possible BNE and our calculations have
verified that it does actually work.
Process I’ve used is like iterated dominance.

4.2 Public Goods II

In the public good game suppose that c1 and c2 are drawn independently
from a uniform distribution on [0, 2]. Then the (essentially) unique BNE is
½
∗ Call if ci ≤ 23
fi (ci ) =
Don’t if ci > 23

Proof: Existence is easy - just check that each is using a BR given that
his rival calls with probability 13 and doesn’t call with probability 23 .
I’ll show uniqueness to illustrate how to find the equilibrium.
Observation: If fi∗ (ci ) = Call then fi∗ (c0i ) = Call for all c0i < ci .
© ∗ ª
To see this write z−i for P rob f−i (c−i ) = Call . If fi∗ (ci ) = call then
¡ ∗
¢ ¡ ∗
¢
Ec−i ui Call, f−i (c−i ) ; ci ≥ Ec−i ui Dont, f−i (c−i ) ; ci
1 − ci ≥ z−i

This clearly implies that for c0i < ci

¡ ∗
¢ ¡ ¢
Ec−i ui Call, f−i (c−i ) ; c0i = 1 − c0i > Ec−i ui Dont, f−i
∗
(c−i ) ; c0i = z−i

The intuition is that calling is more attractive if the cost is lower.

7
 In light of observation a BNE must be of the form:3
½
∗ Call if c1 ≤ c∗1
f1 (c1 ) =
Don’t if c1 > c∗1
½
∗ Call if c2 ≤ c∗2
f2 (c2 ) =
Don’t if c2 > c∗2

For these strategies to be a BNE we need:

1 − ci ≥ z−i for all ci < c∗i

1 − ci ≤ z−i for all ci > c∗i

Hence 1 − c∗i = z−i .

© ª c∗−i
Because c−i is uniform on [0, 2] we get z−i = P rob c−i < c∗−i = 2
.
We have:
c∗2
1 − c∗1 =
2
c∗1
1 − c∗2 =
2
It is easy to see that the unique solution to this system of equations is
c∗1 = c∗2 = 23 .

Remark 2 The result here is common in public goods situations. We get

inefficient underinvestment because of the free rider problem. Each wants
the other to call.

4.3 Auctions
In the sealed bid auction where the players’ valuations are independently
uniformly distributed on [0, 1] the unique BNE is:
v1
f1∗ (v1 ) =
2
∗ v2
f2 (v2 ) =
2
3
The cutoff values themselves are indeterminate - agents might or might not call. In
this sense the equilibrium won’t be unique. However, the cutoff values are probability zero
events and hence the strategy at these points won’t matter.

8
Proof: To verify that this is a BNE is easy. We just show that each type of
each player is using a BR:
1
Ev2 (u1 , f2∗ ; v1 , v2 ) = (v1 − b1 ) P rob (f2∗ (v2 ) < b1 )+ (v1 − b1 ) P rob (f2∗ (v2 ) = b1 )
2
£ ¤
We assume b1 ∈ 0, 12 . No larger bid makes sense given f2∗ . Hence:

Ev2 (u1 , f2∗ ; v1 , v2 ) = (v1 − b1 ) 2b1

This is a quadratic equation which we maximize by the FOC:

0 = 2v1 − 4b1 (1)

v1
Hence b1 = 2
.
To show uniqueness (or find the equilibrium if you don’t know it) is
harder. There are several methods:

• Method 1: Guess that fi∗ (vi ) = ai + ci vi then check to see which

ai and ci work.
• Method 2: Guess that the fi∗ are increasing and differentiable
and that fi∗ (vi ) is always given by the FOC and that f1∗ = f2∗ :

f1∗ (v1 ) = arg max (v1 − b1 ) P rob (f2∗ (b2 ) < b1 )

b1
¡ ¢
= arg max (v1 − b1 ) P rob b2 < f2∗−1 (b1 )
b1

= arg max (v1 − b1 ) f2∗−1 (b1 )

b1

The FOC for this is:

¯
d ∗−1 ¯
(v1 − b1 ) f2 (b1 ) − f2 (b1 )¯¯
∗−1
= 0
db1 b1 =f1∗ (v1 )
1
(v1 − f1∗ (v1 )) ∗0 ¡ ∗−1 ∗ ¢ − f2∗−1 (f1∗ (v1 )) = 0
f2 f2 (f1 (v1 ))

Using the symmetry assumption we get:

1
(v1 − f1∗ (v1 )) − v1 = 0
f10 (v1 )

9
 This gives us:
0
v1 = f1∗ (v1 ) + f1∗ (v1 ) v1
This is a differential equation. Let’s integrate on both sides:
1 2
v1 + K = f1∗ (v1 ) v1
2
∗ 1 k
f1 (v1 ) = v1 +
2 v1
The only true solution is k = 0. We need k ≤ 0 to have increasing
bids, and with 0 as a minimum bid k < 0 is impossible.

4.4 Summary of Solution Methods

We have solved BNE in our games in several ways:

• Discrete type and action space: Iterated conditional domi-

nance, or use equilibrium conditions (finite number of inequalities)
• Discrete actions, continuous type space: identify some sim-
ple cutoff rule
• Continuous action and type space: ’Guess’ equilibrium or
use FOC and differentiability of strategy to get some differential
equation

10
 Lecture XVI: Static Games of Incomplete
Information II
Markus M. Möbius
April 24, 2003

Readings for this class: Gibbons Chapter 3

1 Purification
People are often uncomfortable with mixed equilibria - why should agents
who are indifferent between strategies mix precisely at the right rate to make
the other player indifferent between the strategies in her support?
Harsanyi (1973) developed the idea of ‘purifying’ mixed strategies. The
idea is best explained with an example. Consider the standard BOS game
below:
F O

F 2,1 0,0

O 0,0 1,2

The game has two pure Nash equilibria (F,F) and (O,O) and a mixed one
( 23 F + 31 O, 13 F + 23 O).

1
 Harsanyi pointed out that even if players know each other reasonably well
the above game is an idealization. In reality none of the two players can be
absolutely sure about the other’s payoffs. Instead, he suggested real-world
payoffs are more likely to look as follows:

F O

F 2+a,1 0,0

O 0,0 1,2+b

Each player payoffs are slightly disturbed - assume that both a and b are
distributed uniformly over [0, ²] for ² small. Each player knows his own type
but not the type of the other player.
We now have a static game of incomplete information. As before an
informed guess might tell us that an equilibrium has some nice monotonicity
properties. In particular, we guess that player 1 chooses F whenever a > α
and player 2 chooses O when b > β.
Note, that we are looking for equilibria in which each player
plays a pure strategy.
In this case, the probability that player 1 will player action F is p = ²−α
²
and the probability that player 2 will do so is q = β² . The marginal agent
has to be indifferent between choosing F and O in both cases. This gives us
the following equilibrium conditions:

(2 + ²α)q = (1 − q)
p = (2 + ²β)(1 − p)

This gives us a quadratic equation in α and β. The important point is,

however, that as ² → 0 the probabilities p and q approach precisely the
probabilities of the mixed equilibrium.

2
 In other words, the BNE of the perturbed game in which each type of
agent plays a pure strategy ‘looks’ just like the mixed strategy of the original
game.
Harsanyi showed (1) that each perturbation gives rise to an equilibrium
which looks like a mixed equilibrium, and (2) that each mixed equilibrium
can be approximated by a sequence of BNE as constructed above.

3
 Lecture XVII: Dynamic Games with
Incomplete Information
Markus M. Möbius
May 5, 2003

Readings for this class: Osborne and Rubinstein, Fudenberg

and Tirol, chapter 8.2

1 Introduction
In the last lecture I introduced the idea of incomplete information. We ana-
lyzed some important simultaneous move games such as sealed bid auctions
and public goods.
In practice, almost all of the interesting models with incomplete informa-
tion are dynamic games also. Before we talk about these games we’ll need a
new solution concept called Perfect Bayesian Equilibrium.
Intuitively, PBE is to extensive form games with incomplete games what
SPE is to extensive form games with complete information. The concept
we did last time, BNE is a simply the familiar Nash equilibrium under the
Harsanyi representation of incomplete information. In principle, we could
use the Harsanyi representation and SPE in dynamic games of incomplete
information. However, dynamic games with incomplete information typi-
cally don’t have enough subgames to do SPE. Therefore, many ’non-credible’
threats are possible again and we get too many unreasonable SPE’s. PBE
allows subgame reasoning at information sets which are not single nodes
whereas SPE only applies at single node information sets of players (because
only those can be part of a proper subgame).
The following example illustrates some problems with SPE.

1
1.1 Example I - SPE
Our first example has no incomplete information at all.

L R

2 2

A B

1 3

1 3

Its unique SPE is (R,B).

The next game looks formally the same - however, SPE is the same as
NE because the game has no proper subgames.

L R RR

2 2 2

A B A B

1 3 1 3

1 3 1 3

The old SPE survives - all (pR + (1 − p) RR, B) for all p is SPE. But there
are suddenly strange SPE such as (L, qA + (1 − q) B) for q ≥ 21 . Player 2’s

2
strategy looks like an non-credible threat again - but out notion of SPE can’t
rule it out!
Remember: SPE can fail to rule out actions which are not optimal given
any ’beliefs’ about uncertainty.

Remark 1 This problem becomes severe with incomplete information: moves

of Nature are not observed by one or both players. Hence the resulting exten-
sive form game will have no or few subgames. This and the above example
illustrate the need to replace the concept of a ’subgame’ with the concept of a
’continuation game’.

1.2 Example II: Spence’s Job-Market Signalling

The most famous example of dynamic game with incomplete information is
Spence’s signalling game. There are two players - a firm and a worker. The
worker has some private information about his ability and has the option of
acquiring some education. Education is always costly, but less so for more
able workers. However, education does not improve the worker’s
productivity at all! In Spence’s model education merely serves as a signal
to firms. His model allows equilibria where able workers will acquire educa-
tion and less able workers won’t. Hence firms will pay high wages only to
those who acquired education - however, they do this because education has
revealed the type of the player rather than improved his productivity.
Clearly this is an extreme assumption - in reality education has presum-
ably dual roles: there is some signalling and some productivity enhancement.
But it is an intriguing insight that education might be nothing more than a
costly signal which allows more able workers to differentiate themselves from
less able ones.
Let’s look at the formal set-up of the game:

• Stage 0: Nature chooses the ability θ of a worker. Suppose Θ = {2, 3}

and that P rob (θ = 2) = p and P rob (θ = 3) = 1 − p.

• Stage I: Player 1 (worker) observes his type and chooses eduction level
e ∈ {0, 1}. Education has cost ceθ . Note, that higher ability workers
have lower cost and that getting no education is costless.

• Stage II: Player 2 (the competitive labor market) chooses the wage
rate w (e) of workers after observing the education level.

3
 Suppose that u1 (e, w, ; θ) = w − ceθ and that u2 (e, w; θ) = − (w − θ)2 .
Note, that education does not enter the firm’s utility function. Also note,
that the BR of the firm is to set wages equal to the expected ability of
the worker under this utility function. This is exactly what the competitive
labor market would do if θ is equal to the productivity of a worker (the
dollar amount of output he produces). If a firm pays above the expected
productivity it will run a loss, and if it pays below some other firm would
come in and offer more to the worker. So the market should offer exactly
the expected productivity. The particular (rather strange-looking) utility
function we have chosen implements the market outcome with a single firm
- it’s a simple shortcut.
Spence’s game is a signalling game. Each signalling game has the same
three-part structure: nature chooses types, the sender (worker) observes his
type and takes and action, the receiver (firm) sees that action but not the
worker’s type. Hence the firm tries to deduce the worker’s type using his
action. His action therefore serves as a signal. Spence’s game is extreme
because the signal (education) has no value to the firm except for its sig-
nalling function. This is not the case for all signalling models: think of a car
manufacturer who can be of low or high quality and wants to send a signal
to the consumer that he is a high-quality producer. He can offer a short or
long warranty for the car. The extended warranty will not only signal his
type but also benefit the consumer.
The (Harsanyi) extensive form representation of Spence’s game (and any
other signalling game) is given below.
N
Type θ=2: p Type θ=3: 1−p

W W

e e

F F

w w

w−ce/2 w−ce/3
−(w−2)2 −(w−3)2

4
1.3 Why does SPE concept together with Harsanyi
representation not work?
We could find the set of SPE in the Harsanyi representation of the game.
The problem is that the game has no proper subgame in the second round
when the firm makes its decision. Therefore, the firm can make unreasonable
threats such as the following: both workers buy education and the firms
pays the educated worker w = 3 − p (his expected productivity), and the
uneducated worker gets w = −235.11 (or something else). Clearly, every
worker would get education, and the firm plays a BR to a worker getting
education (check for yourself using the Harsanyi representation).
However, the threat of paying a negative wage is unreasonable. Once the
firm sees a worker who has no education it should realize that the worker has
a least ability level 2 and should therefore at least get a wage of w = 2.

2 Perfect Bayesian Equilibrium

Let G be a multistage game with incomplete information and observed ac-
tions in the Harsanyi representation. Write Θi for the set of possible types
for player i and Hi to be the set of possible information sets of player i. For
each information setS hi ∈ Hi denote the set of nodes in the information set
with Xi (hi ) and X Hi Xi (hi ).
A strategy in G is a function si : Hi → ∆ (Ai ). Beliefs are a function
µi : Hi → ∆ (Xi ) such that the support of belief µi (hi ) is within Xi (hi ).

Definition 1 A PBE is a strategy profile s∗ together with a belief system

µ such that

1. At every information set strategies are optimal given beliefs and oppo-
nents’ strategies (sequential rationality).
¡ ¢
σi∗ (h) maximizes Eµi (x|hi ) ui σi , σ−i
∗
|h, θi , θ−i

2. Beliefs are always updated according to Bayes rule when applicable.

The first requirement replaces subgame perfection. The second requirement

makes sure that beliefs are derived in a rational manner - assuming that
you know the other players’ strategies you try to derive as many beliefs as

5
possible. Branches of the game tree which are reached with zero probability
cannot be derived using Bayes rule: here you can choose arbitrary beliefs.
However, the precise specification will typically matter for deciding whether
an equilibrium is PBE or not.

Remark 2 In the case of complete information and observed actions PBE

reduces to SPE because beliefs are trivial: each information set is a singleton
and the belief you attach to being there (given that you are in the correspond-
ing information set) is simply 1.

2.1 What’s Bayes Rule?

There is a close connection between agent’s actions and their beliefs. Think
of job signalling game. We have to specify the beliefs of the firm in the
second stage when it does not know for sure the current node, but only the
information set.
Let’s go through various strategies of the worker:

• The high ability worker gets education and the low ability worker does
not: e (θ = 2) = 0 and e (θ = 3) = 1. In this case my beliefs at the
information set e = 1 should be P rob (High|e = 1) = 1 and similarly,
P rob (High|e = 0) = 0.

• Both workers get education. In this case, we should have:

P rob (High|e = 1) = 1 − p (1)

The beliefs after observing e = 0 cannot be determined by Bayes rule

because it’s a probability zero event - we should never see it if players
follow their actions. This means that we can choose beliefs freely at
this information set.

• The high ability worker gets education and the low ability worker gets
education with probability q. This case is less trivial. What’s the prob-
ability of seeing worker get education - it’s 1 − p + pq. What’s the
probability of a worker being high ability and getting education? It’s
1 − p. Hence the probability that the worker is high ability after we
1−p
have observed him getting education is 1−p+pq . This is the non-trivial
part of Bayes rule.

6
 Formally, we can derive the beliefs at some information set hi of player
i as follows. There is a probability p (θj ) that the other player is of type θj .
These probabilities are determined by nature. Player j (i.e. the worker) has
taken some action aj such that the information set hi was reached. Each
type of player j takes action aj with some probability σj∗ (aj |θj ) according to
his equilibrium strategy. Applying Bayes rule we can then derive the belief
of player i that player j has type θj at information set hi :

p (θj ) σj∗ (aj |θj )

µi (θj |aj ) = P ³ ´ ³ ´ (2)
p ˜
θ σ ∗
a | ˜
θ
θ˜j ∈Θj j j j j

1. In the job signalling game with separating beliefs Bayes rule gives us
exactly what we expect - we belief that a worker who gets education is
high type.
1−p
2. In the pooling case Bayes rule gives us P rob (High|e = 1) = p×1+(1−p)×1 =
1 − p. Note, that Bayes rule does NOT apply for finding the
beliefs after observing e = 0 because the denominator is zero.
(1−p)×1
3. In the semi-pooling case we get P rob (High|e = 1) = p×q+(1−p)×1
. Sim-
(1−p)×0
ilarly, P rob (High|e = 0) = p×(1−q)+(1−p)×0
= 0.

3 Signalling Games and PBE

It turns out that signalling games are a very important class of dynamic
games with incomplete information in applications. Because the PBE con-
cept is much easier to state for the signalling game environment we define it
once again in this section for signalling games. You should convince yourself
that the more general definition from the previous section reduces to the
definition below in the case of signalling games.

3.1 Definitions and Examples

Every signalling game has a sender, a receiver and two periods. The sender
has private information about his type and can take an action in the first
action. The receiver observes the action (signal) but not the type of the
sender, and takes his action in return.

7
 • Stage 0: Nature chooses the type θ1 ∈ Θ1 of player 1 from probability
distribution p.
• Stage 1: Player 1 observes θ1 and chooses a1 ∈ A1 .
• Stage 2: Player 2 observes a1 and chooses a2 ∈ A2 .
The players utilities are:
u1 = u1 (a1 , a2 ; θ1 ) (3)
u2 = u2 (a1 , a2 ; θ1 ) (4)

3.1.1 Example 1: Spence’s Job Signalling Game

• worker is sender; firm is receiver
• θ is the ability of the worker (private information to him)
• A1 = {educ, no educ}
• A2 = {wage rate}

3.1.2 Example 2: Initial Public Offering

• player 1 - owner of private firm
• player 2 - potential investor
• Θ - future profitability
• A1 - fraction of company retained
• A2 - price paid by investor for stock

3.1.3 Example 3: Monetary Policy

• player 1 = FED
• player 2 - firms
• Θ - Fed’s preference for inflation/ unemployment
• A1 - first period inflation
• A2 - expectation of second period inflation

8
3.1.4 Example 4: Pretrial Negotiation
• player 1 - defendant

• player 2 - plaintiff

• Θ - extent of defendant’s negligence

• A1 - settlement offer

• A2 - accept/reject

3.2 PBE in Signalling Games

A PBE in the signalling game is a strategy profile (s∗1 (θ1 ) , s∗2 (a1 )) together
with beliefs µ2 (θ1 |a1 ) for player 2 such that
1. Players strategies are optimal given their beliefs and the opponents’
strategies, i.e.

s∗1 (θ1 ) maximizes u1 (a1 , s∗2 (a1 ) ; θ1 ) for all θ1 ∈ Θ1 (5)

X
s∗2 (a1 ) maximizes u2 (a1 , a2 ; θ1 ) µ2 (θ1 |a1 ) for all a1 ∈ (6)
A1
θ1 ∈Θ1

2. Player 2’s beliefs are compatible with Bayes’ rule. If any type of player
1 plays a1 with positive probability then
p (θ1 ) P rob (s∗1 (θ1 ) = a1 )
µ2 (θ1 |a1 ) = P 0 ∗ 0
for all θ1 ∈ Θ1
θ 0 ∈Θ1 p (θ1 ) P rob (s1 (θ1 ) = a1 )
1

3.3 Types of PBE in Signalling Games

To help solve for PBE’s it helps to think of all PBE’s as taking one of the
following three forms”
1. Separating - different types take different actions and player 2 learns
type from observing the action

2. Pooling - all types of player 1 take same action; no info revealed

3. Semi-Separating - one or more types mixes; partial learning (often

only type of equilibrium

9
Remark 3 In the second stage of the education game the ”market” must
have an expectation that player 1 is type θ = 2 and attach probability µ (2|a1 )
to the player being type 2. The wage in the second period must be between
2 and 3. This rules out the unreasonable threat of the NE I gave you in the
education game (with negative wages).1

Remark 4 In the education game suppose the equilibrium strategies are

s∗1 (θ = 2) = 0 and s∗1 (θ = 3) = 1, i.e. only high types get education. Then
for any prior (p, 1 − p) at the start of the game beliefs must be:

µ2 (θ = 2|e = 0) = 1
µ2 (θ = 3|e = 0) = 0
µ2 (θ = 2|e = 1) = 0
µ2 (θ = 3|e = 1) = 1
1
If player 1’s strategy is s∗1 (θ = 2) = 2
× 0 + 12 × 1 and s∗1 (θ = 3) = 1:

µ2 (θ = 2|e = 0) = 1
µ2 (θ = 3|e = 0) = 0
p
2 p
µ2 (θ = 2|e = 1) = p =
+1−p 2
2−p
2 − 2p
µ2 (θ = 3|e = 1) =
2−p
Also note, that Bayes rule does NOT apply after an actions which should not
occur in equilibrium. Suppose s∗1 (θ = 2) = s∗1 (θ = 3) = 1 then it’s OK to
assume
57
µ2 (θ = 2|e = 0) =
64
7
µ2 (θ = 3|e = 0) =
64
µ2 (θ = 2|e = 1) = p
µ2 (θ = 3|e = 1) = 1 − p

The first pair is arbitrary.

1
It also rules out unreasonable SPE in the example SPE I which I have initially. Under
any beliefs player 2 should strictly prefer B.

10
Remark 5 Examples SPE II and SPE III from the introduction now make
sense - if players update according to Bayes rule we get the ’reasonable’ beliefs
of players of being with equal probability in one of the two nodes.

4 Solving the Job Signalling Game

Finally, after 11 tough pages we can solve our signalling game. The solution
depends mainly on the cost parameter c.

4.1 Intermediate Costs 2 ≤ c ≤ 3

A separating equilibrium of the model is when only the able worker buys
education and the firm pays wage 2 to the worker without education and
wage 3 to the worker with education. The firm beliefs that the worker is able
iff he gets educated.

• The beliefs are consistent with the equilibrium strategy profile.

• Now look at optimality. Player 2 sets the wage to the expected wage
so he is maximizing.

• Player 1 of type θ = 2 gets 3 − 2c ≤ 2 for a1 = 1 and 2 for a1 = 0.

Hence he should not buy education.
c
• Player 1 of type θ = 3 gets 3 − 3
≥ 2 for a1 = 1 and 2 for a1 = 0.
Hence he should get educated.

1. Note that for too small or too big costs there is no separating PBE.

2. There is no separating PBE where the θ = 2 type gets an education

and the θ = 3 type does not.

4.2 Small Costs c ≤ 1

A pooling equilibrium of the model is that both workers buy education and
that the firm pays wage w = 3 − p if it observes education, and wage 2
otherwise. The firm believes that the worker is able with probability 1 − p if
it observes education, and that the worker is of low ability if it observes no
education.

11
 • The beliefs are consistent with Bayes rule for e = 1. If e = 0 has been
observed Bayes rule does not apply because e = 0 should never occur
- hence any belief is fine. The belief that the worker is low type if he
does not get education makes sure that the worker gets punished for
not getting educated.

• The firm pays expected wage - hence it’s optimal response. The low
ability guy won’t deviate as long 2.5 − 2c ≥ 2 and the high ability type
won’t deviate as long as 2.5 − 3c ≥ 2. For c ≤ 1 both conditions are
true.

1. While this pooling equilibrium only works for small c there is always
another pooling equilibrium where no worker gets education and the
firms thinks that any worker who gets education is of the low type.

4.3 1<c<2
Assume that p = 12 for this section. In the parameter range 1 < c < 2 there is
a semiseparating PBE of the model. The high ability worker buys education
and the low ability worker buys education with positive probability q. The
1
wage is w = 2 if the firm observes no education and set to w = 2 + 1+q if
it observes education. The beliefs that the worker is high type is zero if he
1
gets no education and 1+q if he does.

• Beliefs are consistent (check!).

• Firm plays BR.

1 c
• Player 1 of low type won’t deviate as long as 2 + 1+q
− 2
≤ 2.
1 c
• Player 1 of high type won’t deviate as long as 2 + 1+q
− 3
≥ 2.

Set 1 + q = 2c . It’s easy to check that the first condition is binding and
the second condition is strictly true. So we are done if we choose q = 2c − 1.
Note, that as c → 2 we get back the separating equilibrium and as c → 1 we
get the pooling one.

12
 Lecture XVIII: Games with Incomplete
Information II - More Examples
Markus M. Möbius
May 5, 2003

1 Introduction
This lecture gives more examples of games of incomplete information, in
particular signalling games.

2 The Lobbying Game

We consider the following model of lobbying.

• Nature chooses whether the lobbyist’s industry is headed for Good or

Bad times and reveals the state of the world {G, B} to the lobbyist.

• The a priori probability of Good times is p.

• The Lobbyist can then send a message to Congress. Following this

message, Congress chooses whether or not to enact a subsidy. Let
{S, N } denote the actions available to Congress. At the end of the
period, the state of the world is revealed to Congress.

• A subsidy costs Congress k. It generates a return r > k for Congress

if and only if times are Bad. We assume that (1 − p)r < k.

• The Lobbyist gets a payoff of zero if the subsidy is not passed, a payoff
of 1 if the subsidy passes and times are Bad, and a subsidy of 1/2 if
the subsidy passes and times are good.

1
 1. Is there a PBE in which the subsidy passes? Answer: NO

2. Now suppose lobbying Congress is costly. In particular, the

lobbyist must incur a cost c to be heard. Show that if c > 1/2,
there is a PBE in which the subsidy passes whenever the state
of the world is bad.

3 Legal Settlements
• There are two players, a plaintiff and a defendant in a civil suit. The
plaintiff knows whether or not he will win the case if he goes to trial,
but the defendant does not have this information.

• The defendant knows that the plaintiff knows who would win, and the
defendant has prior beliefs that there is probability 13 that the plaintiff
will win; these prior beliefs are common knowledge.

• If the plaintiff wins, his payoff is 3 and the defendant’s payoff is -4;
if the plaintiff loses, his payoff is -1 and the defendant’s is 0. (This
corresponds to the defendant paying cash damages of 3 if the plaintiff
wins, and the loser of the case paying court costs of 1.)

• The plaintiff has two possible actions: He can ask for either a low
settlement of m = 1 or a high settlement of m = 2. If the defendant
accepts a settlement offer of m, the plaintiff’s payoff is m and the
defendant’s is −m. If the defendant rejects the settlement offer, the
case goes to court.

1. List all the pure-strategy PBE strategy profiles. For each such profile,
specify the beliefs of the defendant as a function of m, and verify that
the combination of these beliefs and the profile is in fact a PBE.

2. Explain why the other profiles are not PBE.

4 Corporate Investment
This is a variant of the IPO game. An entrepreneur needs financing to realize
a new project and can offer an outside investor an equity stake in his company.

2
The stake gives the investor a share of the future (next period’s) cashflow
of the company: the profits from the existing business plus the profits from
the project. The profitability of the nw project is known to both investor
and entrepreneur. However, only the entrepreneur knows the profitability of
the existing company. The investor therefore runs the risk of investing in
an unprofitable business. The new project requires investment I and gives
payoff R > (1 + r) I in the next period (where r is the interest rate).

• Nature chooses the type of the entrepreneur’s firm which can be highly
profitable (π = H) or less profitable (π = L). The business is not so
profitable with probability p.

• The entrepreneur observes π and then offers equity stake s such that
0 ≤ s ≤ 1.

• The investor can accept or reject.

5 Monetary Policy
5.1 The Barro-Gordon model (1983)
There are two periods. In the first period firms form expectations about
inflation πe . Their payoff is − (π − πe )2 . In the second period the Fed sets
inflation π. The Fed has objective function:

−cπ 2 − (y − y ∗ )2 (1)

Actual output y is:

y = by ∗ + d (π − π ∗ ) (2)
where b < 1.

5.2 Barro-Gordon with Signalling

Now assume that the Fed can either be weak (c = W ) or strong (c = S) such
that S > W > 0. The firm and the Fed play the Barro-Gordon game now
for two periods: the first period can now be used to signal the resolve of the
Fed.