Probability and Expected Value

Nordstrom, Introduction to Game Theory §2.3 · nordstrommath.com · CC BY-SA 4.0

A mixed strategy assigns probabilities to pure strategies. The expected value is the weighted average payoff: multiply each outcome by its probability and sum. A game is fair when the expected value is zero.

Probability over strategies

When a player randomizes, each pure strategy gets a probability. The probabilities must sum to 1. A probability distribution over strategies is the simplest object in mixed-strategy game theory. The same machinery applies to one-shot bidding, where a bidder chooses a bid under uncertainty about the competition.

Scheme

; A mixed strategy is a probability distribution over pure strategies.
; Probabilities must sum to 1.

(define (make-mixed-strategy actions probs)
  (if (not (= 1 (apply + probs)))
      (begin (display "ERROR: probabilities must sum to 1") (newline))
      (map list actions probs)))

; Rock-Paper-Scissors: biased toward Paper
(define rps-mix
  (make-mixed-strategy '(rock paper scissors) '(0.2 0.5 0.3)))

(display "Mixed strategy: ") (display rps-mix) (newline)

; Uniform distribution (optimal for RPS)
(define rps-uniform
  (make-mixed-strategy '(rock paper scissors)
    '(0.333 0.334 0.333)))

(display "Uniform: ") (display rps-uniform)

Expected value

The expected value of a game is what you'd average per play over many repetitions. Multiply each outcome's payoff by its probability, then sum. If the expected value is zero, the game is fair. If it's negative, the house wins on average.

Scheme

; Expected value: sum of (probability * payoff) over all outcomes
(define (expected-value outcomes probs)
  (apply + (map * outcomes probs)))

; Fair coin toss: win $25 on heads, lose $25 on tails
(define coin-ev
  (expected-value '(25 -25) '(0.5 0.5)))
(display "Fair coin EV: $") (display coin-ev) (newline)

; Two-coin game: HH wins $2, HT wins $1, TT loses $4
; P(HH)=0.25, P(HT)=0.5, P(TT)=0.25
(define two-coin-ev
  (expected-value '(2 1 -4) '(0.25 0.5 0.25)))
(display "Two-coin EV: $") (display two-coin-ev) (newline)

; Roulette: 18 red, 18 black, 2 green out of 38
; Bet $1 on red: win $1 or lose $1
(define roulette-ev
  (expected-value '(1 -1) '(0.4737 0.5263)))
(display "Roulette EV: $") (display roulette-ev) (newline)
(display "House always wins.")

Expected value of a mixed strategy

When both players mix, the expected payoff is the weighted average over all strategy combinations. Each cell of the payoff matrix contributes its payoff times the product of both players' probabilities for that cell.

Scheme

; Expected value when both players use mixed strategies
; Payoff matrix (row player's payoffs):
;           Col1    Col2
; Row1       3      -1
; Row2      -2       4
;
; Row player mixes (0.6, 0.4), Col player mixes (0.3, 0.7)

(define payoffs '((3 -1) (-2 4)))
(define row-probs '(0.6 0.4))
(define col-probs '(0.3 0.7))

(define (mixed-ev matrix rp cp)
  (apply +
    (map (lambda (row rprob)
      (apply +
        (map (lambda (cell cprob)
          (* rprob cprob cell))
        row cp)))
    matrix rp)))

(define ev (mixed-ev payoffs row-probs col-probs))
(display "Expected payoff: ") (display ev) (newline)

; Break it down:
; 0.6*0.3*3 + 0.6*0.7*(-1) + 0.4*0.3*(-2) + 0.4*0.7*4
; = 0.54 + (-0.42) + (-0.24) + 1.12 = 1.0
(display "Check: ")
(display (+ (* 0.6 0.3 3) (* 0.6 0.7 -1) (* 0.4 0.3 -2) (* 0.4 0.7 4)))

Notation reference

Symbol	Scheme	Meaning
P(E)	p	Probability of event E, between 0 and 1
E(X)	(expected-value ...)	Expected value: weighted average payoff
sigma	(make-mixed-strategy ...)	Mixed strategy: probability distribution over actions
E(X) = 0	(= ev 0)	Fair game: neither player has an edge

Neighbors

Nordstrom series

🍞 §2.2 Dominated Strategies — previous section
🍞 §2.4 Equilibrium Points — next section
🍞 §3.1 Repeated Games — where mixed strategies pay off

Foundations (Wikipedia)

Source: Nordstrom §2.3. Licensed CC BY-SA 4.0.

← Dominated Strategies by june.kim Equilibrium Points →