Generalized Second-Price Auction

Edelman, Ostrovsky & Schwarz · 2007 · AER 97(1)

The Generalized Second-Price auction ranks ads by bid, assigns them to slots with decreasing click rates, and charges each winner the bid of the advertiser below them. GSP is not truthful, but its equilibria are efficient. Google adopted it because it is simpler than VCG and revenue-comparable.

Ranked slots with decreasing click rates

In search advertising, higher positions get more clicks. GSP assigns the highest bidder to position 1, second-highest to position 2, and so on. Each advertiser pays the bid of the one below them (per click). The entire model assumes keywords as discrete units; once you move to continuous embedding spaces, the slot metaphor breaks down.

Scheme

; Generalized Second-Price auction
; Each advertiser pays the bid of the one below them

(define (gsp-auction bids click-rates)
  ;; Sort bids descending, assign to slots
  (let* ((sorted (sort bids >))
         (n (length sorted))
         (payments
           (let loop ((i 0) (result '()))
             (if (>= i (min n (length click-rates)))
                 (reverse result)
                 (let ((pay (if (< (+ i 1) n)
                               (list-ref sorted (+ i 1))
                               0)))
                   (loop (+ i 1) (cons pay result)))))))
    (list sorted payments click-rates)))

(define result (gsp-auction '(10 8 2) '(100 60 20)))
(display "Bids (ranked):    ") (display (car result)) (newline)
(display "Payments per click: ") (display (cadr result)) (newline)
(display "Click rates:      ") (display (caddr result)) (newline)

; Total revenue
(define (dot a b)
  (if (null? a) 0
      (+ (* (car a) (car b)) (dot (cdr a) (cdr b)))))

(display "Total revenue: $")
(display (dot (cadr result) (caddr result)))
; $8*100 + $2*60 + $0*20 = $920

; Generalized Second-Price auction
; Each advertiser pays the bid of the one below them

(define (gsp-auction bids click-rates)
  ;; Sort bids descending, assign to slots
  (let* ((sorted (sort bids >))
         (n (length sorted))
         (payments
           (let loop ((i 0) (result '()))
             (if (>= i (min n (length click-rates)))
                 (reverse result)
                 (let ((pay (if (< (+ i 1) n)
                               (list-ref sorted (+ i 1))
                               0)))
                   (loop (+ i 1) (cons pay result)))))))
    (list sorted payments click-rates)))

(define result (gsp-auction '(10 8 2) '(100 60 20)))
(display "Bids (ranked):    ") (display (car result)) (newline)
(display "Payments per click: ") (display (cadr result)) (newline)
(display "Click rates:      ") (display (caddr result)) (newline)

; Total revenue
(define (dot a b)
  (if (null? a) 0
      (+ (* (car a) (car b)) (dot (cdr a) (cdr b)))))

(display "Total revenue: $")
(display (dot (cadr result) (caddr result)))
; $8*100 + $2*60 + $0*20 = $920

Not truthful, but stable

Unlike 💎 VCG, bidders in GSP can sometimes benefit by bidding below their true value to get a cheaper slot. The paper shows that GSP has a locally envy-free equilibrium equivalent to the VCG outcome. Advertisers shade their bids just enough that no one envies an adjacent slot. The shading problem disappears in space-based auctions, where advertisers buy continuous regions rather than ranked positions.

Notation reference

Paper	Scheme	Meaning
alpha_k	click-rates	Click-through rate for slot k
p_k = b_(k+1)	(list-ref sorted (+ i 1))	Per-click payment = next bid
LEF	locally envy-free	No one envies adjacent slot

Neighbors

june.kim/one-shot-bidding — GSP in practice
💎 Vickrey 1961 — the single-item version GSP generalizes
💎 VCG 1973 — the truthful alternative GSP approximates

Ready for the real thing? Read the paper.

← VCG 1973 · 2 of 8 by june.kim Milgrom & Weber 1982 · 4 of 8 →