vault

The VCG Mechanism

32 min read

The VCG Mechanism

The Vickrey–Clarke–Groves (VCG) mechanism is the one general answer mechanism design has to the question “can I maximise total welfare while making honesty a dominant strategy?” It works by charging each participant the externality they impose on everyone else — the difference between the best welfare the others could have achieved had you never shown up, and the welfare they actually achieve given that you did. Because your payment depends only on other people’s reports and on the chosen outcome, and because the mechanism picks the outcome maximising total reported welfare, your own report affects your utility only through which outcome gets chosen — and reporting the truth makes the mechanism’s objective identical to yours. Roughgarden states the guarantee at full generality: “In every general mechanism design environment, there is a DSIC welfare-maximizing mechanism” (CS364A Lecture 7, Theorem 2.1). It is also, as he immediately adds, “highly non-awesome in many important applications” — it can be computationally out of reach, it can raise zero revenue in a competitive market, and it is defenceless against coalitions and false identities. This note derives it, implements it on a combinatorial auction, attacks that implementation with five million misreports and fails to break it, then attacks it two other ways and succeeds.

This is the fourth rung of P7 — Mechanism Design in Games and Strategic Systems in C MOC. It assumes the vocabulary of Mechanism Design and Incentive Compatibility, and it is the mechanism that The Revelation Principle licenses you to search for in direct form. Its deployment failures are developed at length in the sibling Why VCG Is Rare in Practice; this note states them and hands off rather than duplicating.

Mental Model — You Pay for the Damage You Do

Imagine the auctioneer running the allocation twice: once with everyone, once pretending you do not exist. The others do worse in the first run than in the second — you took something they wanted. That shortfall is your bill.

flowchart TB
    subgraph W1["run 1 — WITHOUT agent i"]
        A1["maximise Σ_{j≠i} b_j(ω)<br/>over all outcomes ω"] --> R1["h_i = best welfare<br/>the others can get<br/>on their own"]
    end
    subgraph W2["run 2 — WITH agent i"]
        A2["maximise Σ_all b_j(ω)<br/>over all outcomes ω"] --> R2["ω* chosen;<br/>others receive Σ_{j≠i} b_j(ω*)"]
    end
    R1 --> P["p_i = h_i − Σ_{j≠i} b_j(ω*)<br/><b>the externality</b>"]
    R2 --> P
    P --> U["u_i = v_i(ω*) − p_i<br/>= [ v_i(ω*) + Σ_{j≠i} b_j(ω*) ] − h_i<br/>= <b>total welfare</b> − a constant"]
    U --> T["so i wants the mechanism to<br/>maximise TOTAL welfare<br/>⇒ report truthfully"]

What it shows: the two winner-determination runs, their difference, and how that difference converts agent i’s private objective into the designer’s public one. The insight to take: the last step is the entire theorem. h_i does not depend on anything i says, so from i’s point of view it is a constant; subtracting a constant does not change an argmax. What remains — v_i(ω*) + Σ_{j≠i} b_j(ω*) — is total welfare with i’s true value substituted in. The one report that makes the mechanism maximise exactly that is the truth.

Deriving It

Set up a general (multi-parameter) mechanism design environment (Roughgarden, Lecture 7 §1): n agents, a finite set Ω of outcomes, and a private valuation vᵢ(ω) for each agent and each outcome. “Multi-parameter” means an agent’s private information is not a single number: in a combinatorial auction, bidder i privately holds a value for every bundle. This matters because the single-parameter toolkit — Myerson’s lemma, allocation-rule monotonicity, critical-value payments (Roughgarden, Lecture 3) — does not apply. Roughgarden is explicit: “with an agent submitting bids in more than one dimension, it’s not even clear how to define ‘monotonicity’ of an allocation rule.”

Step 1: fix the allocation rule. If you want welfare maximisation, there is no choice. Given reports b₁ … bₙ,

    x(b) = argmax_{ω ∈ Ω}  Σᵢ bᵢ(ω)

Symbol by symbol: bᵢ(ω) is what agent i says outcome ω is worth to it; the sum is total reported welfare; the argmax picks the best outcome. The mechanism uses reports as proxies for the unknown true values.

Step 2: find a payment rule that makes truth dominant. This is the step VCG solves. The Groves family is the general answer (Nisan, Algorithmic Game Theory, Definition 9.16):

    pᵢ(b) = hᵢ(b₋ᵢ)  −  Σ_{j≠i} bⱼ( x(b) )

hᵢ is an arbitrary function of everyone else’s reports. The only structural requirement is that it must not depend on bᵢ. Nisan’s account of why this works is worth reading as prose, because it is the whole idea:

“The main idea lies in the term − Σ_{j≠i} vⱼ(f(v)), which means that each player is paid an amount equal to the sum of the values of all other players. When this term is added to his own value vᵢ(f(v)), the sum becomes exactly the total social welfare… Thus this mechanism aligns all players’ incentives with the social goal of maximizing social welfare, which is exactly achieved by telling the truth. The other term in the payment hᵢ(v₋ᵢ) has no strategic implications for player i since it does not depend, in any way, on what he says, and thus from player i’s point of view it is just a constant.”

The formal proof (AGT Theorem 9.17) is four lines. Fix i, fix everyone else’s reports v₋ᵢ, let vᵢ be the truth and v′ᵢ any lie. Write a = f(vᵢ, v₋ᵢ) and a′ = f(v′ᵢ, v₋ᵢ). Agent i’s true utility from reporting truthfully is

    vᵢ(a) + Σ_{j≠i} vⱼ(a) − hᵢ(v₋ᵢ)

and from lying is

    vᵢ(a′) + Σ_{j≠i} vⱼ(a′) − hᵢ(v₋ᵢ)

But a was chosen by the mechanism to maximise Σ_all vⱼ(·) when i reported vᵢ, so vᵢ(a) + Σ_{j≠i} vⱼ(a) ≥ vᵢ(a′) + Σ_{j≠i} vⱼ(a′). Subtract the same hᵢ(v₋ᵢ) from both sides. Done. Notice what the proof never used: any assumption about the other agents’ reports being truthful, or about a prior, or about Ω being small. This is dominant-strategy incentive compatibility in its strongest form.

Step 3: pin down hᵢ. Choosing hᵢ = 0 is legal and disastrous — the mechanism then pays every agent the others’ entire welfare. The Clarke pivot rule is the choice that makes the payments mean something (AGT Definition 9.19):

    hᵢ(b₋ᵢ) = max_{ω ∈ Ω}  Σ_{j≠i} bⱼ(ω)

— the best the others could do without i in the room. Substituting gives the headline formula:

    pᵢ(b) = max_{ω}  Σ_{j≠i} bⱼ(ω)   −   Σ_{j≠i} bⱼ(ω*)
            └── others without i ──┘   └── others with i ──┘

Nisan again: “i pays an amount equal to the total damage that he causes the other players… the payments make each player internalize the externalities that he causes.”

Two properties follow (AGT Lemma 9.20), both verified empirically below:

  • No positive transfers: pᵢ ≥ 0 always, because ω* is one of the outcomes the “without i” maximisation ranged over, so the first term is at least the second.
  • Individual rationality (when every vᵢ(ω) ≥ 0): truthful agents never end up with negative utility.

There is an equivalent reading of the payment that is often more intuitive (Roughgarden Lecture 7, equation 4): rewrite it as pᵢ(b) = bᵢ(ω*) − [ Σ_all bⱼ(ω*) − max_ω Σ_{j≠i} bⱼ(ω) ], i.e. your bid minus a rebate equal to the increase in welfare your presence creates. In the single-item case the winner pays b₁ − (b₁ − b₂) = b₂.

Worked Example — a Combinatorial Auction, Implemented

Three items {A, B, C}, three bidders. Bidder 0 wants item A and nothing else. Bidder 1 wants the pair {B,C} and gets nothing from either alone — a complementarity, the thing combinatorial auctions exist for. Bidder 2 has broad, roughly additive interests.

bidderABCABACBCABC
010001010010
1000001616
24731171014

Winner determination is exact brute force. Every assignment of each item to one of the n bidders or to nobody is enumerated — (n+1)^m of them, here 4³ = 64. This machine has no linear- or integer-programming library available (glpk absent, no pip, no numpy; liblpsolve55.so is present but ships without headers, so nothing can link against it), so brute force is the honest choice and I am naming it as such rather than implying a solver. For the sizes in this note it is also better: it is exact by construction, it has no tolerance parameter to get wrong, and it makes the two optima that a VCG payment subtracts provably consistent.

def alloc_table(n, m):
    """Pre-enumerate every allocation as an n-tuple of item bitmasks."""
    out = []
    for assign in product(range(n + 1), repeat=m):     # item -> bidder, or n = "nobody"
        masks = [0] * n
        for item, who in enumerate(assign):
            if who < n:
                masks[who] |= 1 << item
        out.append(tuple(masks))
    return out
 
 
def wd(bids, table, skip=None):
    """Exact winner determination: argmax over `table` of reported welfare,
    with bidder `skip` (if any) excluded from the auction entirely.
    Ties break by enumeration order -- deterministic, which MATTERS, because
    VCG subtracts two of these optima and an inconsistent tie-break corrupts
    the difference."""
    best_w, best_a = None, None
    for a in table:
        if skip is not None and a[skip]:
            continue                       # bidder `skip` is absent: gets nothing
        w = sum(bids[i][a[i]] for i in range(len(bids)) if i != skip)
        if best_w is None or w > best_w:
            best_w, best_a = w, a
    return best_w, best_a
 
 
def vcg(bids, table):
    """Efficient allocation + Clarke-pivot payments."""
    W, a = wd(bids, table)                              # run 2: with everyone
    pays = [wd(bids, table, skip=i)[0]                  # run 1: without i
            - sum(bids[j][a[j]] for j in range(len(bids)) if j != i)
            for i in range(len(bids))]
    return a, pays, W

The skip parameter deserves a note: “without agent i” is implemented as i exists but may receive nothing, which is the right reading for an auction (the items are still there, they just cannot go to i). Nisan flags that the Clarke rule’s meaning is context-dependent — in a procurement setting “without i” naturally means the mechanism “can simply not use paths that contain e”, and where valuations are negative (costs) the pivot rule has to be adapted so that money flows the right way (AGT §9.3.4, §9.3.5.6).

Running it:

  allocations enumerated per WD call : 64   ((n+1)^m = 4^3)
  efficient allocation : b0<-A | b1<-BC | b2<-nothing
  maximum welfare      : 26

  i | others w/o i | others with i | payment | value | utility
  0 |           20 |            16 |       4 |    10 |       6
  1 |           20 |            10 |      10 |    16 |       6
  2 |           26 |            26 |       0 |     0 |       0
  revenue = 14   welfare = 26

Walk bidder 1’s row. Without bidder 1, the best the others can do is bidder 0 taking A (10) plus bidder 2 taking BC (10) = 20. With bidder 1 present and holding BC, the others get bidder 0’s A (10) + bidder 2’s nothing (0) = 10. Bidder 1’s externality is 20 − 10 = 10, so it pays 10 for something worth 16, keeping a surplus of 6. Bidder 2 is allocated nothing, imposes no externality (26 − 26 = 0), and pays nothing — the losers-pay-nothing property, which falls out rather than being imposed. Total revenue is 14 against welfare of 26: the seller captures 54%, and the bidders keep the rest. That gap is not a bug; it is the price of dominant-strategy truthfulness, and §“What VCG Does Not Have” measures how much worse it gets.

flowchart LR
    subgraph S["the two runs for bidder 1"]
      direction TB
      WO["WITHOUT bidder 1<br/>b0←A (10), b2←BC (10)<br/><b>= 20</b>"]
      WI["WITH bidder 1<br/>b0←A (10), b1←BC (16), b2←∅ (0)<br/>others get <b>10</b>"]
    end
    WO --> D["externality = 20 − 10 = <b>10</b>"]
    WI --> D
    D --> R["bidder 1 pays 10, values BC at 16 ⇒ utility 6"]

What it shows: the same two-run picture instantiated on real numbers. The insight: bidder 1’s bill is not related to its own bid at all — it is entirely determined by what bidder 2 would have done with {B,C}. Raising or lowering its own report can only change whether it wins, never what it pays when it does.

Attacking It

A strategyproofness claim you have tried and failed to break is worth more than one you proved on paper and mistyped. Two attacks, both exhaustive.

Attack 1 — every misreport on the worked instance. A bidder’s report is a value for each of the 7 non-empty bundles. Sweeping a five-point grid {0,4,8,12,16} over each, for each of the three bidders, and evaluating the mechanism’s actual output against the bidder’s true valuation:

  misreports enumerated : 234,375   (5 values ^ 7 bundles, x 3 bidders)
  wall clock            : 4.7 s
  best gain over truth  : 0        <- 0 means the attack FAILED

Attack 2 — randomised sweep. 300 fresh instances, each bidder’s seven bundle values drawn uniformly from {0,…,12} with no monotonicity imposed (so reports and valuations may violate free disposal, which is a strictly harder test), one bidder chosen at random per instance and its entire 4⁷ report grid enumerated:

  instances            : 300
  misreports evaluated : 4,915,200
  wall clock           : 96 s
  profitable deviations found : 0

Zero out of 4.9 million. The theorem survives contact with an implementation. Note carefully what the attack does and does not rule out: the search space is single-agent unilateral deviations, which is exactly the quantifier in the definition of dominant-strategy incentive compatibility. The next section attacks the quantifier itself.

Sanity checks against known special cases, each verified against an independently written formula rather than against the VCG code’s own output:

Special caseIndependent formulaInstancesDisagreements
Single item, 4 biddershighest value wins, pays the second-highest3,0000
k identical units, unit demandevery winner pays the (k+1)-st highest value5,0000

The single-item case is The Vickrey Auction: “VCG payments using the Clarke pivot rule give exactly Vickrey’s second price auction” (AGT §9.3.5.1). The multi-unit case is Vickrey’s own generalisation — and it is worth being precise about what he did and did not prove, because the secondary literature blurs it (see the history section below).

A third special case worth drawing: procuring a path. Each edge of a network is owned by a strategic agent with a private cost; the buyer wants a cheapest s–t path. VCG pays each edge on the winning path (cost of the best path avoiding that edge) − (cost of the winning path without that edge's own cost) (AGT §9.3.5.6).

flowchart LR
    s((s)) -->|"cost 1"| a((a))
    a -->|"cost 1"| b((b))
    b -->|"cost 1"| t((t))
    s -->|"cost 3"| b
    a -->|"cost 3"| t

What it shows: five edges; the cheapest s–t path is s→a→b→t at total cost 3. The insight: removing any one of those three edges forces a detour costing 4, so each is paid 4 − (3 − 1) = 2 for a job that costs it 1. The buyer pays 6 for a path worth 3 — a 100% premium. Truthfulness is not free; here its price is the whole cost of the path again. This is frugality, and it is one of the reasons procurement agencies do not run VCG.

What VCG Does Not Have

Everything above is what VCG gives you. Here is what it does not, each item measured rather than asserted. Why VCG Is Rare in Practice develops these into a deployment argument; this section establishes that they are real.

mindmap
  root((VCG))
    HAS
      dominant-strategy truthful
      exactly welfare-maximising
      no positive transfers
      individually rational
        given Clarke pivot and non-negative values
      essentially the ONLY efficient truthful rule
    LACKS
      revenue
        30-64% of welfare measured
        6.2% of thin markets raise 0
        NON-MONOTONE in bidders
      coalition-proofness
        pairs gain
        false names gain more
      budget balance
        bilateral trade is subsidised
        public projects underfunded
      tractability
        WD is NP-complete
        2^m values per bidder
        approximation breaks DSIC
      robustness to non-quasi-linearity
        budgets
        risk aversion

What it shows: the guarantee and its complement, side by side. The insight: the left branch is short and the right branch is long, and everything on the right is a property a working market operator would list before “welfare-maximising.” That asymmetry — a beautiful theorem whose omissions are exactly the practitioner’s requirements list — is the whole story of why VCG is a benchmark rather than a product.

Revenue: low, and non-monotone

Across 6,000 random combinatorial-auction instances at three sizes:

settingIR violationsnegative paymentsrevenue / welfareinstances raising zero revenue
3 bidders, 3 items0 / 20000 / 20000.302124 (6.2%)
4 bidders, 4 items0 / 20000 / 20000.35626 (1.3%)
5 bidders, 4 items0 / 20000 / 20000.6400 (0.0%)

Individual rationality and no-positive-transfers hold in every single instance, exactly as AGT Lemma 9.20 promises. Revenue is 30–64% of welfare, and in the thin 3-bidder market one instance in sixteen raises nothing at all.

The pathological case is sharper than the average. Roughgarden’s two-item example (Lecture 7 §3.2), reproduced exactly:

  bidder 1 wants both items    : v1(AB) = 1
  bidder 2 wants item A        : v2(A)  = 1
  bidder 3 wants item B        : v3(B)  = 1

  two bidders (1,2)  : welfare 1  payments [1, 0]     revenue 1
  three bidders      : welfare 2  payments [0, 0, 0]  revenue 0

flowchart TB
    subgraph TWO["2 bidders — welfare 1, revenue 1"]
        direction TB
        T1["bidder 1: AB worth 1"]
        T2["bidder 2: A worth 1"]
        TA["winner: bidder 1 takes AB<br/>without b1 the others get 1<br/>with b1 they get 0<br/><b>b1 pays 1</b>"]
        T1 --> TA
        T2 --> TA
    end
    subgraph THREE["3 bidders — welfare 2, revenue 0"]
        direction TB
        H1["bidder 1: AB worth 1"]
        H2["bidder 2: A worth 1"]
        H3["bidder 3: B worth 1"]
        HA["winners: b2←A, b3←B<br/>without b2 the others get 1<br/>with b2 they get 1<br/><b>b2 pays 0</b> — and so does b3"]
        H1 --> HA
        H2 --> HA
        H3 --> HA
    end
    TWO --> ARROW["add one more<br/>real bidder"] --> THREE

What it shows: the same auction with and without bidder 3, and the two-run externality calculation for each. The insight: with three bidders, bidder 2 no longer displaces anyone — bidder 3 absorbs the item bidder 1 would otherwise have taken, so bidder 2’s counterfactual and actual worlds give the others the same welfare, and its externality is exactly zero. Symmetrically for bidder 3. Competition destroyed the revenue rather than creating it, because VCG prices are externalities, and in a market where everyone is substitutable nobody imposes one.

Adding a third genuinely interested bidder doubles welfare and drives revenue from 1 to zero. Roughgarden’s verdict: “The fact that the VCG mechanism has zero revenue in seemingly competitive environments is a dealbreaker in practice.” The mechanism is not merely low-revenue; its revenue is non-monotone in the bidder set, which is what makes the next two attacks possible.

Collusion: the incentive constraint is single-agent by construction

Dominant-strategy incentive compatibility quantifies over one agent deviating alone. Nothing in the definition, and nothing in the four-line proof, constrains two agents who coordinate. Searching joint report pairs on random 3-item instances found a Pareto-improving pair deviation immediately — within the first instance and 65 joint reports evaluated:

  truthful utilities (bidders 0, 1) : 6, 8
  colluding utilities               : 8, 8
  joint gain                        : 2   (neither is worse off)

That is one instance, so I ran the same experiment as a controlled rate measurement: 2 items, 3 bidders, values drawn uniformly from {0,…,9}, and for each instance an exhaustive sweep of the entire joint report space (64 × 64 = 4,096 pairs) alongside the exhaustive single-agent sweep (64 reports) as a control.

  instances                              : 100
  instances where ONE bidder alone gains : 0/100   (0%)   <- DSIC predicts exactly this
  instances where the PAIR gains         : 77/100  (77%)
  mean joint gain when one exists        : 3.87    (max 8)

The control is the point. The single-agent column is the theorem, and it holds perfectly: zero profitable unilateral deviations, in 100 instances, on top of the 4.9 million misreports of Attack 2. Add one accomplice and 77% of instances become manipulable, with a mean joint gain of 3.87 in a market whose total welfare is on the order of 15. Both colluders are always weakly better off and at least one strictly so — this is a Pareto improvement for the coalition, not a transfer between them. The gap between “no agent gains” and “no group gains” is not a technicality; it is most of the outcome space.

False-name bidding: one agent, two identities

Two items, one rival wanting {A,B} at value 3, and our bidder wanting {A,B} at value 2. Honestly, our bidder loses and gets utility 0. Exhaustively enumerating all 9³ = 729 single-identity reports it could submit — every combination of a bid on A, on B, and on AB from 0 to 8 — the best achievable utility is still 0. There is no lie that helps.

Now let it register as two bidders, one claiming to want only A (bid 3) and one claiming to want only B (bid 3):

  best utility over all 729 single-identity reports : 0
  best two-identity utility                        : 2   (payments [0, 0, 0])

flowchart LR
    subgraph H["honest: one identity"]
        HB["me: AB worth 2"] --> HR["rival bids 3 for AB<br/>rival wins<br/><b>my utility 0</b>"]
    end
    subgraph L["best lie: still one identity"]
        LB["me: any of 729 reports<br/>over bids on A, B, AB"] --> LR["either I lose (utility 0)<br/>or I win and pay 3 > 2<br/><b>best utility 0</b>"]
    end
    subgraph F["false names: two identities"]
        F1["shill α: 'A worth 3'"] --> FR["reported welfare 3+3 = 6 > 3<br/>α gets A, β gets B<br/>α's externality: 3 − 3 = 0<br/>β's externality: 2 − 2 = 0<br/><b>I get AB for 0 ⇒ utility 2</b>"]
        F2["shill β: 'B worth 3'"] --> FR
    end

What it shows: three strategies available to the same bidder, and the utility each yields. The insight: the reason the attack works is the same reason revenue collapsed above — each shill makes the other one’s externality vanish. Alone, either shill would have to outbid the rival and pay 3. Together, each one’s counterfactual world already contains the other, so neither displaces anybody, and the pair pays nothing. VCG’s incentive constraint never looked at this because it only ever quantified over one agent, one report.

The two shills’ reported welfare of 6 beats the rival’s 3, so they win A and B — which is to say our bidder gets {A,B} — and each shill’s externality is zero, so the whole bundle is acquired for nothing. A true value of 2 is realised at a price of 0, against an honest payoff of 0 and a best-lie payoff of 0. False-name bidding strictly dominates both honesty and every possible lie.

Vickrey saw the shape of this in 1961. Discussing what happens when a bidder wants more than one unit, he wrote that “It is not possible to consider a buyer wanting up to two units as merely an aggregation of two single-unit buyers: combining the two buyers into one introduces a built-in collusion and community of interest” (Counterspeculation, Auctions, and Competitive Sealed Tenders, Journal of Finance 16(1), p. 27). The false-name attack is that sentence run backwards: instead of merging two bidders into one, split one into two.

Computation: winner determination is the bottleneck

Brute force is (n+1)^m and each bidder must supply 2^m numbers. Measured on this machine:

bidders nitems mallocations enumeratedbundle values per bidderfull VCG (1 + n WD runs)
336480.000 s
44625160.000 s
557,776320.004 s
5646,656640.021 s
67823,5431280.46 s
685,764,8012562.93 s
874,782,9691284.69 s

The wall arrives fast, and a better solver only postpones it: exact winner determination in a combinatorial auction is NP-complete, and the approximation problem is hard too — “approximating the optimal allocation among single-minded bidders to within a factor better than m^{1/2−ε} is NP-hard” (AGT Proposition 11.6), with a matching communication lower bound: approximating within min{n, m^{1/2−ε}} “requires exponential communication” (AGT Theorem 11.27).

The elicitation side is worse than the solving side. At m = 20 items each bidder holds about a million private numbers; Roughgarden’s assessment is that “this exponential number of private parameters makes the VCG mechanism, and every other direct-revelation mechanism, a nonstarter for combinatorial auctions in practice” (Lecture 7 §3.2).

And you cannot rescue it by approximating. VCG’s proof used the fact that the allocation rule is an exact argmax; swap in an approximation and truth-telling generally stops being dominant. Conitzer and Sandholm push this further, showing settings where “by abandoning truthful mechanisms, we can shift a computationally hard problem from the center to one of the agents,” with the striking corollary that if the agent fails to solve its NP-complete manipulation problem, “the social welfare of the outcome is strictly greater than the social welfare that would be produced by any optimal truthful mechanism” (Computational Criticisms of the Revelation Principle, Theorem 2).

Budget balance: the money does not add up

VCG’s payments are determined by the allocation rule up to the hᵢ freedom, and that freedom is not enough. In the bilateral trade problem — one seller valuing an item at vₛ, one buyer at v_b, trade efficient iff v_b > vₛ — VCG has the buyer pay vₛ and the seller receive v_b, so the mechanism subsidises every trade it enables (AGT §9.3.5.3). In the public project problem, the collected payments never cover the project’s cost. Neither is an artifact of a bad hᵢ choice, because the payment rule is essentially unique: “The only incentive compatible mechanisms that maximize social welfare are those with VCG payments” (AGT §9.5.5, corollary (i), following from Theorem 9.37 and originally Green and Laffont 1977). The Nobel background states the same conclusion about Clarke–Groves: “The main drawback of this mechanism is that the total tax revenue typically will not add up to the cost of the project: the mechanism does not in general satisfy budget balance… Both too much funding and too little funding is problematic. For example, sharing surplus funds among the participants will destroy the participants’ truth-telling incentives, while wasting surplus funds is inefficient” (§2.2). Impossibility Results covers the Myerson–Satterthwaite theorem that makes this unavoidable.

Quasi-linearity: the model assumption you will violate first

Every line of the derivation used uᵢ = vᵢ(ω) − pᵢ. Introduce a budget constraint, risk aversion, or non-transferable utility and the argument collapses at step 2, not at some later refinement. Roughgarden devotes a whole lecture to this (Lecture 9, “Beyond Quasi-Linearity”); the practical version is that a bidder with a hard budget cap does not have quasi-linear preferences, and every real spectrum bidder has one.

Failure Modes and Gotchas

Floating point silently changes prices. A VCG payment is the difference of two independently computed optima. If either optimum has ties — and welfare sums over small integer or decimal values produce ties constantly — a float implementation can resolve the two ties inconsistently and hand you a completely different payment vector. Measured over 4,000 random 3-bidder, 3-item instances with values in tenths:

  instances where float payments != exact payments : 17 / 4000  (0.4%)
  worst absolute payment error : 2.7
      exact payments : ['12/5', '27/10', '0']
      float payments : [0.0, 2.4, 2.6999999999999993]

That is not a rounding wobble — the payment vector is permuted, because a different (equally optimal) allocation was selected. The diagnosis, isolated:

  exact optimum 29/5   at alloc ['0b1',  '0b10', '0b100']
  float optimum 5.8000000000000007 at alloc ['0b10', '0b1',  '0b100']
  exact welfare of the FLOAT allocation : 29/5
  -> both allocations are EXACTLY optimal; float broke the tie differently

Both allocations are genuinely optimal at welfare 29/5; the float run’s accumulated 0.1-scaled sums ordered them differently. Use fractions.Fraction, or scale to integers, or fix a deterministic tie-break and apply the identical rule in every one of the n+1 winner-determination runs. All three work; float alone does not.

Inconsistent tie-breaking across the n+1 runs. Even in exact arithmetic, if wd() and wd(skip=i) break ties by different rules, pᵢ picks up a spurious non-zero term. Symptom: payments that violate no-positive-transfers or individual rationality on instances with repeated values. Diagnosis: run the 2,000-instance IR / non-negative-payment sweep above; the Clarke pivot rule guarantees both, so any violation is your bug, not the theory’s.

Getting “without i” wrong. The counterfactual is i is absent, not i is present but bids zero, and not i’s items are removed. In an auction, the items i would have won are still available to the others; in path procurement, the edge is deleted from the graph. Nisan notes the general form: choose b “as to maximize the social welfare ‘when i does not participate’ where the exact meaning of this turns out to be quite natural in most applications” (AGT §9.3.4). Getting it wrong produces a mechanism that looks like VCG and is not truthful.

Assuming losers pay zero is a design choice. It is not — it falls out. A losing bidder changes nothing about the others’ welfare, so its externality is zero. If your implementation charges losers anything, the pivot rule has been misapplied.

Confusing “no single agent gains” with “the mechanism is safe.” The two attacks above are the demonstration. If your threat model includes two parties who can talk, or one party who can open a second account, VCG’s guarantee does not cover you.

Assuming VCG maximises revenue. It maximises welfare. The revenue-maximising auction is a different object entirely, and Myerson stated in his own abstract just how different: the optimal auctions he constructs “generally sell the object at a discount below what the highest bidder is willing to pay, and sometimes they do not even sell to [the] highest bidder” — and yet “no other auction mechanism can give higher expected utility to the seller” (Optimal Auction Design, Mathematics of Operations Research 6(1), p. 58). Selling to the highest bidder — which is exactly what VCG does — is inconsistent with maximising revenue in general. See Reserve Prices and Optimal Auctions.

Treating “Vickrey invented VCG” as settled. He did not, quite; see below.

Alternatives and When to Choose Them

MechanismGives upGainsReach for it when
VCG + Clarke pivotrevenue, budget balance, collusion-resistance, tractabilityDSIC + exact welfare maximisationsmall Ω; you need the strongest incentive guarantee; you are establishing a benchmark
Weighted / affine-maximiser Groves (argmax Σ wⱼvⱼ(a) + c_a)pure efficiencypriorities, reserve-like behaviour, still DSICyou want to favour some agents; note Roberts’ theorem says that on unrestricted domains with ≥3 outcomes these are the only DSIC rules (AGT Theorem 9.32)
d’Aspremont–Gérard-Varet (AGV / expected externality)dominant strategies (only BIC), interim participationexact budget balance with full efficiencymandatory participation, known prior; per the Nobel background this “can be seen as an extension of the Clarke-Groves mechanism to the Bayesian context” (§2.3)
Iterative / ascending combinatorial auctions (the FCC’s SMR family)DSIC and exact welfare maximisationtractable elicitation, better revenue, less information leakagem is large; see The Revelation Principle on why indirect is unavoidable here
Greedy + critical-value paymentsoptimality (an O(√m)-ish approximation)polynomial time, still DSIC on restricted domainssingle-minded bidders; the approximation matches the m^{1/2−ε} hardness bound
Posted prices / simple mechanismsoptimality and sometimes truthfulnessrobustness, obviousness, no solversee Approximate and Simple Mechanisms
The Vickrey Auctiongeneralityeverything VCG has, with none of the pathologiesone item — and note that in the single-item case revenue non-monotonicity, collusion via false names, and the WD blow-up all disappear

That last row deserves emphasis. Roughgarden, having listed VCG’s failures: “None of these issues plague the single-item Vickrey auction” (Lecture 7 §3.2). VCG’s problems are the price of generality, not of the externality idea.

Production Notes

What Vickrey actually wrote (read from the original). The 1961 Journal of Finance paper is a scanned image with zero extractable text and no embedded fonts; it was read here by rendering the pages with pdftoppm -png -r 120 and reading the images directly, from a Princeton course mirror of the JSTOR scan. Three things in it correct the received summary:

  1. He derives the second-price rule as the sealed-bid equivalent of the ascending auction, which is precisely the revelation-principle construction, decades before that name: “it is of interest to inquire whether there is not some sealed-bid procedure that would be logically isomorphic to the progressive auction. It is easily shown that the required procedure is to ask for bids on the understanding that the award will be made to the highest bidder, but on the basis of the price set by the second highest bidder” (p. 20).
  2. He never uses the word “dominant,” and he hedges the argument twice with the phrase collusion aside — “assuming, as is indeed necessary in the analysis of the progressive auction itself, the absence of collusion among bidders… Bidding less than this full value could then only diminish his chances of winning… and could not, collusion aside, affect the price he would actually pay” (p. 20). The dominant-strategy framing is later vocabulary applied to his argument.
  3. His general result is the (m+1)-st price rule for m identical items with unit demand, not the general externality rule: “the bidding will stop at a price equal to the (m + 1)st highest value among those placed on the articles by the bidders… the result is again Pareto-optimal” (p. 24). Section VI scopes it explicitly to “the special class of cases where it is known that each purchaser will want a specified quantity or none at all” (p. 28). Shoham and Leyton-Brown’s characterisation is the accurate one: VCG “was anticipated by Vickrey (1961), who outlined an extension of the second-price auction to multiple identical goods. Groves (1973) explicitly considered the general family of truthful mechanisms applying to multiple distinct goods… Clarke (1971) proposed his tax for use with public goods” (MAS §10.8).

The inventor conceded the failure modes in the original paper. Vickrey devotes most of p. 22 to the mechanism’s operational vulnerabilities: the need “to show the second-best bid to the successful top bidder so that he would be able to assure himself that the price he is being asked to pay is based upon a bona fide bid”; the risk of “the use of a ‘shill’ to jack the price up by putting in a late bid just under the top bid”; and the scenario of “the top bidder and the agent… showing the top bid to the second bidder, together with a quieting douceur, so as to be able to set the price at the third highest bid.” His conclusion, at the top of p. 23: “If corruption of this order cannot be prevented, then this would constitute a serious disadvantage of the second-price method.” That is stronger than any secondary restatement — the inventor conceding the problem in the original text.

He also states the mechanism’s real practical benefit precisely, and it is not revenue: “It is one of the salient advantages of the second-price method that it makes any such general market appraisal entirely superfluous… Each bidder can confine his efforts and attention to an appraisal of the value the article would have in his own hands, at a considerable saving in mental strain and possibly in out-of-pocket expense” (p. 22). Reduced cognitive load, not more money.

Sponsored search does not run VCG. The generalized second-price auction that funds web search is not truthful despite the name, and the industry chose it over the truthful alternative — Ad Auctions and GSP covers the history and the equilibrium analysis.

Spectrum does not run VCG either, for the elicitation reason above, and the iterative formats used instead have their own documented manipulations: in an early FCC auction, USWest signalled retaliation to McLeod by making all its retaliatory bids “a multiple of 1000 plus 378,” the number of the Rochester, MN licence it wanted (recounted in Roughgarden Lecture 7 §3.2, citing Cramton and Schwartz, Collusive Bidding: Lessons from the FCC Spectrum Auctions, J. Regulatory Economics 17(3), 2000).

Where VCG genuinely ships. As a benchmark and as a component. Roughgarden’s framing is the right one: “While it can be infeasible to implement in practice, the VCG mechanism nevertheless serves as a useful benchmark for other, more practical approaches.” Its clean sub-case — the second-price / (k+1)-st price rule under unit demand — is everywhere, because there the winner determination is a sort and none of the pathologies bite.

Uncertain

Verify: the content of Clarke (1971), Multipart pricing of public goods, Public Choice 11:17–33, and Groves (1973), Incentives in teams, Econometrica 41:617–631. Reason: neither could be obtained at all — both sit behind publisher paywalls and no course-page or institutional mirror was found. This is a stronger failure than the one that affected Vickrey: there, jstor.org/stable/2977633 returned an HTTP 200 challenge shell and the PDF from a Princeton course mirror had zero extractable characters, but the pages were rendered with pdftoppm -png -r 120 and read in full as images. “Could not extract text” and “could not obtain the document” are different, and only the latter applies to Clarke and Groves. Myerson (1981) was likewise obtained and read (identity checked against the masthead: Mathematics of Operations Research 6(1):58–73), though its OCR mangles all mathematics — arrows become +, equation numbers split — so only its prose is quoted here and every formula in this note is derived from the definitions or taken from a clean-text source. The attribution of the general Groves family and of the pivot rule to Groves and Clarke respectively therefore rests on Nisan et al., Shoham & Leyton-Brown, and the Nobel committee’s scientific background — all fetched and read in full — not on the primary texts. To resolve: search the */courses/*/papers/*.pdf mirror pattern (which worked for Vickrey and Myerson) for Clarke 1971 and Groves 1973 and check the pivot-rule and Groves-family statements against them, verifying identity against the masthead rather than the filename. #uncertain

See Also

Graph View

Backlinks