Mixed strategy
Chances are you would play a mixed strategy. You would:
‚ sometimesplayrock,
‚ sometimesplaypaper;and ‚ sometimesplayscissors.
A fixed/pure strategy is easy for an adaptive player to beat.
c -Trenn, King’s College London 2
Mixed strategy
A mixed strategy is just a probability distribution across a set of pure strategies.
So, for a game where agent i has two actions a1 and a2, a mixed strategy for i is a probability distirbution:
MSi “ tPpa1q,Ppa2qu
Given this mixed strategy, when i comes to play, they pick action a1 with
probability Ppa1q and a2 with probability Ppa2q.
c -Trenn, King’s College London 3
Mixed strategy
To determine the mixed strategy, i can compute the best values of Ppa1q and Ppa2q.
These will be the values which give i the highest expected payoff given the options that j can choose and the joint payoffs that result.
We could write down the expected payoffs of different mixed strategies and pick the one that optimises expected payoff.
There is also a simple graphical method which works for very simple cases. Will look at this method next.
c -Trenn, King’s College London 4
Mixed strategy
Let’s consider the payoff matrix:
j
a3
a4
-3 3
1 -1
0 0
-1 1
a1 i
a2
We want to compute mixed strategies to be used by the players.
That means decide Ppa1q and Ppa2q etc.
c -Trenn, King’s College London 5
.*i÷%÷÷÷÷ Mae e ra . 0.208
o Et)
S100%p – EEP] =
0-0.4 0 .6
0.6 a I . –
427/250 X EEPafoq-fpieu.HEoelpkn-H.IO
23150 v.P. P playX
=
RPs R°i”
‘
Peter
↳809,P 40%5
o,
%,
I-‘
free
‘
,,o
Pg
-i
Mixed strategy
i’s analysis of this game would be something like this.
c -Trenn, King’s College London 6
Mixed strategy
33
22 1 j picks a3 1
00
−1 −2 −3
−1 −2 −3
0 P(a1) 1
Consider it from i’s perspective. Let’s say you know that j plays a3. i’s payoff will be 3 or 0 depending on whether i picks a1 or a2.
The expected payoff therefore varies along the line, as Ppa1q varies from 0 to 1.
c -Trenn, King’s College London 7
Mixed strategy
33 22 11 00
−1
−2 −3
j picks a4 −1
−2 −3
0 P(a1) 1
Consider it from i’s perspective. Let’s say you know that j plays a4. i’s payoff will be ́1 or 1 depending on whether i picks a1 or a2.
The expected payoff therefore varies along the line, as Ppa1q varies from 0 to 1.
c -Trenn, King’s College London 8
Mixed strategy
33
22 1 j picks a3 1
00
−1 −2 −3
0.2
j picks a4 −1
−2 −3
0 P(a1) 1
Where the lines intersect, i has the same expected payoff whatever j does. This is a rational choice of mixed strategy.
c -Trenn, King’s College London 9
Mixed strategy
j can do the same kind of analysis:
33 22 11
0 −1 −2 −3
i picks a2
i picks a1
0 −1
−2 −3
0.4
0 P(a3) 1
c -Trenn, King’s College London
10
Mixed strategy
This analysis will help i and j choose a mixed strategy in zero-sum games.
(Archives of the Institute of Advanced Study, Princeton)
This approach is due to von Neumann.
c -Trenn, King’s College London 11
General sum games
Battle of the Outmoded Gender Stereotypes ‚ akaBattleoftheSexes
this that this
that
1 2
0 0
0 0
2 1
Game contains elements of cooperation and competition.
The interplay between these is what makes general sum games interesting.
c -Trenn, King’s College London 12
(Time-Life/Getty)
Negotiation
Interplay between cooperation and competition leads to negotiation See, for example, the work of .
(law-train.eu)
c -Trenn, King’s College London 13
Nash equilibrium
Earlier we introduced the notion of Nash equilibrium as a solution concept for general sum games.
(We didn’t describe it in exactly those terms.)
Looked at pure strategy Nash equilibrium.
Issue was that not every game has a pure strategy Nash equilibrium.
c -Trenn, King’s College London 14
Nash equilibrium
For example:
j
DC D
i
C
2 1
1 2
0 2
1 1
Has no pure strategy NE.
c -Trenn, King’s College London
15
Nash equilibrium
The notion of Nash equilibrium extends to mixed strategies.
And every game has at least one mixed strategy Nash equilibrium.
c -Trenn, King’s College London 16
Nash equilibrium
For a game with payoff matrices A (to i) and B (to j), a mixed strategy px ̊, y ̊q is a Nash equilibrium solution if:
@x, x ̊Ay ̊T • xAy ̊T @y, x ̊By ̊T • x ̊ByT
In other words, x ̊ gives a higher expected value to i than any other strategy when j plays y ̊.
Similarly, y ̊ gives a higher expected value to j than any other strategy when i plays x ̊.
c -Trenn, King’s College London 17
Nash equilibrium
Unfortunately, this doesn’t solve the problem of which Nash equilibrium you should play.
c -Trenn, King’s College London 18
rel
r
r e
–
r
–
= l
3
e
r
ite s
S’- —
9
t ,
}
–
f- =
s
s l
Papp
— 8Ig-
A —
io
O–
-lOl -llO
g
l-I0 4
-i n
weed chat
:*:c:: is
⇒ #= (g) ,
1%1
= xAit
P
,
l
-ll
R R
S -I
o
-l
° o
‘ .,
-l i
a o
l
O
lO
–
l-lP-I
:….
¥¥:÷.