Equilibrium Points

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

An equilibrium point is a strategy pair where neither player can improve by switching. In a zero-sum game, every equilibrium point has the same value. This is the Nash equilibrium for two-player zero-sum games.

Neither player wants to switch

Look at a payoff matrix. An equilibrium pair is a cell where the row player is already in their best row (given the column) and the column player is already in their best column (given the row). Neither has a reason to deviate.

Scheme

; Finding equilibrium points in a zero-sum payoff matrix
; An equilibrium is a cell that is:
;   - the maximum in its column (best for row player)
;   - the minimum in its row (best for column player, who wants row low)

(define matrix '((2 -1) (-3 1)))

(define (matrix-ref m r c) (list-ref (list-ref m r) c))
(define (num-rows m) (length m))
(define (num-cols m) (length (car m)))

; Max in column c
(define (col-max m c)
  (apply max (map (lambda (row) (list-ref row c)) m)))

; Min in row r
(define (row-min m r)
  (apply min (list-ref m r)))

; Find all equilibrium points
(define (find-equilibria m)
  (let ((eqs '()))
    (let rloop ((r 0))
      (if (>= r (num-rows m)) eqs
        (let cloop ((c 0))
          (if (>= c (num-cols m)) (rloop (+ r 1))
            (let ((val (matrix-ref m r c)))
              (if (and (= val (col-max m c))
                       (= val (row-min m r)))
                  (begin (set! eqs (cons (list r c val) eqs))
                         (cloop (+ c 1)))
                  (cloop (+ c 1))))))))))

(display "Matrix: ") (display matrix) (newline)
(display "Equilibria (row col value): ")
(display (find-equilibria matrix))
; (0 0 2) — R1,C1 with value 2

; Finding equilibrium points in a zero-sum payoff matrix
; An equilibrium is a cell that is:
;   - the maximum in its column (best for row player)
;   - the minimum in its row (best for column player, who wants row low)

(define matrix '((2 -1) (-3 1)))

(define (matrix-ref m r c) (list-ref (list-ref m r) c))
(define (num-rows m) (length m))
(define (num-cols m) (length (car m)))

; Max in column c
(define (col-max m c)
  (apply max (map (lambda (row) (list-ref row c)) m)))

; Min in row r
(define (row-min m r)
  (apply min (list-ref m r)))

; Find all equilibrium points
(define (find-equilibria m)
  (let ((eqs '()))
    (let rloop ((r 0))
      (if (>= r (num-rows m)) eqs
        (let cloop ((c 0))
          (if (>= c (num-cols m)) (rloop (+ r 1))
            (let ((val (matrix-ref m r c)))
              (if (and (= val (col-max m c))
                       (= val (row-min m r)))
                  (begin (set! eqs (cons (list r c val) eqs))
                         (cloop (+ c 1)))
                  (cloop (+ c 1))))))))))

(display "Matrix: ") (display matrix) (newline)
(display "Equilibria (row col value): ")
(display (find-equilibria matrix))
; (0 0 2) — R1,C1 with value 2

Solution theorem: all equilibria share one value

In a two-player zero-sum game, every equilibrium point has the same payoff. The proof works by contradiction: assume two equilibria with different values, then show that at least one player could have improved by switching, contradicting the equilibrium definition.

Scheme

; Verify: all equilibrium points share the same value
; Try several matrices

(define (every pred lst) (if (null? lst) #t (if (pred (car lst)) (every pred (cdr lst)) #f)))

(define (all-eq-values-same? m)
  (let ((eqs (find-equilibria m)))
    (if (null? eqs) "no equilibria"
        (let ((vals (map caddr eqs)))
          (every (lambda (v) (= v (car vals))) vals)))))

; Matrix 1: one equilibrium
(define m1 '((2 -1) (-3 1)))
(display "M1 equilibria: ") (display (find-equilibria m1)) (newline)
(display "Same value? ") (display (all-eq-values-same? m1)) (newline)

; Matrix 2: two equilibria, both value 0
(define m2 '((0 -1 1) (1 0 -1) (-1 1 0)))
(display "M2 equilibria: ") (display (find-equilibria m2)) (newline)

; Matrix 3: two equilibria
(define m3 '((3 -2 1) (1 3 -2) (-2 1 3)))
(display "M3 equilibria: ") (display (find-equilibria m3)) (newline)
(display "Same value? ") (display (all-eq-values-same? m3))

Same value does not mean equilibrium

A cell can have the same payoff as an equilibrium point without being an equilibrium itself. The value must be simultaneously the row minimum and column maximum. Just matching the number is not enough.

Scheme

; A cell can have the same value as an equilibrium
; without being an equilibrium itself.

(define tricky '((1 3) (2 1)))

(display "Matrix: ") (display tricky) (newline)
(display "Equilibria: ") (display (find-equilibria tricky)) (newline)
; (0 0 1) is an equilibrium: min of row 0, max of col 0.
; (1 1 1) has value 1 but is NOT an equilibrium:
;   row 1 min is 1 (ok), but col 1 max is 3 (not 1).
(display "Cell (1,1) = 1 but col-max of col 1 = ")
(display (col-max tricky 1)) (newline)
(display "So (1,1) is not an equilibrium despite having value 1.")

Notation reference

Concept	Scheme	Meaning
Equilibrium pair	(find-equilibria m)	Strategy pair where neither player benefits from switching
Row min	(row-min m r)	Best the column player can force in that row
Col max	(col-max m c)	Best the row player can get in that column
Solution theorem	(all-eq-values-same? m)	All equilibria in a zero-sum game share one value

Neighbors

Nordstrom series

🍞 §2.3 Probability and Expected Value — previous section
🍞 §2.5 Zero-Sum Summary — next section
💰 Economics Ch.8 — market equilibrium is Nash equilibrium applied to supply and demand
🍞 Hedges, Ghani 2018 — Nash equilibrium composes categorically
🧠 Cognitive Science Ch.6 — decision theory and bounded rationality alongside equilibrium