VCG as a Linear Program

; VCG as optimization: maximize welfare, then compute payments
; For single-item: LP is trivial. Multi-item shows the power.

;; Single item, 3 bidders
(define (vcg-lp-single bids)
  ;; Primal: max sum(v_i * x_i) s.t. sum(x_i) <= 1, x_i in 0,1
  ;; Solution: give item to highest bidder
  (let* ((n (length bids))
         (max-bid (apply max bids))
         (winner (let loop ((i 0))
                   (if (= (list-ref bids i) max-bid) i (loop (+ i 1)))))
         ;; Dual: price = shadow price of capacity constraint
         ;; = second-highest bid (marginal value of relaxing capacity)
         (sorted (sort bids >))
         (dual-price (cadr sorted)))
    (list winner max-bid dual-price)))

(define result (vcg-lp-single '(10 7 4)))
(display "Winner: bidder ") (display (car result)) (newline)
(display "Value: $") (display (cadr result)) (newline)
(display "VCG price (LP dual): $") (display (caddr result)) (newline)

;; Multi-item: 2 items, 3 bidders, unit demand
(define (vcg-lp-multi bids k)
  ;; Give items to top-k bidders
  ;; Each winner's price = (k+1)-th highest bid (the excluded bidder)
  (let* ((sorted (sort bids >))
         (winners (let loop ((i 0) (acc '()))
                    (if (= i k) (reverse acc)
                        (loop (+ i 1) (cons (list-ref sorted i) acc)))))
         (marginal (list-ref sorted k)))
    (list winners marginal)))

(display "\n2 items, bids (10 7 4 3):")
(newline)
(define r2 (vcg-lp-multi '(10 7 4 3) 2))
(display "Winners: ") (display (car r2)) (newline)
(display "Each pays: $") (display (cadr r2))