Game Theory

Lecture 8

Reading: Perlo¤ Chapter 13

August 2015

1 / 64
Introduction

Game theory is the study of strategic interaction.

Game theory is applicable in so many …elds other than economics.
Evolutionary biology, international relations, whether or not to open
the door for the old lady behind you.

2 / 64
Outline

Overview of Game Theory - Terms and De…nitions.

Static Games - Look at games when they happen once and
everybody must make their decisions at the same time.
Dynamic Games - Look at games that don’t happen all at once.
Auctions - Auctions are a type of game when bidders need to
strategically select the best bid.

3 / 64
Overview of Game Theory

A game is a situation in which your payo¤ depends not only on what

you do, but what the others do.
Tick-tack-toe, whether or not to under price a rival …rm, or to cut
carbon emissions are all games.

4 / 64
Overview of Game Theory

An action is a move you can make at a stage in a game.

Cut emissions or don’t cut emissions are actions.
A strategy is a plan conditional on any possible contingency.
Cut emissions if everybody else cuts emissions, don’t otherwise is a
strategy.
An equilibrium is a set of strategies such that neither player wishes
to deviate.

5 / 64
Overview of Game Theory

A static game is one that is played just once at the same time.
A dynamic game is one in which players move sequentially or
repeatedly.
We assume that everybody knows the rules of the game and that
everybody is maximizing there payo¤s with the knowledge their
opponents are as well.

6 / 64
Overview of Game Theory

EXAMPLE
Consider the game rock-paper-scissors.
Is this a static or a dynamic game?
What are the actions and the strategies in this game?

7 / 64
Static Games

It is useful to summarize a game using normal-form representation.

We show the players, their strategies and the payo¤ as a combination
of strategies in a payo¤ matrix.
It is just the summary of the game using a table.

8 / 64
Static Games

The most famous game is the prisoner’s dilemma.

Two men are arrested, but the police do not possess enough information
for a conviction. Following the separation of the two men, the police o¤er
both a similar deal— if one testi…es against his partner (defects/betrays),
and the other remains silent (cooperates/assists), the betrayer goes free
and the one that remains silent receives the full one-year sentence. If both
remain silent, both are sentenced to only one month in jail for a minor
charge. If each ’rats out’the other, each receives a three-month sentence.
Each prisoner must choose either to betray or remain silent; the decision of
each is kept quiet. What should they do?

9 / 64
Static Games

The row player’s payo¤s are written …rst, and the column player’s
payo¤s are written second

Nick
Silent Betray
Tom Silent -1,-1 -12, 0
Betray 0, -12 -3, -3

10 / 64
Static Games

Sometimes players will have a dominant strategy

A dominant strategy is a strategy that produces a higher payo¤ than
any other possible strategy.
No matter what your opponent might do, you play the dominant
strategy.

11 / 64
Static Games

In the prisoner’s dilemma, betray is a dominant strategy for both

players.
If Tom remains silent, Nick will betray getting 0 months in jail rather
than 1 month in jail.
If Tom betrays, Nick will betray getting 3 months in jail rather than
12 months in jail.
No matter what Tom does, Nick will betray. The reverse is true
from Tom.
This is a dominant strategy equilibrium. - Both players always play
their dominant strategy and nobody deviates.

12 / 64
Static Games

EXAMPLE
Do either players have a dominant strategy?
Is there a dominant strategy equilibrium?

Column
Left Right
Row Up 2,4 10,0
Down 1,1 9,-1

13 / 64
Static Games

In many games, the players don’t have a dominant strategy.

But players might have dominated strategies.
A dominated strategy is a strategy the players will never play, so we
can delete them.
Denying the crime is a dominated strategy in the prisoner’s dilemma.

14 / 64
Static Games

After deleting dominated strategies, we have a smaller game where

we might see what happens.
Maybe we can delete some more dominated strategies in the smaller
game.
Hopefully we are left with one set of actions.

15 / 64
Static Games

Consider the following game.

Player 2
Left Middle Right
Player 1 Up 1,0 1,2 0,1
Down 0,3 0,1 2,0

16 / 64
Static Games

Player 2 will never play Right. Player 1 can eliminate Right from the
game.

Player 2
Left Middle
Player 1 Up 1,0 1,2
Down 0,3 0,1

Player 1 will never play Down. Player 2 can eliminate down.

Keep going and we are left with only fup, middle g .
This is called iterated deletion of dominated strategies.

17 / 64
Static Games

But this approach wont always work!

Suppose I meet stranger for the …rst time and she goes in for a kiss
on the cheek.
If we both go to our respective rights or our respective lefts... we will
kiss on the cheek and everything is …ne.
If we go in opposite directions... we will kiss on the lips and that will
be humiliating for both of us.

18 / 64
Static Games

There are no dominant or dominated strategies in this game.

We need to have something stronger.

Nick
Right Left
Stranger Right 5,5 -5, 0
Left -5,0 5, 5

19 / 64
Static Games

We can look at best responses.

A best response is a best strategy given what you think the other
player will do.
A dominant strategy is one that is a best response to all possible
strategies.

20 / 64
Static Games

When players are mutually best responding, we have a Nash

equilibrium.
A set of strategies is a Nash equilibrium if nobody wishes to deviate
from their strategies.
There does not exist a pro…table deviation.
It is self-enforcing.
All dominant strategy equilibria are Nash equilibria, the reverse is not
true.

21 / 64
Static Games

There is one piece of pie left and Nick and Tom want it.
If we both go for the pie, we will …ght and neither of us want that.

Nick
Take Don’t
Tom Take -1,-1 1, 0
Don’t 0,1 0, 0

22 / 64
Static Games

If I take the pie, it is Tom’s best response not to. If Tom doesn’t
take the pie, it is my best response to.
The two Nash equilibria are where one takes the pie and the other
doesn’t. There are no pro…table deviations here.

23 / 64
Static Games

EXAMPLE
Kimon and Rebecca are going out for dinner and they want to wear
matching out…ts. They can wear red or white.
Find a Nash Equilibrium for the following game .

Kimon
Red Blue
Rebecca Red 10,10 2,2
Blue 2,2 10,10

24 / 64
Static Games

A player uses a pure strategy if the player chooses a single action.

A mixed strategy is when a player randomizes between two or more
actions.
For example, a tennis player will randomize between serving to the
left or serving to the right.
Lets illustrate this with the "battle of the sexes" game.

25 / 64
Static Games

Sean and Anna are meeting lunch and they forgot their cell-phones.
They want to eat lunch together.

Anna
Kalpna Red Box
Sean Kalpna 5,4 0,0
Red Box 0,0 4,5

26 / 64
Static Games

There are two Nash equilibria in pure strategies here, one where they
both go to Kalpna and one where they go to Red Box.
If Sean goes to Kalpna for sure, Anna will want to go to Kalpna for
sure and then Sean wont change.
If Sean goes to Red Box for sure, Anna will want to go to Red Box for
sure and then Sean wont change.

27 / 64
Static Games

There is also a mixed strategy equilibrium.

Suppose Sean is randomizing between Kalpna and Red Box with some
probability distribution.
If Kalpna yields a higher expected payo¤, Anna will go to Kalpna for
sure.
In order for Anna to play a mixed strategy, she must be indi¤erent
between the two actions (or else she wont randomize).

28 / 64
Static Games

We must …nd a probability of Sean going to Kalpna that makes Anna

indi¤erent.
We must …nd a probability of Anna going to Kalpna that makes Sean
indi¤erent.

29 / 64
Static Games

Let σ be the probability that Sean goes to Kalpna.

With probability (1 σ), he goes to Red Box
σ must be such that the expected value of going to either place is the
same for Anna to randomize.

30 / 64
Static Games

The payo¤ to Anna of going to Red Box is

5(1 σ ) + 0( σ )

The payo¤ to Anna of going to Kalpna is

4( σ ) + 0(1 σ)

Equalize these

5(1 σ ) + 0( σ ) = 4( σ ) + 0(1 σ)
5
= σ
9

31 / 64
Static Games

To make Anna be indi¤erent, Sean must go to Kalpna with

probability 59 and go to Red Box with probability 49 .
If we complete the same exercise for Anna, we see she must go to
Kalpna with probability 49 and to Red Box with probability 95 to make
Sean indi¤erent.
We can draw best response functions.
Anywhere they cross is a Nash Equilibrium (mutual best responding).

32 / 64
Static Games
α is the probability Anna goes to Kalpna and σ is the probability Sean
goes to Kalpna.

33 / 64
Static Games

EXAMPLE
Draw the best response functions and show all equilibria for the
following matching pennies game.

Nick
Heads Tails
Tom Heads -1,1 1, -1
Tails 1, -1 -1, 1

34 / 64
Dynamic Games

Dynamic games are where players move sequentially or repeatedly.

It is useful to analyze dynamic games in extensive form.
Extensive form games show the sequence of moves and the actions
each player can make each move.
It is important to understand that an action is a move a player makes
at a given point, and a strategy speci…es the actions the player will
take for every contingency.

35 / 64
Dynamic Games

A sequential game is a game in which one player moves before

another.
Sequential games contain subgames.
A subgame consists of all subsequent decisions the player can make
given the action taken.

36 / 64
Dynamic Games

37 / 64
Dynamic Games

To predict the outcome of sequential games, we rely on the subgame

perfect Nash equilibrium (SPNE) concept.
Strategies are a SPNE if the players’strategies a Nash equilibrium in
every subgame.

38 / 64
Dynamic Games

To …nd the SPNE, we rely on backward induction.

We see what the best response of the last player is for every possible
subgame.
Given the action of the last mover, we then see what the best
response is of the next-to-last mover etc.

39 / 64
Dynamic Games

In the example American knows what united will do for each action,
so it will pick 96 knowing united will pick 48.
Not all Nash equilibria are subgame perfect.

40 / 64
Dynamic Games

EXAMPLE
If this game is played simultaneously, what are the Nash Equilibria?
What is the subgame perfect Nash Equilibrium if Firm 1 goes …rst?

41 / 64
Dynamic Games

42 / 64
Dynamic Games

Nick is kidnapped by members of a drug cartel. After the

ransom is paid, the cartel is faced with an important decision.
They can murder Nick, or they can release him. If Nick is
released, he can either go to the police and have the cartel
members arrested, or he can keep his mouth shut. Being the
vengeful type, Nick gets a higher payo¤ from having the cartel
members arrested than from staying silent. The members of the
cartel gave grown fond of Nick so they get no joy in his murder,
but they would rather kill him than go to jail. Nick would rather
see the members of the cartel arrested than remain silent (being
the vengeful type), but Nick promises that he will not say a
word. What does the cartel do?

43 / 64
Dynamic Games

44 / 64
Dynamic Games

Nick would love to convince the cartel he won’t go to the police, but
this is not a credible threat.
The cartel knows it is not in Nick’s best interest to remain silent.
Nick needs some way to burn bridges and make it so he can’t go to
the police to make this credible.

45 / 64
Dynamic Games

Now let’s explore games that are repeated.

A repeated game is when a stage game (such as the prisoner’s
dilemma) occurs over many time periods.
How will this change our results?

46 / 64
Dynamic Games

Lets …rst explore the case in which a game is in…nitely or inde…nitely

repeated (players don’t know when the …nal game is).
We saw in the prisoner’s dilemma that both players betray each other.
This is not a nice outcome as both would like to deny the crime and
get lighter sentences.
If a game is repeated, cooperative behavior can be enforced.

47 / 64
Dynamic Games

If Tom betrays me today, I can betray him tomorrow as a punishment.

Both players might want to cooperate if the threat of future
punishment is strong enough.
All of this depends on the punishment strategy adopted and how
patient everybody is.

48 / 64
Dynamic Games

If there is a de…nite end date in sight, we have a …nitely repeated

game.
Cooperative behavior cannot be enforced in a …nite game... even if
the end is 1,000,000 years away.

49 / 64
Dynamic Games

Cooperative behavior occurs because people want to avoid future

punishments.
Call T the last period of the game.
at time T , there are no future periods and no threat of future
punishment.
at time T , both players will betray each other. There are no future
periods in which to be punished.

50 / 64
Dynamic Games

As {betrayal, betrayal} is happening for sure at time T , I might as

well betray in T 1 because there is no future cooperation possible
{Betrayal, Betrayal} is set in stone in T 1. I might as well betray
in period T 2.
This all unravels and we betray every period.
How reasonable do you think this is?

51 / 64
Auctions

One frequently studied type of game is an auction.

An auction is a sale in which a good or service is sold to the highest
bidder.
In an auction, I know how much I value the good, but I don’t know
how much everybody else values it (I might know the distribution).
Each player must devise a bidding strategy without complete
information.

52 / 64
Auctions

Lets look at a few types of auctions.

English auction

also called ascending-bid auction

The auctioneer starts from a low bid and keeps raising the price until
nobody wants to bid more.
Sotheby’s and Christie’s use this to sell arts and antiques.

53 / 64
Auctions

Dutch auction

Also called descending-bid auction.

The seller starts at a really high price.
If nobody wants to buy, the price is dropped until somebody accepts.
Record stores use this.

54 / 64
Auctions

Sealed-bid auction

everybody submits a bit without seeing the other bids.

In a …rst-price auction, the winner payers her own highest bid.
In second-price auctions (or Vickrey), the winner with the highest bid
pays the second-highest bid.

55 / 64
Auctions

Auctioned goods are either have a private value or common value

If a good has a private value, each bidder places a personal value on
the good, they know exactly how much it is worth to them.
If a good has a common value, the good has the same fundamental
value to everybody.
For example, an oil reserve would have a common value (that not
everybody knows).

56 / 64
Auctions

What kind of strategies will people adopt in auctions?

Second-Price Auction Strategies

Bidding your valuation is a weakly dominant strategy.

This means you are at least as well o¤ by bidding your valuation as
any other bid.
Recall that if you have the highest bid, you have to pay the second
highest bid.
Let’s say there are just two people in the auction.

57 / 64
Auctions

Second-Price Auction Strategies

Suppose my valuation of a piece of candy is v = $100.

Lets consider the case in which I bid $120.
There will be three possibilities.
First, a rival bids greater than $120. I lose. (same payo¤ as if I bid
$100).
Second, a rival bids $80. I win and pay $80 (same as if I had bid
$100).
Third, my rival bids $110. I win, but I pay $110 which is more than
my valuation.
Bidding above my valuation cannot make me better o¤.

58 / 64
Auctions

Second-Price Auction Strategies

Should I bid below?

Suppose I bid $80.
I lower my chances of winning in this case (somebody else might bid
$90).
In no case are you better o¤ by bidding something other than your
valuation.
Bidding something other than your valuation might cause you to lose
the auction, or have to pay more than you value the good.

59 / 64
Auctions

English Auction Strategies

I value the good at $100

If the going bid is $85. I should not drop out of the auction.
Once the going bid reaches $100, I should stop because I will not be
made better o¤ by purchasing the good at $100.
Hence I will always bid my valuation in an English Auction as well.
The item gets sold at the valuation of the second highest person
(same as second price sealed bid).

60 / 64
Auctions

First Price Sealed and Dutch

For Dutch or sealed …rst-price auctions bidders face a trade-o¤

because they must pay their bid.
The lower they make their bid, the more surplus they get if they win.
The higher they make their bid, the greater is the probability that
they win.
Bidders will bid less than their valuations in these auctions.

61 / 64
Auctions

You will learn this in the MSc, but the expected selling price in all 4
auctions is the same.
This is called the revenue equivalence theorem.

62 / 64
Summary

What is the di¤erence between an action and a strategy?

What is a dominant strategy equilibrium?
What is a Nash equilibrium?
What is the di¤erence between pure and mixed strategies (and how
do you …nd the mixed strategy)?

63 / 64
Summary

How do you …nd the outcome of sequential games?

What are the di¤erent types of auctions?
What are the optimal bidding strategies in each auction?

64 / 64