Communications of the ACM
Deep Optimization For Spectrum Repacking
Credit: Getty Images
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 broadcast 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 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.
No entries found