5 Introduction to Game Theory & Evolutionary Game Theory Flashcards
intro game theory:
depends not just on how they choose among several options, but also on the choices made by the people they are interacting with. Game-theoretic ideas arise in many diverse contexts such as economics, biology, marketing and ecology
Game theory is a branch of applied maths concerned with decision-making, and whose ideas have be reformulated to be applied to evolutionary biology => evolutionary game theory
The original formulation of classical Game Theory (CGT) was developed in the 1940s
a branch of applied mathematics
studying models of conflict and cooperation between intelligent rational decision-makers. John
Nash (1994 Nobel Laureate in Economics, Fig. 5.1) made seminal contributions to CGT in the 1950s
centred on the notion of full rationality: in game theory the success of one player depends on its decision but also on the decisions of all other players.
We are going to discuss some aspects of Evolutionary Game Theory (EGT)
championed by John Maynard Smith, that is concerned with the generalization of game-theoretic ideas to a biological context. EGT is thus centred on “phenotypes” rather than genotypes, and aims at modelling the effects of selection on competing organisms. While details will become clearer later in this chapter, for now we should keep in mind that the game-theoretic ideas have a broader scope than just modelling how people reason about their interactions with others.
In CGT, all players have full information and are fully rational: what is their course of actions?
In evolutionary game theory, we will abandon full rationality and use the notion of fitness.
5.1.1 A first example: the Presentation-Exam game
You need to decide whether to study for the exam, or to prepare for the presentation (not both).
assumptions:
(i) You will either study for the exam or prepare for the presentation, but not both.
(ii) You have a reliable estimate of the marks resulting from each of your possible decisions. For the exam, if you study you will get 80, otherwise 40. The outcome of the presentation depends on what
you and your partner do: if you both prepare for the presentation, then you get a joint mark of 84. If just one of you prepares (the other does not), you will get a joint mark 80; but if neither of you prepares, both will get 50.
(iii) We assume that your partner has to take the same exam as you the next day and has the same expectations as you about the marks.
(iv) We assume that you and your partner will decide what to prepare independently of each other
(no communication).
5.1.1 A first example: the “presentation-exam” game
We assume two players, you and a friend, who have 2 (pure) strategies:
Pr, which is prepare for a presentation
Ex, which is prepare for an exam
unit vectors,
table
payoff matrix
For the exam, if you study you will get 80, otherwise 40. The outcome of the presentation depends on what
you and your partner do: if you both prepare for the presentation, then you get a joint mark of 84. If just one of you prepares (the other does not), you will get a joint mark 80; but if neither of you prepares, both will get 50.
pure strategy represented by unit vectr
eₚᵣ =
(1)
(0)
eₑₓ=
(0)
(1)
Each player decides which strategy to play not knowing what the other does
Say that Player 1 uses A against Player 2 that uses B against Player 1
There 4 possible choices with outcomes (marks) summarised in the payoff matrices
A=
vs | Pr Ex |
Pr| 62 60 | player 1
Ex| 80 65 ^
———–>
ᵖˡᵃʸᵉʳ ²
B=
vs | Pr Ex |
Pr| 62 60 | player 2
Ex| 80 65 ^
———–>
ᵖˡᵃʸᵉʳ 1
B^T transpose of B=
vs | Pr Ex |
Pr| 62 80 | player 1
Ex| 60 65 ^
———–>
ᵖˡᵃʸᵉʳ ²
makes it easier to compare
This can be summarized in the bimatrix given by (A,B)^T
In this case A and B symetric, are the same
5.1.1 A first example: the “presentation-exam” game
This can be summarized in the bimatrix given by (A,B)^T
You ↓ Partner→ | Pr Ex
Pr | 62, 62 60, 80
Ex |80, 60 65, 65
In this game, both players have the same to Player 1=me options (strategies Pr or Ex) and have the same info about the outcome. All this is summarized in the matrices (A,B)
Here: both players get the same payoff for a given strategy choice => it does not matter who is player 1 and player 2=>
we can do this as its symmetric
The game is symmetric and A=B
(we need only one payoff matrix for both players)
5.1.1 A first example: the “presentation-exam” game
best strategy
For me: if my friend plays Pr, I should play Ex and get 80
if my friend plays Ex, I should play Ex and get 65
My friend can make exactly the same reasoning
best strategy for both players is to play Ex and we both get
eₑₓ^T A eₑₓ = 65
Payoff to me playing Pr against my friend playing Ex is:
eₚᵣ^T Aeₑₓ =
(1 0) [62 60] (0)
[80 65] (1) = 60
Payoff to my friend playing Ex against me playing Pr is:
eₑₓ^TB eₚᵣ = eₑₓ^TAeₚᵣ = 80
5.1.1 A first example: the “presentation-exam” game
mixed strategy
eₘᵢₓ = 0.5eₑₓ + 0.5eₚᵣ
We now assume that the same situation arises many times, and players alternate Pr and Ex,
i.e. each time they play either Pr or Ex with probability 1/2. This “randomization” of pure strategies is a “mixed strategy”, here
we randomise and combine with some probability a pure strategy
(0.5)
(0.5)
eₘᵢₓ^TAeₘᵢₓ=
(0.5 0.5) (62 60) (0.5)
(80 65) (0.5)
=66.75
>
eₑₓ^T A eₑₓ = 65
Hence both players get a higher payoff with eₘᵢₓ than with eₑₓ
However, as players cannot agree in advance, the rational choice is to play
eₑₓ
5.1.1 A first example: the “presentation-exam” game
Playing against e_ex against e_mix
gives
eₑₓ A eₘᵢₓ =
( 0 1) (62 60) (0.5)
(80 65) (0.5)
=72.5
eₑₓ does better against eₘᵢₓ
than eₘᵢₓ against itself (72.5>66.75)
eₘᵢₓ is not a best reply to itself: incentive to play eₑₓ against eₘᵢₓ
We will see that eₑₓ is a strict Nash equilibrium
also playing eₘᵢₓ against eₑₓ gives
eₘᵢₓ ^T Aeₑₓ =62.5 lower expected payoff than when both
play eₑₓ
=> incentive to use eₑₓ vs eₘᵢₓ but no incentive to use eₘᵢₓ vs eₑₓ
genotype vs phenotype
A person’s genotype is their unique sequence of DNA. More specifically, this term is used to refer to the two forms a person has inherited from their mother and father, for a particular gene. While an organism’s genotype is directly inherited
Phenotype is the observable expression of this genotype – a person’s presentation. An individual’s phenotype is the combination of their observable characteristics or traits.
5.2 Notions and concepts of classical game theory
mixed strategy
strategy profile
- All necessary information (players, strategies, payoffs) is in the payoff matrices
- We assume full rationality of all players
- There is knowledge of what others can do
- There are k pure strategies represented by unit vectors:
e₁=
(1)
(0)
…
(0)
e₂=
(0)
(1)
(0)
…
(0)
eₖ=
(0)
…
(0)
(1)
of R^k
-There are mixed strategies x=Σᵢ₌₁ᵏ xᵢeᵢ which are randomization of pure strategies,
where 0 ≤ xᵢ < 1 is the frequency of the pure strategy i, with Σᵢ₌₁ᵏ xᵢ = 1
- Strategy profile: strategies are in the simplex S ={x = (x₁,…x)^T: xᵢ ≥ 0 and Σᵢ xᵢ =1}
Expected payoff for playing against for a symmetric game (A=B) is
Π(x, y) = x^T Ay=
Σᵢ₌₁ ᵏ xᵢ(Ay)ᵢ = Σᵢ₌₁ᵏΣⱼ₌₁ᵏ xᵢAᵢⱼyⱼ
Expected payoff for pure strategy i against pure strategy j: Π(eᵢ,eⱼ)= Aᵢⱼ
ie we look at entry ij of matrix
SYMMETRIC 2-PLAYER GAMES WITH 2 PURE STRATEGIES
Important case: SYMMETRIC 2-PLAYER GAMES WITH 2 PURE STRATEGIES (C, cooperation and D, defection)=> 2x2 payoff matrix
A=
C D
C (a b)
D(c d)
we will see game depends on this abcd
NASH EQUILIBRIUM
x∗ ∈ S is a NE if it is the best reply to itself,
ie if
x∗ ^T Ax∗ ≥ x^T Ax∗ for all x ∈ S
This means that x∗ does always at least as well as x against itself
=> no incentive to move unilateraly
STRICT NASH EQUILIBIRIUM sNE
If x∗^T Ax∗ > x^T Ax∗ for all x ∈ S/x∗
⇒ x∗ is a sNE
In the Presentation-Exam game x∗= e_ex is a sNE since
eₑₓ^TAeₑₓ > x^T Aeₑₓ, for all x ̸= eₑₓ
65 > 65-5x for x= (x, 1-x)^T with 0 < x ≤ 1
Are there always NE? Nash existence theorem: in any finite game with mixed strategies, there is at least one NE. How many of them and how to find them?
example of the Presentation-Exam game
assumptions for future
example illustrates:
best response, dominant strategy and Nash equilibrium
notions are here introduced by having in mind two-player symmetric games whose payoff matrix is generically denoted by A (same payoff if symmetric)
in the e.g. “study for the exam” is the best response to any strategy played by the other player.
Definition 5.2 (Best response).
Let eᵢ and eⱼ be two pure strategies ∈ S.
If Aᵢⱼ ≥ Aₖⱼ for
all k ̸= i, then eᵢ is a best response to strategy eⱼ.
Furthermore, when Aᵢⱼ > Aₖⱼ for all
k ̸= i, then eᵢ is a strict best response to strategy eⱼ
Definition 5.3 (Dominant strategy)
Let eᵢ and eⱼ be two pure strategies ∈ S. If Aᵢⱼ > Aₖⱼ for all j and all k ̸= i, then eᵢ is a dominant strategy.
Furthermore, when Aᵢⱼ > Aₖⱼ for all
j and all k ̸= i, then eᵢ is a strict dominant strategy.
e.g. and all k ̸= i, then eᵢ is a strict dominant strategy.
In the example of the Presentation-Exam game, “study for the exam” was the strictly dominant strategy.
What is the best reply to a strategy?
The notion of Nash equilibrium (NE) is useful since:
establishes there are strategies that are best reply to themselves:
In a multi-player game, in which the strategy of each player corresponds to a NE, no player has any incentive
to change unilaterally their strategy.
We say that players are in a NE if each one is making the best decision possible, taking into account the decisions of the others, as long the others decisions remain unchanged.
Definition 5.4 (Nash equilibrium)
A pure or mixed strategy x∗ ∈ S is the “best reply to itself” if, against all other pure and mixed strategies x ∈ S, it satisfies
x∗ ^TAx∗ ≥ x^T Ax∗
When this is satisfied, x ∗ is a Nash equilibrium (NE) of the underlying game.
Since x∗ is a strategy that cannot be over-performed by an unilateral change of strategy, it is not beneficial to deviate from the NE even if everyone’s strategy is known.
Note that while x ̸= x∗cannot outperform x∗ , it can perform as well x∗ when x^T Ax∗ =x∗ ^TAx∗, and in this case the best reply to x∗ is not unique
This means that x∗ does always at least as well as x against itself => no incentive to move unilateraly
Definition 5.5 (strict Nash equilibrium)
A Nash equilibrium x∗ is a strict Nash equilibrium (sNE) if it is the unique best reply to itself,
i.e. if for all x ∈ S/x∗
x∗^T Ax∗ > x^T Ax
Example: We want to show that “study for the exam” is a strict NE for the presentation exam game.
With x = (x, 1 − x) and the payoff matrix A given in Sec. 5.1.1, we find
e^T_{ex} Ae_{ex} = 65 and
x^TAe_{ex} = 60x + 65(1 − x) = 65 − 5x.
It is thus clear that e^T_{ex}Ae_{ex} >x^TAe_{ex} for any x > 0, and hence e_{ex} is a sNE.
Are there always Nash equilibria?
An answer to this question was given by John Nash in
his 1950 PhD thesis, in which he showed that every finite game has a NE that can be a mixed
strategy. This is the so-called “fundamental theorem of game theory”,
Theorem 5.1 (Nash’s Existence Theorem).
If mixed strategies are allowed, every game with a finite number of players, in which each player can choose from finitely many pure
strategies, has at least one Nash equilibrium. The Nash equilibrium is not necessarily unique and can be in mixed strategies.
Nash equibrium does not guarantee
non-invadibility by a “mutant strategy”:
“mutant strategy” ̸= “Nash equilibrium”
x ̸= x∗
such that
x^TAx* = x^TAx
and
x^TAx > x*^T Ax
leading to: a Notion of evolutionary stability
In this case, mutant strategy does as well against the NE than x*
but it fares better against itself than x*
x can invade x*
NE allows inequality to be non strict
not if SNE
Evolutionary stable strategies
Evolutionary game theory how is it applied to evolution?
deal with “population games”:
individuals are not assumed to be fully rational (replaced by fitness)
strategies are genotypic variants
=> pure strategies interpreted as “species” and
a mixed strategy: fractions of populations made up of species
x = (x_1, x_2, . . .)^T = population consisting of fraction x_1 of species 1, x_2 of species 2, . . . interpreted as frequency x_i of pure strategy i
A fraction (1 − ϵ) plays x∗ and ϵ ≪ 1 plays x ̸= x∗ :
x∗ is evolutionary stable strategy (ESS) if
x∗ is evolutionary stable strategy (ESS) if it cannot be invaded by any x ∈ S
if x∗ does better than (1 − ϵ)x∗ + ϵx for any x ̸= x∗
=>
x∗ is ESS if
x∗^T A[(1 − ϵ)x∗ + ϵx] >
x^T A[(1 − ϵ)x∗ + ϵx]
(if x∗ against alternative strategy > strictly better)
For symmetric two-player games: x∗ is an ESS if
x∗T Ax∗ > xT Ax∗, ∀x ∈ S/x∗
(x∗ is a sNE)
or
x∗T Ax∗ = xT Ax∗
(x∗ is a NE)
and x∗T Ax > xT Ax, ∀x ∈ S/x∗ (stability condition)
Means
if x∗ sNE implies it is an ESS
or
we could have the situation:
could have x∗ against itself equal to the mutant strategy against x∗
mutant does as well against x∗ as x∗ to itself
so we demand
x∗ against mutant strategy x better than mutant strategy itself against itself
thus will not be invaded
STABILITY CONDITION
In symmetric games
strength of
ESS
NE
sNE
ESS is stronger than NE, but sNE is stronger than ESS:
sNE -> ESS -> NE
In summary, in symmetric games
* all strict-NE are ESSes.
- all ESSes are NE (but not necessarily strict-NE).
(can have inequality sign) - non-neutral games with two pure strategies always have an ESS
(games where payoff for different strategy is different )
True or false:
A strategy that is a NE is not necessarily an ESS, but a strict Nash equilibrium (sNE) is an ESS
true
How to find NE and ESSes?
A necessary (but not sufficient) condition for an interior (mixed) ESS:
x∗ = Σᵢ x∗ᵢ eᵢ with 0 < xᵢ∗ < 1
which are also mixed NE
this is given by the Bishop-Cannings Theorem (BCT):
Bishop-Cannings Theorem (BCT):
if it exists, a mixed ESS x* needs to satisfy
e₁^T Ax∗ = (Ax∗)₁ = · · · = (Ax∗)ᵢ = · · · = (Ax∗)ₖ = x∗T Ax∗
with xᵢ∗ ≥ 0 and Σᵢ xᵢ∗ = 1
(The first and second component of the vector have to be the same,
x* is doing as well against each pure strategy as well against the ESS against itself )
we solve this linear eq simultaneously to find x*
such that all 0 < xᵢ∗ < 1 then its a mixed ESS o/w no such possible
5.5 2x2 symmetric games & social dilemmas
We look at symmetric 2x2 games with 2 pure strategies, “cooperation” (C) and “defection” (D)
Prisoner’s dilemma
two suspects are apprehended by the police and each of them has two options: each can remain silent (“cooperate” with other suspect), or can confess and help charge also their partner (“defect”).
If both suspects cooperate, no serious charges can be pressed against them, whereas if both defect and confess there is a lenient
sentence against both of them.
Finally, if one confesses (defect) and the other remains silent (cooperate), the former is used to testify against the latter who receives a severe sentence while the witness has some immunity
