VCG Mechanism

Clarke 1971 · Groves 1973 · Clarke doi:10.2307/1914085 · Groves doi:10.2307/1914085

Each winner pays the externality they impose on other bidders. This makes truthful bidding dominant, allocation efficient, and participation individually rational.

The externality principle

Your VCG payment = the total value others would have gotten without you, minus the total value others actually get. You pay exactly the harm your presence causes.

Scheme

; VCG mechanism: each winner pays the externality they impose
; payment_i = welfare_others_without_i - welfare_others_with_i

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

(define (remove-nth lst n)
  (if (= n 0) (cdr lst)
      (cons (car lst) (remove-nth (cdr lst) (- n 1)))))

(define (vcg-payment bids winner-idx)
  (let* ((others-with (remove-nth bids winner-idx))
         (welfare-others-with (sum others-with))
         ;; Without winner, next highest gets the item
         (others-without (remove-nth bids winner-idx))
         (welfare-others-without (+ (apply max others-without)
                                     (sum (cdr (sort others-without >))))))
    ;; Simplified: for single-item, payment = second-highest bid
    (apply max others-with)))

; Single item auction: bids = (10 7 4)
(define bids '(10 7 4))
(display "Bids: ") (display bids) (newline)
(display "Winner: bidder 0 (bid $10)") (newline)
(display "VCG payment: $")
(display (vcg-payment bids 0)) (newline)
(display "Surplus: $")
(display (- 10 (vcg-payment bids 0)))
; For a single item, VCG reduces to second-price (Vickrey)

; VCG mechanism: each winner pays the externality they impose
; payment_i = welfare_others_without_i - welfare_others_with_i

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

(define (remove-nth lst n)
  (if (= n 0) (cdr lst)
      (cons (car lst) (remove-nth (cdr lst) (- n 1)))))

(define (vcg-payment bids winner-idx)
  (let* ((others-with (remove-nth bids winner-idx))
         (welfare-others-with (sum others-with))
         ;; Without winner, next highest gets the item
         (others-without (remove-nth bids winner-idx))
         (welfare-others-without (+ (apply max others-without)
                                     (sum (cdr (sort others-without >))))))
    ;; Simplified: for single-item, payment = second-highest bid
    (apply max others-with)))

; Single item auction: bids = (10 7 4)
(define bids '(10 7 4))
(display "Bids: ") (display bids) (newline)
(display "Winner: bidder 0 (bid $10)") (newline)
(display "VCG payment: $")
(display (vcg-payment bids 0)) (newline)
(display "Surplus: $")
(display (- 10 (vcg-payment bids 0)))
; For a single item, VCG reduces to second-price (Vickrey)

Three properties

Truthful: bidding your true value is a dominant strategy. Efficient: items go to those who value them most. Individually rational: every participant is at least as well off as not participating. These three properties make VCG the theoretical backbone of embedding-space ad auctions, where truthfulness matters because advertisers bid continuously without room to iterate.

Notation reference

Paper	Scheme	Meaning
W(N \ i)	welfare-others-without	Social welfare without bidder i
W_(-i)(N)	welfare-others-with	Others' welfare with bidder i present
p_i = W(N\i) - W_(-i)(N)	(vcg-payment bids i)	VCG payment = externality

Neighbors

💰 Economics — econ-20: mechanism design
💎 Vickrey 1961 — VCG reduces to second-price for single items
💎 Lahaie & Lubin 2025 — VCG as a linear program
💎 Vickrey 1961 — the second-price auction is the single-item special case of VCG
💰 Economics Ch.20 — mechanism design: VCG as the canonical incentive-compatible mechanism
💎 Lahaie & Lubin 2025 — VCG as a linear program

Ready for the real thing? Read Clarke 1971 and Groves 1973.

← Vickrey 1961 · 1 of 8 by june.kim GSP 2007 · 3 of 8 →