Mixed Strategies: Expected Value

Jennifer Firkins Nordstrom · Introduction to Game Theory, Section 3.3 · CC BY-SA 4.0

Choose your mix so your opponent is indifferent between their options. If they aren't indifferent, they have a best response, which means your mix isn't optimal. Solve the system of equations where expected values are equal.

The indifference principle

If Player 2 can tell that one column is better against your mix, they'll play it. Your mix is only optimal when Player 2 gets the same expected payoff no matter which column they pick. Set the expected values equal and solve for your probabilities. This indifference condition is the same principle behind optimal one-shot bidding: your bid should make competitors indifferent to marginal changes in theirs.

Scheme

; Matching Pennies (zero-sum):
;         H     T
;   H  [ 1    -1 ]
;   T  [-1     1 ]
;
; Player 1 plays H with prob p, T with (1-p).
; Player 2 plays H with prob q, T with (1-q).
;
; For Player 2 to be indifferent:
;   E2(H) = E2(T)
;   -1*p + 1*(1-p) = 1*p + (-1)*(1-p)
;   1 - 2p = 2p - 1
;   2 = 4p => p = 1/2
;
; For Player 1 to be indifferent:
;   E1(H) = E1(T)
;   1*q + (-1)*(1-q) = (-1)*q + 1*(1-q)
;   2q - 1 = 1 - 2q
;   4q = 2 => q = 1/2

(display "Matching Pennies:") (newline)
(display "  Player 1 mix: p = 1/2 (H), 1/2 (T)") (newline)
(display "  Player 2 mix: q = 1/2 (H), 1/2 (T)") (newline)

; Verify: expected value at equilibrium
(define p 0.5) (define q 0.5)
(define ev1-H (+ (* 1 q) (* -1 (- 1 q))))
(define ev1-T (+ (* -1 q) (* 1 (- 1 q))))
(display "  E1(H) = ") (display ev1-H) (newline)
(display "  E1(T) = ") (display ev1-T) (newline)
(display "  Indifferent? ") (display (= ev1-H ev1-T))

Solving a general 2x2 game

For any 2x2 zero-sum game, write the expected value of each of the opponent's strategies in terms of your mixing probability. Set them equal. Solve. The answer tells you both the optimal mix and the value of the game.

Scheme

; General solver for 2x2 zero-sum games
; Matrix (Player 1's payoffs):
;        C       D
;   A  [ a       b ]
;   B  [ c       d ]
;
; Player 1 plays B with prob p.
; E(vs C) = a(1-p) + cp = a + (c-a)p
; E(vs D) = b(1-p) + dp = b + (d-b)p
; Set equal: a + (c-a)p = b + (d-b)p
; Solve:     p = (b-a) / ((c-a) - (d-b))

(define (solve-2x2 a b c d)
  (let* ((num (- b a))
         (den (- (- c a) (- d b)))
         (p (/ num den))
         (value (+ a (* (- c a) p))))
    (list p value)))

; Example from Section 3.2: A=[1,0], B=[-1,2]
(define result (solve-2x2 1 0 -1 2))
(display "Matrix [[1,0],[-1,2]]:") (newline)
(display "  p(B) = ") (display (car result)) (newline)
(display "  game value = ") (display (cadr result)) (newline)

; Rock-Paper-Scissors needs 3 equations, 3 unknowns
(display "  (RPS: symmetric => each with prob 1/3)")

Why indifference works

If Player 2 is not indifferent, they have a pure best response. Then Player 1 should adjust to exploit that response. The only stable state is where neither player can gain by shifting. Indifference is the algebraic expression of Nash equilibrium in mixed strategies.

Scheme

; If you DON'T make them indifferent, they exploit you.
; Suppose Player 1 plays B with p = 0.8 in our game:
;   E(vs C) = 1 - 2(0.8) = -0.6
;   E(vs D) = 2(0.8) = 1.6
; Player 2 picks C (gives P1 payoff -0.6). Disaster.

(define (show-exploitation p)
  (let ((ec (+ 1 (* -2 p)))
        (ed (* 2 p)))
    (display "p = ") (display p)
    (display "  E(vs C) = ") (display ec)
    (display "  E(vs D) = ") (display ed)
    (display "  P2 picks: ")
    (display (if (< ec ed) "C (hurts you)" "D (hurts you)"))
    (newline)))

(show-exploitation 0.1)
(show-exploitation 0.25)  ; optimal - tied
(show-exploitation 0.5)
(show-exploitation 0.8)

Notation reference

Textbook	Scheme	Meaning
E1(H) = E1(T)	(= ev1-H ev1-T)	Indifference condition
p, 1-p	p, (- 1 p)	Player 1's mixed strategy
q, 1-q	q, (- 1 q)	Player 2's mixed strategy
V	(cadr (solve-2x2 ...))	Value of the game

Neighbors

Nordstrom sequence

🎲 Nordstrom 3.2 — Mixed Strategies: Graphical (previous)
🎲 Nordstrom 4.1 — Non-Zero-Sum Intro (next)

🎲 Nordstrom 2.4 — Probability and Expected Value (the foundation for this method)
🍞 Hedges 2018 — selection functions generalize the indifference principle

Foundations (Wikipedia)

Translation notes

The expected value method scales to larger games by adding more equations. Rock-Paper-Scissors gives three equations in three unknowns. For games bigger than 3x3, the linear algebra is the same but you typically reach for linear programming. The graphical method (previous page) gives the same answer for 2x2 games but with geometric intuition instead of algebra.

Want the full treatment? Read Section 3.3 in Nordstrom's textbook.

← Mixed: Graphical by june.kim Non-Zero-Sum Games →