Bundles don't add up
These bidders want combinations, not items — a pair is worth more than its halves. Greedy grabs the best-looking bid first and leaves money behind.
Run with Greedy combinatorial auction. Here is that auction, run once.
| Bidder | Bundle | Worth to them | Bid |
|---|---|---|---|
| A | north, south | 100 | 100 |
| B | north | 60 | 60 |
| C | south | 55 | 55 |
| D | north, south | 90 | 90 |
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 100 for {north, south}; B bids 60 for {north}; C bids 55 for {south}; D bids 90 for {north, south}. One bidder may submit several bids, but they are alternatives — XOR — so at most one of them can be accepted.
A: {north, south} = 100 | B: {north} = 60 | C: {south} = 55 | D: {north, south} = 90 - 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 100 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 100 - consider bid D's 90 for {north, south} is skipped: north, south already went to A. Greedy never reconsiders a bid it has already accepted, which is precisely how it loses welfare.
D: {north, south} at 90 - consider bid B's 60 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 60 - 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 - 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 100; the exhaustive search accepts B, C and totals 115. 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 = 115 - 100 = 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 100. Everybody whose bid was skipped pays nothing and gets nothing.
revenue = 100
How it came out
| Winner | A |
|---|---|
| Everyone who won something | A -> ['north', 'south'] |
| Price paid by the winner | 100 |
| Seller revenue | 100 |
| Value created | 100 |
| Went to whoever valued it most | no |
| Bidder | Paid | Ended up with |
|---|---|---|
| A | 100 | 0 |
| B | 0 | 0 |
| C | 0 | 0 |
| D | 0 | 0 |
Open this example in the walkthrough
The link carries the whole setup, so you can change a bid and watch what moves — and send the result to somebody else.