Transcript Game Theory

Game Theory
1
By the end of this section, you
should be able to….
► In
a simultaneous game played only once,
find and define:
 the Nash equilibrium
 dominant and dominated strategies
 the Pareto Optimum
► Discuss
games.
strategies in infinitely repeated
2
What is Game Theory?
► DFN:
A way of describing various possible
outcomes in any situation involving two or
more interacting individuals.
► A game is described by:
 1. Players
 2. Strategies of those players
 3. Payoffs: the utility/profit for each of the
strategy combinations.
3
Assumptions in Game Theory
► 1.
Perfect Information – Players observe all
of their rivals’ previous moves.
► 2. Common Knowledge – All players know
the structure of the game, know that their
rivals know it and their rivals know that they
know it.
4
Prisoner’s Dilemma Game
There at 2 players: Player 1, and Player 2.
► Each has 2 possible strategies: Confess (C) or Do Not Confess
(DNC).
► Players only play the games once.
► Payoffs are years in jail, so they are expressed as negative
numbers. Both players want the least amount of years in jail
they can have.
►
Player 2
Player 1
C
C
DNC
DNC
C
C
-6 , -6
0 , -9
DNC
DNC
-9 , 0
-1 , -1
5
Prisoner’s Dilemma Game
► How
do we “solve” this game (predict which
set of strategies will be played)?
► 1. Look for Strictly Dominant Strategies and
Strictly Dominated Strategies
 Strictly Dominant Strategies - the best strategy
regardless of what other players do.
 Strictly Dominated Strategies – a strategy in
which another strategy yields the player a
higher payoff regardless of what other players
do.
6
Prisoner’s Dilemma Game
► 2.
Eliminate Strictly Dominated Strategies
(Player 1’s Strategy if Player 2 Confesses)
 If Player 2 C and Player 1 C, Player 1 gets 6 years.
 If Player 2 C and Player 1 DNC, Player 1 gets 9 years in
jail.
 If Player 2 is going to Confess, # of years in jail if
Player 1 C < # of years in jail if Player 1 DNC
 Thus if Player 1 thinks Player 2 is going to confess,
Player 1 is better off confessing too.
Player 1
C
DNC
Player 2
C
DNC
-6 , -6
0 , -9
-9 , 0
-1 , -1
7
Prisoner’s Dilemma Game
► 2.
Eliminate Strictly Dominated Strategies
(Player 1’s Strategy if Player 2 Does Not Confess)
 If Player 2 DNC and Player 1 C, Player 1 gets 0 years.
 If Player 2 DNC and Player 1 DNC, Player 1 gets 1
year in jail.
 If Player 2 is going to Not Confess, # of years in jail if
Player 1 C < # of years in jail if Player 1 DNC
 Thus if Player 1 thinks Player 2 does not confess,
Player 1 is better off confessing.
Player 1
C
DNC
Player 2
C
DNC
-6 , -6
0 , -9
-9 , 0
-1 , -1
8
Prisoner’s Dilemma Game
► 2.
Eliminate Strictly Dominated Strategies
(Player 1’s Dominant Strategy)
 If Player 2 C, Player 1 is better off confessing.
 If Player 2 DNC, Player 1 is better off confessing.
 Regardless of what Strategy Player 2 uses, Player 1 is
better off confessing.
 Thus, Confessing is a dominant strategy for Player 1
and Do Not Confess is a dominated strategy.
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
9
Prisoner’s Dilemma Game
► 2.
Eliminate Strictly Dominated Strategies
(Player 2’s Dominant Strategy)
 Since we know it is strategic for Player 1 to play
Confess, to determine Player 2’s dominant strategy we
compare Player 2’s years in jail.
 Since Player 1 C, Player 2 is better off confessing.
 Thus, Confessing is a dominant strategy for Player 2
and Do Not Confess is a dominated strategy.
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
10
Prisoner’s Dilemma Game
► 3.
Solution to the Game
 Both Players playing the strategy which is best for them
given what the other person does yields a solution at
Confess, Confess.
 After all dominated strategies are eliminated, what’s left
is a Nash Equilibrium.
 You can eliminate Strictly Dominated Strategies in any
order and will get the same result.
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
11
Nash Equilibrium
► DFN:
The result of all players playing their
best strategy given what their competitors
are doing.
 Player 1 knew it is a strictly dominant strategy
for Player 2 to Confess. Thus Player 1 will
confess because they do best under that
strategy knowing what Player 2 will do and vice
versa.
12
Another Way to Solve a Game
► Star
the highest payoff for one of the Players given
the other Player is locked into each strategy and
vice versa.
► Suppose Player 1 is locked into Confessing, Player
2 is better off Confessing.
► So we put a star above Player 2’s Payoff.
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
13
Another Way to Solve a Game
►Suppose
Player 1 is locked into Not
Confessing, Player 2 is better off
Confessing.
►So we put a star above Player 2’s
Payoff.
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
14
Another Way to Solve a Game
►Suppose
Player 2 is locked into
Confessing, Player 1 is better off
Confessing.
►So we put a star above Player 1’s
Payoff.
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
15
Another Way to Solve a Game
► Suppose
Player 2 is locked into Not
Confessing, Player 1 is better off Confessing.
► So we put a star above Player 1’s Payoff.
► (Confess, Confess) is a Nash Equilibrium
because it has two stars
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
16
Nash Equilibrium vs. Pareto Outcome
► Nash
Equilibrium is the result when both
players act strategically given what the other
is going to do (Confess, Confess).
► Pareto Optimum is the result that benefits
both players the most (DNC, DNC).
Player 2
Player 1
C
DNC
C
-6 , -6
-9 , 0
DNC
0 , -9
-1 , -1
17
Another Game
► Suppose
now there are two Players, Row and
Column, with two Strategies each.
 Row can go Up or Down
 Column can go Left or Right
Row Player
Up
Down
Column Player
Left
Right
5 , 11
1 , 10
10 , 7
2,2
18
Another Game – Eliminating Strictly
Dominated Strategies
► Down
is a Dominant Strategy and Up is a
Dominated Strategy. (10>5 and 2>1)
► Left is a Dominant Strategy and Right is a
Dominated Strategy. (7>2)
► Thus, (Down, Left) is a Nash Equilibrium.
Row Player
Up
Down
Column Player
Left
Right
5 , 11
1 , 10
10 , 7
2,2
19
Another Game – Stars
If Column chooses Left, Row is better choosing Down (10>5)
 Star Row’s payoff for (Down, Left)
► If Column chooses Right, Row is better choosing Down (2>1)
 Star Row’s payoff for (Down, Right)
► If Row chooses Up, Column is better choosing Left (11>10)
 Star Column’s payoff for (Up, Left)
► If Row chooses Down, Column is better choosing Left (7>2)
 Star Row’s payoff for (Down, Left)
►
► Thus
(Down, Left) is the Nash Equilibrium (2 stars)
Row Player
Up
Down
Column Player
Left
Right
5 , 11
1 , 10
10 , 7
2,2
20
Another Game – Nash vs. Pareto
► Notice
the Nash Equilibrium has the highest total
society payoff (Pareto Outcome).
Row Player
Up
Down
Column Player
Left
Right
5 , 11
1 , 10
10 , 7
2,2
21
Another Type of Game
► Coordination
► There
are 2 Nash Equilibriums
Friend 2
Friend 1
Statue of
Liberty
Empire
State Bldg
Statue of
Liberty
8,8
Empire
State Bldg
0,0
0,0
3,3
22
Another Type of Game II
► Battle
of the Sexes
► There are 2 Nash Equilibriums.
Male
Female
Ballet
Game
Ballet
8,3
0,0
Game
0,0
3,8
23
Infinitely Repeated Games
► Strategies
Players can play:
 1. Always play Pareto (Co-operate)
 2. Always play Nash (Strategic)
 3. Grimm Strategy (Punish) – play Pareto until the other
player diverges from Pareto, then play Nash.
 4. Tit-for-Tat (Reciprocate) – play what the other player
played last round.
► One
of two things will happen:
 1. Players Converge on Nash Equilibrium by strategically
playing Dominant Strategies.
 2. Players could end up “co-operating” for the greater
good of all play Pareto.
24
A Final Note on Nash Equilibrium
► Nash
Equilibrium predictions are only accurate if
each player correctly predicts what the other
player is going to do.
► For a player to accurately predict what the other
player is going to do and act on it, both players
must act strategically and NOT select Strictly
Dominated Strategies.
► But, with some other knowledge about the other
player (relationship, partner before, etc.), it could
be strategic to play other strategies.
25