Dominated Strategies

Jennifer Nordstrom · CC BY-SA 4.0 · §2.2 Dominated Strategies

A strategy is dominated if another strategy is always at least as good, no matter what the opponent does. A rational player never plays a dominated strategy. Delete it. Then check again. Repeat until nothing is dominated.

What is a dominated strategy?

Strategy X is dominated by strategy Y if, for every possible opponent action, Y gives a payoff greater than or equal to X. If Y is strictly better in every case, X is strictly dominated. A rational player will never choose a dominated strategy, so we can remove it from the matrix.

Scheme

; Check if strategy X is dominated by strategy Y
; (P1 perspective: compare row payoffs across all columns)

(define (dominates? row-y row-x)
  ; Y dominates X if every entry in Y >= corresponding entry in X
  (every (lambda (pair)
    (>= (car pair) (cdr pair)))
    (map cons row-y row-x)))

; Zero-sum matrix (P1 payoffs only)
(define matrix '((4 3)    ; Row A
                 (1 0)    ; Row B
                 (2 5)))  ; Row C

(display "A dominates B? ")
(display (dominates? (list-ref matrix 0) (list-ref matrix 1)))
(newline)
(display "A dominates C? ")
(display (dominates? (list-ref matrix 0) (list-ref matrix 2)))
(newline)
(display "C dominates B? ")
(display (dominates? (list-ref matrix 2) (list-ref matrix 1)))
; A dominates B (4>=1, 3>=0). A does not dominate C (3 < 5).
; C dominates B (2>=1, 5>=0). So B is dominated. Delete it.

Iterated elimination of dominated strategies

Sometimes no strategy is obviously dominated. But after you delete one dominated strategy, a previously safe strategy becomes dominated in the smaller matrix. Repeat: delete, recheck, delete, recheck. This is iterated elimination.

Scheme

; Iterated elimination of dominated strategies (rows only, for zero-sum)
; Remove dominated rows, then check again.

(define (remove-dominated rows labels)
  (let loop ((remaining rows) (names labels)
             (kept-rows '()) (kept-names '()))
    (if (null? remaining)
        (list (reverse kept-rows) (reverse kept-names))
        (let* ((candidate (car remaining))
               (others (append kept-rows (cdr remaining)))
               (is-dominated (any (lambda (other) (dominates? other candidate)) others)))
          (if is-dominated
              (begin
                (display "  Eliminating ") (display (car names))
                (display " (dominated)") (newline)
                (loop (cdr remaining) (cdr names) kept-rows kept-names))
              (loop (cdr remaining) (cdr names)
                    (cons candidate kept-rows)
                    (cons (car names) kept-names)))))))

(define (iterated-elimination matrix labels)
  (display "Starting matrix: ") (display labels) (newline)
  (let loop ((m matrix) (l labels) (round 1))
    (display "Round ") (display round) (display ":") (newline)
    (let* ((result (remove-dominated m l))
           (new-m (car result))
           (new-l (cadr result)))
      (if (= (length new-m) (length m))
          (begin (display "  No more eliminations.") (newline) (list new-m new-l))
          (loop new-m new-l (+ round 1))))))

; Example: three rows, iterated elimination needed
(define game '((4 3 2)
               (1 0 1)
               (3 4 0)))
(iterated-elimination game '(A B C))

; Iterated elimination of dominated strategies (rows only, for zero-sum)
; Remove dominated rows, then check again.

(define (remove-dominated rows labels)
  (let loop ((remaining rows) (names labels)
             (kept-rows '()) (kept-names '()))
    (if (null? remaining)
        (list (reverse kept-rows) (reverse kept-names))
        (let* ((candidate (car remaining))
               (others (append kept-rows (cdr remaining)))
               (is-dominated (any (lambda (other) (dominates? other candidate)) others)))
          (if is-dominated
              (begin
                (display "  Eliminating ") (display (car names))
                (display " (dominated)") (newline)
                (loop (cdr remaining) (cdr names) kept-rows kept-names))
              (loop (cdr remaining) (cdr names)
                    (cons candidate kept-rows)
                    (cons (car names) kept-names)))))))

(define (iterated-elimination matrix labels)
  (display "Starting matrix: ") (display labels) (newline)
  (let loop ((m matrix) (l labels) (round 1))
    (display "Round ") (display round) (display ":") (newline)
    (let* ((result (remove-dominated m l))
           (new-m (car result))
           (new-l (cadr result)))
      (if (= (length new-m) (length m))
          (begin (display "  No more eliminations.") (newline) (list new-m new-l))
          (loop new-m new-l (+ round 1))))))

; Example: three rows, iterated elimination needed
(define game '((4 3 2)
               (1 0 1)
               (3 4 0)))
(iterated-elimination game '(A B C))

Maximin and minimax

When elimination does not reduce the matrix to a single cell, use maximin (Player 1) and minimax (Player 2). Player 1 assumes the worst case for each row and picks the row where the worst case is best. Player 2 assumes the worst case for each column and picks the column where the worst case is least bad.

Scheme

; Maximin (P1): maximize the minimum payoff across columns
; Minimax (P2): minimize the maximum payoff across columns

(define (maximin matrix row-labels)
  (let loop ((rows matrix) (names row-labels)
             (best-name #f) (best-min -999))
    (if (null? rows)
        (list best-name best-min)
        (let ((row-min (apply min (car rows))))
          (if (> row-min best-min)
              (loop (cdr rows) (cdr names) (car names) row-min)
              (loop (cdr rows) (cdr names) best-name best-min))))))

(define (minimax matrix col-labels)
  (let* ((n-cols (length (car matrix)))
         (col-maxes
          (let col-loop ((j 0) (result '()))
            (if (>= j n-cols) (reverse result)
                (col-loop (+ j 1)
                  (cons (apply max (map (lambda (row) (list-ref row j)) matrix))
                        result))))))
    (let loop ((maxes col-maxes) (names col-labels)
               (best-name #f) (best-max 999))
      (if (null? maxes)
          (list best-name best-max)
          (if (< (car maxes) best-max)
              (loop (cdr maxes) (cdr names) (car names) (car maxes))
              (loop (cdr maxes) (cdr names) best-name best-max))))))

(define game '((3 -2 1)
               (0  4 -1)
               (2  1  0)))

(display "Maximin (P1): ") (display (maximin game '(A B C))) (newline)
(display "Minimax (P2): ") (display (minimax game '(X Y Z))) (newline)
; If maximin value = minimax value, that is the equilibrium value.
(let ((mm (cadr (maximin game '(A B C))))
      (mn (cadr (minimax game '(X Y Z)))))
  (display "Equilibrium? ")
  (display (if (= mm mn) "yes, saddle point" "no, need mixed strategies")))

; Maximin (P1): maximize the minimum payoff across columns
; Minimax (P2): minimize the maximum payoff across columns

(define (maximin matrix row-labels)
  (let loop ((rows matrix) (names row-labels)
             (best-name #f) (best-min -999))
    (if (null? rows)
        (list best-name best-min)
        (let ((row-min (apply min (car rows))))
          (if (> row-min best-min)
              (loop (cdr rows) (cdr names) (car names) row-min)
              (loop (cdr rows) (cdr names) best-name best-min))))))

(define (minimax matrix col-labels)
  (let* ((n-cols (length (car matrix)))
         (col-maxes
          (let col-loop ((j 0) (result '()))
            (if (>= j n-cols) (reverse result)
                (col-loop (+ j 1)
                  (cons (apply max (map (lambda (row) (list-ref row j)) matrix))
                        result))))))
    (let loop ((maxes col-maxes) (names col-labels)
               (best-name #f) (best-max 999))
      (if (null? maxes)
          (list best-name best-max)
          (if (< (car maxes) best-max)
              (loop (cdr maxes) (cdr names) (car names) (car maxes))
              (loop (cdr maxes) (cdr names) best-name best-max))))))

(define game '((3 -2 1)
               (0  4 -1)
               (2  1  0)))

(display "Maximin (P1): ") (display (maximin game '(A B C))) (newline)
(display "Minimax (P2): ") (display (minimax game '(X Y Z))) (newline)
; If maximin value = minimax value, that is the equilibrium value.
(let ((mm (cadr (maximin game '(A B C))))
      (mn (cadr (minimax game '(X Y Z)))))
  (display "Equilibrium? ")
  (display (if (= mm mn) "yes, saddle point" "no, need mixed strategies")))

Notation reference

Term	Scheme	Meaning
Dominates	(dominates? row-y row-x)	Y >= X in every column
Iterated elimination	(iterated-elimination m labels)	Delete dominated, recheck, repeat
Maximin	(maximin matrix labels)	P1: maximize worst-case payoff
Minimax	(minimax matrix labels)	P2: minimize worst-case loss

Neighbors

🎲 Nordstrom §1.1 — players and strategies: the ingredients of a game
🎲 Nordstrom §1.2 — game matrices: payoffs in a table
🎲 Nordstrom §1.3 — zero-sum games: your gain is my loss