Introduction
Muhamet Yildiz
(Lecture 1)
Game Theory is a misnomer for Multiperson Decision Theory, analyzing the decision-
making process when there are more than one decision-makers where each agent’s payoff
possibly depends on the actions taken by the other agents. Since an agent’s preferences
on his actions depend on which actions the other parties take, his action depends on his
beliefs about what the others do. Of course, what the others do depends on their beliefs
about what each agent does. In this way, a player’s action, in principle, depends on the
actions available to each agent, each agent’s preferences on the outcomes, each player’s
beliefs about which actions are available to each player and how each player ranks the
outcomes, and further his beliefs about each player’s beliefs, ad in
fi
nitum.
Under perfect competition, there are also more than one (in fact, in
fi
nitely many)
decision makers. Yet, their decisions are assumed to be decentralized. A consumer tries
to choose the best consumption bundle that he can afford, given the prices — without
paying attention what the other consumers do. In reality, the future prices are not
known. Consumers’ decisions depend on their expectations about the future prices. And
the future prices depend on consumers’ decisions today. Once again, even in perfectly
competitive environments, a consumer’s decisions are affected by their beliefs about
what other consumers do — in an aggregate level.
When agents think through what the other players will do, taking what the other
players think about them into account, they may
fi
ndaclearwaytoplaythegame.
Consider the following “game”:
1
1
\
2
L m R
T
(1,1) (0,2) (2,1)
M
(2,2) (1,1) (0,0)
B
(1,0) (0,0) (
−
1,1)
Here, Players 1 has strategies, T, M, B and Player 2 has strategies L, m, R. (They
pick their strategies simultaneously.) The payoffs for players 1 and 2 are indicated by
the numbers in parentheses, the
fi
rst one for player 1 and the second one for player 2.
For instance, if Player 1 plays T and Player 2 plays R, then Player 1 gets a payoff of 2
and Player 2 gets 1. Let’s assume that each player knows that these are the strategies
and the payoffs, each player knows that each player knows this, each player knows that
each player knows that each player knows this,... ad in
fi
nitum.
Now, player 1 looks at his payoffs, and realizes that, no matter what the other player
plays, it is better for him to play M rather than B. That is, if 2 plays L, M gives 2 and
B gives 1; if 2 plays m, M gives 1, B gives 0; and if 2 plays R, M gives 0, B gives -1.
Therefore, he realizes that he should not play B.
1
NowhecomparesTandM.Herealizes
that, if Player 2 plays L or m, M is better than T, but if she plays R, T is de
fi
nitely
better than M. Would Player 2 play R? What would she play? To
fi
nd an answer to
these questions, Player 1 looks at the game from Player 2’s point of view. He realizes
that, for Player 2, there is no strategy that is outright better than any other strategy.
For instance, R is the best strategy if 1 plays B, but otherwise it is strictly worse than
m. Would Player 2 think that Player 1 would play B? Well, she knows that Player 1 is
trying to maximize his expected payoff,givenbythe
fi
rst entries as everyone knows. She
must then deduce that Player 1 will not play B. Therefore, Player 1 concludes, she will
not play R (as it is worse than m in this case). Ruling out the possibility that Player 2
plays R, Player 1 looks at his payoffs, and sees that M is now better than T, no matter
what. On the other side, Player 2 goes through similar reasoning, and concludes that 1
must play M, and therefore plays L.
This kind of reasoning does not always yield such a clear prediction. Imagine that
you want to meet with a friend in one of two places, about which you both are indifferent.
Unfortunately, you cannot communicate with each other until you meet. This situation
1
After all, he cannot have any belief about what Player 2 plays that would lead him to play B when
M is available.
2
is formalized in the following game, which is called pure coordination game:
\
2
L tRght
Top
(1,1) (0,0)
Bottom
(0,0) (1,1)
Here, Player 1 chooses between Top and Bottom rows, while Player 2 chooses between
Left and Right columns. In each box, the
fi
rst and the second numbers denote the von
Neumann-Morgenstern utilities of players 1 and 2, respectively. Note that Player 1
prefers Top to Bottom if he knows that Player 2 plays Left; he prefers Bottom if he
knows that Player 2 plays Right. He is indifferent if he thinks that the other player is
likely to play either strategy with equal probabilities. Similarly, Player 2 prefers Left if
she knows that player 1 plays Top. There is no clear prediction about the outcome of
this game.
One may look for the stable outcomes (strategy pro
fi
les) in the sense that no player
has incentive to deviate if he knows that the other players play the prescribed strategies.
Here, Top-Left and Bottom-Right are such outcomes. But Bottom-Left and Top-Right
are not stable in this sense. For instance, if Bottom-Left is known to be played, each
player would like to deviate — as it is shown in the following
fi
gure:
\
2
t Ri t
Top
(1,1)
⇐⇓
(0,0)
Bottom
(0,0)
⇑
=
⇒
(1,1)
(Here, ⇑ means player 1 deviates to Top, etc.)
Unlike in this game, mostly players have different preferences on the outcomes, in-
ducing con
fl
ict. In the following game, which is known as the Battle of Sexes,con
fl
ict
and the need for coordination are present together.
\
2
L tRight
Top
(2,1) (0,0)
Bottom
(0,0) (1,2)
Here, once again players would like to coordinate on Top-Left or Bottom-Right, but
now Player 1 prefers to coordinate on Top-Left, while Player 2 prefers to coordinate on
Bottom-Right. The stable outcomes are again Top-Left and Bottom- Right.
3
1
1
1
1
T
B
2
2
L
R
L
R
(2,1)
(0,0)
(0,0)
(1,2)
Figure 1:
Now, in the Battle of Sexes, imagine that Player 2 knows what Player 1 does when
she takes her action. This can be formalized via the following tree:
Here, Player 1 chooses between Top and Bottom, then (knowing what Player 1 has
chosen) Player 2 chooses between Left and Right. Clearly, now Player 2 would choose
Left if Player 1 plays Top, and choose Right if Player 1 plays Bottom. Knowing this,
Player 1 would play Top. Therefore, one can argue that the only reasonable outcome of
this game is Top-Left. (This kind of reasoning is called backward induction.)
When Player 2 is to check what the other player does, he gets only 1, while Player 1
gets 2. (In the previous game, two outcomes were stable, in which Player 2 would get 1
or 2.) That is, Player 2 prefers that Player 1 has information about what Player 2 does,
rather than she herself has information about what player 1 does. When it is common
knowledgethataplayerhassomeinformationornot,theplayermayprefernottohave
that information — a robust fact that we will see in various contexts.
Exercise 1 Clearly, this is generated by the fact that Player 1 knows that Player 2
will know what Player 1 does when she moves. Consider the situation that Player 1
thinks that Player 2 will know what Player 1 does only with probability π<1,andthis
probability does not depend on what Player 1 does. What will happen in a “reasonable”
equilibrium? [By the end of this course, hopefully, you will be able to formalize this
4
situation, and compute the equilibria.]
Another interpretation is that Player 1 can communicate to Player 2, who cannot
communicate to player 1. This enables player 1 to commit to his actions, providing a
strong position in the relation.
Exercise 2 Consider the following version of the last game: after knowing what Player
2 does, Player 1 gets a chance to change his action; then, the game ends. In other words,
Player 1 chooses between Top and Bottom; knowing Player 1’s choice, Player 2 chooses
between Left and Right; knowing 2’s choice, Player 1 decides whether to stay where he
is or to change his position. What is the “reasonable” outcome? What would happen if
changing his action would cost player 1 c utiles?
Imagine that, before playing the Battle of Sexes, Player 1 has the option of exiting,
in which case each player will get 3/2, or playing the Battle of Sexes. When asked to
play, Player 2 will know that Player 1 chose to play the Battle of Sexes.
There are two “reasonable” equilibria (or stable outcomes). One is that Player 1
exits, thinking that, if he plays the Battle of Sexes, they will play the Bottom-Right
equilibrium of the Battle of Sexes, yielding only 1 for player 1. The second one is
that Player 1 chooses to Play the Battle of Sexes, and in the Battle of Sexes they play
Top-Left equilibrium.
1
Play
Exit
2
1
Left
Right
Top
(2,1)
(0,0)
Bottom
(0,0)
(1,2)
(3/2,3/2)
Some would argue that the
fi
rst outcome is not really reasonable? Because, when
askedtoplay,Player2willknowthatPlayer1haschosentoplaytheBattleofSexes,
forgoing the payoff of 3/2. She must therefore realize that Player 1 cannot possibly be
5