Game Theory
What is game theory (GT)?
- GT is the study of multi-agent
decision problems
- GT is used to predict what
will happen (equilibrium) when:
- There are more than one agent
but not too many for each of them to be negligible
- Each agent��s payoff depend
on what they decide to do and what others decide to do
- Examples: members of a team,
oligopolies, international negotiations,
Basic Textbook:
- ��Game Theory for Applied
Economists�� by Robert Gibbons
- The slides are also based
in this textbook
Elements of a game��
- Players:
- agents that take actions
- ��nature�� is also a player
- Information sets: What
is known by each agent at each moment that a decision must be taken
- Actions:
- In each moment of a game,
what can each agent choose. Examples: q=20,30,40; High, medium or low
taxes
- Outcomes: what is the
result for each set of possible actions
- Payoffs: Depending
on the outcome, what each agent gets( could be in terms of utility or
directly money)
Static games of complete
information
What is a static game
of complete information?
- Static (or simulateneous-move)
game:
- Players choose actions
- Each player chooses an action
without knowing what the other players have choosen
- Complete information:
- Every player will know the
payoff that each agent will obtain depending on what actions have been
taken
The normal-form representation
of a game
- Basic tool to analyze games
- Very useful for static games
under complete information.
- It consists of:
- The player in the game
- The strategies available to
each player
- In this type of games, strategies
are actions, but they will be very different in more complicated dynamic
games !!!
- The payoff received by each
player for each combination of strategies the could be chosen by the
players
- Usually represented by a table
The normal-form representation
of a game
The Prisioners�� Dilemma
Two prisoners. They are being question
by the police in different rooms. Each can confess or not
-6,-6
0,-9
Confess
-9,0
-1,-1
Not Confess
Confess
Not Confess
Prisoner B
Prisoner A
Prisoner A
Be sure that you recognize the elements
of the game !!!!
Solutions concepts
for static games with complete information
- Given a game, we will apply
a solution concept to predict which will be the outcome (equilibrium)
that will prevail in the game
- Elimination of strictly dominated
strategies
- Nash equilibrium
- These solution concepts can
also be applied to more complicated games�� but they are terribly useful
for static games with complete information
Elimination of strictly dominated
strategies
- Intuitive solution concept
- Based on the idea that a
player will never play a strategy that is strictly dominated
by another strategy
- An strategy si��
of player i is strictly dominated by si����
if player i��s payoff is larger for si����
than for si��
independently of what the other players play!
- In the prisoners' dilemma,
the strategy ��not confess�� is strictly dominated by ��confess��
Iterative Elimination
of strictly dominated strategies
- In some games, the iterative
process of eliminating strictly dominated strategies lead us to a unique
prediction about the result of the game (solution)
- In this case, we say that
the game is solvable by iterative elimination of strictly dominated
strategies
- Let��s see an example��
Iterative Elimination
of strictly dominated strategies
0,1
1,2
MIDDLE
2,0
0,3
DOWN
0,1
1,0
UP
RIGHT
LEFT
If the red player is rational, it will
never play ��Right�� because it is strictly dominated by ��Middle��.
If the blue player knows that red is rational, then he will play as
if the game were��
Iterative Elimination
of strictly dominated strategies
0,1
1,2
MIDDLE
0,3
DOWN
1,0
UP
LEFT
In this case if the blue player is rational and he knows that red is
rational, then the blue player will never play Down. So, the red player
will play as if the game were:
Iterative Elimination
of strictly dominated strategies
1,2
MIDDLE
1,0
UP
LEFT
So, if the red player is rational, and
he know that blue is rational, and he knows that blue knows that he
is rational, then the red player will play ��Middle��
The solution of the game is (UP, Middle)
Problems with this
solution concept��
We need to assume that rationality is
common knowledge
��Decisions are tough����. In many
games there are no strategies that are strictly dominated�� or there
are just a few and the process of deletion does not take us to a solution
but only to a smaller game��
Example of a game were
there are no dominated strategies
5,3
0,4
4,0
Middle
3,5
4,0
MIDDLE
6,6
3,5
Bott
5,3
0,4
UP
RIGHT
LEFT
In this game, no strategies are dominated,
so the concept of iterated elimination of dominated strategies is not
very useful��
Let��s study the other solution concept��
Some notation, before
defining the solution concept of Nash Equilibrium,
- SA
= strategies available for player A
(a
SA)
- SB
= strategies available for player B (b SB)
- UA
= utility obtained by player A when particular strategies are
chosen
- UB
= utility obtained by player B when particular strategies are
chosen
Nash Equilibrium
- In games, a pair of strategies
(a*,b*) is defined to be a Nash equilibrium if
a* is player A��s best strategy when player B
plays b*, and b* is player B��s best strategy
when player A plays a*
- It has some resemblance with
the market equilibrium where each consumer and producer were taking
optimal decisions��
Nash Equilibrium in Games
- A pair of strategies (a*,b*)
is defined to be a Nash equilibrium if
UA(a*,b*)
UA(a��,b*) for all a��SA
UB(a*,b*)
UB(a*,b��) for all b��SB
Intuition behind Nash
Eq.
- If a fortune teller
told each player of a game that a certain (a*,b*) would
be the predicted outcome of a game
- The minimum criterion that
this predicted outcome would have to verify is that the prediction is
such that each player is doing their best response to the predicted
strategies of the other players�� that is the NE
- Otherwise, the prediction
would not be internally consistent, would be unstable��
Intuition behind Nash
Eq.
- If a prediction was not a
NE, it would mean that at least one individual will have an incentive
to deviate from the prediction
- ��The idea of convention��
if a convention is to develop about how to play a given game, then the
strategies prescribed by the convention must be a NE, else at least
one player will not abide by the convention
Checking whether or not
a pair of strategies is a NE
- In the Prisioners Dilema:
- (No Confess, No Confess)
- Notice that it is not optimal
from the ��society-of-prisoners�� point of view
- In the previous 3x3 game:
BxR
- Notice that these NE also
survived the iterated process of elimination of dominated strategies��
This is a general result��
Relation between NE
and iterated��
- If the process of iterative
deletion of dominates strategies lead to a single solution�� this solution
is a NE
- The strategies that are part
of a NE will survive the iterated elimination of strictly dominated
strategies
- The strategies that survive
the iterated elimination of strictly dominated strategies are NOT necessarily
part of a NE
Finding out the NE of
a game��
- The underlining trick��
let��s see it with previous games��
- One cannot use this if the
strategies are continuous (ie. Production level). We will see afterwards��
Multiple Nash Equilibrium
Some games can have more than one NE��
In this case, the concept of NE is not so useful because it does not
give a clear prediction��as in this game called The Battle of the
Sexes
1,2
0,0
Tennis
0,0
2,1
Basket
Tennis
Basket
SEX B
Prisoner A
SEX A
Nash Equilibrium with
continuous strategies
Example: Duopoly. Firm i
& Firm j
Strategies: Output level, that is continuous
Prisoner A
Prisoner A
Prisoner A
One can draw the best response functions.
The intersection point is the NE
Prisoner A
qi
qj
a-c
(a-c)/2
(a-c)/2
a-c
(a-c)/3
(a-c)/3
Rj(qi)
Ri(qj)
Nash Equilibrium in
Mixed Strategies
- So far, we have used the
word strategy. To be more explicit, we were referring to pure strategies
- We will also use the concept
of mixed strategy
- In a static game with complete
information, a mixed strategy is a vector that tell us with what
probability the player will play each action that is available to him
Nash Equilibrium in
Mixed Strategies
Consider the following game: matching
pennies
-1,1
1,-1
Tails
1,-1
-1,1
Heads
Tails
Heads
Player 2
Prisoner A
Player 1
An example of a mixed strategy for player
1 would be: (1/3,2/3) meaning that player 1 will play Heads with probability
1/3 and Tails with probability 2/3
We can obviously say that a mixed strategy
is (q,1-q) where q is the probability of Heads
Nash Equilibrium in
Mixed Strategies
- Why are Mixed Strategies
useful?
- Because in certain games,
players might find optimal to have a random component in their behavior
- For instance, if it was the
case that the Inland Revenue would never inspect individuals taller
than 190 cms, these individuals will have lots of incentives not to
declare their income truthfully!
Nash Equilibrium in
Mixed Strategies
Notice that the matching pennies
game does not have an equilibrium in pure strategies
-1,1
1,-1
Tails
1,-1
-1,1
Heads
Tails
Heads
Player 2
Prisoner A
Player 1
Does this game have an equilibrium in
mixed strategies?
-1,1
1,-1
Tails
1,-1
-1,1
Heads
Tails
Heads
Player 2
Prisoner A
Player 1
Prisoner A
Prisoner A
Drawing the best responses
q
r
0
1
1
1
1/2
1/2
q*(r); player 2 br
r*(q); player 1 br
Notice the vertical and horizontal lines
are because of the ��any between [0,1]��
The Nash eq. in mixed strategies is the
intersection of the best response��in this case
(1/2,1/2) for player 1 and (1/2,1/2)
for player 2
Existence of Nash Equilibrium
- A game could have more than
one Nash Equilibrium
- The same game could have
equilibria in both pure and mixed strategies or only pure or only mixed
- Notice that this is a bit
artificial�� any pure strategy is a mixed strategy where one action
has probability 1
- Any game has at least one
NE, but this one could be in mixed strategies
Dynamic games of complete
information
Extensive-form representation
-In dynamic games, the normal form representation
is not that useful. The extensive-form representation will be a very
useful tool in this setting. It consists of:
-players
-when
each player has the move
-what
each player can do at each of his opportunities to move
-what
each player knows at each of his opportunities to move
-the
payoff received by each player for each combination of moves that could
be chosen by the players
-Usually
represented by a tree��
Example of Extensive form
representation
A
L
S
The dormitory game:
A chooses loud
(L) or soft (S). B hears the noise and chooses
(L) Or (S).
B
B
L
S
L
S
7,5
5,4
6,4
6,3
Strategies for dynamic games
-In dynamic games, we have to be much
more careful defining strategies.
A strategy is a complete plan
of action – it specifies a feasible action for the player in every
contingency in which the player might be called on to act
In the previous example, a strategy for
player A is (L). Another possible strategy for player A is (H)
An example of a strategy for player B
is (L,S) that means that player B will play L if
he gets to his first node and will play S if he get to the second
node.
Other strategies would be (L,L); (S,S);
and (S,L)
Extensive-form representation
-It could be that when a player moves,
he cannot distinguish between several nodes�� he does not know in what
node he is!
-For instance, it could be that when
player B moves, he has not heard the noise from player A
-We reflect this ignorance by putting
these two nodes together in the same circle�� as in the following slide��
A Dormitory Game
A
L
S
A chooses loud
(L) or soft (S).
B makes a similar
choice without knowing A��s choice
B
B
L
S
L
S
7,5
5,4
6,4
6,3
Notice that this game will actually be
static !!!!!!
Information set
-This take us to the notion of an information
set!!
An information set for a player is
a collection of decision nodes satisfying:
- The player has the move at
every node in the information set
- When the play of the game
reaches a node in the information set, the player with the move does
not know which node in the information set has (or has not) been reached
As a consequence, the nodes surrounded
by the same circle are part of the same information set
Strategies
-We can be more precise defining what
a strategy is.
A player��s strategy is an action
for each information set that the player has !!!
Dynamic games with complete information
Can be divided in:
Perfect information:
at each move in the game, the player with the move knows the full history
of the play of the game so far��
Imperfect information:
at some move the player with the move does not know the history of the
game
Notice, in complete games with perfect
information each information set must have one and only one node (the
information set is singleton). If info is complete but there is an information
set with more than one node, it must be an imperfect information game.
Dynamic games with complete information
Another classification:
Non-repeated games:
The game is just played once
Finitely repeated games: The game
is repeated a finite number of times
Infinitely repeated games:
The game is repeated an infinite amount of times
Non-repeated dynamic games
with perfect information
Two main issues:
-Is the Nash Equilibrium an appropriate
solution concept?
-If not�� Define a better solution concept��
A Two-Period Dormitory
Game
A
L
S
A chooses loud
(L) or soft (S)
B
B
L
S
L
S
B makes a similar
choice knowing
A��s choice
7,5
5,4
6,4
6,3
Thus, we should
put B��s strategies
in a form that takes
the information on
A��s choice into
account
A Two-Period Dormitory
Game
6,3
6,4
6,3
6,4
S
5,4
5,4
7,5
7,5
L
A��s Strategies
S,S
S,L
L,S
L,L
B��s
Strategies
- Each strategy is stated as
a pair of actions showing what B will do depending on A��s
actions
A Two-Period Dormitory
Game
6,3
6,4
6,3
6,4
S
5,4
5,4
7,5
7,5
L
A��s Strategies
S,S
S,L
L,S
L,L
B��s
Strategies
- There are 3 Nash equilibria
in this game
- A:L, B:(L,L)
- A:L, B:(L,S)
- A:S, B:(S,L)
A Two-Period Dormitory
Game
6,3
6,4
6,3
6,4
S
5,4
5,4
7,5
7,5
L
A��s Strategies
S,S
S,L
L,S
L,L
B��s
Strategies
- B (a,b) =
- a =strategy that B plays
if A plays L
- b= strategy that B plays
if A plays S
- A:L,
B:(L,S)
and A:S, B:(S,L)
do not seem appropiate
- each incorporates a non-credible
threat on the part of B (out of the equilibrium path)
- For instance regarding
A:L, B:(L,S), If A chose S –out of equilibrium- it is
not credible that B chose S as (L,S) indicates
- In games with more than one
period, there might be strategies that are Nash Eq but they involve
no credible threats
- We need a concept of equilibrium
for games with more than one period
- The concept will be called
Subgame Perfect Nash Equilibrium (SPNE)
- We will define SPNE more formally
later on. For the time being, let��s say that
- A SPNE is a Nash equilibrium
in which the strategy choices of each player do not involve no-credible
threats
- A strategy involves no-credible
threats if they require a player to carry out an action that would not
be in its interest at the time the choice must be made
- A simple way to obtain the
SPNE in dynamic games with perfect information is to solve the
game backwards, called ��backwards induction��
- Whiteboard with the dormitory
example��
- Algorithm:
- Find the optimal action at
each of the predecessors of the terminal nodes
- Associate these nodes with
the payoffs of the anticipated terminal node
- Start again the process with
this reduced game��
- (see another description of
the algorithm in the distributed handout��)
- Example in distributed handout��
- Another example, Pg. 60 of
the book
- The (c,s) example��
- Of the three NE that we had
in the Dormitory game, only B:(L,L),
A: L is a SPNE
- In the backward induction
procedure, we are asking each individual to do whatever is best
whenever they move�� (independently whether they are or not in
the equilibrium path) so it is not possible to have non-credible threats
- Backwards Induction with
continuous strategies
- Example: Stackelberg model
of duopoly
- Firm 1 produces q1
- Firm 2, observes q1
and produces q2
- Compute R(q1)
= Firm 2��s optimal response to an arbitrary level of production
by Firm 1.
- R(q1)
is Firm 2��s best response.
- Compute what is the optimal
q1 for Firm 1 if she know that Firm 2 will
produce R(q1)
- P=a-b(q1+R(q1))
- Backwards Induction with
continuous strategies
- Example: Stackelberg model
of duopoly
- Firm 1 produces q1
- Firm 2, observes q1
and produces q2
- Compute R(q1)
= Firm 2��s optimal response to an arbitrary level of production
by Firm 1.
- R(q1)
is Firm 2��s best response.
- Compute what is the optimal
q1 for Firm 1 if she know that Firm 2 will
produce R(q1)
- P=a-b(q1+R(q1))
- Non-repeated dynamic games
complete but imperfect information
- At some point of the game,
a player does not know exactly in which node he or she is (��does not
completely know the history of moves)
- See example��
- We cannot apply Backwards
Induction because a player might not know what is best to play as she
might not know in what node she is
- In order to understand the
solution concept, we must define a SPNE more formally.
- To do that, we must understand
what a subgame is
- Non-repeated dynamic games
complete but imperfect information
- A subgame in an extensive
form game:
- Begins at a decision node
n that is a singleton (but is not the game��s first decision
node)
- Includes all the decision
and terminal nodes following n in the game tree (but no nodes
that do not follow n)
- Does not cut any information
sets, that is, if a decision node n��
follows n in the game tree, then all other nodes in the information
set containing n��
must also follow n, and so must be included in the subgame
- See example in paper
- See pg 121 in the book
- Non-repeated dynamic games
complete but imperfect information
- A strategy profile is
SPNE:
- If it is a Nash Equilibrium
of the game and of every subgame of the game
- Two ways to find the SPNE
of a game:
- Obtain the NE and then see
which of them imply that that they are NE of the different subgames
of the game
- Finding the NE of the last
information sets and substitute backwards��
- See example in the handout
Repeated Games
- Many economic situations
can be modeled as games that are played repeatedly
- consumers�� regular purchases
from a particular retailer
- firms�� day-to-day competition
for customers
- workers�� attempts to outwit
their supervisors
Repeated Games
- An important aspect of a
repeated game is the expanded strategy sets that become available to
the players
- opens the way for credible
threats and subgame perfection
- It is important whehter or
not the game is repeated a finite or infinite number of times
Prisoners�� Dilemma
Finite Game
2,2
0,3
H
3,0
1,1
L
A��s Strategies
H
L
B��s
Strategies
- Firms A and B. Low or High
price. In a one shot game, (L,L) –no cooperating- is the NE
Prisoners�� Dilemma Finite
Game
2,2
0,3
H
3,0
1,1
L
A��s Strategies
H
L
B��s
Strategies
- The NE is inferior to (H,H)
the cooperating strategy
Prisoners�� Dilemma Finite
Game
- Suppose this game is to be
repeatedly played for a finite number of periods (T)
- Any expanded strategy in
which A promises to play H in the final period is not
credible
- when T arrives,
A will choose strategy L
- The same logic applies to
player B
Prisoners�� Dilemma Finite
Game
- Any SPNE for this game can
only consist of the Nash equilibrium strategies in the final round
- The logic that applies to
period T also applies to period T-1
- Do ��backward induction��
in the whiteboard��
- The only SPNE in this finite
game is to require the Nash equilibrium in every round -> No cooperation
Eq. in a Finite Repeated
Game
- If the one-shot game that
is repeated a finite number of times has a unique NE then the game repeated
game has a unique outcome: the NE of the one-shot game
Game with Infinite
Repetitions
- We cannot use backward induction
because there is no a terminal node��
- In Infinite games, each player
can announce a ��trigger strategy��
- promise to play the cooperative
strategy as long as the other player does
- when one player deviates from
the pattern, the other player will play no cooperation in the subsequent
periods�� and hence the game will revert to the single period NE
Game with Infinite Repetitions
- Let��s think of a player��s
decision in any arbitrary node of the game��
- If B decides to play
cooperatively, payoffs of 2 can be expected to continue indefinitely
- If B decides to cheat,
the payoff in period K will be 3, but will fall to 1 in all future
periods
- Let��s think of a player��s
decision in any arbitrary node of the game��
- If is player B��s discount rate, the present
value of continued cooperation is
2 + 2
+ 22 + �� = 2/(1-)
- The payoff from cheating
is
3 + 1
+ 21 + ��= 3 + 1/(1-)
- Continued cooperation will
be credible (will be a NE of the subgame that starts in the node where
the player is choosing) if:
2/(1-)
> 3 + 1/(1-)
- If players value the future
enough, they will prefer to cooperate�� in the case of firms this is
called Tacit Collusion
Game with Infinite Repetitions
-
can also be interpreted as the probability that the game will continue
one more period
- (Folk theorem) Let G be a
finite, static game of complete information. Let (e1,e2,��,en)
denote the payoffs from a NE of G, and let (x1,x2,��,xn)
denote any other feasible payoffs from G. If xi>ei
foor every player i and if is sufficiently close to one, then there exists
a SPNE of the infinitely repeated game that achieves (x1,x2��,xn)
as the average payoff
- In other words, if cooperation
is better than the NE for every player and players value the future
enough then cooperation is a SPNE of the game repeated a infinite number
of times
Games of Incomplete Information
- There is at least one player
that does not know the payoff of at least one player
Games of Incomplete Information
- Each player in a game may
be one of a number of possible types (tA and
tB)
- player types can vary along
several dimensions
- We will assume that our player
types have differing potential payoff functions
- each player knows his own
payoff but does not know his opponent��s payoff with certainty
Games of Incomplete Information
- Each player��s conjectures
about the opponent��s player type are represented by belief functions
[fA(tB)]
- consist of the player��s
probability estimates of the likelihood that his opponent is of various
types
- Games of incomplete information
are sometimes referred to as Bayesian games
Games of Incomplete Information
- The payoffs to A and
B depend on the strategies chosen (a
SA, b
SB) and the player types
- For one-period games, it
is fairly easy to generalize the Nash equilibrium concept to reflect
incomplete information
- we must use expected utility
because each player��s payoffs depend on the unknown player type of
the opponent
Games of Incomplete Information
- A strategy pair (a*,b*)
will be a Bayesian-Nash equilibrium if a* maximizes A��s
expected utility when B plays b* and vice versa
A Bayesian-Cournot Equilibrium
- Suppose duopolists compete
in a market for which demand is given by
P
= 100 – qA – qB
- Suppose that MCA
= MCB = 10
- the Nash (Cournot) equilibrium
is qA =
qB =
30 and payoffs are A
= B
= 900
A Bayesian-Cournot Equilibrium
- Suppose that MCA
= 10, but MCB may be either high (= 16)
or low (= 4)
- Suppose that A assigns
equal probabilities to these two ��types�� for B so that the
expected MCB = 10
- B does not have to
consider expectations because it knows there is only a single A
type
A Bayesian-Cournot Equilibrium
B = (P
– MCB)(qB) = (100 –
MCB – qA
– qB)(qB)
- The first-order condition
for a maximum is
qB*
= (100 – MCB
– qA)/2
- Depending on MCB,
this is either
qBH*
= (84 – qA)/2 or
qBL*
= (96 – qA)/2
A Bayesian-Cournot Equilibrium
- Firm A must take into
account that B could face either high or low marginal costs so
its expected profit is
A = 0.5(100
– MCA – qA
– qBH)(qA)
+ 0.5(100 – MCA – qA
– qBL)(qA)
A = (90
– qA
– 0.5qBH – 0.5qBL)(qA)
A Bayesian-Cournot Equilibrium
- The first-order condition
for a maximum is
qA*
= (90 – 0.5qBH – 0.5qBL)/2
- The Bayesian-Nash equilibrium
is:
qA*
= 30
qBH*
= 27
qBL*
= 33
- These choices represent an
ex ante equilibrium
Dynamic Games with Incomplete
Information
- In multiperiod and repeated
games, it is necessary for players to update beliefs
by incorporating new information provided by each round of play
- Each player is aware that
his opponent will be doing such updating
- must take this into account
when deciding on a strategy
- We will not study them in
this course
