COMP9514, 1998

' & '

Game Theory | Lecture 4

$  $ 

Slide 1

Maurice Pagnucco Knowledge Systems Group Department of Arti cial Intelligence School of Computer Science and Engineering The University of New South Wales NSW 2052, AUSTRALIA
morri@cse.unsw.edu.au

Finding Pure Strategy Nash Equilibria

Slide 2

In two player games: for each strategy of opponent, underline own best reply a cell with both entries underlined represents a pure-strategy Nash Equilibrium E.g., original Prisoner's Dilemma Flood 1950 Player 2 -1, -1 -3, 0 0, -3 -2, -2 Fink Fink is a pure-strategy Nash Equilibrium Note: We can also remove dominated strategies in nonzero-sum games
Player 1

&

Loyal Fink

Loyal

Fink

COMP9514, 1998

'

Game Theory | Lecture 4

Pareto Optimality

$  $ 

De nition: An outcome is Pareto optimal if there is no other Slide 3 Loyal Fink

outcome which would give both players a higher payo or would give one player the same payo and the other player a higher payo . Player 2

& '
Slide 4

-1, -1 -3, 0 0, -3 -2, -2 Pareto optimal points are on the north east boundary of the payo polygon

Player 1

Loyal Fink

Payo Polygon
Player 2 -3 Player 1 -1 -2 -1 0

-2

&

-3

COMP9514, 1998

' & '

Jane

Game Theory | Lecture 4

Exercise 4 from last week

A B C

$  $ 

Find the pure-strategy Nash equilibria and Pareto optimal outcomes Player 2

Slide 5

Player 1

1 2 3 Opera Fight

0, 4 4, 0 5, 3 4, 0 0, 4 5, 3 3, 5 3, 5 6, 6 John

Opera Fight
2, 1 0, 0 0, 0 1, 2

Mixed-Strategy Nash Equilibria

Slide 6
As with zero-sum games there may be no pure-strategy Nash equilibria in nonzero-sum games How do we nd mixed-strategy Nash equilibria in nonzero-sum games? Each player considers their opponent's half" of the game and determines a mixed-strategy just as in the zero-sum case

&

COMP9514, 1998

' & '

Game Theory | Lecture 4

$  $ 

Calculating Mixed-Strategy Nash Equilibria

Slide 7
Player 1 Player 2

1 2

4, 8 2, 0 6, 2 0, 8

Player 1 considers Player 2's half" of the game and determines their mixed-strategy Player 2
Player 1

Slide 8

&

8 0 2 8 A: 8x + 21 , x = 6x + 2 B: 0x + 81 , x = 8 , 8x 6x + 2 = 8 , 8x 3 Therefore, x = 7 Player 1 should play 1: 3 7 , 2: optimal mixed-strategy 4 Value to Player 2 = 4 7

1 2

A B

4 7

Player 1's equalising strategy |

COMP9514, 1998

'

Game Theory | Lecture 4

Player 2 considers Player 1's half" of the game and determines their mixed-strategy Player 2
Player 1

$  $ 

Slide 9

& '
Slide 10

4 2 6 0 1: 4x + 21 , x = 2x + 2 2: 6x + 01 , x = 6x 2x + 2 = 6x 1 Therefore, x = 2 1 , B: 1 Player 2's equalising strategy Player 2 should play A: 2 2 Value to Player 1 = 3 If both player's play their equalising strategy none can gain by deviating mutual maximisation

1 2

A B

Payo Polygon
Player 2 2B 8 1A

&

2 1B 0 2 4 6

2A

8 Player 1

COMP9514, 1998

' & '

Game Theory | Lecture 4

Prudential Strategies

$  $ 

Slide 11

From Stra n 1993 For nonzero-sum games a player's prudential strategy is their optimal strategy in their own half" of the game The value of their half" of the game is called their security level that player can guarantee they will get at least this payo  Continuing example above: Player 1: prudential strategy 1, security level = 2 4 4 Player 2: prudential strategy A: 7 B: 3 7 , security level = 4 7 Prudential strategy not necessarily Pareto optimal

Slide 12

&

A player's counter-prudential strategy is their best response to opponent's prudential strategy Player 1: 2, Player 2: A Does this help? Not really! De nition: Stra n 1993 A two-person game is solvable in the strict sense if there is at least one Pareto optimal equilibrium outcome if more than one Pareto optimal equilibria exist, they are equivalent and interchangeable

COMP9514, 1998

'

Game Theory | Lecture 4

A reaction is a best possible response It is a correspondence between strategies giving best set of replies R1 A Player 1's best replies to Player 2's strategy A R2 X  Player 2's best replies to Player 1's strategy X Player 2 Consider the zero-sum game:
Player 1

Reaction

$  $ 

Slide 13

& '
Slide 14

So R1 A = fY g. Can indicate this by, say, circling" Player 1's reaction to each of Player 2's strategies and squaring" Player 2's reaction to each of Player 1's strategies. This gives a reaction curve for pure-strategies in a zero-sum game

X Y Z

8 4 6 18 0 0 0 2 14

A B C

Reaction Curves for Mixed-Strategies

A B

Consider the following matrix Binmore 1992 for a zero-sum game Player 2 1 4 3 2 Player 1's mixed strategy: A: 1x + 31 , x = 3 , 2x B: 4x + 21 , x = 2x + 2 x= 1 4 1 i.e., Player 1 plays 1 less than 1  then Player 2 would play If x 4 4 1 A otherwise x 1 4 and Player 2 plays B if x = 4 , Player 2 is indi erent
Player 1

1 2

&

COMP9514, 1998

' & '

Game Theory | Lecture 4

$  $

Slide 15

Player 2's mixed strategy: 1: 1y + 41 , y = 4 , 3y 2: 3y + 21 , y = y + 2 1 y=2 If Player 2 plays A 1 2 , Player 1 plays 1 If Player 2 plays A 1 2 , Player 1 plays 2 If Player 2 plays A = 1 2 , Player 1 indi erent

y 1 Player 2
Player 2s Reaction Curve

Mixed-strategy Nash Equilibrium

Slide 16

1/2
Player 1s Reaction Curve

&

x 0 1/4 1 Player 1

COMP9514, 1998

' & '

Game Theory | Lecture 4

Reaction Curves for Nonzero-sum Games

y 1 Player 2
Player 1s Reaction Curve

$  $ 

Slide 17
Nash Equilibrium Player 2s Reaction Curve

x 1 Player 1

Figure 1: Reaction curve for Prisoner's Dilemma

Reaction Curves for Nonzero-sum Games

y 1
Player 2s Reaction Curve

Player 2

Slide 18

1/2

Player 1s Reaction Curve

Nash Equilibria

&

x 0 1/2 1 Player 1

Figure 2: Reaction curve for Chicken

COMP9514, 1998

'

Game Theory | Lecture 4

$  $ 

10

Mixed-Motive Games
Slide 19
Games in which there is no single course of action that is best for each player independently of what the other does are called mixed-motive Players not diametrically opposed nor parallel Players may want to cooperate rather than compete There are essentially four non-trivial types of mixed-motive games

& '
Slide 20

Chicken

Two motorists driving towards each other on a collision course. Each can swerve and be a chicken or continue deadly course of action. If one only swerves they get a payo of 2 units while their opponent gets 4 units. If they both swerve they get 3 units payo each. If they both continue they only get 1 unit each. Motorist 2

&

Motorist 1

Swerve Continue

Swerve Continue
3, 3* 4, 2* 2, 4* 1, 1

COMP9514, 1998

'

Game Theory | Lecture 4

$  $ 

11

Slide 21

& '
Slide 22

Payo s not constant for all choices No dominant strategy for either player i.e., no action for either player giving largest payo no matter what other player does Two equilibria no incentive to deviate Cautious approach take best of smallest payo s" gives both motorists swerving

Payo Polygon for Chicken

Motorist 2 4 SC

SS

CS

&

CC

4 Motorist 1

COMP9514, 1998

' & '

Game Theory | Lecture 4

Leader

$  $ 

12

Slide 23

Two drivers entering intersection from opposite sides. When an opening arises they must decide whether to let the other have the right of way or go themselves. If both concede, they will have to wait longer each receives 2 units payo . If both go, they will collide each receives 1 unit payo . If one goes rst there may be time for the other to follow the leader gets 4 units payo while follower gets 3 units payo . Motorist 2
Motorist 1

Concede Go

Concede
2, 2 4, 3*

3, 4* 1, 1

Go

Slide 24

&

No dominant strategy Two pure-strategy Nash Equilibria each player prefers" one of these two over the other In real-world situations other factors e.g., cultural | ladies rst" |, psychological, . . .  resolve stando Cautious approach advocates both conceding

COMP9514, 1998

' & '

Game Theory | Lecture 4

Payo Polygon for Leader

Motorist 2 CG 4

$  $ 

13

Slide 25

3 CC

GC

GG

4 Motorist 1

Battle of the Sexes

Slide 26
Married couple must choose between two entertainment options: opera or prize ght. Wife prefers former but husband prefers latter. However, they would both prefer to be together rather than alone. Wife

&

Husband

Fight Opera

4, 3* 2, 2 1, 1 3, 4*

Fight Opera

COMP9514, 1998

'

Game Theory | Lecture 4

$  $ 

14

Slide 27

& '
Slide 28

Neither husband nor wife has a dominant strategy Cautious approach gives Husband going to prize ght and wife to Opera Two pure-strategy Nash equilibria In contrast to Leader, unilaterally deviating player rewards other player more than themselves Player can gain by communicating to obtain commitment from other play

Payo Polygon for Battle of the Sexes

Wife 4 OO

FF FO

&

OF

4 Husband

COMP9514, 1998

' & '

Game Theory | Lecture 4

Prisoner's Dilemma

$  $ 

15

Slide 29

Two prisoners arrested for joint crime and are interogorated in di erent rooms. If both conceal information cooperate they are acquitted with payo 3 units each. If one defects, they are rewarded with 4 units while the other gains only 1 unit. If both defect they will be convicted of a lesser o ence and receive a payo of 2 units each. Prisoner 2
Prisoner 1

Cooperate Defect

Cooperate Defect
3, 3* 4, 1* 1, 4* 2, 2

Slide 30

&

One Nash equilibrium Cautious approach is mutual defection regret free" Paradox lies in con ict between individual and collective rationality Individually better for players to defecct If both cooperate they are each better o Good principle?: do unto others as you would have them do unto you" Doesn't work for Battle of the Sexes What about a sequence of play?

COMP9514, 1998

' & '

Game Theory | Lecture 4

Payo Polygon for Prisoner's Dilemma

Prisoner 2 4 CD

$  $ 

16

Slide 31

CC

2 DD 1 DC

4 Prisoner 1

Iterated Prisoner's Dilemma

Slide 32
Game played more than once May be bene cial to cooperate early and defect" later on If the number of games is nite and known at the outset, the outcome is still for both players to defect". Why? Rapoport 1984 suggested TIT FOR TAT: begin by cooperating and then choose whichever strategy your opponent played in the previous iteration of the game

&

COMP9514, 1998

'

Game Theory | Lecture 4

Notes on Nash's Theorem

$  $ 

17

Slide 33

& '
Slide 34

Generalises the Minimax Theorem by establishing the existence of a solution for both zero-sum and nonzero-sum games Shows that more than one solution may exist Extends to the case of nitely many players Saddle points in a zero-sum game were equivalent and interchangeable This does not hold for non-zero sum games in which case it may not be clear which to aim for We have seen in mixed-strategy Nash equilibria that each player plays opponent's half" of the game. They neglect their own payo s! Can they do better? Note: In zero-sum games all points are Pareto optimal

Problems with Nash Equilibria?

&

Equilibrium outcome desirable due to stability Nash's Theorem shows at least one exists always However, there can be many Moreover, they can be non-equivalent and non-interchangeable how do player's coordinate? They may not be Pareto optimal cf., Prisoner's Dilemma Conclusion: Solution theory for zero-sum games does not carry over to nonzero-sum games Nash equilibria essentially describe probabilities that rational player can assign to opponent; not what they should do but what they should believe

COMP9514, 1998

'
http: http:

Game Theory | Lecture 4

Slide 35

& '
Slide 36

Hamming The purpose of Game Theory is insight not solutions" There are many excellent works on Game Theory J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, 1944. The classic but perhaps not the best place to start. D. Fudenberg and J. Tirole, Game Theory, MIT Press, 1992. Very mathematical treatment. A. Jones Game Theory, Ellis Horwood, 1980. Hit the web?: History: A Game Theory page: Prisoner's Dilemma:
www.econ.canterbury.ac.nz hist.htm http: www.pitt.edu alroth alroth.html

Where do we go from here?

$  $ 

18

serendip.brynmawr.edu ~ann pd.html

Exercise 1
Determine the pure-strategy Nash equilibria in the following nonzero-sum game Which outcomes are Pareto optimal? Player 2

&

Player 1

1 2 3

4, 3 5, 1 6, 2 2, 1 8, 4 3, 6 3, 0 9, 6 2, 8

COMP9514, 1998

' & '

Game Theory | Lecture 4

$  $ 

19

Exercise 2
Slide 37
Determine the mixed-strategy Nash equilibrium in the following nonzero-sum game. Which points are Pareto optimal? Player 2
Player 1

1 2

6, 4 4, 2 8, 6 2, 8

Exercise 3

Slide 38

Rasmusen 1989 Welfare Game The government wishes to help paupers only if they search for work. The pauper wishes to search for work only if he can't depend on government aid and may not even nd a job if he tries. The nonzero-sum game matrix may be represented as follows. Pauper

&

Government

Aid No Aid

Work Idle

3, 2 -1, 3 -1, 1 0, 0