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