VCG combinatorial auction

The best allocation is solved for exactly, then each winner is charged the welfare the others lose by their presence. Truthful.

Bidding your true value is a dominant strategy here: it is at least as good as anything else you could do, whatever the other bidders do.

A worked example

The same two licences and the same three bids the greedy page just got wrong: A at 90 for the pair, B at 50 for north, C at 55 for south.

What the mechanism does, step by step

1. collect package bids Every bid is all-or-nothing: a bidder who wants two licences together is offering nothing at all for either one alone, which is exactly what separate single-item auctions cannot express. The offers are A bids 90 for {north, south}; B bids 50 for {north}; C bids 55 for {south}. One bidder may submit several bids, but they are alternatives — XOR — so at most one of them can be accepted.

   A: {north, south} = 90 | B: {north} = 50 | C: {south} = 55

2. item universe Nothing was listed for sale in advance. What is on offer is simply the union of everything anybody bid on: north, south. An item nobody names is not in the auction, and an item several bidders name can still go to only one of them.

   items = {north, south} (2)

3. solve for the best allocation Every feasible combination of bids is searched, not just the ones a single pass down the list would reach, and the best of them is C bids 55 for {south}; B bids 50 for {north} — worth 105 in total. This exhaustive step is what the payment rule below depends on, and it is why the auction refuses inputs above 12 items or 20 bids.

   55 + 50 = 105

4. greedy vs optimal Choosing the best set of bids to accept is NP-hard, so a practical auction runs the greedy rule and settles for what it finds. Greedy accepts A and totals 90; the exhaustive search accepts C, B and totals 105. Greedy gave up 15 by accepting A, which the best allocation leaves out, and no amount of care in the payment rule can win that back.

   gap = 105 - 90 = 15

5. price rule Each winner pays the harm their presence does to everybody else: what the other bidders could have collected had this one never shown up, minus what they actually collected alongside them. A winner's own bid never appears in their own bill — it only decides whether they win — so raising it can never raise their price and lowering it can only lose them the bundle, which is why bidding your true value for a bundle is dominant here. That guarantee rests entirely on the allocation being the optimal one: bolt these same formulas onto the greedy allocation and they stop being truthful, because a bidder can then shade a bid to change which bundles greedy happens to accept. It is a real trap in practice, not a footnote.

   p_i = W(without i) - (W(all) - b_i)

6. bundle price C takes {south}. Without C in the room the remaining bids could have been worth 90; alongside C they are worth 50. The difference, 40, is what C took away from everybody else, and it is the whole bill.

   p_C = 90 - (105 - 55) = 40

7. bundle price B takes {north}. Without B in the room the remaining bids could have been worth 90; alongside B they are worth 55. The difference, 35, is what B took away from everybody else, and it is the whole bill.

   p_B = 90 - (105 - 50) = 35

8. payments C tops the allocation and pays 40. Nobody is ever charged for value they did not take away from somebody else, so a winner who displaced nothing pays nothing at all.

   revenue = 40 + 35 = 75

How it came out

Solved exactly, B and C win — 105 of value rather than 90 — and each is charged the difference their presence made to everyone else. B pays what north cost the others, not the 50 they bid. Both properties matter and they are separate: the allocation is optimal because it is searched for rather than sorted into, and truthful bidding is safe because the price a winner pays is computed from everybody else's bids.

Run this auction step by step

The link carries the whole setup, so you can change a bid and watch what moves — and send the result to somebody else.

Read next

• Greedy combinatorial auction — Bids are accepted in descending order, skipping conflicts; each winner pays their own bid. Practical, not truthful.
• VCG position auction — The same slots to the same bidders, but each winner pays the externality they impose. Truthful.