Introduction

Every auction has a problem: why would you ever tell the truth? If you reveal what something is really worth to you, the seller might just charge you that amount. So bidders shade their bids downward, strategize, and the auction produces neither the best outcome nor honest signals.

In 1961, William Vickrey proposed a radical fix for single-item auctions: the winner pays not their own bid, but the second-highest bid. Suddenly, shading your bid can only hurt you — if you bid below your true value, you might lose an item you would have gained. The dominant strategy is to bid exactly what it's worth.

Clarke (1971) and Groves (1973) extended this insight to a far more general setting: any situation where agents have private values and society must choose an outcome. The resulting Vickrey-Clarke-Groves (VCG) mechanism charges each agent exactly the externality they impose — the total value the other agents lose because of the presence of this agent. When the payment is precisely the harm you cause, honesty becomes the uniquely rational choice.

Vickrey shared the 1996 Nobel Prize in Economics for this work. VCG remains the theoretical gold standard of mechanism design: it is the only class of mechanisms that simultaneously achieves efficiency (the outcome maximizes total welfare), truthfulness (reporting true values is a dominant strategy), and individual rationality (no one is forced to participate at a loss).

Try It: Bid in a VCG Auction

Below are 3 items (A, B, C) and 3 bidders (Alice, Bob, Carol). Each bidder has a private value for every subset of items. Adjust their bids with the sliders, then click Run VCG to see the efficient allocation and the externality-based payment each winner owes.

<div class="vcg-wrap">
  <p class="hint">Adjust how much each bidder values each item, then run VCG to see who gets what — and how much they pay.</p>
  <div class="bidder-section">
    <div class="bidder" id="b0">
      <div class="bidder-name">Alice</div>
      <label>Values A: <span class="val" id="v0-0">8</span>
        <input type="range" min="0" max="15" value="8" oninput="updateVal(0,0,this.value)">
      </label>
      <label>Values B: <span class="val" id="v0-1">5</span>
        <input type="range" min="0" max="15" value="5" oninput="updateVal(0,1,this.value)">
      </label>
      <label>Values A+B: <span class="val" id="v0-2">12</span>
        <input type="range" min="0" max="20" value="12" oninput="updateVal(0,2,this.value)">
      </label>
    </div>
    <div class="bidder" id="b1">
      <div class="bidder-name">Bob</div>
      <label>Values B: <span class="val" id="v1-1">9</span>
        <input type="range" min="0" max="15" value="9" oninput="updateVal(1,1,this.value)">
      </label>
      <label>Values C: <span class="val" id="v1-2">6</span>
        <input type="range" min="0" max="15" value="6" oninput="updateVal(1,2,this.value)">
      </label>
      <label>Values B+C: <span class="val" id="v1-3">13</span>
        <input type="range" min="0" max="20" value="13" oninput="updateVal(1,3,this.value)">
      </label>
    </div>
    <div class="bidder" id="b2">
      <div class="bidder-name">Carol</div>
      <label>Values A: <span class="val" id="v2-0">6</span>
        <input type="range" min="0" max="15" value="6" oninput="updateVal(2,0,this.value)">
      </label>
      <label>Values C: <span class="val" id="v2-2">10</span>
        <input type="range" min="0" max="15" value="10" oninput="updateVal(2,2,this.value)">
      </label>
      <label>Values A+C: <span class="val" id="v2-3">14</span>
        <input type="range" min="0" max="20" value="14" oninput="updateVal(2,3,this.value)">
      </label>
    </div>
  </div>
  <button id="run" onclick="runVCG()">Run VCG</button>
  <div id="result" class="result hidden"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.vcg-wrap { padding: 0 2px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.4; }
.bidder-section { display: flex; gap: 10px; flex-wrap: wrap; margin-bottom: .8rem; }
.bidder { flex: 1; min-width: 150px; background: #f0f4f8; border: 1px solid #cdd9e5;
          border-radius: 10px; padding: .7rem .8rem; }
.bidder-name { font-weight: 700; font-size: .95rem; color: #1d3557; margin-bottom: .5rem; }
label { display: block; margin-bottom: .45rem; color: #333; font-size: .82rem; line-height: 1.3; }
.val { font-weight: 700; color: #1d3557; min-width: 18px; display: inline-block; }
input[type=range] { display: block; width: 100%; margin-top: 2px; accent-color: #1d3557; }
button { font: 600 14px system-ui; padding: .45rem 1.1rem; background: #1d3557;
         color: #fff; border: none; border-radius: 8px; cursor: pointer; margin-bottom: .8rem; }
button:hover { background: #16304d; }
.result { background: #eaf4ea; border: 1px solid #b2d8b2; border-radius: 10px; padding: .8rem 1rem; }
.result.hidden { display: none; }
.result h3 { margin: 0 0 .5rem; font-size: .95rem; color: #0a5c2a; }
.alloc-row { display: flex; gap: 8px; flex-wrap: wrap; margin-bottom: .5rem; }
.alloc-chip { background: #1d3557; color: #fff; border-radius: 6px;
              padding: .25rem .55rem; font-size: .8rem; font-weight: 600; }
.payment-table { width: 100%; border-collapse: collapse; font-size: .82rem; margin-top: .4rem; }
.payment-table th { text-align: left; color: #0a5c2a; padding: 2px 6px; border-bottom: 1px solid #b2d8b2; }
.payment-table td { padding: 3px 6px; }
.payment-table tr:nth-child(even) td { background: #d8f0d8; }
.welfare-row { margin-top: .5rem; font-size: .85rem; font-weight: 600; color: #1d3557; }
.expl { font-size: .78rem; color: #555; margin-top: .4rem; line-height: 1.4; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// VCG mechanism for 3 bidders and 3 items (A=0, B=1, C=2).
// Each bidder declares values for subsets. VCG:
//   1) Find allocation maximizing total declared value.
//   2) For each agent i, charge them the "externality":
//      (welfare of others WITHOUT agent i) - (welfare of others WITH agent i in the optimal allocation).
//
// Bidder values: bids[i] is a map from subset-bitmask to value.
// Items: A=bit0, B=bit1, C=bit2. Subsets: 0b001=A, 0b010=B, 0b100=C, 0b011=A+B, 0b110=B+C, 0b101=A+C, 0b111=A+B+C.

const ITEMS = ['A', 'B', 'C'];
const N_ITEMS = 3;
const N_BIDDERS = 3;

// Initial bid matrices indexed by [bidder][subset_mask]
// Bidder 0 = Alice: values A(001)=8, B(010)=5, A+B(011)=12, others=0
// Bidder 1 = Bob:   values B(010)=9, C(100)=6, B+C(110)=13, others=0
// Bidder 2 = Carol: values A(001)=6, C(100)=10, A+C(101)=14, others=0
const bids = [
  { 1:8, 2:5, 3:12 },   // Alice: A=8, B=5, A+B=12
  { 2:9, 4:6, 6:13 },   // Bob: B=9, C=6, B+C=13
  { 1:6, 4:10, 5:14 }   // Carol: A=6, C=10, A+C=14
];

// Slider label mapping: bidder -> index in their displayed labels -> subset mask
const SLIDER_MAP = [
  [1, 2, 3],   // Alice: A, B, A+B
  [2, 4, 6],   // Bob: B, C, B+C
  [1, 4, 5]    // Carol: A, C, A+C
];
const SLIDER_LABELS = [
  ['A', 'B', 'A+B'],
  ['B', 'C', 'B+C'],
  ['A', 'C', 'A+C']
];

function updateVal(bidder, idx, val) {
  const mask = SLIDER_MAP[bidder][idx];
  bids[bidder][mask] = Number(val);
  document.getElementById('v' + bidder + '-' + idx).textContent = val;
}

// Get bidder’s value for a subset bitmask
function bidVal(bidder, mask) {
  if (mask === 0) return 0;
  return bids[bidder][mask] || 0;
}

// Enumerate all feasible allocations (assign disjoint item subsets to bidders).
// Each allocation is an array [mask0, mask1, mask2] where masks are disjoint
// and cover some/all items.
function allAllocations(bidders) {
  const n = bidders.length;
  const results = [];
  // Each item independently assigned to one bidder or unassigned
  // Total assignments = (n+1)^3 (including unassigned=n)
  const total = Math.pow(n + 1, N_ITEMS);
  for (let t = 0; t < total; t++) {
    const alloc = new Array(n).fill(0);
    let tmp = t;
    let valid = true;
    for (let item = 0; item < N_ITEMS; item++) {
      const owner = tmp % (n + 1);
      tmp = Math.floor(tmp / (n + 1));
      if (owner < n) {
        alloc[owner] |= (1 << item);
      }
    }
    results.push(alloc);
  }
  return results;
}

// Find optimal allocation for a subset of bidders (by original indices),
// returns { alloc: [mask_per_bidder_in_subset], welfare }
function optimalAlloc(bidderIndices) {
  const allocations = allAllocations(bidderIndices);
  let bestW = -1, bestAlloc = null;
  for (const a of allocations) {
    let w = 0;
    for (let i = 0; i < bidderIndices.length; i++) {
      w += bidVal(bidderIndices[i], a[i]);
    }
    if (w > bestW) { bestW = w; bestAlloc = a.slice(); }
  }
  return { alloc: bestAlloc, welfare: bestW };
}

function maskToStr(mask) {
  return ITEMS.filter((_, i) => mask & (1 << i)).join('+') || '—';
}

function runVCG() {
  // Step 1: find globally optimal allocation
  const allBidders = [0, 1, 2];
  const { alloc, welfare } = optimalAlloc(allBidders);

  // Step 2: for each bidder i, compute externality payment
  // externality_i = (optimal welfare of others WITHOUT i) - (welfare of others in current optimal)
  const payments = [];
  for (let i = 0; i < N_BIDDERS; i++) {
    // Others’ welfare in full optimal (excluding agent i’s contribution)
    const othersWelfareInOptimal = alloc.reduce((s, m, j) => j !== i ? s + bidVal(j, m) : s, 0);
    // Optimal welfare of others WITHOUT agent i
    const others = allBidders.filter(x => x !== i);
    const { welfare: wOthersAlone } = optimalAlloc(others);
    // VCG payment = harm imposed = what others could have had minus what they get
    const payment = Math.max(0, wOthersAlone - othersWelfareInOptimal);
    payments.push(payment);
  }

  // Render result
  const names = ['Alice', 'Bob', 'Carol'];
  const resultEl = document.getElementById('result');
  resultEl.classList.remove('hidden');

  let allocHTML = '<h3>Efficient Allocation</h3><div class="alloc-row">';
  for (let i = 0; i < N_BIDDERS; i++) {
    if (alloc[i] > 0) {
      allocHTML += `<span class="alloc-chip">${names[i]}: ${maskToStr(alloc[i])}</span>`;
    }
  }
  allocHTML += '</div>';

  let tableHTML = '<table class="payment-table"><tr><th>Bidder</th><th>Gets</th><th>True Value</th><th>VCG Payment</th><th>Surplus</th></tr>';
  for (let i = 0; i < N_BIDDERS; i++) {
    const tv = bidVal(i, alloc[i]);
    const surplus = tv - payments[i];
    tableHTML += `<tr><td>${names[i]}</td><td>${maskToStr(alloc[i])}</td><td>${tv}</td><td>${payments[i].toFixed(1)}</td><td>${surplus.toFixed(1)}</td></tr>`;
  }
  tableHTML += '</table>';

  const welfareHTML = fmt('<div class="welfare-row">Total welfare: %welfare% | Total payments collected: %reduce%</div>', { welfare: welfare, reduce: payments.reduce((s, p) => s + p, 0).toFixed(1) });
  const explHTML = '<p class="expl">Each bidder’s payment = what others would have gained without them minus what others gain with them in this allocation. Bidding your true value is always optimal: overbidding risks overpaying, underbidding risks losing value.</p>';

  resultEl.innerHTML = allocHTML + tableHTML + welfareHTML + explHTML;

  // Log for verification
  console.log('Allocation:', alloc.map((m, i) => names[i] + ':' + maskToStr(m)).join(', '));
  console.log('Payments:', payments.map((p, i) => names[i] + ':' + p.toFixed(1)).join(', '));
  console.log('Total welfare:', welfare);
}
Result
Console

Notice how VCG works in two steps. First it finds the allocation that maximizes total declared value. Then it charges each winner the amount the other bidders would have gained if the winner simply hadn't participated — their externality. Because payment equals the harm you impose on others, bidding your true value is always optimal: overbidding risks overpaying, underbidding risks losing an item you value more than the payment would cost.

The Real Complexity

VCG is a solved problem in the strategic sense: the equilibrium analysis is complete and the optimality proof is watertight. William Vickrey, James Mirrlees, and collaborators established this definitively, earning Vickrey the 1996 Nobel Prize. But "strategically solved" does not mean "computationally easy."

  • The winner determination problem is NP-hard. In a combinatorial auction with n items and m bidders who can bid on any subset, finding the allocation that maximizes total welfare requires solving an integer program over 2n2^{n} possible bundles. With even 30 items this is infeasible by brute force.
  • VCG requires solving the problem n+1 times. Computing the externality for each of n agents means running the welfare-maximization once without that agent — so the already-hard core must be repeated many times.
  • Shill bidding undermines truthfulness. If the auctioneer can submit fake bids, or if a single entity splits into many agents, VCG's guarantees collapse. The mechanism is truthful only under the assumption that agents are independent.
  • Budget balance is sacrificed. VCG payments can be less than the revenue the seller could extract with other mechanisms. In some settings the auctioneer actually loses money (Green–Laffont impossibility).

This tension — strategically perfect but computationally intractable — is exactly why no single mechanism rules the real world. Practitioners use approximation algorithms, restricted-domain auctions, or ascending-bid formats (like the Combinatorial Clock Auction) that trade some theoretical purity for computational feasibility. See also the related question of Nash equilibrium and how linear programming can approximate the winner determination problem.

Where It Matters

VCG is not just a theorem — it shapes how billions of dollars in resources get allocated every day:

  • Spectrum auctions: national regulators (FCC, Ofcom) sell radio frequencies to telecoms. The FCC's Incentive Auction (2017, $19.8 billion) used VCG-inspired payments to clear and reassign spectrum bands efficiently.
  • Online advertising: Google's AdWords auction uses a generalized second-price mechanism closely related to VCG. By charging each advertiser approximately what they displace in the ranking, Google made truthful bidding (nearly) dominant and increased both revenue and relevance.
  • Cloud computing: cloud providers allocate virtual machines, bandwidth, and GPU slots. VCG-style pricing ensures that resources flow to whoever values them most, avoiding the deadweight loss of posted prices.
  • Public goods: classic economic theory uses VCG (as the Clarke tax) to finance public projects: each citizen's tax equals the harm their participation imposes on others, aligning private incentives with social efficiency.
  • Matching markets: hospital residency matches and school choice algorithms embed VCG-like logic to prevent strategic misreporting of preferences.

Understanding VCG means understanding why strategic truthfulness is rare and precious — and why the computational hardness of winner determination is one of the central open engineering problems in modern economics.

Conclusion

The VCG mechanism achieves something that seems almost paradoxical: it makes honesty the dominant strategy not by appealing to ethics, but by engineering the payment rule so that lying is never profitable. Every agent, no matter what others do, maximizes their own payoff by reporting their true values. That is a theorem, not a hope.

The cost is computational. Finding the welfare-maximizing allocation in a combinatorial auction is NP-hard, and VCG needs it solved repeatedly. So the real world compromises — approximations, restricted formats, ascending-bid procedures — but the VCG ideal remains the benchmark against which every auction mechanism is measured.

From Vickrey's 1961 sealed-bid insight to trillion-dollar spectrum auctions, the lesson is the same: when you align private incentives with social welfare through clever payment design, you unlock both efficiency and truth. The mechanism does the work that trust cannot.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/vcg-mechanism/Content licensed under CC BY-NC 4.0.