Mixed Strategies in Game Theory
The Structure of Networks
with emphasis on information and social networks
Game Theory: Chapter 6&7
Ýmir Vigfússon
Mixed strategies
Do Nash equilibria always exist?
◦
Matching Pennies game
◦
Player #1 wins if mismatch, #2 if match
Example of a
zero-sum
game
◦
What one player gains, the other loses
◦
E.g. Allied landing in Europe on June 6, 1944
How would you play this game?
Mixed strategies
You
randomize
your strategy
◦
Instead of choosing H/T directly, choose a
probability
you will choose H.
Player 1 commits to play H with some
probability
p
◦
Similarly, player 2 plays H with probability
q
This is called a
mixed strategy
◦
As opposed to a
pure
strategy (e.g.
p
=0)
What about the payoffs?
Mixed strategies
Suppose player 1 evaluates pure strategies
◦
Player 2 meanwhile chooses strategy
q
◦
If Player 1 chooses
H
, he gets a payoff of
-1
with probability
q
and
+1
with probability
1-
q
◦
If Player 1 chooses
T
, he gets
-1
with
probability
1-q
and
+1
with probability
q
Is
H
or
T
more appealing to player 1?
◦
Rank the
expected values
◦
Pick
H
: expect (
-1
)(
q
) + (
+1
)(
1-q
) = 1-2
q
◦
Pick
T
: expect (
+1
)(
q
) + (
-1
)(
1-q
) = 2
q
-1
Mixed strategies
Def:
Nash equilibrium for mixed strategies
◦
A pair of strategies (now probabilities) such that each is a
best response to the other.
◦
Thm
: Nash proved that this
always
exists.
In Matching Pennies, no Nash equilibrium can use a
pure strategy
◦
Player 2 would have a unique best response which is a
pure strategy
◦
But this is not the best response for player 1...
What is Player 1‘s best response to strategy
q
?
◦
If 1-2q ≠2q-1, then a pure strategy (either H or T) is a
unique best response to player 1.
◦
This can‘t be part of a Nash equilibrium by the above
◦
So must have 1-2q=2q-1 in any Nash equilibrium
Which gives q=1/2. Similarly p=1/2 for Player 1.
This is a unique Nash equilibrium (check!)
Mixed strategies
Intuitively, mixed strategies are used to make it
harder for the opponent to predict what will be
played
◦
By setting
q
=1/2, Player 2 makes Player 1
indifferent
between playing H or T.
How do we interpret mixed equilibria?
◦
In sports (or real games)
Players are indeed randomizing their actions
◦
Competition for food among species
Individuals are hardwired to play certain strategies
Mixed strategies are
proportions
within populations
Population as a
whole
is a mixed equilibrium
◦
Nash equilibrium is an equilibrium in beliefs
If you believe other person will play a Nash equilibrium
strategy, so will you.
It is self-reinforcing – an equilibrium
Mixed strategies: Examples
American football
◦
Offense can run with the ball, or pass forward
What happens?
◦
Suppose the defense defends against a pass
with probability
q
◦
P
: expect (
0
)(
q
) + (
10
)(
1-q
) = 10-10
q
◦
R
: expect (
5
)(
q
) + (
0
)(
1-q
) = 5
q
◦
Offense is indifferent when
q
=2/3
Mixed strategies: Examples
American football
◦
Offense can run with the ball, or pass forward
What happens?
◦
Suppose offense passes with probability
p
◦
Similarly, defense is indifferent when
p
=1/3
◦
(1/3,2/3) is a Nash equilibrium
Expected payoff to offense: 10/3 (yard gain)
Mixed strategies: Examples
Penalty-kick game
◦
Soccer penalties have been studied extensively
◦
Suppose goalie defends left with probability
q
◦
Kicker indifferent when
(0.58)
(q)
+ (0.95)
(1-q)
= (0.93)
(q)
+ (0.70)
(1-q)
◦
Get
q
=0.42. Similarly
p
=0.39
◦
True values from data?
q
=0.42 ,
p
=0.40 !!
The theory predicts reality very well
Pareto optimality
Even playing best responses does not
always reach a good outcome as a group
◦
E.g. prisoner‘s dilemma
Want to define a
socially good outcome
Def
:
◦
A choice of strategies is
Pareto optimal
if no
other choice of strategies gives all players a
payoff at least as high, and at least one player
gets a strictly higher payoff
Note:
Everyone
must do at least as well
Social optimality
Def:
◦
A choice of strategies is a
social welfare
maximizer
(or
socially optimal
) if it maximizes
the sum of the players‘ payoffs.
Example:
◦
The unique Nash equilibrium in this game is
socially optimal
Game theory
Regular game theory
◦
Individual players make decisions
◦
Payoffs depend on decisions made by all
◦
The reasoning about what other players might
do happens simultaneously
Evolutionary
game theory
◦
Game theory continues to apply even if no
individual is overtly reasoning or making
explicit decisions
◦
Decisions may thus not be conscious
◦
What behavior will persist in a population?
Background
Evolutionary biology
◦
The idea that an organism‘s genes largely
determine its observable characteristics
(fitness) in a given environment
More fit organisms will produce more offspring
This causes genes that provide greater fitness to
increase their representation in the population
◦
Natural selection
Evolutionary game theory
Key insight
◦
Many behaviors involve the
interaction
of multiple
organisms in a population
◦
The success of an organism depends on how its
behavior interacts with that of others
Can‘t measure fitness of an individual organism
◦
So fitness must be evaluated in the context of the
full population in which it lives
Analogous to game theory!
◦
Organisms‘s genetically determined
characteristics and behavior
= Strategy
◦
Fitness
= Payoff
◦
Payoff depends on strategies of organisms with
which it interacts
= Game matrix
Motivating example
Let‘s look at a species of a beetle
◦
Each beetle‘s fitness depends on finding and
processing food effectively
◦
Mutation introduced
Beetles with mutation have larger body size
Large beetles need more food
What would we expect to happen?
◦
Large beetles need more food
◦
This makes them less fit for the environment
◦
The mutation will thus die out over time
But there is more to the story...
Motivating example
Beetles compete with each other for food
◦
Large beetles more effective at claiming
above-average share of the food
Assume food competition is among pairs
◦
Same sized beetles get equal shares of food
◦
A large beetle gets the majority of food from
a smaller beetle
◦
Large beetles always experience less fitness
benefit from given quantity of food
Need to maintain their expensive metabolism
Motivating example
The body-size game between two beetles
Something funny about this
◦
No beetle is asking itself:
“
Do I want to be small
or large?
“
Need to think about strategy changes
that operate over longer time scales
◦
Taking place as shifts in population under
evolutionary forces
Evolutionary stable strategies
The concept of a Nash equilibrium
doesn‘t work in this setting
◦
Nobody is changing their personal strategy
Instead, we want an
evolutionary stable
strategy
◦
A genetically determined strategy that tends
to persist once it is prevalent in a population
Need to make this precise...
Evolutionarily stable strategies
Suppose each beatle is repeatedly paired off
with other beetles at random
◦
Population large enough so that there are no
repeated interactions between two beetles
A beetle‘s fitness = average fitness from food
interactions = reproductive success
◦
More food thus means more offspring to carry
genes (strategy) to the next generation
Def
:
◦
A strategy is
evolutionarily stable
if everyone uses
it, and any small group of invaders with a different
strategy will die off over multiple generations
Evolutionarily stable strategies
Def:
More formally
◦
Fitness
of an organism in a population = expected
payoff from interaction with another member of
population
◦
Strategy T
invades
a strategy S
at level x
(for small
x
) if:
x
fraction of population uses T
1-
x
fraction of population uses S
◦
Strategy S is
evolutionarily stable
if there is some
number
y
such that:
When any other strategy T invades S at any level
x
<
y
,
the fitness of an organism playing S is strictly greater
than the fitness of an organism playing T
Is
Small
an evolutionarily stable strategy?
Let‘s use the definition
◦
Suppose for some small number
x
, a
1-
x
fraction of
population use
Small
and
x
use
Large
◦
In other words, a small invader population of
Large
beetles
What is the expected payoff to a
Small
beetle
in a random interaction?
◦
With prob.
1-
x
, meet another
Small
beetle for a
payoff of
5
◦
With prob.
x
, meet
Large
beetle for a payoff of
1
◦
Expected payoff:
5
(
1-
x
) +
1
x
= 5-4
x
Motivating example
Is
Small
an evolutionarily stable strategy?
Let‘s use the definition
◦
Suppose for some small number
x
, a
1-
x
fraction of
population use
Small
and
x
use
Large
◦
In other words, a small invader population of
Large
beetles
What is the expected payoff to a
Large
beetle
in a random interaction?
◦
With prob.
1-
x
, meet a
Small
beetle for payoff of
8
◦
With prob.
x
, meet another
Large
beetle for a
payoff of
3
◦
Expected payoff:
8
(
1-
x
) +
3
x
= 8-5
x
Motivating example
Motivating example
Expected fitness of
Large
beetles is
8-5
x
Expected fitness of
Small
beetles is
5-4
x
◦
For small enough
x
(and even big
x
), the fitness
of
Large
beetles exceeds the fitness for
Small
◦
Thus
Small
is not evolutionarily stable
What about the
Large
strategy?
◦
Assume
x
fraction are
Small
, rest
Large
.
◦
Expected payoff to
Large
:
3
(
1-
x
) +
8
x
= 3+5
x
◦
Expected payoff to
Small
:
1
(
1-
x
) +
5
x
= 1+4
x
◦
Large
is evolutionarily stable
Motivating example
Summary
◦
A few large beetles introduced into a
population consisting of small beetles
◦
Large beetles will do really well:
They rarely meet each other
They get most of the food in most competitions
◦
Population of small beetles cannot drive out
the large ones
So
Small
is not evolutionarily stable
Motivating example
Summary
◦
Conversely, a few small beetles will do very badly
They will lose almost every competition for food
◦
A population of large beetles
resists
the invasion
of small beetles
◦
Large
is thus evolutionarily stable
The structure is like prisoner‘s dilemma
◦
Competition for food = arms race
◦
Beetles can‘t change body sizes, but evolutionarily
forces over multiple generations are achieving
analogous effect
Motivating example
Even more striking feature!
◦
Start from a population of small beetles
◦
Evolution by
natural selection is causing the
fitness of the organisms to
decrease over time
Does this contradict Darwin‘s theory?
◦
Natural selection increases fitness in a
fixed
environment
◦
Each beetle‘s environment includes all other
beetles
◦
The
environment
is thus changing
It is becoming increasingly more hostile for everyone
This naturally decreases the fitness of the population
Evolutionary arms races
Lots of examples
◦
Height of trees follows prisoner‘s dilemma
Only applies to a particular height range
More sunlight offset by fitness downside of height
◦
Roots of soybean plants to claim resources
Conserve vs. Explore
Hard to truly determine payoffs in real-
world settings
Evolutionary arms races
One recent example with known payoffs
◦
Virus populations can play an evolutionary
version of prisoner‘s dilemma
◦
Virus A
Infects bacteria
Manifactures products required for replication
◦
Virus B
Mutated version of A
Can replicate inside bacteria, but less efficiently
Benefits from presence of A
◦
Is B evolutionarily stable?
Virus game
Look at interactions between two viruses
◦
Viruses in a pure A population do better than
viruses in pure B population
◦
But regardless of what other viruses do, higher
payoff to be B
Thus B is evolutionarily stable
◦
Even though A would have been better
◦
Similar to the exam-presentation game
What happens in general?
Under what conditions is a strategy
evolutionarily stable?
◦
Need to figure out the right form of the
payoff matrix
◦
How do we write the condition of
evolutionary stability in terms of these 4
variables, a,b,c,d?
Organism 2
Organism 1
What happens in general?
Look at the definition again
◦
Suppose again that for some small number
x
:
A 1-
x
fraction of the population uses S
An
x
fraction of the population uses T
What is the payoff for playing S in a
random interaction in the population?
◦
Meet another S with prob. 1-
x
. Payoff =
a
◦
Meet T with prob.
x
. Payoff =
b
◦
Expected payoff =
a
(1-
x
)+
bx
Analogous for playing T
◦
Expected payoff =
c
(1-
x
)+
dx
What happens in general?
Therefore, S is evolutionarily stable if for
all small values of
x:
◦
a
(1-
x
)+
bx > c
(1-
x
)+
dx
◦
When
x
is
really
small (goes to 0), this is
a
>
c
◦
When
a=c
, the left hand side is larger when
b > d
In other words
◦
In a two-player, two-strategy symmetric game,
S is evolutionarily stable
precisely
when either
a > c, or
a = c, and b > d
What happens in general?
Intuition
◦
In order for S to be evolutionarily stable, then:
Using S against S must be
at least
as good as using T
against S
Otherwise, an invader using T would have higher
fitness than the rest of the population
◦
If S and T are equally good responses to S
S can only be evolutionarily stable if those who play
S do better against T than what those who play T
do with each another
Otherwise, T players would do as well against the S
part of the population as the S players
Relationship with Nash equilibria
Let‘s look at Nash in the symmetric game
◦
When is (S,S) a Nash equilibrium?
◦
S is a best response to S:
a
≥
c
Compare with evolutionarily stable
strategies:
◦
(i)
a
>
c
or
(ii)
a = c
and
b
>
d
Very similar!
Relationship with Nash equilibria
We get the following conclusion
◦
Thm:
If strategy S is evolutionary stable, then
(S,S) is a Nash equilibrium
Does the other direction hold?
◦
What if
a = c
, and
b < d
?
◦
Can we construct such an example?
From last time
Stag Hunt
◦
If hunters work together, they can
catch a stag
◦
On their own they can each catch a hare
◦
If one hunter tries for a stag, he gets nothing
Two equilibria, but “riskier“ to hunt stag
◦
What if other player hunts hare? Get nothing
◦
Similar to prisoner‘s dilemma
Must trust other person to get best outcome!
Counterexample
Modify the game a bit
Want:
a = c
, and
b < d
Counterexample
Modify the game a bit
Want:
a = c
, and
b < d
◦
We‘re done!
Relationship with Nash equilibria
We get the following conclusion:
◦
Thm:
If strategy S is evolutionarily stable, then (S,S) is
a Nash equilibrium
Does the other direction hold?
◦
Won‘t hold if some game has
a = c
, and
b < d
◦
Can we construct such an example?
Yes!
However! Look at a strict Nash equilibrium
◦
The condition gives
a > c
◦
Thm:
If (S,S) is a
strict
Nash equilibrium, then strategy
S is evolutionarily stable
The equilibrium concepts
refine
one another
Summary
Nash equilibrium
◦
Rational players choosing mutual best
responses to each other‘s strategy
◦
Great demands on the ability to choose
optimally and coordinate on strategies that
are best responses to each other
Evolutionarily stable strategies
◦
No intelligence or coordination
◦
Strategies hard-wired into players (genes)
◦
Successful strategies produce more offspring
Yet somehow they are almost the same!
Mixed strategies
It may be the case that no strategy is
evolutionarily stable
◦
The Hawk-Dove game is an example
Hawk does well in all-Dove population
Dove does well in population of all Hawks
◦
The game even has two Nash equilibria!
We introduced mixed strategies to study
this phenomenon
◦
How should we define this in our setting?
Mixed strategies
Suppose:
◦
Organism 1 plays S with probability
p
Plays T with probability 1-
p
◦
Organism 2 plays S with probability
q
Plays T with probability 1-
q
Expected payoff for organism 1
◦
Probability
pq
of (S,S) pairing, giving
a
◦
Probability
p(1-q)
of (S,T) pairing, giving
b
◦
Probability
(1-p)q
of (T,S) pairing, giving
c
◦
Probability
p(1-q)
of (T,T) pairing, giving
d
In total:
◦
V(p,q) = pq
a
+p(1-q)
b
+(1-p)q
c
+(1-p)(1-q)
d
Mixed strategies
Fitness of an organism = expected payoff
in a random interaction
More precisely:
◦
Def:
p
is an evolutionary stable mixed strategy
if there is a small positive number y s.t.
when any other mixed strategy
q
invades
p
at any
level
x<y
, then
the fitness of an organism playing
p
is strictly
greater than the fitness of an organism playing
q
Mixed strategies
Let‘s dig into this condition
p
is an evolutionarily stable mixed
strategy if:
◦
For some
y
and any
x < y
, the following holds
for all mixed strategies
q ≠ p
:
(1-x)V(p,p) + xV(p,q) > (1-x)V(q,p) + xV(q,q)
This parallels what we saw earlier for
mixed Nash equilibria
◦
If p is an evolutionarily stable mixed strategy
then
V(p,p) ≥ V(q,p),
◦
Thus
p
is a best response to
q
◦
So
(p,p)
is a mixed Nash equilibrium
Example: Hawk-Dove
See book
Interpretation
Can interpret this in two ways
◦
All participants in the population are mixing
over two possible pure strategies with given
probability
Members genetically the same
◦
Population level: 1/3 of animals hard-wired to
play D and 2/3 are hard-wired to always play
H
Explore the concept of mixed strategies in game theory through examples and insights on Nash equilibrium. Discover how players randomize their actions to create uncertainty and strategic advantages. Learn how mixed equilibria are applied in real-world scenarios and how they contribute to the stability of competitive interactions.
Uploaded on Sep 30, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Structure of Networks with emphasis on information and social networks Game Theory: Chapter 6&7 mir Vigf sson
Mixed strategies Do Nash equilibria always exist? Matching Pennies game Player #1 wins if mismatch, #2 if match Heads Tails Heads -1, +1 +1, -1 +1, -1 -1, +1 Tails Example of a zero-sum game What one player gains, the other loses E.g. Allied landing in Europe on June 6, 1944 How would you play this game?
Mixed strategies You randomize your strategy Instead of choosing H/T directly, choose a probability you will choose H. Player 1 commits to play H with some probability p Similarly, player 2 plays H with probability q This is called a mixed strategy As opposed to a pure strategy (e.g. p=0) What about the payoffs?
Mixed strategies Suppose player 1 evaluates pure strategies Player 2 meanwhile chooses strategy q If Player 1 chooses H, he gets a payoff of -1 with probability q and +1 with probability 1-q If Player 1 chooses T, he gets -1 with probability 1-q and +1 with probability q Is H or T more appealing to player 1? Rank the expected values Pick H: expect (-1)(q) + (+1)(1-q) = 1-2q Pick T: expect (+1)(q) + (-1)(1-q) = 2q -1
Mixed strategies Def: Nash equilibrium for mixed strategies A pair of strategies (now probabilities) such that each is a best response to the other. Thm: Nash proved that this always exists. In Matching Pennies, no Nash equilibrium can use a pure strategy Player 2 would have a unique best response which is a pure strategy But this is not the best response for player 1... What is Player 1 s best response to strategy q? If 1-2q 2q-1, then a pure strategy (either H or T) is a unique best response to player 1. This can t be part of a Nash equilibrium by the above So must have 1-2q=2q-1 in any Nash equilibrium Which gives q=1/2. Similarly p=1/2 for Player 1. This is a unique Nash equilibrium (check!)
Mixed strategies Intuitively, mixed strategies are used to make it harder for the opponent to predict what will be played By setting q=1/2, Player 2 makes Player 1 indifferent between playing H or T. How do we interpret mixed equilibria? In sports (or real games) Players are indeed randomizing their actions Competition for food among species Individuals are hardwired to play certain strategies Mixed strategies are proportions within populations Population as a whole is a mixed equilibrium Nash equilibrium is an equilibrium in beliefs If you believe other person will play a Nash equilibrium strategy, so will you. It is self-reinforcing an equilibrium
Mixed strategies: Examples American football Offense can run with the ball, or pass forward Defend run Defend pass Pass 0, 0 5, -5 10, -10 0, 0 Run What happens? Suppose the defense defends against a pass with probability q P: expect (0)(q) + (10)(1-q) = 10-10q R: expect (5)(q) + (0)(1-q) = 5q Offense is indifferent when q=2/3
Mixed strategies: Examples American football Offense can run with the ball, or pass forward Defend run Defend pass Pass 0, 0 5, -5 10, -10 0, 0 Run What happens? Suppose offense passes with probability p Similarly, defense is indifferent when p=1/3 (1/3,2/3) is a Nash equilibrium Expected payoff to offense: 10/3 (yard gain)
Mixed strategies: Examples Penalty-kick game Soccer penalties have been studied extensively Defend left Defend right Left 0.58, -0.58 0.93, -0.93 0.95, -0.95 0.70, -0.70 Right Suppose goalie defends left with probability q Kicker indifferent when (0.58)(q) + (0.95) (1-q) = (0.93)(q) + (0.70) (1-q) Get q =0.42. Similarly p=0.39 True values from data? q=0.42 , p=0.40 !! The theory predicts reality very well
Pareto optimality Even playing best responses does not always reach a good outcome as a group E.g. prisoner s dilemma Want to define a socially good outcome Def: A choice of strategies is Pareto optimal if no other choice of strategies gives all players a payoff at least as high, and at least one player gets a strictly higher payoff Note: Everyone must do at least as well
Social optimality Def: A choice of strategies is a social welfare maximizer (or socially optimal) if it maximizes the sum of the players payoffs. Example: The unique Nash equilibrium in this game is socially optimal Presentation Exam Presentation 98,98 94,96 Exam 96,94 92,92
Game theory Regular game theory Individual players make decisions Payoffs depend on decisions made by all The reasoning about what other players might do happens simultaneously Evolutionary game theory Game theory continues to apply even if no individual is overtly reasoning or making explicit decisions Decisions may thus not be conscious What behavior will persist in a population?
Background Evolutionary biology The idea that an organism s genes largely determine its observable characteristics (fitness) in a given environment More fit organisms will produce more offspring This causes genes that provide greater fitness to increase their representation in the population Natural selection
Evolutionary game theory Key insight Many behaviors involve the interaction of multiple organisms in a population The success of an organism depends on how its behavior interacts with that of others Can t measure fitness of an individual organism So fitness must be evaluated in the context of the full population in which it lives Analogous to game theory! Organisms s genetically determined characteristics and behavior = Strategy Fitness = Payoff Payoff depends on strategies of organisms with which it interacts = Game matrix
Motivating example Let s look at a species of a beetle Each beetle s fitness depends on finding and processing food effectively Mutation introduced Beetles with mutation have larger body size Large beetles need more food What would we expect to happen? Large beetles need more food This makes them less fit for the environment The mutation will thus die out over time But there is more to the story...
Motivating example Beetles compete with each other for food Large beetles more effective at claiming above-average share of the food Assume food competition is among pairs Same sized beetles get equal shares of food A large beetle gets the majority of food from a smaller beetle Large beetles always experience less fitness benefit from given quantity of food Need to maintain their expensive metabolism
Motivating example The body-size game between two beetles Small Small 5, 5 Large 8, 1 Large 1, 8 3,3 Something funny about this No beetle is asking itself: Do I want to be small or large? Need to think about strategy changes that operate over longer time scales Taking place as shifts in population under evolutionary forces
Evolutionary stable strategies The concept of a Nash equilibrium doesn t work in this setting Nobody is changing their personal strategy Instead, we want an evolutionary stable strategy A genetically determined strategy that tends to persist once it is prevalent in a population Need to make this precise...
Evolutionarily stable strategies Suppose each beatle is repeatedly paired off with other beetles at random Population large enough so that there are no repeated interactions between two beetles A beetle s fitness = average fitness from food interactions = reproductive success More food thus means more offspring to carry genes (strategy) to the next generation Def: A strategy is evolutionarily stable if everyone uses it, and any small group of invaders with a different strategy will die off over multiple generations
Evolutionarily stable strategies Def: More formally Fitness of an organism in a population = expected payoff from interaction with another member of population Strategy T invades a strategy S at level x (for small x) if: x fraction of population uses T 1-x fraction of population uses S Strategy S is evolutionarily stable if there is some number y such that: When any other strategy T invades S at any level x < y, the fitness of an organism playing S is strictly greater than the fitness of an organism playing T
Motivating example Is Small an evolutionarily stable strategy? Let s use the definition Suppose for some small number x, a 1-x fraction of population use Small and x use Large In other words, a small invader population of Large beetles What is the expected payoff to a Small beetle in a random interaction? With prob. 1-x, meet another Small beetle for a payoff of 5 With prob. x, meet Large beetle for a payoff of 1 Expected payoff: 5(1-x) + 1x = 5-4x
Motivating example Is Small an evolutionarily stable strategy? Let s use the definition Suppose for some small number x, a 1-x fraction of population use Small and x use Large In other words, a small invader population of Large beetles What is the expected payoff to a Large beetle in a random interaction? With prob. 1-x, meet a Small beetle for payoff of 8 With prob. x, meet another Large beetle for a payoff of 3 Expected payoff: 8(1-x) + 3x = 8-5x
Motivating example Expected fitness of Large beetles is 8-5x Expected fitness of Small beetles is 5-4x For small enough x (and even big x), the fitness of Large beetles exceeds the fitness for Small Thus Small is not evolutionarily stable What about the Large strategy? Assume x fraction are Small, rest Large. Expected payoff to Large: 3(1-x) + 8x = 3+5x Expected payoff to Small: 1(1-x) + 5x = 1+4x Large is evolutionarily stable
Motivating example Summary A few large beetles introduced into a population consisting of small beetles Large beetles will do really well: They rarely meet each other They get most of the food in most competitions Population of small beetles cannot drive out the large ones So Small is not evolutionarily stable
Motivating example Summary Conversely, a few small beetles will do very badly They will lose almost every competition for food A population of large beetles resists the invasion of small beetles Large is thus evolutionarily stable The structure is like prisoner s dilemma Competition for food = arms race Beetles can t change body sizes, but evolutionarily forces over multiple generations are achieving analogous effect
Motivating example Even more striking feature! Start from a population of small beetles Evolution by natural selection is causing the fitness of the organisms to decrease over time Does this contradict Darwin s theory? Natural selection increases fitness in a fixed environment Each beetle s environment includes all other beetles The environment is thus changing It is becoming increasingly more hostile for everyone This naturally decreases the fitness of the population
Evolutionary arms races Lots of examples Height of trees follows prisoner s dilemma Only applies to a particular height range More sunlight offset by fitness downside of height Roots of soybean plants to claim resources Conserve vs. Explore Hard to truly determine payoffs in real- world settings
Evolutionary arms races One recent example with known payoffs Virus populations can play an evolutionary version of prisoner s dilemma Virus A Infects bacteria Manifactures products required for replication Virus B Mutated version of A Can replicate inside bacteria, but less efficiently Benefits from presence of A Is B evolutionarily stable?
Virus game Look at interactions between two viruses A B A 1.00, 1.00 B 1.99, 0.65 0.65, 1.99 0.83,0.83 Viruses in a pure A population do better than viruses in pure B population But regardless of what other viruses do, higher payoff to be B Thus B is evolutionarily stable Even though A would have been better Similar to the exam-presentation game
What happens in general? Under what conditions is a strategy evolutionarily stable? Need to figure out the right form of the payoff matrix Organism 2 S T b, c d, d S T a, a c, b Organism 1 How do we write the condition of evolutionary stability in terms of these 4 variables, a,b,c,d?
What happens in general? Look at the definition again Suppose again that for some small number x: A 1-x fraction of the population uses S An x fraction of the population uses T What is the payoff for playing S in a random interaction in the population? Meet another S with prob. 1-x. Payoff = a Meet T with prob. x. Payoff = b Expected payoff = a(1-x)+bx Analogous for playing T Expected payoff = c(1-x)+dx
What happens in general? Therefore, S is evolutionarily stable if for all small values of x: a(1-x)+bx > c(1-x)+dx When x is really small (goes to 0), this is a > c When a=c, the left hand side is larger when b > d In other words In a two-player, two-strategy symmetric game, S is evolutionarily stable precisely when either a > c, or a = c, and b > d
What happens in general? Intuition In order for S to be evolutionarily stable, then: Using S against S must be at least as good as using T against S Otherwise, an invader using T would have higher fitness than the rest of the population If S and T are equally good responses to S S can only be evolutionarily stable if those who play S do better against T than what those who play T do with each another Otherwise, T players would do as well against the S part of the population as the S players
Relationship with Nash equilibria Let s look at Nash in the symmetric game S S a, a T c, b T b, c d, d When is (S,S) a Nash equilibrium? S is a best response to S: a c Compare with evolutionarily stable strategies: (i) a > c or (ii) a = c and b > d Very similar!
Relationship with Nash equilibria We get the following conclusion Thm: If strategy S is evolutionary stable, then (S,S) is a Nash equilibrium Does the other direction hold? What if a = c, and b < d? Can we construct such an example?
From last time Stag Hunt If hunters work together, they can catch a stag On their own they can each catch a hare If one hunter tries for a stag, he gets nothing Hunt Stag Hunt Hare Hunt Stag 4, 4 3, 0 0, 3 3, 3 Hunt Hare Two equilibria, but riskier to hunt stag What if other player hunts hare? Get nothing Similar to prisoner s dilemma Must trust other person to get best outcome!
Counterexample Modify the game a bit Hunt Stag Hunt Hare Hunt Stag 4, 4 3, 0 0, 3 3, 3 Hunt Hare S T b, c d, d S T a, a c, b Want: a = c, and b < d
Counterexample Modify the game a bit Hunt Stag Hunt Hare Hunt Stag 4, 4 4, 0 0, 4 3, 3 Hunt Hare S T b, c d, d S T a, a c, b Want: a = c, and b < d We re done!
Relationship with Nash equilibria We get the following conclusion: Thm: If strategy S is evolutionarily stable, then (S,S) is a Nash equilibrium Does the other direction hold? Won t hold if some game has a = c, and b < d Can we construct such an example? Yes! However! Look at a strict Nash equilibrium The condition gives a > c Thm: If (S,S) is a strict Nash equilibrium, then strategy S is evolutionarily stable The equilibrium concepts refine one another
Summary Nash equilibrium Rational players choosing mutual best responses to each other s strategy Great demands on the ability to choose optimally and coordinate on strategies that are best responses to each other Evolutionarily stable strategies No intelligence or coordination Strategies hard-wired into players (genes) Successful strategies produce more offspring Yet somehow they are almost the same!
Mixed strategies It may be the case that no strategy is evolutionarily stable The Hawk-Dove game is an example Hawk does well in all-Dove population Dove does well in population of all Hawks The game even has two Nash equilibria! We introduced mixed strategies to study this phenomenon How should we define this in our setting?
Mixed strategies Suppose: Organism 1 plays S with probability p Plays T with probability 1-p Organism 2 plays S with probability q Plays T with probability 1-q Expected payoff for organism 1 Probability pq of (S,S) pairing, giving a Probability p(1-q) of (S,T) pairing, giving b Probability (1-p)q of (T,S) pairing, giving c Probability p(1-q) of (T,T) pairing, giving d In total: V(p,q) = pqa+p(1-q)b+(1-p)qc+(1-p)(1-q)d
Mixed strategies Fitness of an organism = expected payoff in a random interaction More precisely: Def: p is an evolutionary stable mixed strategy if there is a small positive number y s.t. when any other mixed strategy q invades p at any level x<y, then the fitness of an organism playing p is strictly greater than the fitness of an organism playing q
Mixed strategies Let s dig into this condition p is an evolutionarily stable mixed strategy if: For some y and any x < y, the following holds for all mixed strategies q p: (1-x)V(p,p) + xV(p,q) > (1-x)V(q,p) + xV(q,q) This parallels what we saw earlier for mixed Nash equilibria If p is an evolutionarily stable mixed strategy then V(p,p) V(q,p), Thus p is a best response to q So (p,p) is a mixed Nash equilibrium
Example: Hawk-Dove See book
Interpretation Can interpret this in two ways All participants in the population are mixing over two possible pure strategies with given probability Members genetically the same Population level: 1/3 of animals hard-wired to play D and 2/3 are hard-wired to always play H
