29/04/2019

Basic elements of game theory

Game Theory - Motivation

• Game Theory is a tool to understand situations in

which two or more decision-makers interact.
• Outcomes of economic decisions frequently depend
on others’ actions
– effect of price policy depends on competitors
– outcome of wage negotiations depends on choices
of both sides
– outcome of elections depends on others’ votes

1
 29/04/2019

• Decision makers should thus take expectations of

others’ decisions into account
• Such situations are plausibly modeled as a “game”,
a model of interactions where the outcome
depends on others’ as well as one’s own actions
• this definition and the scope of game theory is
much broader than the everyday definition of a
game
– e.g., game theory is not only concerned with
“winning” a competitive game

Definition of a game

A game is a formal representation in which a number of

agents interact in a setting of strategic interdependence.
By that, we mean that each individual’s welfare depends
not only on her own actions but also on the actions of
the other individuals.
Moreover the actions that are best for her to take may
depend on what she expect the other players to do

2
 29/04/2019

To describe such situations we need four things:

1) The players: who is involved?
2) The rules: Who moves when? What do they know
when they move? What they can do?
3) The outcomes: for each possible set of actions by
the players, what is the outcome of the game?
4) The payoffs: what are the players’ preferences over
the possible outcomes?

Example: Matching Pennies v. 1

1) The players: John and Paul
2) The rules: Each player simultaneously puts a penny
down either head up or tail up
3) The outcomes: if the two pennies match John pays
1 euro to Paul, otherwise Paul pays 1 euro to john
4) The payoffs: Paul and John prefer receive 1 euro
instead to pay

3
 29/04/2019

Example: Matching Pennies v. 2

1) The players: John and Paul
2) The rules: John puts a penny down either head up
or tail up. Paul observes the decision of John and
puts a penny down either head up or tail up.
3) The outcomes: if the two pennies match John pays
1 euro to Paul, otherwise Paul pays 1 euro to john
4) The payoffs: Paul and John prefer receive 1 euro
instead to pay

Example: Matching Pennies v. 3

1) The players: John and Paul
2) The rules: John puts a penny down either head up
or tail up. After 1 minute the decision of John and
without the possibility to know the decision of
John, Paul puts a penny down either head up or tail
up.
3) The outcomes: if the two pennies match John pays
1 euro to Paul, otherwise Paul pays 1 euro to john
4) The payoffs: Paul and John prefer receive 1 euro
instead to pay

4
 29/04/2019

Extensive – Form Representation

An extensive form representation of a game specifies:
• Players
• When each player has to move
• The actions a player can use at each of his
opportunities to move
• What a player knows at each of his opportunities to
move
• Payoffs received by each player for each possible
outcome

Game Trees
• An extensive form game can be represented in a
game tree
• This shows
– who moves when (at the nodes)
– available actions (the branches)
– available information
– the payoffs over all possible outcomes (at the
terminal nodes)

10

5
 29/04/2019

Example 1
The preferences can be represented by a payoff
function over the outcomes
Player 1

L R

Player 2 Player 2

l r l r

U1(L,l) U1(L,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(R,l) U2(R,r)

11

Example 2
This dashed line means that
player 2 does not know the
action played by player 1

Player 1

L R

Player 2 Player 2

l r l r

U1(L,l) U1(L,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(R,l) U2(R,r)

12

6
 29/04/2019

Information set

• It is a collection of decision nodes where:

– The player has to move at every node in the
information set
– When a player has to move, he cannot distinguish
the nodes belonging to the same information set
– Example 1: player 1 has one info set, player 2 has
two info sets
– Example 2: player 1 has one info set, player 2 has
one info set

13

Note: What can an info set NOT look like

Player 1 The two nodes in the

Left Right information set have
Player 2 different number of
available actions, then
l r l
m
r player 2 can distinguish
the node

Player 1 Player 1
This could be true only
assuming that player 1
does not remember his
move in the first node
14

7
 29/04/2019

Strategies
• A strategy is a complete description of a player’s
actions in all the information sets where he has to
move, e.g.
– for player 2 to choose r after L and l after R, i.e. (r, l) .
– Player 2 has 4 strategies: {(l,l),(l,r),(r,l),(r,r)}

Player 1

L R

Player 2 Player 2

l r l r

U1(L,l) U1(L,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(R,l) U2(R,r)
15

Definition of subgame:
A subgame starts at an information set with a single node n
- it contains all decision and terminal nodes following n
- an information set cannot belong to two different
subgames
Note: someone considers the whole game a subgame,
others do not consider the whole game a subgame.
In the following we use the first approach

16

8
 29/04/2019

Dynamic games of perfect and imperfect

information
• perfect information, i.e. when choosing an action a
player knows the actions chosen by players moving
before her
i.e. all previous moves are observed before the next move is
chosen
• Imperfect information when at least one player does
not know the history by the time he chooses.
At least one player does not know all the actions chosen by
players moving before him

17

In other words, when a game is of imperfect info, there

exists at least an information set with more than one
decision node
Player 2 knows
that he is in the
information set,
Player 1 but not in which
specific node

Left Right
Player 2

l r l r

U1(L,l) U1(L,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(R,l) U2(R,r)
18

9
 29/04/2019

Example 1: Mini Ultimatum Game

• Proposer (Player 1) can suggest one of two splits of
£10: (5,5) and (9,1).
• Responder (Player 2) can decide whether to accept or
reject (9,1), but has to accept (5,5). Reject leads to 0 for
both
Player 1 Perfect information
Player 1 has one information set
(9,1) (5,5) Player 2 has one information set
Player 2 two subgames
a r

9 0 5
1 0 5
19

Example 2
Imperfect information
Player 1 has one information set
Player 2 has one information set
One subgame

Player 1

Left Right
Player 2

l r l r

U1(L,l) U1(L,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(R,l) U2(R,r)
20

10
 29/04/2019

Example 3
Imperfect information
Player 1 has one information set
Player 2 has two information sets
Two subgames

Player 1

Left Centre Right

Player 2 Player 2

l r l r l r

U1(L,l) U1(L,r) U1(C,l) U1(C,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(C,l) U2(C,r) U2(R,l) U2(R,r)
21

Example 4
Imperfect information
Challenger: one information set
Incumbent: one information set
One subgame
Challenger

Ready Unready Out

Incumbent
2
4
Acquiesce Fight Acquiesce Fight

3 1 4 0
3 1 3 2
22

11
 29/04/2019

Example 5
Imperfect information
Challenger: two information sets
Challenger
Incumbent: one information set
Two subgames In
Out
Challenger

Ready Unready
Incumbent

Acquiesce Fight Acquiesce Fight

3 1 4 0 2
3 1 3 2 4
23

Normal form representation

A normal form specifies:
1. the agents in the game,
2. for each agent, the set of available actions (or strategies):
Si denotes the set of strategies available to player i and si
is an element of Si
3. The payoff received by each player for each combination
of strategies:
– ui (s1 … si … sn) denotes the payoff function of player i
where (s1 … si … sn) are the actions chosen by the
players
Then a game can be represented as:
G = {S1,….. Sn; u1 … un }

12
 29/04/2019

Representation of a sequential game using

the normal form
Case of two players: 1 and 2
Label the rows of the normal form with the player
1’s strategies
Label the columns of the normal form with the
player 2’s strategies
Compute the payoffs to the players for each possible
combination of strategies
Using he normal form representation is possible to
find all Nash equilibrium

25

Challenger
Example 6
Ready Unready

Incumbent

Acquiesce Fight Acquiesce Fight

3 1 4 0
3 1 3 2

Player 1’strategies: {Ready, Unready}

Player 2’strategies: {(A, A), (A, F), (F, A), (F, F)}

26

13
 29/04/2019

Player 1’strategies: {Ready, Unready}

Player 2’strategies: {(A, A), (A, F), (F, A), (F, F)}

Incumbent
(A, A) (A, F) (F, A) (F, F)
Ready 3, 3 3, 3 1, 1 1, 1
Challenger
Unready 4, 3 0, 2 4.3 0, 2

Three Nash equilibria

1. Ready, (A, F)
2. Unready, (A, A)
3. Unready, (F, A)

27

Example 7
Player 2
l, l l, r r, l r, r
Player 1 Left U1(L,l), U2(L,l) U1(L,l), U2(L,l) U1(L,r), U2(L,r) U1(L,r), U2(L,r)
Centre U1(C,l), U2(C,l) U1(C,l), U2(C,l) U1(C,r), U2(C,r) U1(C,r), U2(C,r)
Right U1(R,l), U2(R,l) U1(R,r), U2(R,r) U1(R,l), U2(R,l) U1(R,r), U2(R,r)

Player 1

Left Centre Right

Player 2 Player 2

l r l r l r

U1(L,l) U1(L,r) U1(C,l) U1(C,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(C,l) U2(C,r) U2(R,l) U2(R,r)
28

14
 29/04/2019

Example 8
Incumbent
Acquiesce Fight
Challenger Ready 3, 3 1,1
Unready 4, 3 0, 2
Out 2, 4 2, 4

Challenger

Ready Unready Out

Incumbent
2
4
Acquiesce Fight Acquiesce Fight

3 1 4 0
3 1 3 2
29

Example 9
Incumbent
Acquiesce Fight
Challenger In Ready 3, 3 1,1
In Unready 4, 3 0, 2
Out Ready 2, 4 2, 4
Out Unready 2, 4 In 2, 4 Challenger
In
Challenger

Out
Ready Unready
Incumbent

Acquiesce Fight Acquiesce Fight

3 1 4 0 2
3 1 3 2 4
30

15
 29/04/2019

Simultaneous games
Definition of “Best Response”
The Best Response of a player is his preferred action given
the strategies played by the other players.
• Consider the n-player normal form game
𝐺 = 𝑆1, … . . 𝑆𝑛; 𝑢1 … 𝑢𝑛
• The best response of player i to the strategies
𝑠−𝑖 = (𝑠1, … , 𝑠𝑖−1 , 𝑠𝑖+1 , 𝑠𝑛)
solves the following problem:
max 𝑢(𝑠1, … , 𝑠𝑖, … , 𝑠𝑛)
𝑠𝑖 ∈𝑆𝑖

We denote the set of best responses to 𝑠−𝑖 as 𝐵𝑅(𝑠−𝑖 )

Example 1

Player 2
L C R
T 2,3 2,2 5,0
Player 1 Y 3,2 5,3 3,1
Z 4,3 1,1 2,2
B 1,2 0,1 4,4

The best response of player 1 to player 2 playing L is Z, i.e. 𝑍 = 𝐵𝑅(𝐿)

The best response of player 1 to player 2 playing C is Y , i.e. 𝑌 = 𝐵𝑅(𝐶)
The best response of player 2 to player 1 playing B is R , i.e. 𝑅 = 𝐵𝑅(𝐵)

16
 29/04/2019

Example 2
Suppose a game with two players, 1 and 2.
payoff of player 1 is
(10 – 𝑎1– 𝑎2) 𝑎1
where 𝑎1 is the action of player 1 and 𝑎2 is the action of
player 2
What is player 1’s best response if player 2 plays 𝑎2 = 3 ?

To find it we have to solve

𝑀𝑎𝑥 (10– 𝑎1– 𝑎2)𝑎1
The FOC are: 10 – 2𝑎1– 𝑎2 = 0
Solving by a1 we get player 1’best response
𝑎1 = (10 − 𝑎2)/2

Nash Equilibrium

• It is a prediction about the strategy each player will

choose
• This prediction is correct if each player’s predicted
strategy is a best response to the predicted strategies of
the other players.
• Such prediction is strategically stable or self enforcing:
no player wants to change his/her predicted strategy
• We call such a prediction a Nash Equilibrium.

17
 29/04/2019

Consider the n-player normal form game

G = {S1,….. Sn; u1 … un }
The strategy profile
𝑠1∗ , 𝑠2∗ , 𝑠3∗, … , 𝑠𝑛∗
is a Nash equilibrium if:
for every player i and every action siSi:
𝑢𝑖 𝑠1∗, … , 𝑠𝑖∗ , … , 𝑠𝑛∗ ≥ 𝑢𝑖 𝑠1∗ , … , 𝑠𝑖 , … , 𝑠𝑛∗
i.e.
in a Nash equilibrium, each player strategy is a best response
to the other players' strategies
in a Nash equilibrium there are no players that want to
deviate

Example 1: the Prisoner’s Dilemma

Player 2
C(ooperate) D(efect)
Player 1 C(ooperate) 2,2 0,3
D(efect) 3,0 1,1

• The unique Nash equilibrium is (D,D)

• For every other profile, at least one player wants to
deviate
• For Player 1 defect is a best response to Player 2
playing defect. For Player 2 defect is a best
response to Player 2 playing defect

18
 29/04/2019

Example 2: the “Battle of the Sexes”

Player 2
Football Theatre
Player 1 Football 2,1 0,0
Theatre 0,0 1,2
• There are two Nash equilibria: (Football, Football) and
(Theatre, Theatre)
• For Player 1 Football is a best response to Player 2 playing
Football. For Player 2 Football is a best response to Player
2 playing Football.
• For Player 1 Theatre is a best response to Player 2 playing
Theatre. For Player 2 Theatre is a best response to Player 2
playing Theatre.

Example 3: Matching Pennies

Player 2
Head Tail
Player 1 Head 1,-1 -1,1
Tail -1,1 1,-1

• There is no Nash equilibrium

19
 29/04/2019

Example 4: “Stag-Hunt”
Player 2
Stag Hare
Player 1 Stag 2,2 0,1
Hare 1,0 1,1

• There are two equilibria:

• (Stag, Stag) and (Hare, Hare)

Example 5: Public good game

This is an example of a game with continuous strategies
Two individuals are endowed with 10 pounds.
They can contribute to a public good by delivering any amount of
money out of their endowment (𝑐1 , 𝑐2)
For each individual the value of the public good is given by the sum
of the contributions multiplied by 0.7
𝑣𝑝 = 0.7 𝑐1 + 𝑐2
Payoff of player 1 =
= Endowment – contribution + value of the public good
𝜋1 = 10 − 𝑐1 + 𝑣𝑝 = 10 − 𝑐1 + 0.7 𝑐1 + 𝑐2
Payoff of player 2 =
= Endowment – contribution + value of the public good
𝜋2 = 10 − 𝑐2 + 𝑣𝑝 = 10 − 𝑐2 + 0.7 𝑐1 + 𝑐2

20
 29/04/2019

The best response of player 1 is given by the solution of the

problem:
max 𝜋1 = 10 − 𝑐1 + 0.7 𝑐1 + 𝑐2
𝑐1
FOCs are:
−1 + 0.7 < 0
Then player 1’s best response is 𝑐1 = 0
The best response of player 2 is given by the solution of the
problem:
max 𝜋2 = 10 − 𝑐2 + 0.7 𝑐1 + 𝑐2
𝑐2
FOCs are:
−1 + 0.7 < 0
Then player 2’s best response is 𝑐2 = 0
Unique Nash equilibrium: both individuals contribute by 0
But the efficient outcome is both contributing by 10

Definition:
Subgame perfect Nash equilibrium
A Nash equilibrium is subgame perfect (Nash
equilibrium) if the players’ strategies constitute a
Nash equilibrium in every subgame.
(Selten 1965)

Note that every finite sequential game of complete

information has at least one subgame perfect
Nash equilibrium

We can find all subgame perfect NE using backward

induction 42

21
 29/04/2019

Backward Induction in dynamic games

of perfect information
• Procedure:
– We start at the end of the trees
– first find the optimal actions of the last player to
move
– then taking these actions as given, find the optimal
actions of the second last player to move
– continue working backwards
• If in each decision node there is only one optimal
action, this procedure leads to a Unique Subgame
Perfect Nash equilibrium

43

• Player 1 choose action a1 from the set A1={Left, Right}

• Player 2 observes a1 and choose an action a2 from the
set A2={l, r}
• Payoffs are u1(a1, a2) and u2(a1, a2)

Player 1

Left Right

Player 2 Player 2

l r l r

U1(L,l) U1(L,r) U1(R,l) U1(R,r)

U2(L,l) U2(L,r) U2(R,l) U2(R,r)
44

22
 29/04/2019

• When Player 2 gets the move, she observes player’s 1

action a1 and faces the following problem
Max u 2 (a1 , a2 )
a 2 { A2 }

• Solving this problem, for each possible a1 A1, we get

the best response of Player 2 to Player 1’s action.
• We denote it by R2(a1) , the reaction function of Player 2.
• Player 1 can anticipate Player 2’s reaction, then Player
1’s problem is:
Max u1 (a1 , R2 (a1 ))
a1 { A1 }

45

• The backwards induction outcome is denoted by

(a1* , R2 (a1* ))
• It is different from the description of the equilibrium
• To describe the Nash equilibrium we need to describe
the equilibrium strategies:
– Action of Player 1 (Left or Right)
– Action of Player 2 after Left, action of player 2 after Right

46

23
 29/04/2019

Example: Mini Ultimatum Game

• Consider Player 2, the optimal action is accept
• Taking “accept” as given, we see that (9,1) is the optimal
action for player 1
Player 1

(9,1) (5,5)

Player 2

a r

9 0 5
1 0 5

47

The Ultimatum Game

• Proposer (Player 1) suggest (integer) split of a fixed pie, say £10.
• Responder (Player 2) accepts the proposal or rejects (both receive 0)
• There is no unique best response following (10,0), so we have two SPNE

Player 1

(10,0)
(9,1) (5,5) (0,10)
… …
Player 2

a r a r a r a r

10 0 9 0 5 0 0 0
0 0 1 0 5 0 10 0

48

24
 29/04/2019

The Ultimatum Game

• First SPNE:
• Player 1 proposes (10, 0)
• Player 2 accepts in all of his decision nodes (a, a, a, a, a, a, a, a, a, a, a)

Player 1

(10,0)
(9,1) (5,5) (0,10)
… …
Player 2

a r a r a r a r

10 0 9 0 5 0 0 0
0 0 1 0 5 0 10 0

49

The Ultimatum Game

Second SPNE:
Player 1 proposes (9, 1)
Player 2 rejects after (10, 0) and accepts in all other decision nodes
(r, a, a, a, a, a, a, a, a, a, a)

Player 1

(10,0)
(9,1) (5,5) (0,10)
… …
Player 2

a r a r a r a r

10 0 9 0 5 0 0 0
0 0 1 0 5 0 10 0

50

25
 29/04/2019

Challenger

Ready Unready

Incumbent

Acquiesce Fight Acquiesce Fight

3 1 4 0
3 1 3 2
Three Nash equilibria
1. Ready, (A, F)
2. Unready, (A, A)
3. Unready, (F, A)
Only {Unready, (A, A)} is subgame perfect

Incumbent
(A, A) (A, F) (F, A) (F, F)
Ready 3, 3 3, 3 1, 1 1, 1
Challenger
Unready 4, 3 0, 2 4.3 0, 2 51

Backward Induction in dynamic games of

imperfect information

• We start at the end of the trees

• first find the Nash equilibrium (NE) of the last
subgame
• then taking this NE as given, find the NE in the
second last subgame
• continue working backwards
If in each subgame there is only one NE, this procedure
leads to a Unique Subgame Perfect Nash equilibrium

26
 29/04/2019

Incumbent
Acquiesce Fight
Challenger In Ready 3, 3 1,1
In Unready 4, 3 0, 2
Out Ready 2, 4 2, 4
Out Unready 2, 4 2, 4

Challenger
In
Challenger
Out
Ready Unready
Incumbent

Acquiesce Fight Acquiesce Fight

3 1 4 0 2
3 1 3 2 4
53

3 Nash equilibria:
• (In Unready) (Acquiesce)
• (Out Unready) (Fight)
• (Out ready) (Fight)
Subgame Perfect Nash equilibrium?
Start solving the last subgame
Challenger

Ready Unready
Incumbent

Fight Acquiesce Fight

3 1 4 0
3 1 3 2

27
 29/04/2019

The normal form of the last subgame is:

Incumbent
Acquiesce Fight
Challenger Ready 3, 3 1,1
Unready 4, 3 0, 2

Only one Nash equilibrium:

(Unready) (Acquiesce)

Then the Challenger can predict that playing “In”

the outcome in the subgame will be the Nash equilibrium
(Unready) (Acquiesce)
with payoff (4, 3)
The reduced form is:

Challenger
In
4 Out
3

2
4

Then the best action the challenger can take is “in”

Then the subgame perfect Nash equilibrium is
(In Unready) (Acquiesce)

28