Greedy combinatorial auction
Bids are accepted in descending order, skipping conflicts; each winner pays their own bid. Practical, not truthful.
Bidding your true value is not dominant here. A bidder who knows something about their rivals can do better by bidding something else, and the worked example below shows what and why.
A worked example
Two licences, north and south. A wants both together and bids 90 for the pair; B wants north alone for 50 and C wants south alone for 55. Bidders here bid on bundles, all or nothing, because half a network is worth less than half of a network.
| Bidder | Bundle | Worth to them | Bid |
|---|---|---|---|
| A | north, south | 90 | 90 |
| B | north | 50 | 50 |
| C | south | 55 | 55 |
What the mechanism does, step by step
- 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 - 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) - consider bid A's 90 for {north, south} is accepted: none of those items is spoken for and this bidder has not already won something else.
A: {north, south} at 90 - consider bid C's 55 for {south} is skipped: south already went to A. Greedy never reconsiders a bid it has already accepted, which is precisely how it loses welfare.
C: {south} at 55 - consider bid B's 50 for {north} is skipped: north already went to A. Greedy never reconsiders a bid it has already accepted, which is precisely how it loses welfare.
B: {north} at 50 - 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
- price rule Every winner simply pays their own bid — first price, one bundle at a time. Nothing here charges a bidder for the harm they do to anybody else, and nothing protects a winner from having offered more than they had to, so wherever there is room to shade a bid down and still be accepted, doing so is pure profit and bidding your true value for a bundle is not a best reply. On top of that the allocation being charged for is greedy's, not the optimal one.
p_i = b_i
- payments The winners hand over exactly what they offered: A pays 90. Everybody whose bid was skipped pays nothing and gets nothing.
revenue = 90
How it came out
| Winner | A |
|---|---|
| Everyone who won something | A -> ['north', 'south'] |
| Price paid by the winner | 90 |
| Seller revenue | 90 |
| Value created | 90 |
| Went to whoever valued it most | no |
| Bidder | Paid | Ended up with |
|---|---|---|
| A | 90 | 0 |
| B | 0 | 0 |
| C | 0 | 0 |
Greedy takes the biggest bid first — A's 90 — and then has nothing left to give B or C. Total value created: 90. But B and C together were worth 105, and a solver that looked ahead would have said so. This page is the argument for why combinatorial auctions need exact winner determination and not a sensible-looking sort, and the VCG page runs these same three bids to show the difference.
The link carries the whole setup, so you can change a bid and watch what moves — and send the result to somebody else.