Game theory 1
Lukáš Lehotský
llehotsky@mail.muni.cz

Can suicide terrorism be rational?
•


Many criticisms against Rational choice
•Common criticism of rational choice – people behave irrationally
•
•Many times incorrect
•
•Rationality ≠ Sensibility
•
•Ordering preferences
•
•I can mostly prefer taking over the world and least painful death, but equally prefer most painful
death and least taking over the world

Rationality
•Defined by two key premises
•Completeness
•Transitivity
•
•Indifferent to normative assessment of preferences and choices

Completeness
•Preference ordering complete if and only if for any two outcomes X and Y individual:
•A) Prefers X to Y – strong preference relation
•B) Prefers Y to X – strong preference relation
•C) Is indifferent – weak preference relation

> > >
Incomplete preferences
1 000 000 CZK
Die painful death
0 CZK

Transitivity
•For any three outcomes X, Y and Z, if X is preferred to Y and Y is preferred to Z, X must be
preferred to Z
> > >
1 000 000 CZK
Die painful death
0 CZK

Seems easy – X > Y, Y > Z = X > Z
Undistributed middle!
X > Y; X > Z
Can we say Y > Z?
No! All relations possible – Y < Z; Y = Z
We have to know preferences in such way that we can order any two of the known preferences to each
other




Intransitive preferences
•Prefer X to Y, Y to Z and Z to X
•Doesn’t make sense

Other notions about preferences
•Preferences over outcomes are stable and do not change in the time of making decision – are fixed
•
•Preferences are ordinal – they order actions but the difference between the two values has no
meaning unless they state utility
•
•Compare two situations
•u(C1) = 1, u(C2) = 2, u(C3) = 0
•u(C1) = 1, u(C2) = 200, u(C3) = -50
•
•Both situations have same preference ordering
•C2 p C1 p C3
•
•
•
•

Other notions about rationality
•People do not calculate their actions – the definition of rationality is narrower than
common-sense one
•
•Rationality tells nothing about preferences over outcomes
•
•Rational actors may differ in choices in same situation
•
•Rational actors can err
•

Types of games



Types of games
•Games of perfect information
•Games of imperfect information
•
•Cooperative games
•Non-cooperative games
•
•Constant-sum game
•Positive-sum game
•

Games of perfect/imperfect information
•Perfect information games
•All players know other players’ strategies available to them
•All players know payoffs over actions
•All players know other players know
•Imperfect information games
•Some information about other players’ actions is not know to the player

Cooperative/non-cooperative games
•Cooperative games
•Actors are allowed to make enforceable contracts
•Players do not need to cooperate, but cooperation is enfoceable by an outside party
•Non-cooperative games
•Actors unable to make enforceable contracts outside of those specifically modeled in the game
•Players might cooperate, but any cooperation must be self-enforcing

Constant-sum/Positive-sum games
•Constant sum games
•Sum of all players' payoffs is the same for any outcome
•Gain for one participant is always at the expense of another
•Special case of zero-sum game where all outcomes involve a sum of all player's payoffs of 0
•Positive-sum games
•Combined payoffs of all players are not the same in every outcome of the game
•Positive-sum game implies that players may have interests in common, to achieve an outcome that
maximizes total payoffs.

Introducing a game



What makes a game the game
•Players
•
•Actions
•
•Strategies
•
•Outcomes
•
•Payoffs of player

Game of grades
•Each pair can choose 2 actions: α or β
•
•If both choose α, both will receive C
•
•If both choose β, both will receive B
•
•If one chooses α and other β, one will receive A and other D – applies to both players equally
•
•

Game of grades – my grades
My pair
α
β
Me
α
C
A
β
D
B

Game of grades – my pair’s grades
My pair
α
β
Me
α
C
D
β
A
B

Game of grades – normal form
My pair
α
β
Me
α
C , C
A , D
β
D , A
B , B

Games in normal form



Normal form representation of a game
•Called also “strategic form” or “matrix form”
•
•Visualized as a matrix
•
•Represents a game as if agents were acting simultaneously

Utilities (Payoffs)
•Grades are not utilites
•
•Utilities for game:
•EU(A) = 3
•EU(B) = 2
•EU(C) = 1
•EU(D) = 0
•
•Preference over outcomes: A > B > C > D -> APBPCPD

Game of grades with payoffs
My pair
α
β
Me
α
1 , 1
3 , 0
β
0 , 3
2 , 2

Solution concepts
•Nash Equilibrium
•Dominant Strategy Equilibrium
•Pure Strategy Equilibrium
•Mixed Strategy Equilibrium
•Subgame Perfect Equilibrium
•Bayesian Equilibrium
•Weak Perfect Bayesian Equilibrium

My pair
α
β
Me
α
1 , 1
3 , 0
β
0 , 3
2 , 2

My pair
α
β
Me
α
1 , 1
3 , 0
β
0 , 3
2 , 2

My pair
α
β
Me
α
1 , 1
3 , 0
β
0 , 3
2 , 2

My pair
α
β
Me
α
C , C
A , D
β
D , A
B , B

Prisoner’s dilemma
•Both players are tempted to defect, since cooperate is strictly dominated by defect
•
•The outcome of the game is that both players betray the other one and end up choosing α
•
•Both will end up with outcome that is less preferred than the optimal outcome β, β by seeking
maximal gain from own action
•
•β, β is Pareto Efficient outcome – brings best outcomes for all players – no one could be
better-off without making someone worse-off

Dominance



Dominant Strategy Equilibrium
•Strategy might be dominant
•
•Two types of dominance
•Strict (strong) dominance
•Weak dominance

Strict dominance
•Player i
•Payoff ui
•Dominant strategy si
•Dominated strategy si’
•Strategy of all other players s-i
•
•Player i‘s strategy si’ is strictly dominated by player i‘s strategy si if and only if
•ui( si , s-i) > ui( si’ , s-i ) for all s-i
•
•utility of playing si against others’ strategies s-i is greater than utility of playing si’
against others’s strategies s-i for all others’ strategies s-i

Game of grades – strict dominance
My pair
α
β
Me
α
1 , 1
3 , 0
β
0 , 3
2 , 2

Weak dominance
•Player i
•Payoff ui
•Dominant strategy si
•Dominated strategy si’
•Strategy of all other players s-i
•
•Player i‘s strategy si’ is weakly dominated by player i‘s strategy si if
•ui( si , s-i) ≥ ui( si’ , s-i ) for all s-i and
•ui( si , s-i) > ui( si’ , s-i ) for some s-i
•
•utility of playing si against others’ strategies s-i is greater or equal to utility of playing si’
against others’s strategies s-i for all others’ strategies s-i and greater for some others’
strategies s-i

Game of grades – weak dominance
My pair
α
β
Me
α
1 , 1
3 , 0
β
0 , 3
3 , 2

Never play dominated strategies
•


•Dominated strategy brings lesser payoffs than dominant strategy
•
•Dominated strategy brings lesser payoffs no matter what strategy is selected by other player
•
•Can’t control minds of others to force them not to play dominant strategy
•
•Event if could control minds of others and be sure they’ll play dominated strategy, than rational
to play dominant strategy anyway

Choosing numbers
•Choose integer between 1 – 100 incl.
•All numbers will be averaged
•Winner is the one who will be closest to the 2/3 of the group’s average

Choosing numbers
•Average = 100
•2/3 of average = ~ 66.66
•X > 67 is strictly dominated strategy
•Even if everyone else selected 100
•One selected 67
•I selected 68
•Outcome – 68 is dominated by 67
•
•What is the rational choice for this game?

If all players were strictly rational, result is 1
•


I know you know
•I know
•Numbers above 67 are never rational
•
•You know that I know
•You’ll never select number above 67, therefore numbers above 46 are never rational either
•
•I know You know that I know
•I know that You’ll never select above 46, hence I should never select number higher than 30
•
•You know that I know that You know that I know
•You know that I won’t select above 30, therefore I should never select number above 20

Get into opponent’s shoes
•


Real life results
•2012 Game theory online course
•
•10 000 + players
•
•Mean 34
•Mode 50
•Median 33
•Winner 23
•
•Spikes: 50, 33, 20, 1

Iterated deletion of dominated strategies



Iterated deletion of dominated strategies
•Can delete dominated strategies as if they were not present in the game
•
•Game becomes simpler than the original one
•
•Can find equilibriums quickly – games are dominance-solvable

Game of grades






My pair
α
Me
α
1 , 1

This game is dominance-solvable
•


Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2

Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
S1 vs S2

Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
S1 vs S3

Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
S2 vs S3

Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
s1 vs s3

Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
s1 vs s2

Opponent
s1
s2
s3
Me
S1
0 , 1
-2 , 3
4 , -1
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
s2 vs s3




Opponent
s1
s2
s3
Me
S2
0 , 3
3 , 1
6, 4
S3
1, 5
4 , 2
5 , 2

Opponent
s1
s2
s3
Me
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
s1 vs s3 after deletion

Opponent
s1
s2
s3
Me
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
s1 vs s2 after deletion

Opponent
s1
s2
s3
Me
S2
0 , 3
3 , 1
6 , 4
S3
1 , 5
4 , 2
5 , 2
s2 vs s3 after deletion




Opponent
s1
s3
Me
S2
0 , 3
6 , 4
S3
1 , 5
5 , 2

Opponent
s1
s3
Me
S2
0 , 3
6 , 4
S3
1 , 5
5 , 2

Opponent
s1
s3
Me
S2
0 , 3
6 , 4
S3
1 , 5
5 , 2

Sometimes not solvable,
but simplified
•

Limits of iterated deletion of dominated strategies
•Strictly dominated strategies may be deleted in a random order
•
•Deleting weakly dominated strategies in some order might delete equilibriums
•
•This solution concept is not always applicable – sometimes game simply don’t have dominance

How to solve the game without dominance?
Opponent
s1
s3
Me
S2
0 , 3
6 , 4
S3
1 , 5
5 , 2

How to solve the game without dominance?
Opponent
s1
s3
Me
S2
0 , 3
6 , 4
S3
1 , 5
5 , 2

Nash Equilibrium



Nash Blonde Game
•2 or more lusty males
•
•Several interested females
•
•At least one more female than male
•
•Just one female blonde
•
•Every male prefers blonde to brunette and brunette to no companion
•

Nash Blonde Game – normal form
M2
Bl
Br
M1
Bl
0 , 0
2 , 1
Br
1 , 2
1 , 1

Nash Equilibrium
•Set of strategies, one for each player, such that no player has incentive to unilaterally change
her action
•
•Players are in equilibrium if a change in strategies by any one of them would lead player to earn
less (considering strategies of others’) than if she remained with her current strategy
•
•Mutual best response to others’ choices

A
L
C
R
B
T
1 , 1
0 , 0
0 , 0
M
0 , 2
1 , 1
2 , -1
B
0 , 0
1 , 2
2 , 1

A
L
C
R
B
T
1 , 1
0 , 0
0 , 0
M
0 , 2
1 , 1
2 , -1
B
0 , 0
1 , 2
2 , 1

A
L
C
R
B
T
1 , 1
0 , 0
0 , 0
M
0 , 2
1 , 1
2 , -1
B
0 , 0
1 , 2
2 , 1

A
L
C
R
B
T
1 , 1
0 , 0
0 , 0
M
0 , 2
1 , 1
2 , -1
B
0 , 0
1 , 2
2 , 1

Games might have more NE
•


Pure strategy equilibrium
•Two equilibriums in this game
•( T , L )
•u(A) = 1
•u(B) = 1
•
•( C , B )
•u(A) = 1
•u(B) = 2
•
•These are pure strategy equilibriums

Other basic games



Chicken
B
s
h
A
S
5 , 5
0 , 10
H
10 , 0
-10 , -10

Chicken NE
•Pure strategies NE
•( H , s )
•EU(A) = 10
•EU(B) = 0
•( S , h )
•EU(A) = 0
•EU(B) = 10
B
s
h
A
S
5 , 5
0 , 10
H
10 , 0
-10 , -10

Stag hunt
B
s
r
A
S
5 , 5
0 , 3
R
3 , 0
3 , 3

Stag hunt NE
•Pure strategies NE
•( S , s )
•EU(A) = 5
•EU(B) = 5
•( R , r )
•EU(A) = 3
•EU(B) = 3
B
s
R
A
S
5 , 5
0 , 3
R
3 , 0
3 , 3