Combinatorial Clock Auction

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.

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.

<!-- {{c_intro}} -->
<div class="auction-wrap">
  <div class="phase-label" id="phase-label">{{lbl_clock_phase}}</div>
  <div class="bands-row" id="bands-row"></div>
  <div class="bidders-section">
    <div class="section-title">{{lbl_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">{{btn_next_round}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="result-panel" id="result-panel" style="display:none">
    <div class="result-title">{{lbl_result_title}}</div>
    <div id="result-rows"></div>
    <div class="result-revenue" id="result-revenue"></div>
  </div>
</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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 $2^{n}$ and only heuristics keep it tractable.

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 $2^{m}$ subsets of $m$ bids — hopeless once $m$ 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 $n^{1-\varepsilon}$ for any $\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.

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.

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.