Introduction

Every time you make a phone call or stream a video, you are using radio spectrum — invisible slices of the electromagnetic band that governments own and licence out. Because one broadcaster's signal can drown out another's, regulators must assign non-overlapping bands. Historically they did so by auction.

The trouble is that spectrum bands are complementary goods: a mobile operator that wins the 700 MHz band is far better off if it also wins the adjacent 800 MHz band. Buying them separately at independent auctions risks paying for both and getting only one — the exposure problem. The Combinatorial Clock Auction (CCA), first used by the UK's Ofcom in 2008, was designed to solve this.

A CCA runs in two phases. In the clock phase, the auctioneer announces per-unit prices that rise each round until demand no longer exceeds supply. Bidders respond only with how many units they want at the current price — a simple up/down decision. Once the clock stops, a supplementary round lets bidders submit sealed package bids: "I will pay $X for this exact combination of lots." The auctioneer then solves a Winner Determination Problem (WDP): which non-overlapping set of package bids maximises total revenue? That last step is NP-hard.

Watch the Clock Rise

Below is a simplified CCA with three spectrum bands and four bidders. During the clock phase prices rise each round; each bidder holds demand as long as the price stays below their private value. When every band is wanted by exactly one bidder, the clock stops and the solver picks the maximum-revenue assignment.

<!-- Combinatorial Clock Auction demo: clock phase raises prices until demand meets supply, then WDP solver picks winners. -->
<div class="auction-wrap">
  <div class="phase-label" id="phase-label">Clock Phase</div>
  <div class="bands-row" id="bands-row"></div>
  <div class="bidders-section">
    <div class="section-title">Bidders</div>
    <div id="bidder-cards"></div>
  </div>
  <div class="status-bar" id="status-bar"></div>
  <div class="btns">
    <button id="btn-next" type="button">Next Round</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="result-panel" id="result-panel" style="display:none">
    <div class="result-title">Winning Assignment</div>
    <div id="result-rows"></div>
    <div class="result-revenue" id="result-revenue"></div>
  </div>
</div>

/* Layout and style for the CCA demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.auction-wrap { max-width: 520px; margin: 0 auto; }
.phase-label { font-size: .82rem; font-weight: 700; text-transform: uppercase;
  letter-spacing: .06em; color: #1d3557; background: #dce8f5; border-radius: 6px;
  padding: .28rem .7rem; display: inline-block; margin-bottom: .6rem; }
.bands-row { display: flex; gap: .6rem; margin-bottom: .8rem; flex-wrap: wrap; }
.band-card { flex: 1; min-width: 110px; border: 1.5px solid #cdd9e3; border-radius: 10px;
  padding: .55rem .7rem; background: #f0f5fa; }
.band-name { font-weight: 700; font-size: .95rem; color: #1d3557; }
.band-price { font-size: 1.1rem; font-weight: 700; color: #0a7d33; margin: .1rem 0; }
.band-demand { font-size: .78rem; color: #555; }
.section-title { font-size: .8rem; font-weight: 700; text-transform: uppercase;
  letter-spacing: .05em; color: #888; margin-bottom: .4rem; }
#bidder-cards { display: grid; grid-template-columns: 1fr 1fr; gap: .5rem; margin-bottom: .7rem; }
.bidder-card { border: 1.5px solid #e0e0e0; border-radius: 8px; padding: .45rem .6rem;
  font-size: .85rem; background: #fafafa; }
.bidder-name { font-weight: 700; color: #333; margin-bottom: .2rem; }
.bidder-wants { color: #1d3557; font-size: .8rem; }
.bidder-card.dropped { opacity: .4; }
.bidder-card.won { border-color: #0a7d33; background: #eafbee; }
.status-bar { font-size: .95rem; font-weight: 600; min-height: 1.4em;
  margin: .4rem 0; color: #555; }
.status-bar.alert { color: #c92f3c; }
.status-bar.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui; padding: .42rem .9rem; border: 1px solid #1d3557;
  background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.result-panel { border: 2px solid #0a7d33; border-radius: 10px; padding: .8rem 1rem;
  background: #eafbee; }
.result-title { font-weight: 700; font-size: .95rem; color: #0a7d33; margin-bottom: .5rem; }
.result-row { font-size: .88rem; margin-bottom: .25rem; }
.result-revenue { font-weight: 700; font-size: 1rem; margin-top: .5rem; border-top: 1px solid #b6dfc0;
  padding-top: .4rem; color: #065220; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Winner Determination Problem (WDP): find a non-overlapping subset of bids that maximises total revenue. NP-hard in general.
// Clock phase: prices rise each round until each band is demanded by at most one bidder.

// Three spectrum bands, each with supply of 1 unit.
const BANDS = [
  { id: 'A', label: 'Band A (700 MHz)', supply: 1 },
  { id: 'B', label: 'Band B (800 MHz)', supply: 1 },
  { id: 'C', label: 'Band C (900 MHz)', supply: 1 }
];

// Four bidders, each with a private value for each band.
// Private values: bidder pays up to this price for the band.
const BIDDERS = [
  { id: 0, name: 'Alpha Mobile', values: { A: 120, B: 80, C: 50 } },
  { id: 1, name: 'Beta Wireless',  values: { A: 90,  B: 110, C: 70 } },
  { id: 2, name: 'Gamma Telecom', values: { A: 60,  B: 65,  C: 100 } },
  { id: 3, name: 'Delta Net', values: { A: 75,  B: 95,  C: 85 } }
];

const PRICE_STEP = 20;
const START_PRICE = 40;

let prices = {};
let round = 0;
let phase = 'clock';
let dropped = new Set();
let assignment = null;

function init() {
  prices = {};
  BANDS.forEach(b => { prices[b.id] = START_PRICE; });
  round = 0;
  phase = 'clock';
  dropped = new Set();
  assignment = null;
  document.getElementById('result-panel').style.display = 'none';
  document.getElementById('btn-next').disabled = false;
  document.getElementById('btn-next').textContent = 'Next Round';
  render();
  setStatus('Press Next Round to start the clock.', '');
}

// A bidder demands a band iff their value meets or exceeds the current price and they have not dropped out.
function demandFor(bidderId, bandId) {
  if (dropped.has(bidderId)) return false;
  return BIDDERS[bidderId].values[bandId] >= prices[bandId];
}

function totalDemand(bandId) {
  return BIDDERS.filter((_, i) => demandFor(i, bandId)).length;
}

function isCleared() {
  return BANDS.every(b => totalDemand(b.id) <= 1);
}

// Brute-force WDP solver: try all 2^n subsets of active bidders and find the feasible assignment with highest revenue.
function solveWDP() {
  // Enumerate all subsets of active bidders.
  const active = BIDDERS.filter((_, i) => !dropped.has(i));
  const n = active.length;
  let best = { revenue: 0, picks: [] };
  for (let mask = 0; mask < (1 << n); mask++) {
    const chosen = active.filter((_, i) => mask & (1 << i));
    const used = new Set();
    let feasible = true;
    let revenue = 0;
    for (const b of chosen) {
      // Assign the band that this bidder values most among still-available bands.
      let allocBand = null;
      for (const band of BANDS) {
        if (!used.has(band.id) && b.values[band.id] >= prices[band.id]) {
          if (allocBand === null || b.values[band.id] > b.values[allocBand]) allocBand = band.id;
        }
      }
      if (!allocBand) { feasible = false; break; }
      used.add(allocBand);
      revenue += prices[allocBand];
    }
    if (feasible && revenue > best.revenue) best = { revenue, picks: chosen.map(b => ({ bidder: b.id, band: [...used][chosen.indexOf(b)] })) };
  }
  // Fallback: assign each band to its highest-valued active bidder (one band per bidder).
  if (best.picks.length === 0) {
    const usedB = new Set();
    const picks = [];
    for (const band of BANDS) {
      let winner = null, winVal = -1;
      for (const b of BIDDERS) {
        if (!dropped.has(b.id) && b.values[band.id] >= prices[band.id] && b.values[band.id] > winVal) {
          winner = b; winVal = b.values[band.id];
        }
      }
      if (winner && !picks.some(p => p.bidder === winner.id)) {
        picks.push({ bidder: winner.id, band: band.id });
        usedB.add(band.id);
        best.revenue += prices[band.id];
      }
    }
    best.picks = picks;
  }
  return best;
}

function render() {
  const bandsRow = document.getElementById('bands-row');
  bandsRow.innerHTML = '';
  BANDS.forEach(b => {
    const card = document.createElement('div');
    card.className = 'band-card';
    const d = totalDemand(b.id);
    card.innerHTML = `<div class="band-name">${b.label}</div>
      <div class="band-price">${prices[b.id]}</div>
      <div class="band-demand">${i18nFmt('%d% bidder(s) want this', { d })}</div>`;
    bandsRow.appendChild(card);
  });

  const bidderCards = document.getElementById('bidder-cards');
  bidderCards.innerHTML = '';
  BIDDERS.forEach(b => {
    const card = document.createElement('div');
    const isDrop = dropped.has(b.id);
    const isWon = assignment && assignment.picks.some(p => p.bidder === b.id);
    card.className = 'bidder-card' + (isDrop ? ' dropped' : '') + (isWon ? ' won' : '');
    const wants = BANDS.filter(band => demandFor(b.id, band.id)).map(band => band.label).join(', ') || 'no demand';
    card.innerHTML = `<div class="bidder-name">${b.name}</div>
      <div class="bidder-wants">${isDrop ? 'dropped out' : i18nFmt('wants: %wants%', { wants })}</div>`;
    bidderCards.appendChild(card);
  });

  document.getElementById('phase-label').textContent =
    phase === 'clock' ? 'Clock Phase' : 'Result';
}

function setStatus(msg, cls) {
  const el = document.getElementById('status-bar');
  el.textContent = msg;
  el.className = 'status-bar' + (cls ? ' ' + cls : '');
}

function nextRound() {
  if (phase !== 'clock') return;
  round++;

  // Bidders who want nothing at current prices drop out.
  BIDDERS.forEach(b => {
    if (!dropped.has(b.id)) {
      const hasAny = BANDS.some(band => demandFor(b.id, band.id));
      if (!hasAny) dropped.add(b.id);
    }
  });

  if (isCleared()) {
    phase = 'wdp';
    document.getElementById('btn-next').disabled = true;
    assignment = solveWDP();
    render();
    showResult();
    return;
  }

  // Raise prices on over-demanded bands.
  BANDS.forEach(b => {
    if (totalDemand(b.id) > 1) prices[b.id] += PRICE_STEP;
  });

  render();
  setStatus(i18nFmt('Round %r% — prices rise on contested bands.', { r: round }), '');
}

function showResult() {
  const panel = document.getElementById('result-panel');
  panel.style.display = 'block';
  const rows = document.getElementById('result-rows');
  rows.innerHTML = '';
  if (assignment && assignment.picks.length > 0) {
    assignment.picks.forEach(p => {
      const b = BIDDERS[p.bidder];
      const band = BANDS.find(x => x.id === p.band);
      const div = document.createElement('div');
      div.className = 'result-row';
      div.textContent = i18nFmt('%name% wins %band% at $%price%', { name: b.name, band: band ? band.label : p.band, price: prices[p.band] });
      rows.appendChild(div);
    });
    document.getElementById('result-revenue').textContent =
      i18nFmt('Total revenue: $%total%', { total: assignment.revenue });
    setStatus('Market cleared — winning assignment found.', 'ok');
  } else {
    setStatus('No feasible assignment found.', 'alert');
  }
}

document.getElementById('btn-next').addEventListener('click', nextRound);
document.getElementById('btn-reset').addEventListener('click', init);
init();
Result
Console

Notice what happens when two bidders both covet the same band right up to a high price: the solver must try every possible assignment to confirm which one gives the best total. With only a handful of bidders and bands this is instant; in a real FCC auction with hundreds of licences the search space is 2n2^{n} and only heuristics keep it tractable.

The Real Complexity

The Winner Determination Problem (WDP) asks: given a set of package bids, each covering some items and offering a price, find a non-overlapping subset that maximises total revenue. Formally it is a variant of weighted set packing, which is NP-hard.

  • Checking a proposed allocation is easy: confirm no two chosen packages share an item, then add the prices.
  • Brute force tries all 2m2^{m} subsets of mm bids — hopeless once mm reaches the dozens.
  • It's NP-hard (Sandholm, 2002). Even worse, the WDP is hard to approximate: no polynomial-time algorithm can guarantee revenue within a constant factor of optimal unless P vs NP collapses.
  • Inapproximability follows from the hardness of maximum independent set, which cannot be approximated within n1−εn^{1-\varepsilon} for any ε>0\varepsilon > 0 under standard assumptions.

Real auctioneers (FCC, Ofcom, Industry Canada) run branch-and-bound solvers with problem-specific cuts. These work well on typical instances but have no worst-case polynomial guarantee. The clock phase is cleverly designed to reduce the number of competitive bids and shrink the effective search space — yet the NP-hard core remains.

The WDP is related to other hard problems you may know: it generalises set cover and can be encoded as an integer program, which in the worst case is again intractable.

Where It Matters

The CCA format spread quickly once its efficiency gains were demonstrated, and the underlying WDP appears wherever goods come in bundles:

  • Radio spectrum: the UK 4G auction (2013), Canada's 700 MHz auction (2014), and the FCC's US incentive auctions all used CCA-style designs; billions of dollars in revenue depend on the WDP solver running in time.
  • Airport take-off and landing slots: airlines want matched departure/arrival pairs; selling them separately creates the same exposure problem as spectrum.
  • Electricity and gas markets: power plants bid on generation schedules that are only profitable as whole blocks; a combinatorial market clears them jointly.
  • Procurement and logistics: a buyer purchasing trucks, drivers and fuel can insist on full packages rather than risk half a fleet.
  • Cloud compute resources: a job needing CPUs, GPUs and memory together is a natural package bid against a resource pool.

In every case the economic benefit — no exposure risk, higher efficiency — comes at the cost of an NP-hard clearing problem. The tension between "what bidders want to express" and "what computers can solve quickly" is one of the defining engineering problems in modern market design.

Conclusion

The Combinatorial Clock Auction is a triumph of economic engineering: rising prices elicit honest demand, package bids eliminate the exposure problem, and billions in spectrum value flow to the highest-value operators. Yet at the centre of every CCA sits an NP-hard Winner Determination Problem — a combinatorial search no one knows how to shortcut in general.

The auctioneers win the race against complexity in practice by exploiting structure in real bids: few packages genuinely conflict, and branch-and-bound solvers finish in minutes. But the worst case is always there, lurking. The next time your phone locks onto a clean signal, remember: someone's solver found a nearly-optimal assignment out of an astronomically large search space, and there is no proof they can always do it fast. That is P vs NP hiding inside the airwaves.

Share this article

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

Comments

Loading comments...

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