Game theory 1
Lukáš Lehotský
llehotsky@mail.muni.cz
Can rational choice explain
suicide terrorism?
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
1 000 000
CZK
Die0 CZK
1 000 000
CZK
Die0 CZK
1 000 000
CZK
Die0 CZK
Incomplete preferences
1 000 000
CZK
Die0 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
Die0 CZK
1 000 000
CZK
Die0 CZK
1 000 000
CZK
Die0 CZK
1 000 000
CZK
Die0 CZK
1 000 000
CZK
Die0 CZK
Intransitive preferences
• Prefer X to Y, Y to Z and Z to X
• Doesn’t make sense
1 000 000
CZK
Die0 CZK
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
• Rational choice theory is not attempting to explain cognitive
processes happening in individuals
• 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
Game of grades – my grades
My opponent
α β
Me
α C A
β D B
Game of grades – my opponent’s grades
My opponent
α β
Me
α C D
β A B
Game of grades – normal form
My opponent
α β
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 opponent
α β
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 opponent
α β
Me
α 1 , 1 3 , 0
β 0 , 3 2 , 2
My opponent
α β
Me
α 1, 1 3, 0
β 0 , 3 2 , 2
My opponent
α β
Me
α 1, 1 3, 0
β 0 , 3 2 , 2
My opponent
α β
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 3 , 0
β 0 , 3 2 , 2
My pair
α
Me
α 1, 1
β 0 , 3
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
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
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 s2 s3
Me
S2 0 , 3 3 , 1 6 , 4
S3 1 , 5 4 , 2 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
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