Nordstrom, Introduction to Game Theory §2.5 · nordstrommath.com · CC BY-SA 4.0
The minimax theorem: the row player's maximin (best guaranteed minimum) equals the column player's minimax (least the row player can be held to) at the saddle point. When they meet, both players have a pure equilibrium strategy.
Maximin and minimax
The row player looks at each row's worst outcome (the minimum) and picks the row with the best worst case. That's maximin. The column player looks at each column's best outcome for the row player (the maximum) and picks the column that minimizes it. That's minimax. When maximin equals minimax, the game has a saddle point.
Scheme
; Maximin: row player's best guaranteed minimum; Minimax: column player's best limit on row player's gain; Saddle point: where they meet
(define matrix '((4-25) (130) (-126)))
(define (row-mins m)
(map (lambda (row) (apply min row)) m))
(define (col-maxes m)
(let ((cols (length (car m))))
(let loop ((c 0) (result '()))
(if (>= c cols) (reverse result)
(loop (+ c 1)
(cons (apply max (map (lambda (r) (list-ref r c)) m))
result))))))
(define (maximin m) (apply max (row-mins m)))
(define (minimax m) (apply min (col-maxes m)))
(display "Row minimums: ") (display (row-mins matrix)) (newline)
(display "Maximin: ") (display (maximin matrix)) (newline)
(display "Column maximums: ") (display (col-maxes matrix)) (newline)
(display "Minimax: ") (display (minimax matrix)) (newline)
(display "Saddle point? ")
(display (if (= (maximin matrix) (minimax matrix))
(string-append "Yes, value = "
(number->string (maximin matrix)))
"No saddle point"))
Python
# Maximin, minimax, and saddle points
matrix = [[4, -2, 5], [1, 3, 0], [-1, 2, 6]]
row_mins = [min(row) for row in matrix]
col_maxes = [max(matrix[r][c] for r inrange(len(matrix)))
for c inrange(len(matrix[0]))]
maximin = max(row_mins)
minimax = min(col_maxes)
print(f"Row minimums: {row_mins}")
print(f"Maximin: {maximin}")
print(f"Column maximums: {col_maxes}")
print(f"Minimax: {minimax}")
print(f"Saddle point: {'Yes' if maximin == minimax else 'No'}, value = {maximin}")
When there is no saddle point
If maximin does not equal minimax, the game has no pure-strategy equilibrium. The row player's guaranteed floor is below the column player's guaranteed ceiling. The gap between them is where mixed strategies live, covered in the next chapter.
Nordstrom summarizes the procedure for solving a zero-sum game. First eliminate dominated strategies. Then check for equilibrium points. If one exists, both players should play it (pure strategy). If none exists, use mixed strategies to find the game's value.
Scheme
; Full zero-sum analysis pipeline
(define (analyze-zero-sum m)
(display "Matrix: ") (display m) (newline)
(display "1. Row minimums: ") (display (row-mins m)) (newline)
(display " Maximin: ") (display (maximin m)) (newline)
(display "2. Column maximums: ") (display (col-maxes m)) (newline)
(display " Minimax: ") (display (minimax m)) (newline)
(if (= (maximin m) (minimax m))
(begin
(display "3. Saddle point exists at value ")
(display (maximin m)) (newline)
(display " -> Play pure strategies."))
(begin
(display "3. No saddle point.") (newline)
(display " -> Use mixed strategies (next chapter).")))
(newline))
(analyze-zero-sum '((4-25) (130) (-126)))
(newline)
(analyze-zero-sum '((1-1) (-11)))
Minimax theorem