Deep Optimization
for Spectrum Repacking
By Neil Newman, Alexandre Fréchette, and Kevin Leyton-Brown
DOI: 10.1145/3107548
Abstract
Over 13 months in 2016–17 the U.S. Federal Communications
Commission conducted an “incentive auction” to repurpose
radio spectrum from broadcast television to wireless internet. In the end, the auction yielded $19.8 bn, $10.05 bn of which
was paid to 175 broadcasters for voluntarily relinquishing
their licenses across 14 Ultra High Frequency (UHF) channels.
Stations that continued broadcasting were assigned potentially new channels to fit as densely as possible into the channels that remained. The government netted more than $7 bn
(used to pay down the national debt) after covering costs
(including retuning). A crucial element of the auction design
was the construction of a solver, dubbed SAT-based Feasibility
Checker (SATFC), that determined whether sets of stations
could be “repacked” in this way; it needed to run every time a
station was given a price quote. This paper describes the process by which we built SATFC. We adopted an approach we dub
“deep optimization,” taking a data-driven, highly parametric,
and computationally intensive approach to solver design.
More specifically, to build SATFC we designed software that
could pair both complete and local-search SAT-encoded feasibility checking with a wide range of domain-specific techniques, such as constraint graph decomposition and novel
caching mechanisms that allow for reuse of partial solutions
from related, solved problems. We then used automatic algorithm configuration techniques to construct a portfolio of 8
complementary algorithms to be run in parallel, aiming to
achieve good performance on instances that arose in proprietary auction simulations. To evaluate the impact of our
solver in this paper, we built an open-source reverse auction
simulator. We found that within the short time budget
required in practice, SATFC solved more than 95% of the
problems it encountered. Furthermore, the incentive auction
paired with SATFC produced nearly optimal allocations in a
restricted setting and substantially outperformed other alternatives at national scale.
1. INTRODUCTION
Many devices, including broadcast television receivers and
cellphones, rely on the transmission of electromagnetic
signals. These signals can interfere with each other, so
transmission is regulated: For example, in the U.S., by the
Federal Communications Commission (FCC). Since electro-
magnetic spectrum suitable for wireless transmission is a
scarce resource and since it is difficult for a central authority
to assess the relative merits of competing claims on it, since
1994 the FCC has used spectrum auctions to allocate broad-
cast rights (see, e.g., Milgrom27). Many regulators around the
world have followed suit. At this point, in the US (as in many
other countries), most useful radio spectrum has been
This paper builds in part on an AAAI 2016 conference
publication by the same authors (see Fréchette et al. 11).
allocated. Interest has thus grown in the reallocation of radio
spectrum from less to more valuable uses. Spectrum currently allocated to broadcast television has received particular attention, for two reasons. First, over-the-air television
has been losing popularity with the rise of cable, satellite,
and streaming services. Second, the upper UHF frequencies
used by TV broadcasters are particularly well suited to wireless data transmission on mobile devices—for which
demand is growing rapidly—as they can penetrate walls and
travel long distances. 23
It thus made sense for at least some broadcasters to sell
their licenses to wireless internet providers willing to pay for
them. Ideally, these trades would have occurred bilaterally
and without government involvement, as occurs in many
other markets. However, two key obstacles made such trade
unlikely to produce useful, large-scale spectrum reallocation, both stemming from the fact that wireless internet services require large, contiguous blocks of spectrum to work
efficiently. First, a buyer’s decision about which block of
spectrum to buy would limit the buyer to trading only with
broadcasters holding licenses to parts of that block; it could
be hard or impossible to find such a block in which all broadcasters were willing to trade. Second, each of these broadcasters would have “holdout power,” meaning the
broadcaster could demand an exorbitant payment in
exchange for allowing the deal to proceed. The likely result
would have been very little trade, even if broadcasters valued
the spectrum much less than potential buyers.
A 2012 Act of Congress implemented a clever solution to
this problem. It guaranteed each broadcaster interference-free coverage in its broadcast area on some channel, but not
necessarily on its currently used channel. This meant that if a
broadcaster was unwilling to sell its license, it could instead
be moved to another channel, solving the holdout problem.
To free up the channel that would permit this move to take
place, broadcast rights could be bought from another station
in the appropriate geographical area, even if this second station did not hold a license for spectrum due for reallocation.
In what follows, we call such an interference-free reassignment of channels to stations a feasible repacking.
These trades and channel reassignments were coordinated via a novel spectrum auction run by the FCC between
March 2016 and April 2017, dubbed the Incentive Auction. It
consisted of two interrelated parts. The first was a forward
auction that sold large blocks of upper UHF spectrum to
interested buyers in a manner similar to previous auctions
of unallocated spectrum. The key innovation was the second