Nash.
(princeton.edu, Universal Pictures/DreamWorks)
c -Trenn, King’s College London 2
In general, we will say that two strategies s1 and s2 are in Nash equilibrium (NE) if: 1. under the assumption that agent i plays s1, agent j can do no better than play s2; and 2. under the assumption that agent j plays s2, agent i can do no better than play s1.
Neither agent has any incentive to deviate from a NE.
Eh?
c -Trenn, King’s College London 3
Let’s consider the payoff matrix for the grade game:
j
YX Y
i
X
Here the Nash equilibrium is pY, Y q.
If i assumes that j is playing Y , then i’s best response is to play Y . Similarly for j.
2 2
1 4
4 1
3 3
c -Trenn, King’s College London 4
i
D
s
5
A
” ”
cD 24
z
2
G y
LAID) (0,4XNE (Ad)
ft,17)NE (Adsl (QD) XUE
CAN
XNE
If two strategies are best responses to each other, then they are in Nash equilibrium.
c -Trenn, King’s College London 5
In a game like this you can find the NE by cycling through the outcomes, asking if either agent can improve its payoff by switching its strategy.
j
YX Y
i
X
Thus, for example, pX, Y q is not an NE because i can switch its payoff from 1 to 2
by switching from X to Y .
2 2
1 4
4 1
3 3
c -Trenn, King’s College London 6
More formally:
A pair of strategies pi ̊, j ̊q is a Nash equilibrium solution to the game pA, Bq if:
@i,ai ̊,j ̊ • ai,j ̊ @j,bi ̊,j ̊ • bi ̊,j
That is, pi ̊, j ̊q is a Nash equilibrium if:
‚ If j plays j ̊, then i ̊ gives the best outcome for i. ‚ If i plays i ̊, then j ̊ gives the best outcome for i.
c -Trenn, King’s College London 7
Unfortunately:
1. NoteveryinteractionscenariohasapurestrategyNE. 2. SomeinteractionscenarioshavemorethanoneNE.
c -Trenn, King’s College London 8
This game has two pure strategy NEs, pC, Cq and pD, Dq: j
DC D
i
C
In both cases, a single agent can’t unilaterally improve its payoff.
5 3
1 2
0 2
3 3
c -Trenn, King’s College London 9
This game has no pure strategy NE:
DC D
i
C
For every outcome, one of the agents will improve its utility by switching its strategy.
We can find a form of NE in such games, but we need to go beyond pure strategies.
j
2 1
1 2
0 2
1 1
c -Trenn, King’s College London 10
Nash equilibria?
Consider this scenario (again):
j
CD A
1 2
4 3
2 3
3 2
i
B Are there any Nash equilibria?
c -Trenn, King’s College London
11
Nash equilibria?
Consider this scenario (again):
j
CD A
1 2
4 3
2 3
3 2
i
B Are there any Nash equilibria?
c -Trenn, King’s College London
11