Zero-Sum Games

; Check if a game is zero-sum
; Every payoff vector must sum to the same constant

(define (zero-sum? payoff-fn strategies1 strategies2)
  (let* ((first-sum (apply + (payoff-fn (car strategies1) (car strategies2))))
         (all-same
          (every (lambda (s1)
            (every (lambda (s2)
              (= (apply + (payoff-fn s1 s2)) first-sum))
              strategies2))
            strategies1)))
    (list all-same first-sum)))

; Matching Pennies: zero-sum
(define (matching-pennies r c)
  (if (eq? r c) '(1 -1) '(-1 1)))

(display "Matching Pennies zero-sum? ")
(display (zero-sum? matching-pennies '(H T) '(H T)))
(newline)

; Prisoner's Dilemma: NOT zero-sum
(define (prisoners r c)
  (cond ((and (eq? r 'C) (eq? c 'C)) '(3 3))
        ((and (eq? r 'C) (eq? c 'D)) '(0 5))
        ((and (eq? r 'D) (eq? c 'C)) '(5 0))
        (else '(1 1))))

(display "Prisoner's Dilemma zero-sum? ")
(display (zero-sum? prisoners '(C D) '(C D)))

; Simplified zero-sum matrix: only store P1 payoffs
; P2 payoff = negative of P1 payoff

(define (make-zero-sum-matrix p1-payoffs)
  p1-payoffs)

(define (full-payoff zs-matrix row col)
  (let ((p1 (list-ref (list-ref zs-matrix row) col)))
    (list p1 (- p1))))

; Election campaign game (Nordstrom example)
; Two candidates choose positions. Values = P1 vote share above 50 percent.
(define election '((0 4 -1)
                   (-4 0 3)
                   (1 -3 0)))

(display "Full payoffs from simplified matrix:") (newline)
(let loop ((i 0))
  (if (< i 3)
    (begin (let col-loop ((j 0))
      (if (< j 3)
        (begin (display (full-payoff election i j)) (display " ")
               (col-loop (+ j 1)))))
    (newline)
    (loop (+ i 1)))))

; Find equilibrium (saddle point) in a zero-sum game
; A cell is an equilibrium if:
;   it is the minimum of its row (P1 cannot be exploited)
;   AND the maximum of its column (P2 cannot be exploited)

(define (row-min matrix row)
  (apply min (list-ref matrix row)))

(define (col-max matrix col)
  (apply max (map (lambda (row) (list-ref row col)) matrix)))

(define (find-saddle-points matrix)
  (let ((n-rows (length matrix))
        (n-cols (length (car matrix))))
    (let row-loop ((i 0) (results '()))
      (if (>= i n-rows) results
          (let col-loop ((j 0) (res results))
            (if (>= j n-cols)
                (row-loop (+ i 1) res)
                (let ((val (list-ref (list-ref matrix i) j)))
                  (if (and (= val (row-min matrix i))
                           (= val (col-max matrix j)))
                      (col-loop (+ j 1) (cons (list i j val) res))
                      (col-loop (+ j 1) res)))))))))

; Game with a saddle point
(define game1 '((3 1 2)
                (0 -1 4)
                (2 1 0)))

(display "Saddle points: ") (display (find-saddle-points game1))
; Row 0, Col 1, value 1 is equilibrium if present

(newline)
; Game without a saddle point
(define game2 '((2 -1)
                (-3 4)))
(display "Saddle points: ") (display (find-saddle-points game2))
; Empty. No pure-strategy equilibrium.