Ranked-slot auction (GSP and VCG)

Deep dive

How it works

Parts:

• Scorer — s_i = b_i · q_i per candidate (b = bid per action, q = predicted action probability, from a CTR model); drops s_i < ρ (reserve)
• Selector — keeps the top k+1 scores (top-k selection); the (k+1)-th only sets a price
• Pricer — GSP price per action for rank j: max(s_{j+1}, ρ) / q_j
• Reference — VCG payment per impression: Σ_{t=j..k} (α_t − α_{t+1}) · max(s_{t+1}, ρ), with α_{k+1} = 0

Position factors α_1 ≥ … ≥ α_k (click probability α_j · q_i) are known to the platform.

1. Score every candidate; discard q ≤ 0 and s < ρ.
2. Select the top k+1 by score (fixed tie rule, e.g. id) and sort them.
3. Rank j gets position j.
4. Price per action p_j = max(s_{j+1}, ρ) / q_j (s = 0 if no next candidate): the minimum bid that keeps rank j.
5. Expected payment per impression = α_j · q_j · p_j = α_j · max(s_{j+1}, ρ).
6. VCG: the externality of removing j (everyone below moves up one slot); ρ is the seller's own score on an empty slot.
7. GSP − VCG = Σ_{t=j..k} (α_t − α_{t+1})(s_{j+1} − s_{t+1}) ≥ 0, since scores are sorted.

 b·q scores        reserve ρ      sorted top k+1       slot (α)        price per action
 A 2.0·.50 = 1.0 ─┐              D 8.0·.75 = 6.0 ──── 1 (α1) ── s(B)/q(D) = 4.0/.75
 B 4.0·1.0 = 4.0 ─┼─ s ≥ ρ ─►    B              4.0 ── 2 (α2) ── s(C)/q(B) = 1.5
 C 3.0·.50 = 1.5 ─┤              C              1.5 ── 3 (α3) ── s(A)/q(C) = 1.0/.5
 D 8.0·.75 = 6.0 ─┘              A              1.0    (k+1-th: only prices slot 3; k = 3)

Truthfulness. VCG: bidding your value is dominant. GSP: not. Toy case, q = 1, α = (200, 100), values (10, 6, 1): the top bidder pays 6 in slot 1, utility 200·4 = 800; bidding 5 gets slot 2 at price 1, utility 100·9 = 900. So bidders shade. EOS show GSP still has a pure equilibrium with VCG's allocation and payments: s_j = (1 − α_j/α_{j−1}) · w_j + (α_j/α_{j−1}) · s_{j+1}, w = q·value. I checked this recursion on one instance (4 slots, 5 bidders): GSP payments equalled VCG.

Code

#[derive(Clone, Copy)]
pub struct Bidder { pub id: u32, pub bid: f64, pub quality: f64 }
pub struct Slot { pub id: u32, pub price: f64, pub gsp: f64, pub vcg: f64 } // per click, per impression x2

/// alpha: non-increasing position factors (len k); reserve: floor on bid*quality.
pub fn run_auction(bidders: &[Bidder], alpha: &[f64], reserve: f64) -> Vec<Slot> {
    let k = alpha.len();
    let mut c: Vec<(f64, Bidder)> = bidders.iter()
        .filter(|b| b.quality > 0.0 && b.bid * b.quality >= reserve) // prune before ranking
        .map(|b| (b.bid * b.quality, *b)).collect();
    let by_score = |a: &(f64, Bidder), b: &(f64, Bidder)| b.0.total_cmp(&a.0).then(a.1.id.cmp(&b.1.id));
    let m = (k + 1).min(c.len());
    if m == 0 { return Vec::new(); }
    if c.len() > m { c.select_nth_unstable_by(m - 1, by_score); c.truncate(m); } // top k+1 only
    c.sort_unstable_by(by_score);

    let a = |t: usize| alpha.get(t).copied().unwrap_or(0.0);           // alpha[k] = 0
    let next = |t: usize| c.get(t).map_or(0.0, |x| x.0).max(reserve);   // score of rank t, floored
    let mut vcg = vec![0.0; k + 1];
    for j in (0..k).rev() { vcg[j] = (a(j) - a(j + 1)) * next(j + 1) + vcg[j + 1]; } // externalities
    (0..k.min(c.len())).map(|j| {
        let b = c[j].1;
        let price = next(j + 1) / b.quality;                            // min bid that keeps rank j
        Slot { id: b.id, price, gsp: a(j) * b.quality * price, vcg: vcg[j] }
    }).collect()
}

fn main() {
    let bd = |id, bid| Bidder { id, bid, quality: 1.0 };
    let v = [bd(1, 10.0), bd(2, 6.0), bd(3, 1.0)];
    let r = run_auction(&v, &[200.0, 100.0], 0.0);
    assert_eq!((r[0].gsp, r[0].vcg, r[1].gsp, r[1].vcg), (1200.0, 700.0, 100.0, 100.0));
    let one = run_auction(&v, &[0.5], 0.0);                 // one slot: GSP == VCG == second price
    assert_eq!((one[0].gsp, one[0].vcg, one[0].price), (3.0, 3.0, 6.0));
    let shade = run_auction(&[bd(1, 5.0), bd(2, 6.0), bd(3, 1.0)], &[200.0, 100.0], 0.0);
    assert_eq!((shade[1].id, shade[1].gsp), (1, 100.0));    // shading wins slot 2 at 100 < 1200
    let res = run_auction(&v, &[200.0, 100.0], 2.0);        // reserve: bidder 3 is out, slot 2 pays rho
    assert!(res.iter().all(|s| s.price >= 2.0 && s.price <= 10.0)); // reserve respected, price <= bid
    assert!(res.iter().all(|s| s.gsp >= s.vcg));
    let raised = run_auction(&[bd(1, 20.0), bd(2, 6.0), bd(3, 1.0)], &[200.0, 100.0], 0.0);
    assert_eq!(raised[0].gsp, r[0].gsp);                    // price independent of own bid
}

A 20,000-case randomized run of the same properties (also total VCG ≤ total GSP, k = 1 equality) passed.

Complexity and constants

• Select + sort of k+1: O(n + k log k); one pass reads each candidate (16 B).
• Measured, Apple M4 Pro, one thread, f64, release build, candidate-vector allocation included: n = 1000, k = 4-10: 3.7-4.0 µs (full sort 13 µs); n = 100: 0.6 µs (1.1 µs); n = 10: 0.17 µs (no gain).
• Cost drivers: the candidate copy, branches in selection, and the model scoring before the auction, which usually dominates.

Efficiency

• Cost: one auction on an Apple M4 Pro, n = 1000, k = 10: 3.7 µs measured (about 4 ns per candidate); n = 100: 0.64 µs. Bound: reading candidate records and branch misses in selection, not arithmetic; the CTR model costs more.
• Levers:
  • top-k selection instead of a full sort — 3.3-3.5x at n = 1000, 1.8-1.9x at n = 100 (measured) — n ≫ k
  • prune by reserve before ranking — fewer candidates reach the select (not measured) — many low bids, high reserve
  • precompute quality, flat arrays of bids and qualities — no per-auction model call — repeated candidate sets
  • batch auctions, SIMD the score product, reuse the candidate buffer — no allocation or scalar loop per auction (order of) — high QPS
• Naive → standard → state of the art:
  • sort all, recompute quality per auction · O(n log n) plus a model call each
  • cached quality, filter, select k+1 · O(n + k log k), about 4 µs at n = 1000
  • SIMD over struct-of-arrays, pre-filter, buffer reuse, batching · bandwidth-bound (order of, not measured)

Implementation notes

• Price from the sorted top k+1, never from raw bids; a fixed tie rule (id) makes replays match.
• Charge in minor units, rounded up, so the price is never below s_{j+1}/q_j.
• A score floor ρ is the clean case; a per-action floor r is a per-bidder score floor r·q_i.
• Quality squashing: rank by b · q^s, s from 0 (by bid only) to 1; the price is b_{j+1} q_{j+1}^s / q_j^s (rule family: Lahaie and Pennock 2007).

Pitfalls

• Quality that is not a calibrated probability makes ranks and prices wrong (calibration).
• Expecting truthful bids: GSP bidders shade; proxy bidding tools automate that.
• Budgets run out mid-day and change who is in the top k (budget pacing).
• A reserve that is too high leaves slots empty; Ostrovsky and Schwarz ran a field experiment on reserves in sponsored search.
• Float ties rank differently across machines: use total_cmp and a tie key.

Variants and alternatives

In production

Search engines use quality-weighted GSP (the setting of EOS and Varian). Shops, app stores and job boards commonly rank promoted listings by bid times predicted action rate. Display exchanges using OpenRTB name the auction type per request; Prebid header bidding clears first-price.

Implementations

Sources

• Benjamin Edelman, Michael Ostrovsky, Michael Schwarz, Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords, American Economic Review 97(1), 2007. paper
• Hal R. Varian, Position auctions, International Journal of Industrial Organization 25(6), 2007. paper
• William Vickrey, Counterspeculation, Auctions, and Competitive Sealed Tenders, Journal of Finance 16(1), 1961. paper
• Edward H. Clarke, Multipart pricing of public goods, Public Choice 11, 1971. paper
• Theodore Groves, Incentives in Teams, Econometrica 41(4), 1973. paper
• Roger B. Myerson, Optimal Auction Design, Mathematics of Operations Research 6(1), 1981. paper
• Sébastien Lahaie, David M. Pennock, Revenue analysis of a family of ranking rules for keyword auctions, ACM EC 2007. paper
• Michael Ostrovsky, Michael Schwarz, Reserve Prices in Internet Advertising Auctions: A Field Experiment, Journal of Political Economy 131(12), 2023. paper
• Prebid, Bidder adaptor guide. docs · IAB Tech Lab, OpenRTB 2.6. spec