Lecture 1: Intro to game theory; static games with
complete information I
1 Intro to game theory
1.1 What is game theory?
De�nition: The study of multi-person decision problems. It analyses situations in which
two or more intellectual, rational individuals make decisions that will in�uence one
another’s welfare.
Examples: house auctions; a �rm and a union bargaining over salaries; airlines setting
airfares; jury members deciding on a verdict; governments deciding whether to go to
war; animals �ghting over prey; and of course traditional games such as chess and
poker…
Counter-examples: individual investment decision/resource allocation; production/purchase
in a perfectly competitive market
Goal: Game theory provides general mathematical techniques to predict the outcomes of
these situations. It also helps people to understand how human interaction is a�ected
by factors such as information, risk, social norms, punishment and threat, reputation,
etc.
• Game theory applies a simple and tractable solution concept in an extremely wide
range of applications.
• The majority of new research on microeconomic theory involves game theory.
• Remarkable advancement in game theory has been made in the past 100 years, yet
this science is still full of open questions – some are old puzzles, such as equilibrium
selection, some are new questions emerged from new business models.
Warning:
• This unit is very mathematical and it demands a great deal of logical thinking.
• It studies multi-person interaction at an abstract level. If you are more interested
in applications of game theory in business, please consider the alternative units:
ECOS2201, ECOS3003, ECOS3005.
1
1.2 Use models to analyse complex human interaction
• A model is like a fable: it parallels a situation in real life and conveys a moral, yet it
can be unrealistic and simplistic. But the simplicity is precisely its advantage! (The
most realistic model is the most useless!)
A good model is free of irrelevant details and unnecessary diversions . It helps us discern
an aspect of reality. Once we come back to reality, something signi�cant remains. Just
as in a good fable.
• In Game Theory we study strategic situations with many decision makers. Who are
our decision makers?
Real people are, of course, too complicated, so we will replace them with rational utility
maximisers whose behavior we can fully understand. Hopefully, they will turn out to
be good fable characters!
• How to develop an understanding of human interaction using models?
� Start with the simplest model to get the sharpest prediction.
� Then, complicate the model a little bit. Do we still get the same answer? If so,
discard this direction of extension. If not, pursue it.
1.3 Structure of the unit
1.3.1 Content
1. Static games with complete information (examples: rock-paper-scissors)
2. Dynamic games with complete information (examples: repeated rock-paper-scissors)
3. Static games with incomplete information (examples: strategic voting)
4. Dynamic games with incomplete information (examples: persuasion)
One round of action?
Yes No
Complete information?
Yes I II
No III IV
Complexity: I < II, III < IV
Restrictiveness of solution concept: I < II, III < IV
When a game is played for multiple rounds or when uncertainty is involved, a wider range
of outcomes are possible, which makes it di�cult to predict a unique outcome. To solve this
problem, we will learn to develop more and more restrictive solution concepts in order to
select the more likely predictions as the game gets complicated.
2
2 Static games with complete information
2.1 How to describe a static game with complete information?
Example 1. The Prisoners' Dilemma
Prisoner 2
not confess confess
Prisoner 1
not confess -1, -1 -9, 0
confess 0, -9 -6, -6
The police hold the suspects in separate cells and explain the consequences that will
follow from the actions they could take. If neither confesses then both will be convicted of a
minor o�ense and sentenced to one month in jail. If both confess then both will be sentenced
to jail for six months. Finally, if one confesses but the other does not, then the confessor
will be released immediately but the other will be sentenced to nine months in jail-six for
the crime and a further three for obstructing justice.
De�nition 1. The normal-form representation of a game speci�es:
1) the players in the game: 1, 2, 3, ..., n
2) the set of strategies available to each player: S1, S2, ..., Sn (each Si is a set that contains
all strategies sj ∈ Si available to player i)
3) the payo� received by each player for each combination of strategies that could be
chosen by the players {ui(s1, ..., sn)}i
In this example:
The players in the game: prisoner 1, prisoner 2
The strategies of each player: S1 = S2 ={confess, not confess}
The payo� functions: as speci�ed by the numbers in the payo� matrix (u1(NC,NC) =
−1, u1(C,NC) = 0, etc.)
Convention: �rst number in the box = payo� for the row player (Prisoner 1), second
number in the box = payo� for the column player (Prisoner 2)
Remark 1. Game theory does not study what the players' payo�s should be. Game theory
takes the payo� functions as given and predicts the strategic outcome.
In game theory we often say that the players choose their strategies �simultaneously�. It
doesn't mean that the players must literally choose their actions at the same time; it only
requires that each player chooses his strategy without knowing other players' choices. If,
instead, a player can choose his strategy after knowing what others have chosen, then the
outcome of the game may be very di�erent. We will discuss those cases next month.
2.2 How to predict the outcome of a static game with complete
information?
2.2.1 Iterated elimination of strictly dominated strategies
Revisit the prisoners' dilemma: for either player, no matter what the other player chooses,
it is always better to confess. Therefore, if the game is correctly speci�ed and the prisoners
3
are both rational, we predict that they will both confess and be sentenced for 6 months, even
though they are both better o� if neither confesses.
If you think this outcome is unreasonable, my guess is that you might be thinking about
a di�erent game instead, perhaps a game where players feel guilty if they confess, or that
they fear there will be bad consequences in the future if they confess. Those cases will have
di�erent payo� matrices or di�erent game structure.
If the prisoners care only about this one-time sentence, then we predict that �confess,
confess� is the unique outcome, because to confess is the dominant strategy no matter what
the other prisoner does. This logic turns out to be very useful to predict the outcomes of a
lot of games. Let's generalise this concept.
Other applications of the prisoner's dilemma game: two classmates working on a joint
project, two countries deciding how much to spend on national defense, two �rms deciding
whether to charge high or low price.
De�nition 2. In a normal-form game, let s′i and s
′′
i be feasible strategies for player i.
Strategy s′i is strictly dominated by strategy s
′′
i if for each feasible combination of the other
players' strategies, i's payo� from playing s′i is strictly less than i's payo� from playing s
′′
i .
• Rational players do not play strictly dominated strategies.
• We can eliminate irrational game outcomes by iteratively eliminating strictly domi-
nated strategies.
Example 2. Iterated elimination of strictly dominated strategies
Player 2
Left Middle Right
Player 1
Up 1, 0 1, 2 0, 1
Down 0, 3 0, 1 2, 0
First round: Right is strictly dominated by Middle for player 2. => Delete Right.
Second round: Down is strictly dominated by Up for player 1. => Delete Down.
Third round: Left is strictly dominated by Middle. => Delete Left.
=> Unique outcome: (Up, Middle).
Remark 2. Two problems with this method:
Problem 1: Sometimes it deletes too many outcomes because it requires a common knowl-
edge that players are rational. I.e., it assumes that: all players are rational; all players know
that all players are rational; all players know that all players know that all players are
rational……
Example: beauty contest game: each pick a number between 0 and 100. Calculate 2
3
×
the mean. You win if your number is the closest to the result.
Solution: Epistemic game theory; behavioral economics with bounded rationality (unfor-
tunately this is beyond the scope of this class)
Problem 2: Sometimes it deletes too few outcomes.
Example:
4
Player 2
L M R
Player 1
T 0, 4 4, 0 5, 3
M 4, 0 0, 4 5, 3
B 3, 5 3, 5 6, 6
There is no strictly dominated strategy to be eliminated!
Solution: Nash equilibrium – not only require that no one foolishly plays a strictly dom-
inated strategy, but also require that no player has an incentive to change to a di�erent
strategy.
2.2.2 Nash equilibrium
Idea: if game theory makes a prediction about the strategy that each player will choose, then
in order for this prediction to be correct, each player must be willing to choose the strategy
predicted by the theory. Therefore, each player’s predicted strategy must be that player’s
best response to the predicted strategies of the other players, and no single player wants to
deviate from his or her predicted strategy.
If this is the case, we will call such a prediction a Nash equilibrium.
De�nition 3. In the n-player normal form game G = {S1, …Sn;u1, …, un}, the strategies
(s∗1, …, s
∗
n) are a Nash equilibrium if, for each player i, s
∗
i is (at least tied for) player i’s best
response to the strategies speci�ed for the n− 1 other players, (s∗1, …, s∗i−1, s∗i+1, …, s∗n). I.e.,
s∗i solves
max
si∈Si
ui
(
s∗1, …, s
∗
i−1, si, s
∗
i+1, …, s
∗
n
)
Remark 3. Saying that (s′1, …, s
′
n) is not a Nash equilibrium of G is equivalent to saying that
there exists some player i such that s′i is not a best response to (s
′
1, …, s
′
i−1, s
′
i+1, …, s
′
n). That
is, there exists some strictly pro�table deviation s′′i ∈ Si s.t.
ui(s
′
1, …, s
′
i−1, s
′
i, s
′
i+1, …, s
′
n) < ui(s ′ 1, ..., s ′ i−1, s ′′ i , s ′ i+1, ..., s ′ n) Application: �nd NE in a 2-player normal-form game 1. for each player's each strategy, underline the opposite player's best response to that strategy 2. if both strategies in a cell are underlined, then it is a NE Example 3. revisit: Player 2 L M R Player 1 T 0, 4 4, 0 5, 3 M 4, 0 0, 4 5, 3 B 3, 5 3, 5 6, 6 => (B, R) is the unique NE with outcome (6,6)
5
Remark 4. NE is a stronger solution concept than iterative elimination of strictly dominated
strategies (IESDS), because
1. Strategies that survive IESDS may not be NE (see example 3)
2. All Nash equilibria survive IESDS: if a strategy is eliminated in a round, then it
cannot be a best response. This implies that if IESDS gives a unique prediction, then that
prediction must be a NE. For example, the NE of prisoners’ dilemma is (Confess, Confess),
and the NE of the beauty contest game is 0.
Although NE is the most dominant solution concept in modern game theory, it is, nev-
ertheless, just one of many solution concepts. Here’s an alternative solution concept.
Example 4. Maximin: choose the strategy that gives the highest payo� in the worst case
scenario. This low-risk method does not maximise payo�, but it helps to avoid highly
unfavorable outcomes.
Firm 2
Do nothing Create new product
Firm 1
Do nothing 4,4 3,6
Create new product 6,3 2,2
Maximin: (Do nothing, Do nothing). If a �rm chooses DN, then in the worst case scenario
it can guarantee a payo� of 3. If it chooses to create a new product then the lowest payo�
it can end up getting is 2, which is lower than that in the previous case. Note that each
player’s maximin strategy does not depend on any information about the opponent.
However we do not call this prediction an �equilibrium�, because if Firm 1 knows that
Firm 2 will do nothing, it should choose to promote a new product to maximize its payo�.
Pure-strategy NE: (New product, Do nothing), (Do nothing, New product)
More examples of NE:
Example 5. The battle of the sexes
Bob
Opera Fight
Ann
Opera 2,1 0,0
Fight 0,0 1,2
Pure NE: (Opera, Opera) and (Fight, Fight)
(Preview: in the future we’ll also learn that there is a mixed strategy NE: each player
goes to his/her favorite event with probability 2/3, and the other event with probability 1/3)
Example 6. [Stag-hunt/ game of social cooperation by Jean-Jacques Rousseau]
Each of a group of hunters has two options: she may remain attentive to the pursuit of
a stag, or catch a hare. If all hunters pursue the stag, they catch it and share it equally; if
any hunter devotes her energy to catching a hare, the stag escapes, and the hare belongs to
the defecting hunter alone. Each hunter prefers a share of the stag to a hare.
6
Hunter 2
Stag Hare
Hunter 1
Stag 2,2 0,1
Hare 1,0 1,1
Payo�-dominant NE: (Stag, Stag). It maximizes the sum of two hunters’ payo�s.
Risk-dominant NE: (Hare, Hare).
Example 7. Penalty Kick
Goalie
Left Right
Kicker
Left 0,1 1,0
Right 1,0 0,1
Agent 1 is the kicker and Agent 2 is the goalie. Each has to commit to going either to the
left side of the goal or the right side before learning what the other is doing. If they choose
the same side, the advantage is to the goalie. � Here there are no (pure) Nash equilibria. �
Understanding rational behavior in games like this will require us to expand our notion of
strategy to include randomization.
Next, a 3-player example:
Example 8. 3 voters, two candidates (A and B), majority-rule voting
voters’ preferences:
1 and 2: A > B
3: B > A
The candidate with 2 votes wins
voter 3: A
voter 2
A B
voter 1
A 1,1,0 1,1,0
B 1,1,0 0,0,1
voter 3: B
voter 2
A B
voter 1
A 1,1,0 0,0,1
B 0,0,1 0,0,1
Pure-strategy NE: (A,A,A), (A,A,B), (B,B,B)!
Take-away lesson for politician: it’s not enough to make people like you; it’s equally
important to make each voter believe that his/her has the pivotal vote that makes the
di�erence!
2.3 More examples
1. On the April Fool’s Day of 2017, Reddit created an extraordinary social experiment
called �Place�. The �Place� is an online canvas of 1000×1000 pixels. During a 72-hour
window, each user can colour one pixel every 5 minutes.
https://en.wikipedia.org/wiki/Place_(Reddit)
7
Let’s consider a simpli�ed version of this game. Suppose there are two users, Ann and
Bob. Each user can color exactly 7 pixel squares on a canvas, and they must pick
their pixel squares simultaneously. They can work together to draw a lovely heart (14
pixels), or work separately to draw smiley faces (each = 7 pixels). They prefer heart
to smiley face. The worst case is to draw half a heart and �nd out later that the other
user has drawn a smiley face. (https://www.pixilart.com/draw)
= Excellent!!!
= Good
= Sad
This scenario is qualitatively equivalent to which of the following games?
(a) Prisoners’ dilemma
(b) Battle of the sexes
(c) Stag hunt
(d) Penalty kick
2. Consider the following scenario:
You and your roommate have just entered the �nal round of interview with your dream
company, but there is only one position available. On the morning of the interview,
you must decide how to dress: business casual or business formal. Both you and your
roommate prefer the comfort of business casual, but if the other person dresses casually,
you want to dress formally to impress the company and boost your chance of success.
8
(me formal, roommate casual) > (both casual) > (both formal) > (me casual, room-
mate formal).
This scenario is qualitatively equivalent to which of the following games?
(a) Prisoners’ dilemma
(b) Battle of the sexes
(c) Stag hunt
(d) Penalty kick
9