Introduction

Imagine the government is selling radio-spectrum licenses, one per region. A phone company that wins California and Nevada can build one network across both — but winning California alone, stranded next to a rival, is worth far less. The value lives in the bundle, not in the pieces.

A combinatorial auction embraces this. Instead of selling items one at a time, it lets each bidder name a price for any bundle of items they want — "$10M for {CA, NV}", "$7M for {NV}", and so on. Bidders express exactly what things are worth to them together.

That flexibility comes with a sting. Once the bids are in, the auctioneer must answer one question: which set of bids do we accept to make the most money, without selling the same item twice? That innocent-sounding choice is the winner determination problem, and it is one of the genuinely hard problems in computer science.

Pick the Winners

Below are five items (A–E) and a list of bids, each on a bundle of items. Click bids to accept them — but two accepted bids may never share an item. Watch the revenue total climb, and try to beat the computer.

<p class="hint">Five items, A&ndash;E, are for sale. Each bid names a price for a <b>bundle</b>. Accept bids to earn their price &mdash; but two accepted bids may never share an item. Maximize revenue, then let the computer brute-force the best set.</p>
<div id="bids" class="bids"></div>
<div class="totals">
  <div class="t"><span>Your revenue</span><b id="rev">$0M</b></div>
  <div class="t"><span>Optimal</span><b id="opt">?</b></div>
</div>
<div class="status" id="status">Click bids to accept them.</div>
<div class="btns">
  <button id="find" type="button">Find optimal</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.bids { display: flex; flex-direction: column; gap: 6px; margin: .4rem 0; }
.bid { display: flex; align-items: center; gap: 10px; padding: .5rem .7rem;
       border: 1px solid #cdd9e3; border-radius: 10px; background: #f3f6f9; cursor: pointer;
       transition: all .12s; }
.bid:hover { background: #e8eef3; }
.bid.on { background: #1d3557; border-color: #16283f; color: #fff; }
.bid.blocked { opacity: .45; }
.bundle { display: flex; gap: 4px; }
.item { width: 26px; height: 26px; display: flex; align-items: center; justify-content: center;
        font: 700 13px ui-monospace, monospace; border-radius: 6px; background: #dfe7ee; color: #1d3557; }
.bid.on .item { background: #2c4a6e; color: #fff; }
.price { margin-left: auto; font: 700 15px system-ui, sans-serif; }
.totals { display: flex; gap: 1.4rem; margin: .7rem 0 .2rem; }
.t { font-size: .85rem; color: #555; }
.t b { display: block; font-size: 1.3rem; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Combinatorial-auction WINNER DETERMINATION. Each bid is a price on a bundle of items. A feasible accept-set is a set of bids that are pairwise item-disjoint (no item sold twice). Goal: maximize total price. This is weighted set packing / weighted independent set — NP-hard. Checking a set is a quick scan; finding the optimum brute-forces all 2^m subsets of the m bids.
const ITEMS = ['A','B','C','D','E'];
const BIDS = [
  { id:0, set:['A','B'],     price:7 },
  { id:1, set:['C'],         price:4 },
  { id:2, set:['B','C','D'], price:9 },
  { id:3, set:['A'],         price:5 },
  { id:4, set:['D','E'],     price:6 },
  { id:5, set:['E'],         price:3 },
  { id:6, set:['A','C','E'], price:10 }
];
BIDS.forEach(b => b.mask = b.set.reduce((m,i)=> m | (1 << ITEMS.indexOf(i)), 0));
const accepted = new Set();

// Feasible iff no two accepted bids share an item.
function usedMask(exclude){ let m=0; for(const id of accepted){ if(id===exclude) continue; m |= BIDS[id].mask; } return m; }
function revenue(){ let s=0; for(const id of accepted) s += BIDS[id].price; return s; }

function render(){
  const wrap = document.getElementById('bids'); wrap.innerHTML='';
  const others = usedMask(-2); // mask of all accepted bids
  BIDS.forEach(b => {
    const on = accepted.has(b.id);
    // a non-accepted bid is "blocked" if it collides with the current accept-set
    const collides = !on && (b.mask & usedMask(-1)) !== 0;
    const div = document.createElement('div');
    div.className = 'bid' + (on?' on':'') + (collides?' blocked':'');
    const bundle = b.set.map(i=>`<span class="item">${i}</span>`).join('');
    div.innerHTML = `<div class="bundle">${bundle}</div><span class="price">${b.price}M</span>`;
    div.addEventListener('click', ()=>{
      if(on){ accepted.delete(b.id); }
      else { if((b.mask & usedMask(-1))!==0){ setStatus('That bundle shares an item with one you already accepted.','bad'); render(); return; } accepted.add(b.id); }
      update(); render();
    });
    wrap.appendChild(div);
  });
  document.getElementById('rev').textContent = '


Notice the asymmetry. Checking your choice is effortless: confirm no item is sold twice, then add up the prices. Finding the accept-set that maximizes revenue is the hard part — press Find optimal and the computer tries every subset of bids that fits. With a handful of bids that is fine; add more overlapping bundles and the number of combinations explodes, the same wall you meet in P vs NP.

+revenue()+'M';
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function update(){
  const r = revenue();
  if(r===0) setStatus('Click bids to accept them.','');
  else setStatus(fmt('Accepted set is valid — revenue $%r%M.', { r: r }),'ok');
}

// Brute force: best item-disjoint subset of bids.
function findOptimal(){
  let best=0, bestSet=0, steps=0;
  for(let s=0; s<(1<<BIDS.length); s++){ steps++;
    let used=0, val=0, ok=true;
    for(let i=0;i<BIDS.length;i++) if(s&(1<<i)){
      if(used & BIDS[i].mask){ ok=false; break; }
      used |= BIDS[i].mask; val += BIDS[i].price;
    }
    if(ok && val>best){ best=val; bestSet=s; }
  }
  accepted.clear();
  for(let i=0;i<BIDS.length;i++) if(bestSet&(1<<i)) accepted.add(i);
  document.getElementById('opt').textContent = '


Notice the asymmetry. Checking your choice is effortless: confirm no item is sold twice, then add up the prices. Finding the accept-set that maximizes revenue is the hard part — press Find optimal and the computer tries every subset of bids that fits. With a handful of bids that is fine; add more overlapping bundles and the number of combinations explodes, the same wall you meet in P vs NP.

+best+'M';
  render();
  setStatus(fmt('Optimal revenue $%best%M, found after checking %steps% of %v% subsets.', { best: best, steps: steps, v: 1<<BIDS.length }),'ok');
  console.log('Optimal:', best, 'bids:', [...accepted].join(' '), '| checked', steps, 'subsets');
}
document.getElementById('find').addEventListener('click', findOptimal);
document.getElementById('reset').addEventListener('click', ()=>{ accepted.clear(); document.getElementById('opt').textContent='?'; render(); setStatus('Click bids to accept them.',''); });
render();
Result
Console

Notice the asymmetry. Checking your choice is effortless: confirm no item is sold twice, then add up the prices. Finding the accept-set that maximizes revenue is the hard part — press Find optimal and the computer tries every subset of bids that fits. With a handful of bids that is fine; add more overlapping bundles and the number of combinations explodes, the same wall you meet in P vs NP.

The Real Complexity

How hard is it to pick the winners? Not the bidding — the optimization.

  • Checking a proposed set of winners is trivial: verify no item appears in two accepted bids, then sum the prices.
  • Brute force tries every subset of the bids and keeps the best feasible one — 2ᵐ possibilities for m bids, hopeless once there are more than a few dozen.
  • It's NP-hard. Winner determination is exactly the weighted set packing problem: choose a maximum-value collection of pairwise-disjoint sets. That is equivalent to weighted maximum independent set — make a graph with one node per bid and an edge between any two bids that share an item; an optimal accept-set is a maximum-weight independent set. Both are classic NP-hard problems, so no algorithm is known that solves every instance efficiently.
  • Even approximating it well is hard: with no restriction on the bundles, you cannot guarantee getting close to the best revenue in polynomial time (unless P = NP).

That is the punchline: the freedom that makes combinatorial auctions so expressive is the very thing that makes choosing the winners intractable. The auctioneer's "just pick the best bids" is a genuine instance of the same difficulty behind P vs NP.

Where It Matters

"Allocate scarce items to whoever values the right combination most" is one of the most valuable problems a market can solve, and combinatorial auctions are how it's done:

  • Spectrum auctions: the U.S. FCC and regulators worldwide have raised tens of billions selling radio licenses where regional bundles matter enormously.
  • Transportation and logistics: shippers auction off bundles of trucking lanes; carriers bid on routes that combine efficiently.
  • Airport landing slots and procurement: bundling complementary slots or supplies lets bidders express real operational value.
  • Cloud and computing resources: allocating combinations of CPU, memory and bandwidth to jobs is the same packing question.

Because the exact problem is intractable, real auctions lean on the toolkit of hard optimization — integer programming solvers, branch-and-bound and clever bid restrictions. The same core links to set cover and the packing side of knapsack-style allocation.

Conclusion

Combinatorial auctions hide a beautiful tension: letting bidders speak in bundles captures what items are really worth together, but it hands the auctioneer a problem — pick the disjoint bids that maximize revenue — that is NP-hard. Checking any proposed outcome stays instant; finding the best one is as hard as anything in computer science.

So the next time a spectrum sale or a logistics tender quietly mentions "optimal allocation," remember what's underneath. It's P vs NP wearing a price tag — and the reason these auctions run on heavy-duty solvers instead of a simple sort.

Share this article

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

Comments

Loading comments...

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