Auctions

Sources: Wikipedia (CC BY-SA 4.0) · Vickrey (1961) · Milgrom & Weber (1982)

Four canonical auction formats, one deep result: under standard assumptions, revenue equivalence says they all yield the same expected revenue. The differences matter when those assumptions break down, which they always do in practice.

Four canonical formats

English (ascending): bidders raise prices until one remains. Dutch (descending): price drops until someone claims the item. First-price sealed: highest bid wins, pays their bid. Second-price sealed (Vickrey): highest bid wins, pays the second-highest bid. English and Vickrey are strategically equivalent (dominant strategy: bid your value). Dutch and first-price sealed are strategically equivalent (must shade your bid below your value).

Scheme

; Four auction formats with three bidders
; True values: 80, 60, 45

(define values (list 80 60 45))

; --- Vickrey (second-price sealed) ---
; Dominant strategy: bid true value
(define vickrey-bids values)
(define vickrey-winner (apply max vickrey-bids))
(define vickrey-payment
  (car (sort (cdr (sort vickrey-bids >)) >)))

(display "=== Vickrey ===") (newline)
(display "Bids: ") (display vickrey-bids) (newline)
(display "Winner pays: $") (display vickrey-payment) (newline)

; --- First-price sealed ---
; Equilibrium bid = value * (n-1)/n for uniform values
(define n (length values))
(define fp-bids
  (map (lambda (v) (* v (/ (- n 1) n))) values))

(newline) (display "=== First-price ===") (newline)
(display "Shaded bids: ")
(display (map (lambda (b) (/ (round (* b 100)) 100)) fp-bids)) (newline)
(define fp-payment (apply max fp-bids))
(display "Winner pays: $")
(display (/ (round (* fp-payment 100)) 100)) (newline)

; Revenue equivalence: both yield ~same expected revenue
(newline) (display "Revenue equivalence:") (newline)
(display "Vickrey revenue: $") (display vickrey-payment) (newline)
(display "First-price revenue: $")
(display (/ (round (* fp-payment 100)) 100))

; Four auction formats with three bidders
; True values: 80, 60, 45

(define values (list 80 60 45))

; --- Vickrey (second-price sealed) ---
; Dominant strategy: bid true value
(define vickrey-bids values)
(define vickrey-winner (apply max vickrey-bids))
(define vickrey-payment
  (car (sort (cdr (sort vickrey-bids >)) >)))

(display "=== Vickrey ===") (newline)
(display "Bids: ") (display vickrey-bids) (newline)
(display "Winner pays: $") (display vickrey-payment) (newline)

; --- First-price sealed ---
; Equilibrium bid = value * (n-1)/n for uniform values
(define n (length values))
(define fp-bids
  (map (lambda (v) (* v (/ (- n 1) n))) values))

(newline) (display "=== First-price ===") (newline)
(display "Shaded bids: ")
(display (map (lambda (b) (/ (round (* b 100)) 100)) fp-bids)) (newline)
(define fp-payment (apply max fp-bids))
(display "Winner pays: $")
(display (/ (round (* fp-payment 100)) 100)) (newline)

; Revenue equivalence: both yield ~same expected revenue
(newline) (display "Revenue equivalence:") (newline)
(display "Vickrey revenue: $") (display vickrey-payment) (newline)
(display "First-price revenue: $")
(display (/ (round (* fp-payment 100)) 100))

Revenue equivalence theorem

Under four conditions (independent private values, risk-neutral bidders, symmetric bidders, the lowest-type bidder gets zero surplus), all standard auctions yield the same expected revenue. The seller's choice of format does not matter for revenue. It matters for other things: the Vickrey auction is simpler (truth-telling is dominant), but first-price auctions are more robust to collusion.

Scheme

; Revenue equivalence: simulation
; N bidders draw values uniformly from [0, 100]
; Expected revenue in both formats = (N-2)/(N-1) * 100 * N/(N+1)
; For uniform [0,1]: E[revenue] = (N-1)/(N+1)

(define (expected-revenue-uniform n)
  ; E[second-highest of n draws from Uniform(0,100)]
  ; = 100 * (n-1) / (n+1)
  (/ (* 100 (- n 1)) (+ n 1)))

(display "Expected revenue (uniform values on [0,100]):") (newline)
(for-each
  (lambda (n)
    (display "  ") (display n) (display " bidders: $")
    (display (/ (round (* (expected-revenue-uniform n) 100)) 100))
    (newline))
  (list 2 3 5 10 20))

(newline)
(display "More bidders = more competition = higher revenue") (newline)
(display "But format does not matter (given the assumptions).")

VCG for multiple items

The VCG mechanism extends to multi-item auctions. Each bidder reports values for all bundles of items. The mechanism finds the welfare-maximizing allocation, then charges each bidder the externality they impose on others. This generalizes the Vickrey auction from one item to any combinatorial allocation problem. Computational complexity is the catch: finding the optimal allocation is NP-hard in general.

Scheme

; VCG multi-item: 2 items (A, B), 3 bidders
; Bidder values for individual items and the bundle

; (value-A  value-B  value-AB)
(define bidder-1 (list 10 8 15))   ; slight complementarity
(define bidder-2 (list 7 12 18))   ; complementarity
(define bidder-3 (list 9 6 14))

; Efficient allocation: maximize total welfare
; Try: bidder-1 gets A (10), bidder-2 gets B (12) => 22
; Try: bidder-2 gets AB (18) => 18
; Try: bidder-1 gets A (10), bidder-3 gets B (6) => 16
; Best: bidder-1 gets A, bidder-2 gets B => 22

(display "Efficient allocation:") (newline)
(display "  Bidder 1 gets A (value=10)") (newline)
(display "  Bidder 2 gets B (value=12)") (newline)
(display "  Total welfare: 22") (newline) (newline)

; VCG payment for bidder 1:
; Without bidder 1: best is bidder-2 gets AB (18)
;   Others' welfare without 1: 18
; With bidder 1: others' welfare: 12 (bidder-2 gets B)
; Payment = 18 - 12 = 6

; VCG payment for bidder 2:
; Without bidder 2: bidder-1 gets A (10), bidder-3 gets B (6) = 16
; With bidder 2: others' welfare: 10 (bidder-1 gets A)
; Payment = 16 - 10 = 6

(display "VCG payments:") (newline)
(display "  Bidder 1: $6 (gets $10 item, surplus $4)") (newline)
(display "  Bidder 2: $6 (gets $12 item, surplus $6)") (newline)
(display "  Total revenue: $12")

; VCG multi-item: 2 items (A, B), 3 bidders
; Bidder values for individual items and the bundle

; (value-A  value-B  value-AB)
(define bidder-1 (list 10 8 15))   ; slight complementarity
(define bidder-2 (list 7 12 18))   ; complementarity
(define bidder-3 (list 9 6 14))

; Efficient allocation: maximize total welfare
; Try: bidder-1 gets A (10), bidder-2 gets B (12) => 22
; Try: bidder-2 gets AB (18) => 18
; Try: bidder-1 gets A (10), bidder-3 gets B (6) => 16
; Best: bidder-1 gets A, bidder-2 gets B => 22

(display "Efficient allocation:") (newline)
(display "  Bidder 1 gets A (value=10)") (newline)
(display "  Bidder 2 gets B (value=12)") (newline)
(display "  Total welfare: 22") (newline) (newline)

; VCG payment for bidder 1:
; Without bidder 1: best is bidder-2 gets AB (18)
;   Others' welfare without 1: 18
; With bidder 1: others' welfare: 12 (bidder-2 gets B)
; Payment = 18 - 12 = 6

; VCG payment for bidder 2:
; Without bidder 2: bidder-1 gets A (10), bidder-3 gets B (6) = 16
; With bidder 2: others' welfare: 10 (bidder-1 gets A)
; Payment = 16 - 10 = 6

(display "VCG payments:") (newline)
(display "  Bidder 1: $6 (gets $10 item, surplus $4)") (newline)
(display "  Bidder 2: $6 (gets $12 item, surplus $6)") (newline)
(display "  Total revenue: $12")

Neighbors

Cross-references

Hedges 2018 — compositional game theory: auctions as composed open games
june.kim: One-Shot Bidding — optimal strategies in single-round auctions
june.kim: Power Diagrams in Ad Auctions — geometric view of auction equilibria

Foundations (Wikipedia)

← Comparative Systems by june.kim