vault

Why VCG Is Rare in Practice

41 min read

Why VCG Is Rare in Practice

The Vickrey–Clarke–Groves (VCG) mechanism is the closest thing mechanism design has to a universal solvent: in any environment with quasi-linear payoffs it selects the welfare-maximizing outcome, truth-telling is a dominant strategy for every participant, and — by theorems of Green–Laffont and Holmström — it is essentially the only direct mechanism with all three properties at once. And essentially nobody runs it. Writing in the MIT Press volume Combinatorial Auctions, Lawrence Ausubel and Paul Milgrom titled their chapter “The Lovely but Lonely Vickrey Auction” and opened with exactly that puzzle: “Why is the Vickrey auction design, which is so lovely in theory, so lonely in practice?” Michael Rothkopf, seventeen years after his own “Why Are Vickrey Auctions Rare?”, was blunter still: as of 2007 he believed “no one has conducted a general VCG process … in real commerce” (Rothkopf 2007). This note is the catalogue of reasons, each one worked through on an instance you can check by hand, and then the epilogue: what actually ships instead.

The companion note The VCG Mechanism develops the construction and proves the dominant-strategy theorem. This note assumes only the one-sentence version of that result — each winner pays the externality it imposes on everybody else, computed as the difference between the welfare others could have achieved without it and the welfare they actually achieve with it — and spends its length on what goes wrong.

Every numeric example below was recomputed from scratch

Each instance in this note was solved by a brute-force winner-determination routine over all (n+1)^m assignments of m items to n bidders plus “unsold”, written for this note, with all arithmetic in Python’s stdlib fractions.Fraction. No integer-programming library was used (none is linkable on this machine — glpk is absent and liblpsolve55.so ships without headers), so the winner determination is brute-forced, not solved by an ILP. That choice is not merely a limitation; §7 shows it is also the safe choice, because VCG payments are differences of two optima and IEEE-754 doubles silently corrupt them.

1. Mental Model: a theorem about incentives, not about deployment

The single most useful reframing is this. VCG’s dominant-strategy theorem constrains one bidder’s report against a fixed profile of other reports. It says nothing at all about (a) how much money the seller ends up with, (b) whether groups of bidders can profit by deviating together, (c) whether one bidder can pretend to be several, (d) whether the auctioneer can compute the allocation before the heat death of the universe, or (e) whether the bidders can even write down their valuations. Every documented failure of VCG lives in one of those five blind spots.

flowchart TB
    subgraph GUARD["What the VCG theorem actually guarantees"]
        T1["Unilateral deviation by ONE bidder<br/>against FIXED reports of others<br/>never pays"]
        T2["Given truthful reports,<br/>the chosen allocation<br/>maximizes total value"]
    end
    subgraph BLIND["What it says nothing about — every failure lives here"]
        B1["<b>Seller revenue</b><br/>can be zero with<br/>ample competition"]
        B2["<b>Coalitions</b><br/>losing bidders have<br/>profitable joint deviations"]
        B3["<b>Identity</b><br/>one firm bidding<br/>under many names"]
        B4["<b>Computation</b><br/>winner determination<br/>is NP-hard"]
        B5["<b>Elicitation</b><br/>2^m − 1 numbers<br/>per bidder"]
    end
    GUARD -.->|"proves nothing<br/>about"| BLIND
    B1 --> C["Outcome outside the CORE"]
    B2 --> C
    B3 --> C
    C --> D["<b>Substitutes condition</b><br/>Ausubel–Milgrom Thm 9 &amp; 10:<br/>all three vanish iff every bidder's<br/>goods are substitutes"]

What it shows: the dominant-strategy guarantee (top) and the five categories of practical failure (middle), plus the fact — proved by Ausubel and Milgrom — that three of the five collapse into one condition on preferences. Insight to take: VCG is not “usually fine, occasionally awkward.” Its problems are a sharp dichotomy. Where goods are substitutes for every bidder, all the revenue and manipulation pathologies provably vanish; where even a single bidder sees complements, they can all be constructed. And complements are precisely the case for which package bidding was invented, so the mechanism fails exactly where it was most wanted.

2. The zero-revenue example, computed

Ausubel and Milgrom’s opening example is three bidders and two spectrum licences, A and B.

Bidderv(A)v(B)v(AB)Character
100$2BComplements — wants the pair or nothing
2$2B$2B$2BWants exactly one licence
3$2B$2B$2BWants exactly one licence

Bidder 1 sees the two licences as pure complements: a national footprint is worth $2 billion, half a footprint is worth nothing. Bidders 2 and 3 are regional carriers, each of whom will pay $2 billion for a single licence and gains nothing from a second.

Efficient allocation: give A to bidder 2 and B to bidder 3, for total value $4 billion (versus $2 billion if bidder 1 takes both). Now compute bidder 2’s payment. The welfare others could achieve without bidder 2 is w(L−2): bidder 3 takes one licence for $2B, bidder 1 gets nothing (it needs both), so w(L−2) = 2. The welfare others actually achieve with bidder 2 present is bidder 3’s $2B. Payment = 2 − 2 = 0. By symmetry bidder 3 also pays zero.

$ python3 vcg.py
--- all three bidders present
    efficient welfare w(L) = 4
          pkg1: wins -      pays 0  utility 0
       single2: wins A      pays 0  utility 2
       single3: wins B      pays 0  utility 2
    SELLER REVENUE = 0
    NOT IN CORE. blocking coalitions:
       {'pkg1', 'SELLER'} could make 2 but the VCG outcome gives them 0

Two things are worth saying slowly. First, this is not a thin market. There are three bidders, each willing to pay $2 billion. If the government had sold the two licences as one indivisible lot, an ascending auction among three bidders each valuing it at $2 billion would have closed near $2 billion. Ausubel and Milgrom make exactly this point: “That is ample competition.” Splitting the lot in two and running the theoretically optimal mechanism takes the price from $2 billion to nothing.

Second, the reason is structural, not a knife-edge coincidence. Bidder 2’s payment is the marginal opportunity cost of the licence it takes, and because bidder 1 needs both licences, the marginal cost of denying it one licence — given that it has already been denied the other — is zero. Each of bidders 2 and 3 individually causes no harm; together they destroy $2 billion of bidder 1’s value. VCG charges each of them their individual externality, and the joint externality is nobody’s bill.

flowchart LR
    subgraph WITH["With both regionals present"]
        A1["A → bidder 2 (2)"]
        B1["B → bidder 3 (2)"]
        P1["bidder 1: nothing (0)"]
    end
    subgraph W2["Counterfactual: remove bidder 2"]
        A2["A → bidder 3 (2)"]
        B2["B: unsold — bidder 1<br/>needs BOTH, so it<br/>still gets nothing"]
    end
    WITH -->|"w(L) = 4"| CALC
    W2 -->|"w(L−2) = 2"| CALC
    CALC["p₂ = w(L−2) − [w(L) − v₂]<br/>= 2 − (4 − 2)<br/>= <b>0</b>"]
    CALC --> R["Symmetric for bidder 3.<br/><b>Total revenue $0</b>"]

What it shows: the two optimization problems whose difference is bidder 2’s VCG payment. Insight: the counterfactual world “without bidder 2” is barely worse than the real one, because bidder 1’s complementary valuation means the freed-up licence has no taker who values it on its own. A bidder’s VCG price is low precisely when its absence would not have helped anyone else — and complements manufacture that condition.

Making it worse on purpose

Nothing stops the construction from being pushed arbitrarily far. Replace the two regionals with k regionals and k licences, one bidder wanting all k as a package. Every regional’s departure frees a licence that no remaining bidder wants alone, so every regional pays zero regardless of k, and the seller’s revenue is zero no matter how many billion-dollar bidders show up. Revenue does not merely fail to grow with competition; it is identically zero for all levels of competition.

3. The outcome need not be in the core

“Low revenue” is a vague complaint until you fix a benchmark. Ausubel and Milgrom adopt the core, and justify it as a competitive standard rather than a normative one: if two or more risk-neutral brokers competed to buy the services of all the auction participants, the competitive-equilibrium price vectors of that economy are exactly the core payoff vectors. Zero-profit for brokers matches feasibility; no-profitable-deviation matches unblockedness.

Formally, players are L = {0, 1, …} with player 0 the seller. The coalitional value function is

w(S) = max over feasible allocations of Σ_{l∈S} v_l(x_l)   if the seller 0 ∈ S
w(S) = 0                                                    if 0 ∉ S

— a coalition can only create value if it contains the party that owns the goods. The core is the set of payoff vectors π that are feasible for the grand coalition (Σ π_l = w(L)) and unblocked: w(S) ≤ Σ_{l∈S} π_l for every coalition S. A payoff vector is blocked by S if S could go off and do better by itself than the mechanism gives it.

In the zero-revenue example, the coalition {seller, bidder 1} can generate $2 billion on its own. The VCG outcome gives that coalition $0 (the seller gets no revenue, bidder 1 wins nothing). So w({0,1}) = 2 > 0 = π_0 + π_1, and the coalition blocks. The core-check routine finds it automatically, printed above.

The practical translation is Day and Milgrom’s, and it is the sentence that should be tattooed on any auction designer: any failure to select a core allocation “implies that there is a group of bidders who have offered to pay more in total than the winning bidders, yet whose offer has been rejected. Imagine trying to explain such an outcome to the actual seller or, in a government sponsored auction, to a skeptical public!” (Day & Milgrom 2008). Rothkopf puts the same objection in the bidder’s voice: bidder 1 “can go to the bid taker and truthfully say, ‘Ignore those bidders. I will give you $1 for {a, b, c}, and we will both be better off.’”

Ausubel and Milgrom’s Theorem 4 pins down the relationship exactly: a bidder’s Vickrey payoff is its highest payoff over all points in the core. Consequently (their Theorem 5) if the Vickrey payoff vector lies in the core at all, it is the bidder-dominant point — unanimously the bidders’ favourite core outcome — and if it does not lie in the core, then “the seller’s Vickrey payoff is strictly less than the smallest of the seller’s core payoffs.” VCG is never merely near the competitive benchmark from below; it is either the most bidder-friendly point of the benchmark set, or strictly outside it.

flowchart TB
    C["<b>The core</b><br/>payoff vectors no coalition can block"]
    V1["Vickrey payoff π̄<br/>INSIDE the core"]
    V2["Vickrey payoff π̄<br/>OUTSIDE the core"]
    C --> V1
    C --> V2
    V1 --> R1["It is the unique <b>bidder-dominant</b> point:<br/>every bidder's favourite core outcome.<br/>Seller gets the LOWEST competitive price."]
    V2 --> R2["No bidder-dominant point exists.<br/>Seller revenue is strictly BELOW<br/>every competitive price.<br/>A losing coalition would pay more."]
    R1 --> S["Ausubel–Milgrom Thm 6/8/9:<br/>π̄ ∈ core for every participation subset<br/>⟺ w is bidder-submodular<br/>⟸ goods are substitutes for all bidders"]
    R2 --> S

What it shows: the two-case structure of Theorems 4 and 5. Insight: “VCG revenue is a bit low” is the wrong mental model. Either it sits at the bidder-optimal corner of the competitive range — already the worst competitive outcome for the seller — or it falls off the range entirely, at which point the auction is producing an allocation a coalition of losers would have outbid.

The unifying condition, and a measurement

Ausubel and Milgrom’s Theorems 6 through 10 reduce all of the revenue and manipulation pathologies to one condition. Goods are substitutes for a bidder if the demand for each good is non-decreasing in the prices of the others (equivalently — their Theorem 7 — if the bidder’s indirect utility function u(p) = max_z {v(z) − p·z} is submodular). Their Theorem 8 shows substitutes for every bidder implies the coalitional value function w is bidder-submodular, w(S ∪ {l}) − w(S) ≥ w(S′ ∪ {l}) − w(S′) for S ⊆ S′; their Theorem 6 shows bidder-submodularity is equivalent to the restricted Vickrey payoff lying in the core for every subset of participating bidders. Their Theorem 9 closes the loop: if the admissible value set contains all additive valuations and there are at least four possible bidders, then “VCG payoffs are robustly in the core” holds if and only if all admissible valuations are substitutes valuations.

I measured how often this bites on random small instances: 1,500 random two-item, three-bidder instances with integer values in [0, 20], drawn twice — once forcing every bidder subadditive (v(AB) ≤ v(A)+v(B), the substitutes case for two goods), once letting one bidder be strictly superadditive.

== (3) Random 2-item / 3-bidder instances: VCG outcome in the core?
   ALL bidders substitutes (v(AB) <= v(A)+v(B))
      outside the core: 0/1500  (0.0%)   mean VCG revenue 17.07
   at least one COMPLEMENTS bidder allowed
      outside the core: 207/1500  (13.8%)   mean VCG revenue 21.81

Zero out of 1,500 under substitutes — the theorem, seen empirically. 13.8% once a single bidder is allowed complements. The higher mean revenue in the second row is not a contradiction: superadditive draws produce higher total values, so the level rises even as the competitive shortfall appears. The comparison that matters is the first column.

Uncertain

Verify: that the 13.8% figure generalizes beyond m = 2, n = 3 with uniform integer values. Reason: it is a property of my sampling distribution, not a theorem — Ausubel–Milgrom prove existence of bad profiles under complements, never a frequency. To resolve: sweep m, n, and the value-generating distribution; the number should be read as “common, not exotic,” not as a rate. uncertain

4. Revenue non-monotonicity, and the disqualification problem

Delete bidder 3 from the zero-revenue instance and re-solve:

Drop bidder single3 entirely (revenue MONOTONICITY test):
--- two bidders
    efficient welfare w(L) = 2
          pkg1: wins AB     pays 2  utility 0
       single2: wins -      pays 0  utility 0
    SELLER REVENUE = 2
    outcome IS in the core

Revenue rises from $0 to $2 billion when a bidder with a $2 billion valuation is removed from the auction. Roughgarden’s lecture notes give an even starker unit-scaled version, which I also recomputed: v₁(AB) = 1, v₂(A) = 1 gives revenue 1; adding v₃(B) = 1 doubles the maximum welfare from 1 to 2 while driving revenue to 0 (CS364A Lecture 7).

Ausubel and Milgrom define bidder monotonicity as the property that adding a bidder weakly reduces incumbents’ equilibrium profits and weakly raises the seller’s revenue. It is the familiar, taken-for-granted property of single-item auctions. Their Theorem 10 makes it another face of the same coin: bidder monotonicity, unprofitability of shills, and unprofitability of loser collusion are all three equivalent to the substitutes condition (given at least three or four bidders, depending on the implication).

Day and Milgrom name the operational consequence the disqualification problem. Real auctions do not finalize instantly; in the US radio spectrum auctions bidders file a “short form” before bidding and a “long form” afterwards that is checked in detail. A seller who can disqualify a bidder after the bids arrive, under a mechanism whose revenue is non-monotone, is a seller with a live financial incentive to find a disqualifying technicality. That is a governance hazard that has nothing to do with any bidder misbehaving.

5. Collusion by losing bidders

Take the same three bidders, but suppose the regionals are genuinely weak: bidders 2 and 3 each value a single licence at $0.5 billion.

--- truthful reports
    efficient welfare w(L) = 2
          pkg1: wins AB     pays 1  utility 1
       single2: wins -      pays 0  utility 0
       single3: wins -      pays 0  utility 0
    SELLER REVENUE = 1
    outcome IS in the core

Truthfully, bidder 1 wins the pair for $1 billion and the regionals get nothing. Now let the two regionals agree — before the auction, in a smoke-filled room — to each report $2 billion for a single licence. The reports are now exactly the reports of §2, and the computed outcome is exactly the outcome of §2:

    under the JOINT LIE (both report 2 for a single licence):
      single2: wins A pays 0 -> TRUE utility 1/2 (was 0 truthfully)
      single3: wins B pays 0 -> TRUE utility 1/2 (was 0 truthfully)

Each collusive bidder goes from a payoff of 0 to a payoff of $0.5 billion, and the seller goes from $1 billion to nothing.

This deserves emphasis because it inverts the usual intuition about collusion. In a standard first-price sealed-bid auction, a losing bidder is irrelevant — it can shade or inflate its bid without changing anything except its own risk of an unwanted win. In VCG, losing bids set winners’ prices, so the losers are exactly the participants with leverage and nothing to lose. And the cartel is self-enforcing in the way that matters: neither regional is tempted to defect by bidding higher, because each is already winning at a price of zero.

Rothkopf makes the complementary point about single-item Vickrey auctions: a conspiracy in which the high-value bidder bribes the other to stay out is stable under second-price and English rules but unstable under first-price or Dutch rules, because in a sealed first-price auction the designated loser can simply submit a bid one dollar above the designated winner’s $10 and take the item. There is no way to enforce the illegal agreement. Second-price rules remove that self-policing.

6. Shill bidding pays

Now collapse the two regionals into one firm. Suppose a single company values a licence at $0.5 billion and the pair at $1.0 billion. Honestly reported, it loses:

--- combined bidder reports honestly
    efficient welfare w(L) = 2
      combined: wins -      pays 0  utility 0
          pkg1: wins AB     pays 1  utility 1
    SELLER REVENUE = 1

But if the auctioneer cannot police identities, the firm registers two shell subsidiaries, “bidder 2” and “bidder 3,” each bidding $2 billion for one licence. The computation is again identical to §2: both shells win, both pay zero, and the firm walks away with both licences at a total price of zero against a true value of $1 billion — a profit of $1 billion where honest participation earned nothing.

This is Sakurai, Yokoo and Matsubara’s false-name bidding, and it is a genuinely new failure class rather than a restatement of collusion: there is no coalition to hold together and no agreement to enforce, because it is one agent all along. Rothkopf’s own version uses three items and two bidders: bidder 1 values {a,b,c} at $2, bidder 2 values {a,b,c} at $3, neither values any smaller bundle. Honestly, bidder 2 wins all three and pays $2. Splitting into 2a/2b/2c bidding $1 each for one item apiece, all three win and none makes any net payment — each pays $1 and receives a $1 Vickrey discount.

Note that the internet-anonymity framing undersells the problem. Day and Milgrom point out that in the US spectrum auctions “several of the largest corporate bidders (including AT&T, Cingular, T-Mobile, Sprint, and Leap Wireless) have at times had contracts with or financial interests in multiple bidding entities in the same auction.” A mechanism whose correctness depends on the auctioneer having “complete control of the identities and contractual arrangements between all of the bidders” (Rothkopf’s phrasing) is depending on something regulators demonstrably do not have.

flowchart TB
    subgraph HON["Honest participation"]
        H1["Firm reports<br/>v(A)=v(B)=0.5, v(AB)=1.0"]
        H2["Loses. Payoff 0.<br/>Seller collects 1."]
        H1 --> H2
    end
    subgraph SHILL["Two registered shells"]
        S1["'bidder 2' reports v(A)=2<br/>'bidder 3' reports v(B)=2"]
        S2["Both 'win'. Each pays 0.<br/>Firm holds A and B.<br/>Payoff 1. Seller collects 0."]
        S1 --> S2
    end
    HON -->|"same firm,<br/>same true values"| SHILL
    S2 --> WHY["<b>Why it works:</b> splitting one bidder into k<br/>splits ONE externality into k marginal<br/>externalities, each of which is smaller —<br/>and under complements, each is zero."]

What it shows: the same firm’s two options and their payoffs. Insight: shill bidding is not a bug in the payment formula, it is the payment formula. VCG charges marginal externalities; marginal externalities are subadditive across a split when the residual bidders see complements; therefore splitting yourself is a discount. Ausubel and Milgrom’s proof of (1)⇒(3) in Theorem 10 is exactly a telescoping-sum argument showing that this discount vanishes when the residual coalition’s value function is submodular.

7. The computation: NP-hard, and numerically treacherous

Winner determination

VCG for a combinatorial auction requires solving n + 1 welfare-maximization problems: one with everybody, and one with each bidder deleted. Each is the winner determination problem, and it is NP-hard even in the simplest interesting case.

Nisan’s chapter in the Algorithmic Game Theory book gives the reduction (Nisan et al. 2007, Ch. 11). Restrict to single-minded bidders — bidder i wants one specific bundle S*ᵢ and will pay v*ᵢ for it or any superset, and zero otherwise. Winner determination becomes: choose a set W of bidders with pairwise-disjoint bundles maximizing Σ_{i∈W} v*ᵢ. Given an INDEPENDENT-SET instance (G = (V,E), k), make the edges the items and put one bidder per vertex, whose desired bundle is that vertex’s incident edges, with value 1. Two bidders’ bundles are disjoint exactly when the corresponding vertices are non-adjacent, so a feasible winner set is an independent set and the welfare is its size. Independent set of size ≥ k exists iff optimal welfare ≥ k.

The reduction is approximation-preserving, which is the sharper point. Independent set is NP-hard to approximate within n^{1−ε}, and since m ≤ n² in the construction, Proposition 11.6 states: approximating the optimal allocation among single-minded bidders to within a factor better than m^{1/2−ε} is NP-hard. On 100 items no polynomial algorithm can be guaranteed within a factor of 10 of optimal. And an approximate winner-determination rule does not preserve truthfulness in general — Rothkopf’s flat statement is that approximate solution “will destroy the incentive for truth-revealing strategies that is a key purpose of the VCG process.” (The escape hatch, developed in Approximate and Simple Mechanisms, is to design the approximation to be monotone and charge critical values, which buys back dominant-strategy truthfulness at the cost of exact efficiency.)

I measured the brute-force cost directly, since that is what an implementation without an ILP library actually pays:

== (1) Brute-force winner determination: (n+1)^m allocations enumerated
   m items   n bidders   allocations     seconds   allocs/sec
         2           4            25      0.0001        218,616
         3           4           125      0.0004        294,393
         4           4           625      0.0031        203,849
         5           4         3,125      0.0146        214,173
         6           4        15,625      0.0898        173,986
         7           4        78,125      0.5535        141,152
         8           4       390,625      3.1738        123,077

Throughput is roughly flat at ~10⁵ allocations/second (CPython, exact Fraction arithmetic), so the wall clock is 5^m / 10^5 seconds for four bidders. Eight items: 3 seconds. Twelve items: 5^12 = 244M ≈ 33 minutes. Fifteen items: 5^15 = 30.5 billion ≈ 69 hours — for one of the n+1 optimizations. The FCC’s 1994–2015 spectrum auctions offered hundreds to thousands of licences. Brute force is not a slow path here; it is not a path.

Uncertain

Verify: the extrapolation past m = 8. Reason: it assumes constant throughput, but memory pressure and Fraction denominator growth are not modelled, and I stopped measuring at 8 items to keep the run under a couple of minutes. To resolve: measure m = 10, 12 directly with a background run. The order of magnitude is not in doubt — the exponent is m — but treat “69 hours” as an estimate. uncertain

The numerical trap nobody warns you about

A VCG payment is α_i − (W − v_i(x*_i)): the difference of two independently computed optima. When those optima are equal — which happens constantly, because the marginal externality of a bidder is often exactly zero — the difference is exactly zero in exact arithmetic and is a small non-zero float otherwise. I measured this on 3,000 random three-item, three-bidder instances with values drawn as k/d for d ∈ {3, 6, 7, 9} (deliberately non-dyadic, so they are not exactly representable), solving each instance twice: once in Fraction, once in float.

instances                                : 3000
instances where float picked a DIFFERENT allocation: 2  (0.07%)
payments computed                        : 9000
exactly zero under Fraction              : 4374  (48.6%)
  -> non-zero in double, SAME allocation : 682  (15.59% of zeros)  [pure rounding]
       of which NEGATIVE                 : 347
       largest magnitude                 : 3.553e-15
  -> non-zero in double, DIFFERENT alloc : 2  (0.05% of zeros)  [wrong winner]

Three findings, in increasing order of nastiness.

  1. Almost half of all VCG payments in these instances are exactly zero. That is not an artifact; it is the mechanism’s character. Bidders whose presence does not change what the others could have done pay nothing.
  2. 15.6% of those exact zeros come out non-zero in doubles, and 347 of them come out negative — a payment of −1.8 × 10⁻¹⁵ means a naive implementation is paying the bidder rather than charging them, which will trip an assertion (p_i ≥ 0 is a theorem), silently underflow into a ledger, or — worse — pass silently. Magnitudes are around 10⁻¹⁵, i.e. pure last-bit cancellation of the kind you get subtracting two sums of ~10 terms of magnitude ~10.
  3. In 2 of 3,000 instances the float run selected a different allocation entirely. Winner determination is an argmax over a set with ties; float comparisons break those ties differently from exact comparisons, and once the allocation differs, the payments differ by O(1), not by 10⁻¹⁵. This is the failure that no epsilon-tolerance will catch, because the answer is not slightly wrong, it is a different answer.

The engineering rule follows: compute VCG payments in exact rational arithmetic, or in scaled integers, and never in floating point. If your values are currency they are already integers in the smallest unit; keep them that way through the optimization. fractions.Fraction cost this note roughly a 20× slowdown relative to floats and eliminated the entire failure class.

Failure Modes and Gotchas

Beyond the five headline pathologies, the literature records a long tail. Rothkopf’s paper is organized as thirteen of them, and his answer to “which matters most” is worth quoting because it is the correct methodological stance: “it is as difficult to answer this question as it would be to say which of 13 bullets that hit a shooting victim contributed most to his demise.”

Weak equilibria, and the bidders who do not bother to bid. Truth-telling in a second-price auction is weakly dominant, not strictly. Rothkopf’s example: bidder 1 draws from U[0,10], bidder 2 from U[5,10]. Bidding truthfully is a weakly dominant equilibrium — but bidder 1 loses nothing by not bidding at all whenever its value is below 5, since it cannot win. Under truthful bidding the seller’s expected revenue is 55/12 ≈ 4.583; under the equivalent “don’t bother” strategy it is 10/3 ≈ 3.333. The seller loses 1.25 to a change of strategy that costs the bidder nothing. Add any infinitesimal cost ε of submitting a bid and not-bidding becomes strictly better, so the revenue loss is not a knife-edge. In VCG, losing bids set winners’ prices, so a mechanism that gives losers no reason to participate carefully has a revenue problem by construction.

Deliberative agents. Larson and Sandholm’s model has bidders spending costly effort to learn their own values, with better estimates costing more. Rothkopf’s summary: in this model “there are no reasonable dominant strategy equilibria, including in Vickrey auctions.” How hard you should work to learn your own value depends on how hard your rivals are working — so the dominant-strategy property does not survive contact with the fact that valuations must be discovered rather than possessed.

Budget constraints destroy the dominant strategy. VCG assumes quasi-linear payoffs with no budget limit. Ausubel and Milgrom’s worked example: every bidder has a $1.2B budget. Bidder A values one licence at $1B, the pair at $2B; bidder B values a licence at $800M; bidder C values a licence at either $1.1B or $0 depending on an outside option. A’s payment would be $800M either way, comfortably inside its budget — yet if the budget caps its bids at $1.2B, A has no dominant strategy: it must bid under $400M for a single licence if C bids zero (to win both), and over $800M if C bids $1.1B (to win one). The best bid depends on C’s bid. Borgs et al. (2005) proved the general version. Note carefully that the budget never binds on the price paid; it binds on the bid, and that alone is enough.

Information revelation, and the negotiation you have afterwards. A first-price bid is an offer; a Vickrey bid is a sworn statement of value. Rothkopf’s scenario: you win a construction procurement at your true cost of $100M against a next-best bid of $150M, so your $50M surplus is now public. You then have to negotiate with licensing boards, banks, subcontractors and unions, all of whom now know you have $50M you do not need. Rothkopf, Teisberg and Kahn showed that if third parties capture a fraction of the revealed gain, bidders shade their bids upward by exactly that captured amount in expectation. There is also the political version: a large visible gap between the winning bid and the price paid is, as Day and Milgrom put it, “proof of the sale’s lack of competitiveness,” and McMillan (1994) records that in New Zealand “heads rolled” when second-price rules produced highest bids orders of magnitude above revenue.

Cheating by the auctioneer. In a second-price auction the seller sets the price using a number only the seller sees. Insert a fake bid of $14 between a high bid of $15 and a second bid of $10 and the seller gains $4 with no visible trace. Rothkopf notes that a trusted third party is not a complete cure, since a seller who can approximately anticipate the top two bids can procure an insincere bid from an ally instead; Lucking-Reiley (2000) documents an actual instance. This vulnerability is specific to auction formats where a non-winning number determines the price.

Sequences of strategy-proof auctions are not strategy-proof. Juda and Parkes’ example: concrete mixer Alice values one ton of sand before Wednesday at $1,000. Bob runs a Vickrey auction Monday and another Tuesday. Alice has no dominant strategy Monday, because her value in Monday’s auction depends on her forecast of Tuesday’s competition. Since economically important auctions are rarely isolated, the headline benefit — “you need not think about your rivals” — is often unavailable in practice even when each individual auction is textbook-correct.

Prices that look unfair. Two identical items; bidder 1 bids 12 for one and 13 for both; bidder 2 bids 12 for one and 20 for both. I recomputed the outcome:

--- bidder1 bids 12/13, bidder2 bids 12/20
            b1: wins A      pays 8  utility 4
            b2: wins B      pays 1  utility 11
    SELLER REVENUE = 9

Each wins one identical item, each bid 12 for the item it won, and they pay 8 and 1. Nothing is wrong; the opportunity costs genuinely differ because the bidders’ package values differ. But it is close to unexplainable to a participant, and unexplainable prices are a real deployment obstacle rather than an aesthetic one.

Common values evaporate the theorem. Everything above assumes private values — your payoff depends on your own estimate and not on others’. Ausubel and Milgrom note that outside private values VCG “immediately loses the dominant-strategy property”; in Milgrom’s common-value model and Klemperer’s almost-common-value model, second-price revenues can be near zero for an entirely different reason, driven by the extreme sensitivity of second-price equilibria to the winner’s curse. See The Winner’s Curse.

It distorts pre-auction decisions. Even with everyone playing dominant strategies and no manipulation at all, Ausubel and Milgrom show VCG can block value-creating mergers. In the zero-revenue example, unmerged bidders 2 and 3 pay zero and earn $4B. Merging raises the combined bidder’s payment from $0 to $2B, so the merger is privately profitable only if it creates more than $2B of new value — even though any positive synergy is socially good. The mechanism gets bidding incentives right and investment incentives wrong.

The counter-case, in fairness. Rothkopf’s paper drew a published rebuttal. Paul Healy’s comment in the same Operations Research forum argues several of the thirteen are not specific to VCG — many auction formats share the budget, sequencing and collusion problems — and that the comparison should be VCG against realistic alternatives rather than VCG against perfection. That is a fair methodological point and it is why §“Alternatives” below is framed as a comparison rather than a dismissal. It does not rescue the revenue and core failures, which are specific to VCG, but it should temper the conclusion from “VCG is bad” to “VCG’s specific advantages are usually not worth its specific costs.”

Alternatives and When to Choose Them

If VCG is out, something has to allocate the goods. Four families ship.

Simultaneous ascending auctions (SMRA)

The workhorse of spectrum policy since 1994. Conceptually, one English auction per licence, all running in parallel in the same room, with an activity rule forcing bidders to participate from the start (roughly: the number of items you bid on may only decrease as prices rise). The first round with no new bids ends everything.

The reason it beats the obvious alternatives is price discovery: a bidder learns the likely selling prices as the auction runs and can course-correct, abandoning contested licences and assembling a different package. Roughgarden’s Lecture 8 documents both alternatives failing in the field:

  • Sequential auctions. Switzerland, March 2000, sold three spectrum blocks in sequence. Two identical 28 MHz blocks went for 121M and 134M Swiss francs — already more dispersion than identical goods should show — and then a larger 56 MHz block sold for 55 million. Bidding was nowhere near equilibrium.
  • Simultaneous sealed-bid. New Zealand, 1990, sold television broadcasting licences by simultaneous Vickrey auctions. Revenue was $36 million against a projected $250 million. On one licence the high bid was $100,000 and the second-highest — hence the price — was $6. On another, $7 million against $5,000. The bids were published, so the public could see exactly how much had been left on the table.

SMRA has two well-documented vulnerabilities of its own. Demand reduction: with two identical items, bidder 1 valuing one at 10 and both at 20, and bidder 2 valuing one at 8, bidder 1 does better targeting a single item (utility ≈ 10 at near-zero price) than insisting on both (utility 20 − 16 = 4). The exposure problem: bidder 1 wants both items only, at 100; bidder 2 will pay 75 for either; bidder 2 stays in until each price reaches 75, so bidder 1 must risk paying 150 for a bundle worth 100, or risk being stranded with a single worthless item. Exposure is the direct cost of not allowing package bids — the same complementarity that breaks VCG’s revenue also breaks item-by-item ascending auctions, in the opposite direction.

Core-selecting package auctions

The mainstream successor. Instead of requiring dominant strategies and accepting whatever revenue results, require the outcome to lie in the core with respect to reported values and accept whatever incentives result. Day and Milgrom’s theorems say this is a well-chosen trade: among core-selecting auctions, those that minimize seller revenue subject to being in the core (a) maximize incentives for truthful reporting in a precise sense, (b) produce the Vickrey outcome exactly when the Vickrey outcome is in the core, and (c) unlike VCG, give the seller no incentive to exclude qualified bidders — their Theorem 5 states that the seller’s minimum core payoff is non-decreasing in the set of bidders. Their Theorem 1 characterizes the shill-resistance: an efficient mechanism is immune to a bidder disaggregating into shills if and only if no bidder ever earns more than its Vickrey payoff, and since the Vickrey payoff is the maximum core payoff (Theorem 4), core-selection delivers exactly that.

The cost is honest and should be stated: core-selecting auctions are not strategy-proof. Bidders can profit by shading. Day and Milgrom’s defence is the analogy to deferred acceptance in matching — the National Resident Matching Program’s pre-1998 algorithm was not strategy-proof for doctors either, yet Roth and Peranson found that few doctors could gain at all and tactical misreporting was risky. See The Gale-Shapley Algorithm and Proposer-Optimality and Strategic Truncation for the matching side of that parallel; the structural correspondence (bidder-optimal core point ↔ proposer-optimal stable match) is not a metaphor, it is the same theorem in two costumes.

The clock-proxy auction

Ausubel, Cramton and Milgrom’s concrete design: a clock phase (auctioneer announces per-item prices, bidders state quantities, prices rise where there is excess demand) followed by a single last-and-final proxy round in which bidders submit package values to proxy agents that bid on their behalf. Their claim is that the hybrid “has no exposure problem, eliminates incentives for demand reduction, and prevents most collusive bidding strategies,” keeping linear pricing (which bidders understand) as long as possible and abandoning it only at the end where efficiency requires package bids. Roughgarden’s Lecture 8 notes the practical catch: the proxy round’s payment rule is deliberately not VCG “because of its poor revenue and incentive properties,” and “typical behavior of bidders with this relatively complex pricing rule does not seem to be well understood.”

Greedy / deferred allocation rules

Where the welfare problem is intractable, give up exactness and keep monotonicity. The FCC’s incentive auction reverse phase — buying out TV broadcasters so the freed spectrum can be repacked into a contiguous band — was designed around a deferred allocation rule: start with everyone feasible, greedily remove bidders (by a scoring rule that is increasing in a bidder’s own bid and independent of others’) while feasibility is preserved. Feasibility checking is itself a graph-colouring-flavoured NP-hard problem solved by SAT and integer-programming solvers. Because the rule is monotone, Myerson’s Lemma supplies critical-value payments and the auction is DSIC after all — just not efficient. This is the constructive answer, developed in Approximate and Simple Mechanisms.

DesignTruthful?Revenue vs coreHandles complementsComputationDeployed
VCG (general)Dominant strategyCan be far below coreYes, in principleNP-hard, n+1 solvesEssentially never
Vickrey (single item)Dominant strategyIn coreN/ATrivialeBay proxy bidding, ad exchanges
SMRANoEmpirically goodNo — exposure problemOne price per itemFCC and most spectrum auctions since 1994
Core-selectingNo (shading pays)In core by constructionYesCore-price LP over an NP-hard baseCombinatorial spectrum auctions
Clock-proxyNoIn core (proxy round)YesClock + package solveProposed/used for spectrum
GSPNo (despite the name)n/a — position auctionN/ASort by bid × qualityGoogle, Microsoft search ads
Greedy / deferredDominant strategyn/aDependsPolynomial + feasibility oracleFCC incentive auction reverse phase

Production Notes

Google chose GSP over VCG, twice, and then partly reversed

The best-documented deployment decision in this whole literature is Hal Varian and Christopher Harris’s The VCG Auction in Theory and Practice (AER P&P 2014) — Varian being Google’s chief economist and Harris a Google engineer/economist, writing about their own system.

The timeline they give: Google designed the generalized second-price auction in autumn 2001 and shipped it in February 2002. “A few months later, Eric Veach, the computer engineer who was the main architect of the original GSP auction, came up with a way to create a truthful auction for clicks and showed it to Hal, who immediately recognized it as a VCG auction.” So Google had VCG in hand within months of launching GSP, and considered switching in the summer of 2002. Three problems killed it:

(i) the existing GSP auction was growing very rapidly and required a lot of engineering attention, making it difficult to develop a new auction; (ii) the VCG auction was harder to explain to advertisers; and (iii) the VCG auction required advertisers to raise their bids above those they had become accustomed to in the GSP auction.

Reason (iii) is the sharpest and least often noticed. VCG prices are lower than GSP prices for the same values, so a truthful VCG bid is numerically larger than the equilibrium GSP bid that produces the same outcome. Migrating means telling every advertiser to raise the number in the box while promising they will not pay more. Reason (ii) is the one economists systematically underrate: a mechanism whose payment rule cannot be explained to the people paying is, in a competitive marketplace, a mechanism with a churn problem. Reason (i) is pure engineering opportunity cost — the exact reason plenty of correct designs never ship.

Crucially, this is not a story about the pathologies of §§2–6. A sponsored-search position auction is a single-parameter environment with substitutes-like structure; the low-revenue and shill problems do not really arise. Varian and Harris say as much: Ausubel–Milgrom and Rothkopf “describe some other problematic issues, but most of these are not relevant for the particular situation we face.” VCG lost on migration cost, explicability and engineering bandwidth — which is a much more common way for good mechanisms to die than a counterexample in a journal.

The sequel matters too. In 2012 Google reconsidered VCG for contextual ads (ads keyed to page text rather than a search query) and shipped it in late 2012. Two things had changed. First, flexibility: by 2012 Google was doing “dynamic resizing” — if one of four ads is highly relevant and three are mediocre, enlarging the good one and showing it alone yields more total clicks. Pricing that under GSP “was quite difficult”; under VCG it falls out of the externality formula. Second, composability: contextual ads compete in ad exchanges against display ads sold by ordinary Vickrey auctions, where truth-telling is dominant. Mixing a non-truthful GSP bid with a truthful Vickrey bid in one exchange is incoherent; making both truthful “enabled the contextual ads to compete on an equal footing.”

Their closing engineering note is the honest one: “The design of the Vickrey auction is so elegant, one might hope that it would be relatively easy to implement. Alas, it is not so. There were many edge cases that needed to be dealt with, adding to design complexity.” And the shipped system “cannot be considered a ‘pure’ Vickrey auction, but it is reasonably close to one.”

Varian and Harris also record which auction each major platform ran as of 2014: search ads → GSP (Google, Microsoft); display ad exchanges → Vickrey second-price; Facebook → VCG. So VCG is not literally unused at internet scale — it is unused for general combinatorial allocation, which is precisely Rothkopf’s claim.

Uncertain

Verify: whether these platform choices still hold in 2026. Reason: the source is dated May 2014 and ad-tech auction design has moved substantially since — display advertising’s industry-wide shift from second-price to first-price auctions occurred around 2018–2019 and is not covered by any source I fetched. To resolve: primary documentation from the current ad platforms. Treat the platform table as a 2014 snapshot, not a present-tense claim. uncertain

Why GSP is not truthful, briefly

Since the epilogue turns on it: GSP ranks advertisers by bid (times a quality score) and charges each the bid below. With one slot that is exactly the Vickrey auction. With two or more it is not, because a bidder’s price is set by the bid below rather than by the externality it imposes, and a bidder may prefer a cheaper lower slot to an expensive higher one. Edelman, Ostrovsky and Schwarz’s analysis and Varian’s Position Auctions both establish the connection that makes the substitution defensible: the minimum-revenue equilibrium of GSP has the same revenue as VCG. Varian and Harris rederive it in three slots and note it is a special case of Demange–Gale and Demange–Gale–Sotomayor. So GSP is not truthful, but it lands on the VCG outcome in a natural equilibrium — which is a great deal of what one wanted, at a price advertisers understand. Ad Auctions and GSP develops this properly.

Spectrum: the actual deployment record

The FCC has run dozens of spectrum auctions since 1994, raising hundreds of billions of dollars, and the format has been SMRA with accumulating bells and whistles, not VCG. Package bidding entered only cautiously and late: Roughgarden’s 2013 notes describe limited package bidding as having been incorporated “only over the past 5–10 years,” with the conservative view — that package bids “add complexity to a quite functional auction format and might do more harm than good” — having dominated practice until recently. Two approaches exist: bolt a proxy round onto the end of an SMRA, or predefine a limited menu of allowable packages (hierarchical packages — individual licences, regional bundles, nationwide bundles — being the empirical sweet spot). The failure mode of predefined packages is memorable: if you want ABCD and the menu offers ABEF and CDHI, you have no strategy.

Two other pieces of field evidence deserve recording because they concern iterative auctions generally, not VCG specifically. Cramton and Schwartz found that in an early, uncompetitive FCC auction, bidders used the low-order digits of their bids as a signalling channel: USWest, tired of a bidding war with McLeod over licence #378 (Rochester, MN), started bidding on unrelated licences where McLeod was the standing high bidder, and made every retaliatory bid a multiple of 1000 plus 378 so the message could not be missed. Forcing bids to be multiples of a large number kills that particular channel; it does not kill the general problem that iterative auctions create rounds in which to communicate.

How to sanity-check an auction whose valuations you cannot see

Because bidders’ true values are never observable, “did the auction work?” cannot be answered directly. Roughgarden lists the field’s proxies, and they are the right operational checklist for anyone running one:

flowchart TB
    Q["Did the auction perform well?<br/>(true valuations are unobservable)"]
    Q --> S1["<b>Little or no resale</b> afterwards —<br/>and any resale at a price near<br/>the auction's selling price"]
    Q --> S2["<b>Similar items sold at<br/>similar prices</b><br/>(cf. Switzerland 2000: 121M, 134M, 55M)"]
    Q --> S3["<b>Revenue met or exceeded<br/>projections</b><br/>(cf. New Zealand 1990: $36M vs $250M)"]
    Q --> S4["<b>Evidence of price discovery</b> —<br/>mid-auction prices and provisional<br/>winners correlate with final ones"]
    Q --> S5["<b>Packages are sensible</b> —<br/>licences adjacent geographically<br/>or in frequency"]
    S1 --> V["All five passing ⇒ probably fine.<br/>Any one failing loudly ⇒ investigate."]
    S2 --> V
    S3 --> V
    S4 --> V
    S5 --> V

What it shows: five observable proxies for unobservable welfare, each with the historical failure that motivates it. Insight: auction quality is validated the way distributed-systems correctness is validated — not by proving the invariant but by instrumenting the symptoms of its violation. Speculator activity shows up as resale; miscoordination shows up as identical goods at different prices; format failure shows up against revenue projections.

If you build one anyway

For the P7 exercise in Games and Strategic Systems in C MOC — implement VCG for a small combinatorial allocation, then try to break it — the lessons that cost me time:

  1. Exact arithmetic is not optional. §7 measured 15.6% of exact zeros going non-zero in doubles and 347 of them going negative. Use scaled integers or rationals.
  2. Assert the theorems, and expect the assertions to fire. p_i ≥ 0 and v_i(x_i) − p_i ≥ 0 are both theorems; violations mean a bug in the counterfactual solve, not a surprising economic result. In Fraction arithmetic mine never fired; in float they fired 347 times.
  3. Free disposal must be implemented, not assumed. A bidder who bids only on {A,B} must be scored as valuing {A,B,C} at the same amount. Getting this wrong changes the counterfactual optima and therefore every payment.
  4. The interesting test is not “does truth-telling win” — it is “can a coalition win.” A search over unilateral misreports will correctly find nothing. Search over joint deviations by losers, and over splitting one bidder into two, and it will find the profitable deviations of §§5–6 immediately. That is the whole content of this note reduced to a test harness.

See Also

Graph View

Backlinks