Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Efficient feasibility checking in reverse clock auctions for radio spectrum Newman, Neil 2017

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2017_february_newman_neil.pdf [ 6.02MB ]
Metadata
JSON: 24-1.0340850.json
JSON-LD: 24-1.0340850-ld.json
RDF/XML (Pretty): 24-1.0340850-rdf.xml
RDF/JSON: 24-1.0340850-rdf.json
Turtle: 24-1.0340850-turtle.txt
N-Triples: 24-1.0340850-rdf-ntriples.txt
Original Record: 24-1.0340850-source.json
Full Text
24-1.0340850-fulltext.txt
Citation
24-1.0340850.ris

Full Text

Efficient Feasibility Checking in Reverse Clock Auctionsfor Radio SpectrumbyNeil NewmanBA.Sc. in Engineering Science, University of Toronto, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)January 2017c© Neil Newman, 2017AbstractWe investigate the problem of building a feasibility checker to repack stations in thereverse auction part of the FCC’s ongoing, multi-billion-dollar “incentive auction”.In this work, we describe the design of a feasibility checker, SATFC, that has beenadopted by the FCC for use in the incentive auction. We also construct a reverseauction simulator both in order to evaluate SATFC and also to gain insight into howthe performance of the feasibility checker impacts the overall cost and efficiency ofthe auction. Through running simulations that differ only in the feasibility checkerused, we show that the feasibility checker has a significant impact on auction costand efficiency.iiPrefaceA significant fraction of Chapter 3 was published in the Thirtieth AAAI Conferenceon Artificial Intelligence held in 2016 as “Solving the Station Repacking Problem”[17]. This paper was authored by Alexandre Fre´chette, myself, and my supervisorKevin Leyton-Brown. I was involved in writing text, running experiments, analyz-ing data, and coding SATFC. The remainder of this thesis has not been publishedelsewhere. I wrote the code for the simulator described in Chapter 4, and performedall of the experiments and data analysis in Chapter 5.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 The Reverse Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 The Reverse Auction Limited to UHF Stations . . . . . . . . . . . 62.1.1 Computing Prices . . . . . . . . . . . . . . . . . . . . . . 72.1.2 Scoring Rule . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Generalizing the Reverse Auction to Include VHF Stations . . . . 82.2.1 Computing Prices with Multiple Bands . . . . . . . . . . 92.2.2 Placing Bids . . . . . . . . . . . . . . . . . . . . . . . . 112.2.3 Bid Processing . . . . . . . . . . . . . . . . . . . . . . . 112.2.4 Provisional Winners . . . . . . . . . . . . . . . . . . . . 122.2.5 Removing Stations That Can Never Become Winners . . . 12iv2.2.6 Termination . . . . . . . . . . . . . . . . . . . . . . . . . 133 Designing an Efficient Feasibility Checker . . . . . . . . . . . . . . . 143.1 The Station Repacking Problem . . . . . . . . . . . . . . . . . . 143.2 Structure of Constraints . . . . . . . . . . . . . . . . . . . . . . . 153.3 Structure of Station Repacking Problems in the Reverse Auction . 163.4 Complete and Local Search Solvers . . . . . . . . . . . . . . . . 173.5 Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.5.1 MIP Encoding . . . . . . . . . . . . . . . . . . . . . . . 183.5.2 SAT Encodings . . . . . . . . . . . . . . . . . . . . . . . 183.6 Using the Previous Solution . . . . . . . . . . . . . . . . . . . . 203.6.1 Locally Altering the Previous Solution . . . . . . . . . . . 203.6.2 Starting Near the Previous Solution . . . . . . . . . . . . 213.7 Problem Simplification . . . . . . . . . . . . . . . . . . . . . . . 223.7.1 Arc Consistency . . . . . . . . . . . . . . . . . . . . . . 223.7.2 Unconstrained Station Removal . . . . . . . . . . . . . . 223.7.3 Problem Decomposition . . . . . . . . . . . . . . . . . . 243.8 Meta-Algorithmic Techniques . . . . . . . . . . . . . . . . . . . 243.9 Containment Caching . . . . . . . . . . . . . . . . . . . . . . . . 253.10 SATFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Designing a Reverse Auction Simulator . . . . . . . . . . . . . . . . 314.1 Station Bidding Model . . . . . . . . . . . . . . . . . . . . . . . 314.2 Station Valuation Model . . . . . . . . . . . . . . . . . . . . . . 324.3 Determining Clearing Target . . . . . . . . . . . . . . . . . . . . 334.4 Feasibility Checker . . . . . . . . . . . . . . . . . . . . . . . . . 344.5 Revisiting Timeouts . . . . . . . . . . . . . . . . . . . . . . . . . 344.6 Reusing Solutions Within a Simulation . . . . . . . . . . . . . . . 365 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.1 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.2 Creating a Test Set of Non-Trivial Problems . . . . . . . . . . . . 395.3 Evaluating Test Set Performance . . . . . . . . . . . . . . . . . . 395.4 Containment Cache Evaluation . . . . . . . . . . . . . . . . . . . 42v5.5 Simulations with Different Feasibility Checkers . . . . . . . . . . 435.5.1 Comparing Reverse Auction Outcomes . . . . . . . . . . 435.5.2 Comparing the Reverse Auction and VCG . . . . . . . . . 455.5.3 National Simulation Results . . . . . . . . . . . . . . . . 476 Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . 51Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53viList of TablesTable 3.1 A breakdown of the different solvers composing SAT-based Fea-sibility Checker (SATFC) showing the different ideas from thischapter that are used in each algorithm. . . . . . . . . . . . . . 30Table 5.1 A breakdown of the marginal value of adding each new config-uration to our portfolio by building the portfolio greedily. . . . 41viiList of FiguresFigure 3.1 Interference graph derived from the Federal CommunicationsCommission (FCC)’s November 2015 constraint data [14]. . . 17Figure 3.2 The first two subproblems in a series of applying the “locallyaltering the previous solution” method. In 3.2a we allow thenewly added station (blue) and its neighbors (green) to take onany channel in their domains, but hold the remaining stations(orange) fixed on their channels. If a feasible solution cannotbe found in the first subproblem, we unfix neighbors of neigh-bors and try again (see 3.2b). . . . . . . . . . . . . . . . . . . 21Figure 3.3 This figure shows a solution to a graph coloring problem Sthat can trivially be made into a solution for the graph coloringproblem S′ by restricting the solution for S to vertices in S′.This is analogous to how our Propositional Satisfiability (SAT)cache works. . . . . . . . . . . . . . . . . . . . . . . . . . . 27Figure 3.4 Translating six sets (left) into integers (right) according to asecondary cache ordering. . . . . . . . . . . . . . . . . . . . 28Figure 3.5 A visualization of looking up a superset in a secondary cache.Only one secondary cache is shown in these figures, but mul-tiple secondary caches can be used to decrease the number ofelements to search over. . . . . . . . . . . . . . . . . . . . . 29Figure 4.1 An illustration of the greedy feasibility checker. Only the newlyadded station (blue) can vary on its domain, other stations areall fixed on their channels. . . . . . . . . . . . . . . . . . . . 35viiiFigure 5.1 Empirical Cumulative Distribution Function (ECDF) of run-times for default configurations of Mixed-Integer Programming(MIP) and SAT solvers on our test set. The legend is orderedby percentage of problems solved before the cutoff. The barsshow fraction of SAT and unsatifiable (UNSAT) instances binnedby their (fastest) runtime. Although present, unsatisfiable in-stances form an insignificant portion of instances solved. . . . 40Figure 5.2 SATFC performance on test set broken down by configuration(numbers in names correspond to Table 5.1). The bold red lineis the parallel portfolio performance. . . . . . . . . . . . . . . 42Figure 5.3 Bar chart where each bar represents the fraction of instancessolvable by a cache filled with problems from the other auctions. 43Figure 5.4 Interference graph of the set of 218 ultra high frequency (UHF)stations within two edges of a New York station. Each edgerepresents the existence of at least one pairwise binary con-straint between two stations under a 126 MHz clearing target. 48Figure 5.5 Fraction of Vickrey-Clarke-Groves (VCG) cost versus fractionof VCG value loss plotted for three different feasibility check-ers (indicated by colors) for five different value profiles (indi-cated by markers). All VCG points lie at (1,1). SATFC 2.3.1and the best single configuration had equivalent outcomes onthe second value profile (the markers coincide). . . . . . . . . 49Figure 5.6 Value loss and cost of national simulations using three differ-ent feasibility checkers for 20 value profiles. Both axes arenormalized by the cost and value loss of the correspondingSATFC 2.3.1 simulation. The figure also contains a secondSATFC 2.3.1 series which revisit timeouts. . . . . . . . . . . . 50ixGlossaryFCC Federal Communications CommissionSATFC SAT-based Feasibility CheckerVHF very high frequencyUHF ultra high frequencyLVHF lower VHFHVHF higher VHFBIA BIA KelseyNAB National Association of BroadcastersSAT Propositional SatisfiabilityUNSAT unsatifiableMIP Mixed-Integer ProgrammingSMAC Sequential Model-based Algorithm ConfigurationALO at least oneAMO at most oneNP nondeterministic polynomial timeVCG Vickrey-Clarke-GrovesxCSP Constraint Satisfaction ProblemAC-3 Arc Consistency Algorithm #3ECDF Empirical Cumulative Distribution FunctionxiAcknowledgmentsI would like to thank my supervisor Kevin Leyton-Brown for all of his supportthroughout my degree and for giving me the opportunity to work on such an ex-citing project. I would also like to thank Alexandre Fre´chette, who helped mesettle into graduate school by providing mentoring and guidance, and for layingthe groundwork for this research direction.I am indebted to Paul Milgrom for many helpful conversations on the topic ofthe incentive auction and for his efforts in transforming my research into softwareused in production. I also want to recognize Ilya Segal for providing clarifica-tions of the incentive auction rules and for his and Paul’s valuable inputs on thesimulation experiments.I gratefully acknowledge support from Auctionomics and the FCC.I am grateful to Hu Fu for taking the time to be my second reader.SATFC was enhanced by the contributions of several undergraduate students,of which I had the pleasure of working directly with Paul Cernek and Emily Chen.Thanks for all of your hard work!Lastly, I want to thank everyone in our GTDT research group—Jason, Chris,Alice, Lars, James and Hedayat—for many stimulating conversations, both re-search related and not. The positive and friendly lab culture has been one of myfavorite parts of graduate school.xiiFor Mom, Dad, and Robert. Thanks for all your support.xiiiChapter 1IntroductionMany devices, including cell phones, operate by sending and receiving electro-magnetic signals. These signals can interfere with each other, so transmissionis regulated to ensure that devices can effectively communicate. In the US, thisregulation is enforced by the Federal Communications Commission (FCC), a gov-ernment body that allocates licenses to broadcast over specific frequency bandsin a geographic region. Since electromagnetic spectrum bands suitable to wire-less transmission are scarce, the FCC has used spectrum auctions to allocate theselicenses efficiently since 1994.Presently, the FCC is running a novel spectrum auction known as the incentiveauction. What makes the incentive auction unique compared to prior spectrumauctions is that rather than allocating previously unlicensed spectrum, this auctionreallocates spectrum currently held by television broadcasters. These broadcastershold licenses in either the very high frequency (VHF) band, spanning channels 2-13, or the ultra high frequency (UHF) band, spanning channels 14-51. The UHFfrequencies, which are in the 600 megahertz (Mhz) range, are particularly wellsuited to wireless data transmission on mobile devices, as they can penetrate wallsand travel long distances [28]. Given that over-the-air television has become moreredundant with the rise of cable, satellite, and streaming services1, and that inparallel demand for mobile data is increasing, the incentive auction is a unique1A 2012 estimate says that only roughly 10% of viewers rely solely on over-the-air broadcastsfor video programming [10].1opportunity to reallocate spectrum to higher-value use.The reallocated spectrum is most useful to mobile carriers if the same channelscan be acquired across the country. Therefore, the auction process removes stationsfrom the upper channels of the UHF band, either moving each station into the lowerchannels or purchasing that station’s broadcast rights when this cannot be achieved.Broadcast rights must be acquired for some stations because stations interfere witheach other, so it will not be possible to pack all of the existing stations into thereduced channel set. Once the upper channels are cleared of stations, broadcastlicenses in those channels can be auctioned off.The incentive auction is thus composed of two related parts: a reverse auctionin which the FCC will acquire spectrum from some broadcasters while remainingbroadcasters will be “repacked” into a reduced set of channels, and a forward auc-tion in which the FCC sells the freed up channels to mobile carriers. The choiceof how many channels to reallocate, known as the clearing target, links these twoparts. The incentive auction alternates between the two parts in a series of stageswith progressively shrinking clearing targets until demand in the forward auctioncovers the cost of purchasing and reassigning stations in the reverse auction. Whilethe forward auction process resembles prior spectrum auctions, the reverse auctionwas designed specifically for the incentive auction and is an unprecedented under-taking; this thesis will focus exclusively on the reverse auction.The reverse auction mechanism decides which stations will be winners (havetheir broadcast rights purchased) and which stations to reassign to a new chan-nel, and must do so in a way that does not violate interference constraints. Therewill be many feasible partitions—how should it choose between them? A sensi-ble efficiency-related goal for the reverse auction might be, for any given clearingtarget, to maximize the total value of the stations that remain on-the-air, or equiva-lently, to minimize the total value of the winning stations. This suggests a straight-forward maximization problem (e.g., a Vickrey-Clarke-Groves (VCG) mechanism),but in practice at the national scale this is computationally intractable.2The FCC chose to use a descending-clock auction for the reverse auction. Roughly,2An approximate VCG solution is not a promising direction either, as even small optimizationerrors can lead to dramatic pricing errors and destroy strategy-proofness, as laid out by Milgrom andSegal (2014).2it works as follows: stations are approached in a round-robin fashion and made aseries of decreasing price offers for their spectrum. When a station declines an of-fer, it exits the auction and is guaranteed to be assigned a channel in its pre-auctionband when the auction concludes. As more and more stations exit over time, itmay no longer be possible to make this guarantee to certain stations: a feasibilitychecker is used to determine whether or not there is a way to assign channels to astation along with all of the exited stations that does not cause interference. Whenthe feasibility checker detects that a station can no longer safely exit, that station’sspectrum is acquired at its most recently accepted price offer.This auction format does not escape computational intractability either, as thejob of the feasibility checker—determining whether or not a set of stations canbe packed into a set of channels—is a nondeterministic polynomial time (NP)-complete problem, meaning that it belongs to a class of problems not known to betractable. Since the reverse auction must conclude in a timely manner, and sincethe feasibility checker will be queried tens of thousands of times throughout theauction, a tight cutoff—on the order of minutes—is imposed on each query. Thereis no guarantee that a proof of feasibility or infeasibility will be found in the allotedtime. In the event of a timeout, the auction proceeds as if the result was infeasible.The consequences of mislabeling an answer are not symmetric: it would beterrible to incorrectly conclude that a repacking problem is feasible (this couldmake the auction outcome infeasible), whereas wrongly claiming that a problemis infeasible prevents a price offer from being lowered, possibly decreasing theauction’s efficiency and causing the government to overpay for a station, but doesnot pose a fundamental problem for the auction itself. Nevertheless, these timeoutsshould be minimized for the sake of both the efficiency and cost of the auction (thedescending clock is geometric, so early individual unsolved problems can cost theFCC millions of dollars each!).We built SAT-based Feasibility Checker (SATFC), the feasibility checker usedin the reverse auction.3 Our goal was to design an efficient feasibility checker thatminimizes timeout results. Working with anonymized versions of repacking prob-3The reverse auction uses SATFC 2.3.1, released April 13, 2016.3lems from FCC simulations45, we combined a Propositional Satisfiability (SAT) en-coding, constraint graph decomposition, algorithm configuration, algorithm port-folios, local and complete search, domain-specific heuristics, and a novel cachingscheme to create an efficient feasibility checker. This thesis describes both SATFCand a reverse auction simulator that we use to evaluate SATFC’s performance. Wealso use the simulator to explore ways in which the feasibility checker affects theefficiency and cost of the reverse auction by comparing simulations that differ onlyin their feasibility checkers.The incentive auction is interesting to study both due to its novelty and its eco-nomic importance: the spectrum reallocation is expected to improve social welfareby putting spectrum to a higher-value use, and, according to the CongressionalBudget Office, the resale of spectrum is forecast to net tens of billions of dollarsfor the US government [5]. As a result, the auction has been the subject of con-siderable recent study by the research community, mostly focused on elements ofauction design [3, 9, 25, 29, 33, 35, 40]. From a theory perspective, the reverseauction is a deferred-acceptance auction [34], an auction that selects its alloca-tion by repeatedly rejecting the least attractive bids. Deferred acceptance clockauctions have many desirable properties: They are obviously strategy-proof [30],since an agent can conclude that deviating from honest reporting can never leadto better payoffs regardless of how other agents behave (and, in this context, cancome to this conclusion even without understanding the details of how price offersare decremented!). These auctions are also weakly group strategy-proof, meaningthat there are no profitable group deviations from honest reporting that benefit eachagent in the deviating group. However, the highly non-uniform interference con-straints used in feasibility checking make it difficult to analyze the reverse auction4In order to validate the auction design, the FCC ran extensive simulations of the auction, basedon a wide variety of assumptions about station participation and bidding behavior. These simulationsexplored a very narrow set of answers to the questions of which stations would participate and howbidders would interact with the auction mechanism; they do not represent a statement either by usor by the FCC about how these questions are likely to be resolved in the real auction. It is of courseimpossible to guarantee that variations in the assumptions would not have yielded computationallydifferent problems.5Note that there is an interesting bootstrapping problem here, as the reverse auction simulatorand feasibility checker co-evolve, and so the problems generated by the simulator change as thefeasibility checker improves and handles denser packings.4solely with theory. Simulations have been used as a tool to forecast the cost of real-locating spectrum and the amount of spectrum that might be cleared [2]; to evaluatemethods for setting price decrements [36]; to determine what must happen in anyrepacking solution based on the interference constraints (i.e., without appealing tothe reverse auction process or prices) [26]; and to evaluate the impact of proposedrule changes, such as alternative scoring rules6 [6]. Each of these works solves sta-tion repacking problems, although efficient feasibility checking is not their primaryfocus and none of them use SATFC, the feasibility checker optimized for this ex-act setting and deployed in the live incentive auction. While the station repackingproblem has been studied in other contexts, falling under the umbrella of frequencyassignment problems7, we are not aware of other work with the goal of optimizingfeasibility checking in the setting of the incentive auction.The remainder of this document is as follows: Chapter 2 describes the reverseauction algorithm. Chapter 3 details the station repacking problem and our method-ology for designing an efficient feasibility checker. Chapter 4 walks through thedesign of our reverse auction simulator. Chapter 5 shows experimental results ofevaluating our feasibility checker on our reverse auction simulator. Finally, Chap-ter 6 provides directions for future research.6Scoring rules are used to set station-specific prices in the reverse auction. They are covered inmore detail in Section 2.1.2.7See e.g., Aardal et al. (2007) for a survey and a discussion of applications to mobile telephony,radio and TV broadcasting, satellite communication, wireless LANs, and military operations.5Chapter 2The Reverse AuctionThe goal of this chapter is to present the reverse auction algorithm used in the in-centive auction, which is the mechanism by which the FCC decides from whichstations to purchase broadcast licenses and at what prices. Both UHF and VHFstations participate in the reverse auction: Even though VHF stations do not havebroadcast rights in the more valuable UHF band, removing VHF stations createsspace to move UHF stations into VHF. While utilizing the VHF band leads to moreefficient solutions, it complicates the auction’s rules significantly. We therefore be-gin with a simplified description which only considers UHF stations in Section 2.1,and then extend our description to handle VHF stations in Section 2.2. For a moredetailed description of the auction process see Appendix D of the FCC’s December2014 public notice [12].2.1 The Reverse Auction Limited to UHF StationsWe now proceed with a description of the reverse auction in a world with only UHFstations. First, stations respond to opening clock prices and decide to participate inthe auction or exit permanently. Next, the feasibility checker identifies a feasibleassignment for all non-participating stations. The auction then proceeds over aseries of rounds, which consist of: (1) decrementing the clock and offering newprices, (2) collecting bids, and (3) processing bids. Only the processing step isnot straightforward: Bids are considered sequentially. When processing a bid, the6feasibility checker first determines whether a station is still packable along withthe exited stations. If it is packable, the station either accepts the new clock priceor exits the auction. Otherwise, the station becomes frozen, meaning that it canno longer be packed in its original band. The station is now a provisional winner1and will be paid according to its most recently accepted offer. To complete thisdescription we now show how prices are computed.2.1.1 Computing PricesThe prices offered to each station differ based on station-specific characteristics.These characteristics are captured by a volume, which is computed by a scoringrule. The price P for a station s at round t is computed by multiplying its volumewith a base clock price ct . The base clock price is decremented each round by dt ,the maximum of 5% of its previous value or 1% of its initial value. More formally,dt = max{0.05 · ct−1,0.01 · c0} (2.1)ct = ct−1−dt (2.2)Ps,t = ct ·Volume(s) (2.3)where c0 is the initial base clock price, used to compute the opening prices.2.1.2 Scoring RuleScoring rules compute station volumes. The choice of scoring rule is importantbecause varying the prices non-uniformly between stations is a way to influencethe order in which stations exit and the prices they are paid, which impacts theauction’s efficiency and cost. For example, it may be advantageous to encourage astation that causes much interference to remain in the auction, because by exitingit could freeze many other stations (and if it exits early, they would be frozen atvery high prices!). Similarly, from a cost perspective, it might be possible to savemoney by offering lower prices to stations that service smaller populations, withthe expectation that a station’s value for its broadcast rights is proportional to the1Provisional in the sense that the winning offer is conditional on the auction terminating in itscurrent stage, which depends on demand in the forward auction.7size of the population it serves. The FCC uses a scoring rule that considers both ofthese issues, in which a station’s score is proportional to both a heuristic estimatinghow difficult it makes other stations to repack and its population:Volume(s) = A ·√Interference(s) ·√Population(s) (2.4)In this formula, Interference(s) is computed by taking the sum over each otherstation s′ of the maximum number of channels that s can prohibit s′ from beingassigned to, Population(s) is the interference-free population that s reaches, andA is a scaling constant used to make the maximum volume one million (thereforecapping the largest price offer at one million times the initial base clock price).Volumes for each station are computed only once before the auction begins—theydo not vary throughout the auction.2.2 Generalizing the Reverse Auction to Include VHFStationsWe now extend our description of the reverse auction to handle participation byVHF stations. VHF can be further divided into lower VHF (LVHF) (channels{2, . . . ,6}) and higher VHF (HVHF) (channels {7, . . . ,13}). In what follows, werefer to the band that a station is on prior to the reverse auction as the home bandof that station. The relinqushiment options—that is, the ending states for stationsin the auction—are therefore going off air (OFF), LVHF, HVHF, and UHF, orderedin terms of quality. When we say that one band is above or below another, we referto this ordering. The reverse auction places restrictions on the options that stationscan bid on. First, a station cannot bid on an option above its home band. Second,the reverse auction is a ladder auction, meaning that if a station ever bids to moveto a band b, it will no longer be allowed to bid on options below b. The ladderrestriction helps the auction set prices and prevents complex bidding strategies,making the auction simpler from a bidder’s perspective. Simplicity is an importantgoal of the auction in order to encourage participation.82.2.1 Computing Prices with Multiple BandsThe reverse auction can no longer simply calculate a single price for each station,but must instead calculate a price for each option available to each station. We nowexplain how these prices are computed.An Ideal Case: Similar StationsThe easiest case to reason about is when there are three stations which serve iden-tical populations: a UHF station, an HVHF station, and an LVHF station, with theproperty that none of these stations can co-exist on the same band, and that if anystation moves to a lower band, its interference constraints in the new band are iden-tical to the station it displaces. There are then four ways to clear the UHF channel,each of which create the same amount of value and hence should cost the sameamount.1. The UHF station can go to OFF for a price of $X2. The UHF station can go LVHF for a price of $Y (where $Y < $X) and theLVHF station can go to OFF at a price of $X−$Y3. The UHF station can move to HVHF for a price of $Z (where $Z < $Y ) andthe HVHF station can go OFF at a price of $X−$Z4. The UHF station can move to HVHF for a price of $Z, the LVHF station cango to OFF for a price of $X −$Y , and the HVHF station can go to LVHF at aprice of $Y −$Z.Benchmark PricesThe reverse auction uses benchmark prices based on the above thought experiment:the auction first pretends that we are in the scenario of the above example wherecomparable stations exist and computes a benchmark price (which we will denotep), which it later transforms into an actual price as described below.To compute the benchmark price for a station s in round t for the option ofmoving into b, a base clock decrement dt is computed as before in Equation 2.1,except that now the previous round’s price is decremented by a fraction of dt . This9fraction is called a reduction coefficient, rt,s,b. We will describe the computation ofreduction coefficients in Section 2.2.1.pt,s,b = pt−1,s,b− rt,s,b ·dt (2.5)The initial benchmark prices, denoted p0,b, are chosen prior to the auction (withp0,UHF = 0). The benchmark price is then converted to an actual price as follows.Pt,s,b = Volume(s) ·max{0,min{pt,s,OFF, pt,s,b− pt,s,Home-Band(s)}}(2.6)Let us break down this formula: The prices are weighted by volume as before.The max ensures the price is non-negative and the min upper bounds the priceby the price offered to a UHF station to go to OFF. Lastly, the second term inthe min reflects the pricing division described in Section 2.2.1, where the totalpayments for each of the four possibilities sum to the same amount (e.g., a UHFstation moving to HVHF would get paid pt,s,HVHF, an HVHF station moving to LVHFwould get paid pt,s,LVHF− pt,s,HVHF, and an LVHF station moving to OFF would getpaid pt,s,OFF− pt,s,LVHF, all of which sum together to a total payment of pt,s,OFF).VacancyBefore describing the calculation of reduction coefficients, we need to describeone more concept, known as vacancy. Vacancy, denoted Vt,s,b, is a heuristic thatestimates the competition that a station s faces for a spot in band b in round t, withhigher values indicating less competition. More formally, vacancy is a volumeweighted average of a function f over potential competitors for the vacant spacein the band: Let G(t,s,b) denote the set containing both s and stations which havethe possibility to interfere with s in b which are currently bidding on options belowb. The function f is computed by taking the number of channels in b to whichs can be feasibly assigned (given the current assignment of the exited stations)and normalizing by the number of channels in b. If s cannot be assigned to anychannels, 0.5 is used in place of the numerator.10f (t,s,b) =# of feasible channels for s in b in round t# of channels in b(2.7)Vt,s,b =∑s′∈G(t,s,b)Volume(s′) · f (t,s′,b)∑s′∈G(t,s,b)Volume(s′)(2.8)Reduction CoefficientsWe now provide equations for computing the reduction coefficients. The full decre-ment is always applied to going off-air, that is rt,s,OFF = 1.The reduction coefficient for moving to HVHF is:rt,s,HVHF =p0,HVHF ·√Vt,s,UHF(p0,OFF− p0,HVHF) ·√Vt,s,HVHF+ p0,HVHF ·√Vt,s,UHF(2.9)Finally, the reduction coefficient for moving to LVHF is:rt,s,LVHF =((p0,LVHF− p0,HVHF) ·√Vt,s,HVHF(p0,OFF− p0,LVHF) ·√Vt,s,LVHF+(p0,LVHF− p0,HVHF) ·√Vt,s,HVHF)·(1− rt,s,HVHF)+ rt,s,HVHF2.2.2 Placing BidsA station is presented with prices for each permissible option as described above, aswell as the option to exit the auction and receive no compensation. It then submitsits preferred option. If a station bids to move to a VHF band that it is not alreadyin, the station must also submit a fallback bid to be used in case the feasibilitychecker is unable to pack the station into the preferred band. The fallback bid mustbe either to retain the currently held option or to exit the auction.2.2.3 Bid ProcessingIn this section we describe how the algorithm processes the stations’ bids. Bids areall placed in a queue, sorted in order of the ratio between the price reduction forthe station’s currently held option in this round and the station’s volume, with ties11broken randomly. The auction system then begins a loop in which it finds the firststation in the queue that is feasible in its home band, processes that station’s bid,and removes it from the queue. This phase completes when the queue is empty orevery station in the queue is frozen. When a station’s bid is processed, if the bidrequires a fallback option, the feasibility of the move is first tested: if the move isfeasible, the station is moved, otherwise the station’s fallback bid is processed. Ifa station moves bands, the tentative assignment is updated accordingly.2.2.4 Provisional WinnersA station becomes a provisional winner once the auction determines that the stationwill be frozen for the remainder of the stage. A UHF station becomes a provisionalwinner as soon as it is frozen: being frozen for this UHF station means that it cannotbe repacked along with the current set of exited UHF stations, and since exiting is apermanent move, this set will not lose any members throughout the auction. There-fore, if a UHF station becomes unpackable in UHF at any point during the auction,it will remain unpackable in UHF for the duration of the auction. However, this isnot true for VHF stations: e.g., if an LVHF station bids for OFF, and a UHF stationmoves into LVHF, the LVHF station may become frozen. However, the UHF stationmay later move out of LVHF, which might unfreeze the LVHF station. Therefore, atthe end of the bid processing step, the reverse auction checks each frozen station tosee if it has become a provisional winner. For a VHF station s, this means using thefeasibility checker to determine that it is not possible to pack s into its home bandalongside all of the exited stations and provisional winners in s’s home band.2.2.5 Removing Stations That Can Never Become WinnersIt may be possible to determine over the course of the reverse auction that a stationwill always remain repackable in its home band regardless of the actions taken byother stations. Such a station will never become a winner: the reverse auction cancontinue to lower the compensation offered to that station all the way down to zero,and at some point the station will be better off exiting. Therefore, when the reverseauction identifies such a station, it forces that station to exit in order to speed upthe inevitable.12In order to determine whether a station s with home band b can never becomea winner, the reverse auction first identifies the set of stations X that might finishthe auction in b: these are stations that are either already in b or else are in a bandbelow b, are not provisionally winning, and have home bands weakly greater thanb. Once the set X has been identified, in order to prove that s can never become awinner, the reverse auction must show that no matter which stations in Y ⊆ X windup in b at the end of the auction, it will be feasible to repack {s}∪Y in b. This maybecome easier to show as the auction progresses, since X can shrink as stationsthat might have finished the auction in b become provisional winners on bandsother than b or move to bands above b. The reverse auction relies on a sound butincomplete heuristic to identify these stations. The heuristic works by computingonce at the start of the auction the maximum number of channels for each pair ofstations s,s′ that s′ can prevent s from being assigned to in s’s home band. If thissum taken over all s′ ∈ X is smaller than the number of channels on which s can beplaced in its home band, then s can never become a winner.2.2.6 TerminationA stage of the reverse auction terminates when a round concludes and every stationhas either exited the auction or is a provisional winner.13Chapter 3Designing an Efficient FeasibilityCheckerIn this chapter, we provide a detailed description of feasibility checking and ex-plain the design of our feasibility checker SATFC. We begin with a more formaldescription of the station repacking problem. Then we explain ways in which theproblem can be encoded into SAT and Mixed-Integer Programming (MIP) form. Wethen turn to some domain-specific heuristics we use to solve problems, as well asways in which problems can be simplified into smaller problems. We then discusshow algorithm configuration can be used to combine all of these ideas. Lastly, wedescribe a caching scheme for station repacking problems and explain how all ofthe aforementioned ideas combine to form our solver, SATFC. In what follows, wewill sometimes say that a problem is SAT or unsatifiable (UNSAT) meaning it isfeasible or infeasible respectively.3.1 The Station Repacking ProblemEach television station in the US and Canada s ∈ S is currently assigned to a chan-nel cs ∈ C ⊆ N that ensures that it will not excessively interfere with other, nearbystations. The FCC reasons about what interference would be harmful via a com-plex, grid-based physical simulation (“OET-69” [11]), but has also processed theresults of this simulation to obtain a Constraint Satisfaction Problem (CSP) style14formulation listing forbidden pairs of stations and channels, which it has publiclyreleased [14]. These constraints prohibit channel reassignments in which one sta-tion would reduce the interference-free population served by another station bymore than 0.5%, so that after the incentive auction each station that remains on-the-air will serve roughly the same viewers that it served prior to the auction [13].Let I ⊆ (S ×C)2 denote a set of forbidden station–channel pairs {(s,c),(s′,c′)},each representing the proposition that stations s and s′ may not concurrently beassigned to channels c and c′, respectively. The effect of the auction will be to re-move some broadcasters from the airwaves completely, and to reassign channels tothe remaining stations from a reduced set of channels. This reduced set is definedby a clearing target: some channel c ∈ C such that all stations are only eligibleto be assigned channels from C = {c ∈ C | c < c}. The clearing target is fixed foreach stage of the reverse auction. Each station can only be assigned a channel ona subset of C, given by a domain function D : S → 2C that maps from stationsto these reduced sets. The station repacking problem is then the task of findinga repacking γ : S → C that assigns each station a channel from its domain thatsatisfies the interference constraints, i.e., for which γ(s) ∈ D(s) for all s ∈ S, andγ(s) = c⇒ γ(s′) 6= c′ for all {(s,c),(s′,c′)} ∈ I. A problem instance thus corre-sponds to a choice of stations S⊆S and channels C⊆C to pack into, with domainsD and interference constraints I implicitly being restricted to S and C; we call theresulting restrictions D and I.3.2 Structure of ConstraintsInterference constraints are more structured than in the general formulation. Allconstraints are of the form ADJ(s,s′,c, i) with i ∈ {0,1,2} prohibiting concurrentassignment of s to c and s′ to any channel in [c,c+ i]. Note that when i = 0 aconstraint simply says that two stations may not be concurrently assigned to aparticular channel; these are known as co-channel constraints. When i > 0 theconstraint is known as an adjacent-channel constraint. Notice that it is very sim-ple to translate the constraints into a large set of forbidden station–channel pairsof the form {(s,c),(s′,c)}, {(s,c),(s′,c+ 1)}, or {(s,c),(s′,c+ 2)}. One notablestructural feature of the constraints is that adjacent-channel constraints always im-15ply the existence of a set of related constraints: the property holds that for i > 0,ADJ(s,s′,c, i) =⇒ ADJ(s,s′,c+1, i−1). This means, for example, that eachi= 1 adjacent-constraint between two stations on c implies a co-channel constraintbetween the two stations on c+1. Other structural features include that constraintswhere i = 2 always involve a Canadian station and that no interference constraintinvolves channels in more than one frequency band.Finally, it is interesting to visualize the constraint structure. Let us define theinterference graph as an undirected graph in which there is one vertex per stationand an edge exists between two vertices s and s′ if the corresponding stations par-ticipate together in any interference constraint: i.e., if there exist c,c′ ∈C such that{(s,c),(s′,c′)} ∈ I. If we were dealing exclusively with co-channel constraints,station repacking problems would be graph coloring problems, where stations arevertices and channels are colors, which is a simple way to see that the station pack-ing problem is NP-complete. Figure 3.1 shows the US and Canada interferencegraph. Notice that the graph is very densely connected in areas such as New York.While this graph includes both UHF and VHF constraints, it is interesting to notethat when restricting the graph to only showing UHF constraints, the eastern com-ponent of the graph is disconnected from the western components.3.3 Structure of Station Repacking Problems in theReverse AuctionWhy should we hope that an NP-complete problem can be solved effectively inpractice? First, we only need to be concerned with problems involving subsets ofa fixed set of stations and a fixed set of interference constraints: those describ-ing the television stations currently broadcasting in the United States and Canada.Furthermore, we are not interested in worst-case performance (i.e., the hardest pos-sible problems within these limits), or even average case performance, but rather ingood performance on the sort of instances generated by actual reverse auctions. Forexample, the repacking problems encountered depend on the order in which sta-tions exit the auction, which depends on stations’ valuations, which depend in turn(among many other factors) on the size and character of the population reachedby their broadcasts. The distribution over repacking problems is hence far from16Figure 3.1: Interference graph derived from the FCC’s November 2015 con-straint data [14].uniform. Second, descending clock auctions repeatedly generate station repackingproblems by adding a single station s+ to a set S− of provably repackable stations.This means that every station repacking problem (S−∪{s+},C) comes along witha partial assignment γ− : S−→C which we know is feasible on restricted stationset S−.3.4 Complete and Local Search SolversBefore heading into a discussion of problem solving techniques, we quickly re-view the differences between complete and local search SAT solvers, since someof our techniques only make sense for one or the other. Complete solvers aretypically based on backtracking algorithms such as DPLL [7] in which variablesare tentatively assigned and the consequences of the assignments are propagateduntil a conflict emerges, at which point the solver backtracks, or until a feasibleassignment is found. These solvers are able to exhaust the search space and prove17that a problem has no feasible solution. Local search solvers, on the hand, workby searching a space of complete assignments and seeking a feasible point, typ-ically following gradients to minimize an objective function that counts violatedconstraints, and periodically randomizing. Unlike complete solvers, local searchsolvers cannot prove that a problem is infeasible. A final important difference isthat while local search solvers maintain a full assignment of the variables as partof their state, complete solvers do not.3.5 EncodingsIn this section we describe various ways of encoding the station repacking problemso that it can be solved using standard methods.3.5.1 MIP EncodingThe FCC’s initial investigations included modeling the station repacking problemas a MIP and using off-the-shelf solvers paired with problem-specific speedups.Unfortunately, the problem-specific elements of this solution were not publiclyreleased, so we do not discuss them further in this document. The station repackingproblem can be encoded as a MIP straightforwardly as follows:xs,c+ xs′,c′ ≤ 1 ∀{(s,c) ,(s′,c′)} ∈ I (3.1)∑c∈D(s)xs,c = 1 ∀s ∈ S (3.2)xs,c ∈ {0,1} ∀c ∈ D(s)∀ s ∈ S (3.3)Constraint 3.1 ensures that no interference constraints are violated, Constraint 3.2ensures that each station gets assigned to exactly one channel, and lastly, Con-straint 3.3 makes the variables integral.3.5.2 SAT EncodingsWe decided to instead consider SAT encodings: this formalism is well suited tostation repacking, which is a pure feasibility problem (no objective function) with18only combinatorial constraints.1 A SAT encoding has the advantage of makingit possible to leverage the research community’s vast investment into developinghigh-performance SAT solvers (see e.g., Ja¨rvisalo et al. (2012)). In all of the fol-lowing encodings, we create a variable xs,c ∈ {0,1} for every station–channel pair,representing the proposition that station s is assigned to channel c. Many SAT en-codings for our problem are possible (see e.g., Prestwich (2003) for a number ofapplicable encodings). Here we focus on two relatively straightforward encodings:the direct encoding, and the multivalued encoding.Direct SAT EncodingThe direct SAT encoding is analogous to the MIP encoding. We create three kindsof clauses:∨d∈D(s)xs,d ∀s ∈ S (3.4)¬xs,c∨¬xs,c′ ∀s ∈ S, ∀c,c′ 6= c ∈ D(s) (3.5)¬xs,c∨¬xs′,c′ ∀{(s,c),(s′,c′)} ∈ I ∀c ∈ D(s) ∀ s ∈ S (3.6)Clause 3.4 is an at least one (ALO) constraint, ensuring that every station getsassigned a channel. Clause 3.5 is an at most one (AMO) constraint, ensuring thatevery station gets assigned at most one channel (so together, these clauses ensurethat every station gets exactly one channel). Finally Clause 3.6 ensures that inter-ference constraints are not violated.Multivalued SAT EncodingThe multivalued encoding is exactly the same as the direct encoding withoutClause 3.5, the AMO constraint. It is trivial to transform a solution to the multival-ued problem into a solution of the original problem: if a station is assigned morethan one channel, we can simply pick one channel from these arbitrarily. This en-coding significantly reduces the number of constraints (recall that there is an AMO1Of course, it may nevertheless be possible to achieve good performance with MIP or other tech-niques; we did not investigate such alternatives in depth.19constraint for every pair of channels in a station’s domain in the direct encoding),and it increases the size of the feasible region by allowing solutions where stationsoccupy more than one channel. This encoding is well suited to local search solvers,which cannot benefit from the constraint propagation of the AMO constraints in thesame way that a complete solver can.3.6 Using the Previous SolutionIn this section we present two methods that leverage the partial assignment γ− toquickly solve problems.3.6.1 Locally Altering the Previous SolutionOn a majority of problem instances, a simple transformation of γ− is enough toyield a satisfiable repacking: we consider whether it is possible to assign s+ to achannel and update the channel assignments of the stations in s+’s neighborhood,holding the rest of γ− fixed. Specifically, we find the set of stations Γ(s+)⊆ S thatneighbor s+ in the interference graph, then solve the reduced repacking problem inwhich all non-neighbors S\Γ(s+) are fixed to their assignments in γ−. Observe thata feasible repacking for this reduced problem is also feasible on the full set; on theother hand, if we prove that the reduced problem is infeasible, we cannot concludeanything. The value of this approach is in its speed: often a station’s immediateneighborhood in the induced problem’s interference graph is very small, hence thereduced problem can be solved very quickly. Also note that if the reduced problemis infeasible, we can unfix additional stations and try again: a natural second stepwould be to also unfix stations in Γ(s′),s′ ∈ Γ(s+), that is, neighbors of neighborsof s+, though of course other expansion rules are possible. We proceed in thismanner until a solution is found or we wind up with the initial problem. Figure 3.2illustrates the approach. Note that it may happen that later subproblems in the seriesare easier to solve than earlier ones, so we impose a cutoff on each problem in theseries to ensure the solver gets to attempt later subproblems even if it gets stuck onearlier ones. Also note that complete solvers have an advantage in applying thisidea because they can prove problems are infeasible, whereas a local search solverwould need to exhaust its entire cutoff before expanding.20{14, 15, 16}{14, 15, 16}{15, 16}1416171817(a) Locally altering the previous solution{14, 15, 16}{14, 15, 16}{15, 16}{14, 15}{16, 17, 18}{15, 16, 17}1718(b) Expanding the set of unfixed stationsFigure 3.2: The first two subproblems in a series of applying the “locally al-tering the previous solution” method. In 3.2a we allow the newly addedstation (blue) and its neighbors (green) to take on any channel in theirdomains, but hold the remaining stations (orange) fixed on their chan-nels. If a feasible solution cannot be found in the first subproblem, weunfix neighbors of neighbors and try again (see 3.2b).3.6.2 Starting Near the Previous SolutionWhen working with local search solvers, which maintain a full variable assignmentin their state, we can leverage γ− by assigning the stations in γ− to their channels inγ− and randomly assigning a channel for s+. If a solution exists “near” this startingpoint, i.e., γ− can be converted into a solution with only a few variable changes,such an initialization can help us to find it much more quickly (although there isno guarantee that the solver will not immediately randomize away to another partof the space), so we interleave initializations to the previous solution with randomrestarts. We observe that this approach does not generalize the “locally altering theprevious solution” approach discussed in Section 3.6.1, as we do not constrain thelocal search algorithm to consider only s+’s (extended) neighborhood.213.7 Problem SimplificationIn this section we provide three preprocessing methods that can be used to take astation repacking problem and transform it into a more manageable, smaller prob-lem.3.7.1 Arc ConsistencyStation repacking problems are CSPs where all constraints are between pairs ofvariables. We can therefore use local consistency techniques to reduce the searchspace. In particular we can make a given station repacking problem arc consistentusing the well known polynomial time Arc Consistency Algorithm #3 (AC-3) [32].A station s is arc consistent with another station s′ if whenever s is assigned to anychannel c∈D(s) ,∃c′ ∈D(s′)such that{(s,c),(s′,c′)} 6∈ I. If c does not satisfy thisproperty, then no feasible assignment can ever assign s to c and so we can prune cfrom D(s). Enforcing arc consistency therefore works as a preprocessing step tocreate smaller problems, though it is also possible for it to prune all of the channelsin a station’s domain thereby proving a problem is infeasible.3.7.2 Unconstrained Station RemovalIn a given repacking problem (S,C), there may exist stations with the followingproperty: given any feasible assignment of all of the other stations in S \ s, therewill always exist a channel in D(s) into which s can be feasibly packed. We callthese stations unconstrained, since we can remove them from the problem andsolve a smaller problem (S\Sunconstrained,C). If the smaller problem is infeasible,so is the larger problem. If a feasible solution is found, we can sequentially add theunconstrained stations back by iterating over their domains until a feasible channelis found. Testing whether or not a station is unconstrained is a co-NP hard problem,so we rely on a sound but incomplete set of heuristics to identify unconstrainedstations.Consider that each neighbor s′ ∈ Γ(s) can be assigned to any channel c′ ∈D(s′), and in doing so would make any solution where s was assigned to a channelin {c | c ∈ D(s) ,{(s,c),(s′,c′)} ∈ I} infeasible. A station is unconstrained if thereis no feasible way for the neighbors to select channels in such a way that they block22out all of D(s). We can relax the problem by removing the requirement that theneighbors’ assignment must be feasible. If a station is unconstrained in the relaxedproblem, it will also be unconstrained in the base problem since imposing a feasibleassignment on the neighbors only makes blocking out channels more difficult.Unblockable Channel HeuristicOur first heuristic is simple: If there exists a channel on s’s domain that no neigh-bor has the ability to block, then s is unconstrained since it can always be as-signed to this channel. More formally, s is unconstrained if ∃ c ∈ D(s) such that∀s′ ∈ Γ(s) , ∀c′ ∈ D(s′) ,{(s,c),(s′,c′)} 6∈ I. This heuristic can be computed intimeO (|Γ(s)| · |D(s)| ·d), where d is the size of the largest neighbor’s domain andchecking whether or not a constraint exists in I is an O(1) operation.Worst Case Selection HeuristicOur second heuristic is based on upper bounding the number of channels thatneighboring stations can block. If this upper bound is smaller than |D(s) |, s isunconstrained. To compute this upper bound, we observe that every neighboringstation s′ has at least one channel that it could be assigned to on which it blocks themaximum number of channels possible for s′ to block on D(s). Let Blockss′ be themaximum number of channels s′ can block for s:Blockss′ = maxc′∈D(s′)∣∣{c ∈ D(s) | {(s,c) ,(s′,c′)} ∈ I}∣∣ (3.7)We compute an upper bound on the total number of channels that can be blockedfor s by assigning all of the neighbors to such a maximum blocking channel andassuming that the blocked sets are non-overlapping. If ∑s′∈Γ(s)Blockss′ ≤ |D(s) |,then s has more channels on its domain than can possibly be blocked by otherstations, so s is unconstrained. This heuristic is also computable in timeO (|Γ(s)| · |D(s)| ·d).Our two heuristics complement each other: the first heuristic only applies whena station has a constraint-free channel, whereas the second heuristic can fail toidentify a station with a constraint-free channel as unconstrained but can identify23unconstrained stations that do not posses such a channel.Recursively Unconstrained StationsWe use the above two heuristics to identify unconstrained stations. Notice how-ever that in the smaller problem induced by removing unconstrained stations, newstations may become unconstrained that were not unconstrained in the originalproblem. Therefore, we recursively run our unconstrained station removal proce-dure until it can no longer remove any stations. Note that when adding back theunconstrained stations after solving the smallest induced problem, we must addstations back at same the level of recursion in which they were removed, since un-constrained stations at higher recursion depths are only unconstrained conditionalon the removal of stations at shallower recursion levels.3.7.3 Problem DecompositionThe interference graph induced by a problem may consist of multiple connectedcomponents; we can separate them in linear time. We only need to solve the onecomponent that contains s+, as we can directly leverage γ− to fill in a feasible as-signment for the other components. This is particularly useful for complete solvers,which cannot otherwise leverage γ−. Note that arc consistency and unconstrainedstation removal can remove edges and links in the interference graph, possiblyshrinking the size of the component containing s+.3.8 Meta-Algorithmic TechniquesIn recent years, there has been increasing development of artificial intelligencetechniques that reason about how existing heuristic algorithms can be modified orcombined together to yield improved performance on specific problem domainsof interest. These techniques are called meta-algorithmic because they consist ofalgorithms that take other algorithms as part of their input. For example, algo-rithm configuration consists of setting design decisions exposed as parameters tooptimize an algorithm’s average performance across an instance distribution. Thisapproach has proven powerful in the SAT domain, as many SAT solvers expose pa-rameters that can drastically modify their behavior, from the probability of random24restarts to the choice of search heuristics or data structures [22]. We performed con-figuration using Sequential Model-based Algorithm Configuration (SMAC) [21] inorder to tune the performance of generic SAT solvers to station repacking problems.Many ideas in this chapter, such as the choice of what encoding to use discussedin Section 3.5, or the preprocessing ideas in Section 3.7 can be exposed as meta-parameters to an algorithm configurator; we did so whenever possible.Unfortunately, even after performing algorithm configuration, it is rare to finda single algorithm that outperforms all others on instances of an NP-complete prob-lem such as SAT. This inherent variability across solvers can be exploited by algo-rithm portfolios [19, 37]. Most straightforwardly, one selects a small set of algo-rithms with complementary performance on problems of interest and, when askedto solve a new instance, executes them in parallel.Finally, algorithm configuration and portfolios can be combined. Hydra [41] isa technique for identifying sets of complementary solvers from highly parameter-ized design spaces via algorithm configuration. It operates by altering an algorithmconfigurator to optimize an algorithm’s marginal gains over an existing portfolio:this allows for discovery of algorithms that might perform poorly where existingalgorithms are known to do well but that can outperform known configurationson other problems. In each iteration, Hydra greedily adds configurations that makethe greatest possible marginal contribution to an existing portfolio. Specifically, wecreate a (parallel) portfolio by greedily selecting the algorithm that most improvesits performance.3.9 Containment CachingWe know that every repacking problem we encounter will be derived from a re-striction of the interference graph to some subset of S. We know this graph inadvance of the auction; this suggests the possibility of doing offline work to pre-compute solutions. However, this graph involves a total of |S| = 2990 stations,and the number of possible subsets is exponential in this number. Thus, it is notpossible to exhaustively range over all possible subsets prior to the auction.One possibility would simply be to store the solution to every repacking prob-lem we encounter and build a giant cache, but in practice we found that identical25problems were rarely encountered across auction simulations. However, observethat if we know whether or not it is possible to repack a particular set of stations S,we can also answer many different but related questions. Specifically, if we knowthat S was packable then we know the same is true for every S′ ⊆ S (and indeed,we know the packing itself—the packing for S restricted to the stations in S′). Sim-ilarly, if we know that S was unpackable then we know the same for every S′ ⊇ S.This observation dramatically magnifies the usefulness of each cached entry S, asS can be used to answer queries about an exponential number of subsets or super-sets (depending on the feasibility of repacking S). This is especially useful becausesometimes it can be harder to find a repacking for subsets of S than it can be to finda repacking for S (it may be that the added interference constraints constrain thesearch space in a way that makes a solution easier to find). Analogously, it mightsometimes be easier to prove a smaller subset of S is infeasible than S itself.We call a cache meant to be used in this way a containment cache, because itis queried to determine whether one set contains another (i.e., whether the querycontains the cache item or vice versa). To the best of our knowledge, containmentcaching is a novel idea. A likely reason why this scheme is not already commonis that querying a containment cache is nontrivial, as we will explain below. Weobserve that containment caching is applicable to any family of feasibility testingproblems generated as subsets of a master set of constraints, not just to spectrumrepacking.In more detail, containment caching works as follows. We maintain two caches,a feasible cache and an infeasible cache, and store each problem we solve in theappropriate cache. We store full instances for SAT problems and the smallest sim-plified component (created by applying all of the methods from Section 3.7 to aproblem instance) for UNSAT problems, in order to be able to service the largestnumber of possible queries. When asked whether it is possible to repack stationset S, we proceed as follows. First, we check whether a subset of S belongs to theinfeasible cache, in which case the original problem is infeasible. If we find nomatches, we decompose the problem into its smallest simplified component andcheck if the feasible cache contains a superset of those stations, in which case theoriginal problem is feasible.Containment caching is less straightforward than traditional caching, because26Figure 3.3: This figure shows a solution to a graph coloring problem S thatcan trivially be made into a solution for the graph coloring problem S′by restricting the solution for S to vertices in S′. This is analogous tohow our SAT cache works.we cannot simply index entries with a hash function. Instead, an exponential num-ber of keys could potentially match a given query. We were nevertheless able toconstruct an algorithm that solved this problem quickly2 Specifically, our approachproceeds as follows. Offline, we build (1) a traditional cache C indexed by a hashfunction and—in the case of feasible problems—storing solutions along with eachproblem; and (2) a secondary cache Co containing only a list of station sets thatappear in C. This secondary cache is defined by an ordering o over S, which wechoose uniformly at random. We represent each station set stored in Co as a bitvector, with the bit in position k set to 1 if and only if the k-th station in ordering obelongs to the given station set. We say that one station set is larger or smaller thananother by interpreting both station set bit vectors as integers under the orderingo and then comparing the integers. Appealing to this ordering, we sort the entriesof Co in descending order. Figure 3.4 illustrates a set of six subsets of the powerset 2{a,b,c,d,e} and a secondary cache constructed based on these sets along with arandom ordering over their elements. As the figure suggests, secondary caches arevery compact: we can thus afford to build multiple secondary caches Co1 , . . . ,Co` ,based on the same set of station sets but ` different random orderings.We now explain how to query for a superset, as we do to test for feasible solu-tions; the algorithm for subsets is analogous. A sample execution of this algorithmis illustrated in Figure 3.5. Given a query S, we perform binary search on each ofthe ` secondary caches to find the index corresponding to S itself (if it is actually2There is a literature on efficiently finding subsets and supersets of a query set [4, 20, 39]. How-ever, our algorithm was fast in our setting and we did not explore alternatives; indeed, our approachmay be of independent interest.270 1 2 3 4b d a e cc bd c ab de a d ca c bc d e0 1 2 3 4b d a e c0 1 1 1 1 (30)0 1 0 1 1 (26)0 1 1 0 1 (22)1 0 1 0 1 (21)1 0 0 0 1 (17)1 1 0 0 0 (3)Figure 3.4: Translating six sets (left) into integers (right) according to a sec-ondary cache ordering.stored in the cache) or of the smallest entry larger than S (if not); denote the indexreturned for cache Cok as ik. If we find S, we are done: we retrieve its correspondingsolution from the main cache. Otherwise, the first i1 entries in cache Co1 containa mix of supersets of S (if any exist) and non-supersets that contain one or morestations not in S that appear early in the ordering o1. Likewise, the first i2 entriesin Co2 contain the same supersets of S (because Co1 and Co2 contain exactly thesame elements) and a different set of non-supersets based on the ordering o2, andso on. We have to search through the first ik entries of some cache Cok ; but it doesnot matter which Cok we search. We thus choose the shortest list: k = argmin j i j.This protects us against unlucky situations where the secondary cache’s orderingyields a large ik: this is very unlikely to happen under all ` random orderings forlarge enough `. The superset search itself can be performed efficiently by testingwhether the cached bit vector is bitwise logically implied by the query bit vector.If we find a superset, we query the main cache to retrieve its solution.28Get a superset of:d c0 1 2 3 4b d a e c0 1 1 1 1 (30)0 1 0 1 1 (26)0 1 1 0 1 (22)1 0 1 0 1 (21)1 0 0 0 1 (17)1 1 0 0 0 (3)Get a superset of:0 1 0 0 1 (18)0 1 2 3 4b d a e c0 1 1 1 1 (30)0 1 0 1 1 (26)0 1 1 0 1 (22)1 0 1 0 1 (21)1 0 0 0 1 (17)1 1 0 0 0 (3)Figure 3.5: A visualization of looking up a superset in a secondary cache.Only one secondary cache is shown in these figures, but multiple sec-ondary caches can be used to decrease the number of elements to searchover.3.10 SATFCWe combined all of the methods described in this chapter to create our feasibilitychecker, SATFC. Using problems from FCC simulations, we performed algorithmconfiguration as described in Section 3.8 on 18 different SAT solvers, obtainedmainly from SAT solver competition entries collected in AClib [23]. We observedgood performance from the solvers Clasp [18] and SATenstein [27]. Clasp is ahighly-parameterized complete solver that relies on conflict-driven nogood learn-ing, and SATenstein is a local search framework that can instantiate most existinghigh-performance local search algorithms for SAT in the literature, as well as novelsolvers that have never been thought of before. We then used Hydra to create aneight-algorithm portfolio of various parameterizations of these two solvers. To-gether with the cache described in Section 3.9 these algorithms make up SATFC29PortfolioClasp (Direct encoding, Locally altering the previous solution)Clasp (Direct encoding, Fully simplified problems)Clasp (Direct encoding, Fully simplified problems)SATenstein (Direct encoding, Previous solution restarts)SATenstein (Multivalued encoding, Previous solution restarts)SATenstein (Multivalued encoding, Previous solution restarts, Problem decomposition)SATenstein (Multivalued encoding, Previous solution restarts, Problem decomposition)SATenstein (Multivalued encoding, Previous solution restarts, Fully simplified problems)Table 3.1: A breakdown of the different solvers composing SATFC showingthe different ideas from this chapter that are used in each algorithm.2.3.1, the version used by the FCC.3 In particular, the portfolio contains threeClasp threads, all of which use the direct encoding. One is used for the locallyaltering the previous solution idea of Section 3.2a and the other two operate onfully simplified components. The remaining five threads are SATenstein, all ofwhich sometimes restart to previous solutions, and four of which use the multival-ued encoding. The portfolio composition is outlined in Table 3.1.3The set of configuration experiments that produced this version’s portfolio are unpublished. Weacknowledge some limitations of these experiments here. Firstly, instead of merging the designspaces of Clasp and SATenstein and then running Hydra on the merged design space, we per-formed separate runs of Hydra on each of their design spaces in isolation. As a result, we were onlyable to exploit complementarity available within each of these solvers’ design spaces—and not acrossthem—during configuration. We assembled the final portfolio greedily by evaluating configurationsfrom both Hydra runs on a validation set, so complementarity could be exploited between the twodesign spaces amongst the configurations that were found. A second issue with our configurationexperiments is that we did not extract the “locally altering the previous solution” idea described inSection 3.6.1 as a meta-parameter, and instead tuned it manually. This work does not contain anynew configuration experiments, and hence does not address either of these flaws.30Chapter 4Designing a Reverse AuctionSimulatorOne of our main contributions is a simulator for the reverse auction algorithm.Much of the work involved in building a simulator is implementing all of the auc-tion rules, which we explained in Chapter 2 and do not repeat here. In this chapter,we focus on what still needs to be specified in order to actually run a simulation.First, we need a model of how stations will bid in the auction, which we givein Section 4.1. Next, we need to come up with value profiles for these stations;we describe how we generate these in Section 4.2. We also need to select whatclearing target to use; we go over how we select clearing targets in Section 4.3.Another decision is what feasibility checker to use: SATFC is one option; we de-scribe another in Section 4.4. Section 4.5 explains two methodologies for dealingwith timeouts. Lastly, Section 4.6 describes how we can save calls to the feasibil-ity checker by reasoning about cases where a station must have remained feasiblebetween checks.4.1 Station Bidding ModelIn order to actually run a simulation, we need a model of how stations bid. Weassume that each station s has a private value for broadcasting on each of its per-missible bands, vs,b, and that in each bidding round, a station selects the offer that31myopically maximizes its utility Pb,s,t + vb,s. Fallback options (see Section 2.2.2),when required, are also selected in this manner.4.2 Station Valuation ModelIn this section we describe how we generate value profiles for each station. Letvs,OFF = 0, since a station gets no value if it gives up its license. To assign theremaining values, we turned to the valuation model developed by Doraszelski et al.(2016). Their work uses data from the MEDIA Access Pro Database from BIAKelsey (BIA) and the Television Financial Report from the National Association ofBroadcasters (NAB) to estimate station valuations for UHF stations. In their model,a station’s value is the maximum of its cash-flow value and its stick value, wherethe former reflects the “the price a TV station expects if it sells itself on the privatemarket as a going concern” and the latter purely reflects the value of the broadcastlicense.vs,UHF = max{vCFs ,vSticks } (4.1)The cash flow value is computed by multiplying a station’s cash flow CFs with acash flow multiple MultipleCFs .vCFs = CFs ·MultipleCFs (4.2)The stick value is proportional to the interference-free population that a stationreaches and a stick multiple MultipleSticks .vSticks = MultipleCFs ·6Mhz ·Population(s) (4.3)where 6 Mhz is the size of a channel. While we know the population values for eachstation, we need to estimate cash flows and both of the multiples in order to applythis model. The authors of Doraszelski et al. (2016) shared with us distributionsthat we can use to sample estimates of these unknown values. This allows us toapply the above equations to produce samples of vs,UHF. Now that we have entriesfor vs,UHF, we fill in the VHF values by making the simplifying assumption thatvs,HVHF = 23 vs,UHF and that vs,LVHF =13 vs,UHF.324.3 Determining Clearing TargetIn order to simulate a reverse auction, we need to select a clearing target. Priorto the auction, the FCC announced a series of ten clearing targets, ranging from126–42 Mhz (corresponding to a maximum allowable channel of 29–44). In theincentive auction, in order to avoid limiting the clearing target by the most con-strained regions of the country, some impairments are allowed, meaning that somestations can be placed on channels otherwise disallowed by the clearing target. Sec-tion 3 of an FCC public notice [15] details the initial clearing target determinationprocedure, which involves optimizing a tentative assignment for every clearing tar-get and selecting the most aggressive clearing target that meets a standard set fortolerable impairments. One other role of the initial clearing target determinationprocedure is to set the starting band of each participating station. Prior to the auc-tion, stations select all of the options that they would be willing to consider at theopening prices. While there is unlimited room in OFF, if too many stations restricttheir willingness to participate only to VHF bands it may be impossible to find aninitial feasible assignment that accommodates all of them in their preferred op-tions. The initial clearing target determination procedure decides which stationsto initially place on each band. If a station did not indicate OFF as an allowableoption, it may place the station on its home band, causing it to exit.The initial clearing target determination procedure is somewhat complex, andwe do not simulate it. Instead, we use the following procedure to determine theclearing target and find an initial assignment. In our simulator, only those stationsthat are offered more to go off-air than their values for broadcasting in their homebands (i.e., those stations for which P0,s,OFF > vs,HOME-BAND(s)) will participate inthe auction. Our simulator places all participating stations in OFF at the beginning,even if their most preferred offer would have led them to starting in a VHF band(though they are free to bid for their preferred option in the first round). As a con-sequence of this restriction, we do not allow stations that would have had positiveutility for starting in one of the VHF bands but negative utility from starting in OFFto participate in the auction in our simulator. We make this restriction to ensure thatstations always have positive utilities for participating: our concern is that a stationmight freeze in the first round before it is able to move to its preferred option, and33then it would have a negative utility for participating.After the set of participating stations is determined, we select a clearing targetby iterating through all possible clearing targets in order, starting with the mostaggressive, and selecting the first clearing target for which we are able to finda feasible assignment for the non-participating stations. We do not simulate thepossible multi-stage nature of the incentive auction, so this clearing target will beused throughout the entire simulation.4.4 Feasibility CheckerIn order to run a reverse auction simulation, we need to select a feasibility checker.Since we want to investigate the impact that the quality of a feasibility checkerhas on the efficiency and cost of the reverse auction, we need alternative feasibilitycheckers to compare with SATFC. We propose what is perhaps the simplest rea-sonable feasibility checker, which we call the greedy feasibility checker. It simplyiterates through the domain of s+ checking to see if any channel results in a feasibleassignment when augmented with γ− (as shown in Figure 4.1). It does not alter γ−in any way. If it cannot find a feasible channel for s+, the greedy feasibility checkerreports a timeout. We use the greedy feasibility checker as a zero reference pointfor feasibility checker quality in order to measure the impact of feasibility checkerquality on auction efficiency and cost (although we do not know that either of thesetwo metrics monotonically improve with feasibility checker quality).4.5 Revisiting TimeoutsRecall that the bid processing step of the reverse auction (see Section 4.5) loopsover a queue of stations, processing the first station found to be feasible, removingit form the queue, and continuing in this manner until an iteration in which it cannotprove any remaining stations in the queue are feasible. We need to decide how tohandle timeouts during this step of the reverse auction. If a station is found infeasi-ble in UHF, it will remain that way until the end of the auction (because no stationsleave UHF). Therefore, when we find a station to be infeasible in UHF in one loopiteration of the bid processing step, then in subsequent loops over the queue we canskip the call to the feasibility checker for that station because that station must still34{14, 15, 16}16151416171817Figure 4.1: An illustration of the greedy feasibility checker. Only the newlyadded station (blue) can vary on its domain, other stations are all fixedon their channels.be infeasible. However, if instead the result of a UHF feasibility check is a time-out, a future call to the feasibility checker in that same bid processing step maybe able to prove that the station is actually feasible in UHF (as more stations exit,the problem of finding a feasible repacking for that station could become easier).In other words, just because a station is skipped over the first time it is examinedin the queue does not mean it should necessarily be skipped over again during thenext iteration. We therefore need to decide whether to run our feasibility checkeragain the next time the station is processed in bid processing and other stationshave exited to UHF since the last check (we refer to this as revisiting timeouts), orto simply declare that the station is infeasible because it timed out once and willlikely time out again. The latter approach can save computational resources, butmay harm the reverse auction’s cost and efficiency. Our simulator has supportsboth approaches, with the default behavior being to not revisit timeouts.354.6 Reusing Solutions Within a SimulationWithin a given auction simulation, we can reuse feasible solutions to UHF problemsin order to reduce the number of queries to the feasibility checker. The idea is thatonce a station s is proven feasible to pack in UHF, it will remain so as long as noother station s′ exits into UHF where s and s′ are in the same connected componentof the interference graph. Therefore, once we find a feasible assignment for sin UHF, we mark that s is feasible and skip future calls to the feasibility checkerregarding placing s in UHF (since we know that s remains feasible). Whenevera station exits to UHF, we clear our stored results for any stations in the samecomponent of the interference graph as the exited station.36Chapter 5ExperimentsIn this chapter, we perform experiments using the reverse auction simulator de-scribed in Chapter 4 in order to evaluate the performance of SATFC and to investi-gate the feasibility checker’s impact on reverse auction outcomes. First, we explainhow we ran our simulations (Section 5.1). Next, we create a test set of problems(Section 5.2) and use it to evaluate solvers (Section 5.3). We then evaluate the con-tainment cache (Section 5.4). Lastly, we compare the reverse auction mechanismwith VCG and observe how replacing SATFC 2.3.1 in our simulator with alternatefeasibility checkers affects reverse auction outcomes (Section 5.5).5.1 SimulationsWe ran 20 reverse auction simulations. For each simulation, we used a differentrandom seed to create a value profile as described in Section 4.1. The FCC releaseda document announcing the opening prices for each station on November 2015[16]. To initialize benchmark prices (see Section 2.2.1) we followed this documentand set p0,UHF = 0, p0,HVHF = 360, p0,LVHF = 675, and p0,OFF = 900. We also usedthe volumes for each station that were listed in this document, so that our openingprices matched up with the incentive auction’s opening prices. We furthermoreused the opening price document as our eligibility criteria for the simulator: weallowed any station that was offered an opening price to participate in the reverseauction in our simulations. The document lists stations for which “the auction37system has determined that this station will always have a feasible channel assign-ment in its pre-auction band at all of the possible auction clearing targets”—wesimply dropped such stations from our simulations. We also dropped stations forwhich our valuation model contains no information, which can happen due to anyof three reasons: Firstly, Doraszelski et al. only considered stations in mainlandUS and Hawaii, so we did not have valuations for stations outsides of these ar-eas. Secondly, Doraszelski et al. did not model VHF station values, so we droppedall 39 eligible US LVHF stations and all 378 eligible US HVHF stations from oursimulations. Lastly, since Doraszelski et al. used a different source to determineeligibility, we were unable to use their model to sample valuations for some of thestations that were eligible in our source but not in theirs1. After dropping thesestations, we were left with 1,638 eligible US UHF stations.Canadian stations are also involved in the reverse auction. They act exactlylike stations that decide not to participate: they cause interference with other sta-tions and must be repacked. Since Canadian stations are not bidders in the reverseauction, we did not need to model their valuations and hence we included all ofthe Canadian stations in all our simulator. In total, we included 113 CanadianLVHF stations, 332 Canadian HVHF stations, and 348 Canadian UHF stations in oursimulations.We downloaded the interference constraints and station domains from the FCC’swebsite [14] posted November 12, 2015. For each simulation, we determined par-ticipation and set the clearing target using the method described in Section 4.3.In all cases this led to a clearing target of 84 Mhz, corresponding to a maximumallowable channel of 36 for US stations and 35 for Canadian stations.2 We usedSATFC 2.3.1 as our feasibility checker, with a cutoff of 60 seconds and did notrevisit timeouts. All of our experiments were run on Intel Xeon E5-2640 v2 pro-cessors on nodes with 96 GB of RAM running Red Hat Enterprise Linux Serverrelease 6.7. We allocated 8 cores to each simulation, so that all 8 configurationsin SATFC 2.3.1 could run in parallel. The simulations took between 3.52 and 4.021Specifically we dropped 25 UHF stations with the following facility IDs: 4353, 259, 71425,70414, 70415, 70423, 70426, 70428, 168094, 41375, 38562, 38437, 17830, 57905, 8500, 68406,51656, 34894, 34341, 34342, 14315, 27501, 57456, 66549, 69753.2At every clearing target, the maximum allowable channel for Canadian stations is always 1channel below the maximum US channel.38hours to run (wall time), of which the majority of the time—between 2.52 and3.07 hours—was spent within SATFC solving UHF problems. In each simulationbetween 1,553 and 1,571 stations participated at the opening prices.5.2 Creating a Test Set of Non-Trivial ProblemsThe feasibility checker must solve tens of thousands of station repacking problemsin a single auction simulation. However, the vast majority of these problems arenot very difficult to solve. For example, even in our earliest official release, SATFC1.3, we never observed any timeouts on VHF problems, likely because these bandscontain at most 7 channels and are home to fewer stations. In addition, most UHFproblems, especially earlier in the auction, can be solved by the simple greedyfeasibility checker described in Section 4.4; we observed that across all of oursimulations 97.39% of UHF problems can be solved this way. When creating a testset of station repacking problems, we first filter out these “trivial” problems. Acrossall of our simulations, this left us with a pool of 60,057 problems. We then sampled10,000 of these problems uniformly at random to use as our test set.3 This test setconsists of 9,482 feasible problems, 121 infeasible problems, and 397 problemsthat timed out at our one minute cutoff and therefore have unknown feasibility.5.3 Evaluating Test Set PerformanceAs mentioned in Section 3.10, in our initial experiments [17] we configured SATsolvers from AClib [23] in order to determine which SAT solvers to include inSATFC. We do not repeat these configuration experiments here (i.e., try to build anewer, better SATFC) and instead study the version of SATFC that is actually beingused in the reverse auction.4 Figure 5.1 shows the performance of the default3We acknowledge that a test set is an imperfect way to evaluate a feasibility checker, since unlessthe test set is generated by a perfect feasibility checker that never times out, scoring well on a testset does not necessarily imply good performance in practice. We generated our test set using SATFC2.3.1 as our feasibility checker, which encounters relatively few timeouts, and for which we haveobserved that most unsolved problems turn out to be infeasible (and hence would not change theproblem trajectory of an auction). Nevertheless, it is difficult to reason about the true ceiling inthis setting, and there is certainly a larger gap than that implied merely by the fraction of unsolvedproblems in our test set.4This is not to say that running new configuration experiments would not be very interesting—onthe contrary, we view this as promising future work!39Figure 5.1: ECDF of runtimes for default configurations of MIP and SATsolvers on our test set. The legend is ordered by percentage of problemssolved before the cutoff. The bars show fraction of SAT and UNSATinstances binned by their (fastest) runtime. Although present, unsatisfi-able instances form an insignificant portion of instances solved.configurations of 20 SAT solvers from AClib5 as well as what are arguably the twobest-performing MIP solvers—CPLEX and Gurobi.6Note that with one exception, the SAT solvers outperformed the MIP solvers.We observed that one solver, Gnovelty+PCL, was able to solve the largest num-ber of problems in our test set within the cutoff—79.96% of the problems in 41.74hours. The parallel portfolio of all of these 22 solvers together was able to solve81.58% of the problems in 38.08 hours. In our previous experiments [17] we ob-served the best performance (post algorithm configuration) from clasp and DCCA[31]. DCAA is a local search solver with no exposed parameters. We recruited anundergraduate student, Paul Cernek, who integrated DCAA into SATenstein and5At the time of writing, there are 22 SAT solvers in AClib. In two cases (clasp andlingeling) AClib contains submissions from multiple years; we use only the latest submissions.6We used CPLEX 12.6.2 and Gurobi 6.0.0.40# Solved % ∆ % Time (s)1 92.91 - 53, 8742 94.42 1.51 39, 4153 95.14 0.72 37, 7514 95.59 0.45 34, 9675 95.78 0.19 34, 3296 95.92 0.14 33, 6507 96.01 0.09 32, 5698 96.03 0.02 32, 503Table 5.1: A breakdown of the marginal value of adding each new configura-tion to our portfolio by building the portfolio greedily.exposed 3 parameters.As was described previously in Section 3.10, SATFC is composed of 8 config-urations of clasp and SATenstein. Figure 5.2 shows the performance of SATFC2.3.1 and each individual configuration in SATFC 2.3.1 on the test set. SATFC 2.3.1was able to solve 96.03% of the test set’s problems in 9.03 hours (wall time), solv-ing 87.73% of the problems in under one second. The figure shows five individualconfigurations in SATFC 2.3.1 which outperform any of the default solver configu-rations.Another result that stands out from the figure is that the gap between the portfo-lio performance and the performance of the single best configuration is quite small.Table 5.1 quantifies this gap, breaking down the marginal gains of each configura-tion to SATFC by constructing its portfolio greedily. From this table we concludethat if SATFC 2.3.1 only ran a single configuration, it would still be able to solve92.92% of the problems in the test set, only 3.12% fewer than the entire portfoliowas able to solve. How much are the extra seven configurations contributing to thereverse auction? To better understand the value of the extra configurations, we de-fine a new feasibility checker, the best single configuration, consisting solely of thetop SATenstein configuration; we will have more to say about it in Section 5.5.We conclude by noting that the returns on both problems solved and runtime di-minish fairly quickly after the fourth configuration is added.41Figure 5.2: SATFC performance on test set broken down by configuration(numbers in names correspond to Table 5.1). The bold red line is theparallel portfolio performance.5.4 Containment Cache EvaluationWe cannot evaluate our caching scheme from Section 3.9 by looking at its test setperformance as we do the rest of SATFC’s portfolio because we would first needto decide with what solutions the cache should be initialized. One idea might beto initialize the cache with all of the problems that we did not include in the testset, but doing so could overstate cache performance because related instances fromthe same auction simulation could appear both in the initialization set and the testset. We avoided this concern by performing a “leave-one-out” analysis: For eachauction we built a cache composed of problems from all of the other auctions, andthen computed what fraction of the non-trivial problems this cache would havebeen able to solve in that auction. Before performing this analysis, we checkedto make sure that the problems across each simulation did not overlap (i.e., thata conventional cache would not have sufficed). We observed no auction shared42Figure 5.3: Bar chart where each bar represents the fraction of instances solv-able by a cache filled with problems from the other auctions.any non-trivial problems in common with any other auction (where we define aproblem for this purpose by the set of stations to repack, ignoring the previousassignment), so a conventional cache would have a hit rate of 0% in our setting.Our results for the containment cache are shown in Figure 5.3. At worst the cachewas able to solve 9.3% of the problems, and at best 32.4%, with a median of 22.6%problems solved. We note that these numbers would only improve if we addedmore simulations to grow the cache.5.5 Simulations with Different Feasibility Checkers5.5.1 Comparing Reverse Auction OutcomesThe outcome of the reverse auction is a channel assignment γ for stations that re-main on-the-air and a set of prices that winning stations will be paid to go off-air.We compare reverse auction outcomes based on their efficiency and cost. A natural43way to measure efficiency is by the value preserved by the auction, in other wordsby defining an efficient repacking as one that maximizes the total value of the par-ticipating stations that remain on-the-air. We instead choose to measure efficiencyby the total value lost by the auction, defining an efficient repacking as one thatminimizes the total value loss of winning stations, which for any given station ismeasured as the difference between that station’s value for broadcasting in its homeband and its post-auction band. Note that an efficient repacking satisfying one def-inition also satisfies the other. We prefer the latter definition because it is onlyinfluenced by stations that a feasibility checker is unable to repack in their homebands and therefore does not assign credit for easy to repack stations. For example,holding everything else constant, increasing the value of an easy to repack stationarbitrarily high would make the value preserved arbitrarily high as well, but valueloss would be unaffected. We therefore feel that the value loss definition allowsfor more meaningful comparisons between different feasibility checkers. If we canfind an efficient repacking γ∗, then we have an upper bound on efficiency. We canuse γ∗ to relate the total value loss of another repacking to the optimal total valueloss through a value loss ratio:Value Loss Ratio =∑s∈S vs,HOME-BAND(s)− vs,POST-AUCTION-BAND(γ,s)∑s∈S vs,HOME-BAND(s)− vs,POST-AUCTION-BAND(γ∗,s)(5.1)where POST-AUCTION-BAND is a function that takes in a channel assignmentand a station and returns the band that the station is assigned to, or OFF if it is notassigned to a band. Since γ∗ is optimal, a value loss ratio will always be weaklygreater than 1.To get a feel for what this ratio means, imagine a setting containing two stationseach with values of $25 and one station with a value of $100 for broadcasting intheir home bands. Furthermore, imagine that the optimal repacking in this settingcauses the two $25 stations to go off-air for a total value loss of $50. If we have anon-optimal repacking that instead causes the $100 station to go off-air for a totalvalue loss of $100, then the value loss ratio of this solution would be 2, since twiceas much value has been lost as in the optimal solution.Unfortunately we cannot compute γ∗ at a national scale, so we cannot compareto an optimal repacking in our national simulations. However, we can still compare44the value loss between two assignments to see which is more efficient.For computing cost, we define a price function P : S → R that maps froma station to its payment (returning 0 for stations that are not winners). Then anoutcome’s cost is:Cost = ∑s∈SP (s) . (5.2)We prefer outcomes with value loss ratios close to 1 and low cost. It is straightfor-ward to compare two outcomes if one Pareto dominates the other with respect toefficiency and cost, otherwise any comparison is at least partially subjective.5.5.2 Comparing the Reverse Auction and VCGIn this section we compare the FCC’s reverse auction mechanism to a VCG mech-anism. We chose to compare to VCG because it computes a globally efficient out-come and is truthful for bidders.VCG EncodingWe now specialize VCG to our setting to code for the relevant constraints. Weencode the global repacking problem as a MIP. We differentiate between non-participating stations that must be repacked in their home bands, Snon-participating,and participating stations, Sparticipating, that can be repacked on any band weaklybelow their homes or placed off-air. For simplicity, we use an objective functionthat maximizes the value preserved, noting that a solution to this maximizationproblem also minimizes the total value loss.maximize ∑s∈Sparticipating∑c∈D(s)xs,c · vs,CHANNEL-TO-BAND(c)subject to xs,c+ xs′,c′ ≤ 1 ∀{(s,c) ,(s′,c′)} ∈ I (5.3)∑c∈D(s)xs,c ≤ 1 ∀s ∈ Sparticipating (5.4)∑c∈D(s)xs,c = 1 ∀s ∈ Snon-participating (5.5)xs,c ∈ {0,1} ∀c ∈ D(s)∀ s ∈ S (5.6)45The objective function maximizes the aggregate on-the-air value of the partic-ipating stations by summing over the channel indicator variables for each partici-pating station multiplied by its value for broadcasting in that channel’s band. Notethat if a station is placed off-air, it does not contribute to the objective function, andthat a station contributes most to the objective function when it is placed where ithas the highest value, i.e., in its home band. The rest of our encoding is very similarto the MIP encoding of the station repacking problem presented in Section 3.5.1. Infact, besides the objective function there is only one difference, which is that herewe differentiate between participating stations, which Constraint (5.4) says maybe assigned or unassigned, and non-participating stations, which Constraint (5.5)ensures are assigned to a channel in their home band.7The VCG price for a winning station s is calculated as the difference (excludingthe value of s) in the value of the optimal packing γ∗ and the value of the optimalpacking γ∗−s when s is added to Snon-participating. The price paid to any losing stationis zero. The |Swinners| pricing problems can be solved in parallel once the initialallocation has been found.VCG SimulationsWe were unable to compute the VCG allocation with all of the eligible stations evenafter several days of computing time. To make the problem tractable, we restrictedourselves in the following manner: We dropped all of the Canadian stations andrestricted ourselves to the UHF band using the smallest possible clearing target,126 MHz, corresponding to a maximum allowable of channel of 29. Using theinterference graph induced by these restrictions, we furthermore dropped everystation that was not reachable by following at most two interference constraintsfrom stations in New York City. We chose New York City as it is one of the mostdensely connected areas of the interference graph. The induced constraint graphcontains 218 stations and is shown in Figure 5.4.We computed the optimal repackings and pricing problems using CPLEX 12.6.2,with 8 cores available, solving all MIPs optimally to within 10−6 absolute MIP gaptolerance. Since the VCG experiments were computationally very expensive (it7We implicitly restrict D(s) to the home band for each non-participating station.46took a mean of 93.92 days CPU time to compute the allocation and prices for eachvalue profile), we only ran them for our first five value profiles. We then ran reverseauction simulations in the same New York setting using the following feasibilitycheckers: SATFC 2.3.1, the greedy feasibility checker, and the best single config-uration. Figure 5.5 plots the cost and value loss normalized by the correspondingVCG cost and value loss for each of these simulations. The SATFC 2.3.1 simula-tions had a mean value loss ratio of 1.047, so the reverse auction achieved outcomeswith value losses very near to optimal in this setting and at lower cost than the VCGprices. Both the SATFC 2.3.1 and best single configuration runs Pareto dominatedthe greedy runs. Averaging across all results, greedy runs cost 1.732 times moreand had value loss ratios 1.424 times higher than the SATFC 2.3.1 runs. SATFC2.3.1 is a strictly more powerful feasibility checker than the best single config-uration because SATFC 2.3.1 contains the best single configuration as part of itsportfolio. The performance of SATFC 2.3.1 and the best single configuration werevery similar in this setting, though we observed in three cases that the best singleconfiguration actually led to a slightly higher value loss ratio than using SATFC2.3.1. These results show that reverse auction performance does not always im-prove monotonically with a better feasibility checker.5.5.3 National Simulation ResultsWhile we could not simulate VCG at the national scale, we were still able to com-pare the cost and value loss resulting from substituting different feasibility checkersinto our national simulations. Using the same value profiles as for our original na-tional simulations, we ran new two new sets of simulations replacing SATFC 2.3.1with the greedy feasibility checker and the best single configuration. We observedhow the cost and efficiency of each auction varied with the new feasibility checkers.The results are shown in Figure 5.6, which plots the value loss and cost of each sim-ulation normalized by the corresponding SATFC 2.3.1 simulation. Similarly to theVCG results, we observed that each SATFC 2.3.1 simulation and best single config-uration simulation Pareto dominated their greedy counterparts. Averaging over allof our observations, the greedy simulations cost 3.550 times ($5.114 billion) moreand had value losses 2.850 times ($2.030 billion) higher than the SATFC 2.3.1 sim-47Figure 5.4: Interference graph of the set of 218 UHF stations within two edgesof a New York station. Each edge represents the existence of at leastone pairwise binary constraint between two stations under a 126 MHzclearing target.ulations. The gaps between SATFC 2.3.1 and the greedy feasibility checker in boththe cost and efficiency dimensions were significantly larger at the national scalethan in the smaller New York setting. The best single configuration simulationshad values losses on average 1.101 times ($110 million) higher and were 1.142times ($284 million) more expensive than their SATFC counterparts. The SATFC2.3.1 simulations Pareto dominated the best single configuration simulations in allbut one sample, in which the best single configuration simulation had a value loss0.05% ($569 thousand) smaller than its corresponding SATFC 2.3.1 simulation, butwas 6.8% ($137 million) more expensive. This is quite different from how thesetwo feasibility checkers compared in our VCG simulations, where the best singleconfiguration performed more favorably. These results strengthen our intuition thatwhile the efficiency and cost of a reverse auction may not improve monotonicallywith a better feasibility checker, in general we expect that improvements to theperformance of the feasibility checker will improve both of these metrics. An-other intuition, also validated by these results, is that in larger settings with harderrepacking problems, the importance of a strong feasibility checker is amplified.Finally, recall that Section 4.5 described how a feasibility checker could revisit48Figure 5.5: Fraction of VCG cost versus fraction of VCG value loss plotted forthree different feasibility checkers (indicated by colors) for five differentvalue profiles (indicated by markers). All VCG points lie at (1,1). SATFC2.3.1 and the best single configuration had equivalent outcomes on thesecond value profile (the markers coincide).timeouts within a bid processing round. We ran SATFC 2.3.1 simulations that revis-ited timeouts for each of the 20 simulations. These simulations took much longerthan the runs that did not revisit timeouts, spending on average between 24.4 and54.5 hours on solving UHF problems. We observed that this extra computation timeon average led to better outcomes. The runs that did not revisit timeouts cost 1.011times ($21 million) more and had value losses that were 1.010 times ($10 million)higher on average than the runs that did revisit timeouts.49Figure 5.6: Value loss and cost of national simulations using three differentfeasibility checkers for 20 value profiles. Both axes are normalized bythe cost and value loss of the corresponding SATFC 2.3.1 simulation.The figure also contains a second SATFC 2.3.1 series which revisit time-outs.50Chapter 6Discussion and ConclusionsStation repacking in the reverse auction of the “incentive auction” is a difficultproblem, but one in which progress is translatable into both large monetary sumsand social welfare. We presented our feasibility checker, SATFC, which com-bines state-of-the-art SAT solvers, recent meta-algorithmic techniques, and furtherspeedups based on domain-specific insights to yield a feasibility checker that meetsthe performance needs of the real incentive auction. We also presented our re-verse auction simulator, which we used to explore the effect that the reverse auc-tion’s choice of feasibility checker has on the reverse auction’s efficiency and cost.Specifically we showed that using SATFC vastly outperforms a very naı¨ve feasi-bility checker, and that even substituting SATFC with a feasibility checker that isnearly as good as SATFC still results in significant losses in efficiency and increasedcost. Pointers to source code and documentation for both SATFC and our reverseauction simulator are available at http://www.cs.ubc.ca/labs/beta/Projects/SATFC/.There are many possible directions for future work. First, it would be interest-ing to continue to work towards a feasibility checker that can perform perfectly inthis domain. This would involve further improvements to SATFC, such as addingnew encodings and heuristics, or performing another round of configuration ex-periments. It would also be interesting to be able to compare the value loss fromrepackings generated by the reverse auction to the value loss of globally optimalrepackings in larger settings (i.e., beyond just stations near New York City). Thiscould be achieved by improving the performance of computing optimal repackings51(e.g., by applying algorithm configuration and new encodings to our VCG MIP) sothat optimal repackings can be computed over larger sets of stations, or by bound-ing the value loss of optimal repackings if they cannot be computed exactly. Thereare other research questions that could be answered with some additions to our sim-ulator: For example, we could enhance the valuation model to include values forVHF stations. This would allow for more realistic simulation results and could an-swer questions such as how much efficiency is gained by adding the complexity ofthe VHF bands. Other improvements that we could make to our simulator would beto enhance it to handle the initial clearing target optimization and the multi-stagenature of the incentive auction, which would allow us to answer questions suchas whether the multi-stage nature of the auction decreases efficiency. We close byadding that even with the current simulator, there are many more interesting experi-mental questions that can be answered. For example, we can investigate alternativescoring rules, or better understand the tradeoffs involved in using fixed timeouts ofone minute for each feasibility checking problem, as compared to longer timeoutsor dynamic alternatives.52Bibliography[1] K. I. Aardal, S. P. Van Hoesel, A. M. Koster, C. Mannino, and A. Sassano.Models and solution techniques for frequency assignment problems. Annalsof Operations Research, 153(1):79–129, 2007. → pages 5[2] C. Bazelon, C. L. Jackson, and G. McHenry. An engineering and economicanalysis of the prospects of reallocating radio spectrum from the broadcastband through the use of voluntary incentive auctions. TPRC, 2011. → pages5[3] M. Calamari, O. Kharkar, C. Kochard, J. Lindsay, B. Mulamba, and C. B.Scherer. Experimental evaluation of auction designs for spectrum allocationunder interference constraints. In Systems and Information DesignSymposium, pages 7–12. IEEE, 2012. → pages 4[4] M. Charikar, P. Indyk, and R. Panigrahy. New algorithms for subset query,partial match, orthogonal range searching, and related problems. InAutomata, Languages and Programming, pages 451–462. Springer, 2002.→ pages 27[5] Congressional Budget Office. Proceeds from auctions held by the FederalCommunications Commission. https://www.cbo.gov/publication/50128,2015. Accessed 2015-04-21. → pages 4[6] P. Cramton, H. Lopez, D. Malec, and P. Sujarittanonta. Design of the reverseauction in the broadcast incentive auction. 2015. → pages 5[7] M. Davis, G. Logemann, and D. Loveland. A machine program fortheorem-proving. Communications of the ACM, 5(7):394–397, 1962. →pages 17[8] U. Doraszelski, K. Seim, M. Sinkinson, and P. Wang. Ownershipconcentration and strategic supply reduction. 2016. → pages 32, 3853[9] P. Du¨tting, V. Gkatzelis, and T. Roughgarden. The performance ofdeferred-acceptance auctions. In Proc. of EC, EC ’14, pages 187–204, NewYork, NY, USA, 2014. ACM. ISBN 978-1-4503-2565-3.doi:10.1145/2600057.2602861. → pages 4[10] FCC. In the matter of expanding the economic and innovation opportunitiesof spectrum through incentive auctions. FCC Notice of ProposedRulemaking, FCC 12-118, September 2012. → pages 1[11] FCC. Office of engineering and technology releases and seeks comment onupdated OET-69 software. FCC Public Notice, DA 13-138, February 2013.→ pages 14[12] FCC. Comment sought on competitive bidding procedures for broadcastincentive auction 1000, including auctions 1001 and 1002. FCC PublicNotice, 14-191, December 2014. → pages 6[13] FCC. In the matter of expanding the economic and innovation opportunitiesof spectrum through incentive auctions. FCC Report & Order, FCC 14-50,June 2014. particularly section IIIB. → pages 15[14] FCC. Repacking constraint files.http://data.fcc.gov/download/incentive-auctions/Constraint Files/, 2015.Accessed 2015-11-20. → pages viii, 15, 17, 38[15] FCC. Procedures for competitive bidding in auction 1000, including biddingin auction 1000, including initial clearing target determination, qualifying tobid, and bidding in auctions 1001 (reverse) and 1002 (forward). FCC PublicNotice, FCC 15-78, August 2015. section III. → pages 33[16] FCC. Reverse auction opening prices. http://wireless.fcc.gov/auctions/incentive-auctions/Reverse Auction Opening Prices 111215.xlsx, 2015.Accessed 2015-11-15. → pages 37[17] A. Fre´chette, N. Newman, and K. Leyton-Brown. Solving the stationrepacking problem. 2016. → pages iii, 39, 40[18] M. Gebser, B. Kaufmann, A. Neumann, and T. Schaub. clasp: Aconflict-driven answer set solver. In Logic Programming and NonmonotonicReasoning, pages 260–265. Springer, 2007. → pages 29[19] C. P. Gomes and B. Selman. Algorithm portfolios. AIJ, 126(1):43–62, 2001.→ pages 2554[20] J. Hoffmann and J. Koehler. A new method to index and query sets. 1999.→ pages 27[21] F. Hutter, H. H. Hoos, and K. Leyton-Brown. Sequential model-basedoptimization for general algorithm configuration. In Proc. of LION, page507523, 2011. → pages 25[22] F. Hutter, M. Lindauer, S. Bayless, H. Hoos, and K. Leyton-Brown.Configurable SAT solver challenge (CSSC) (2014). 2014. Accessed2015-11-01. → pages 25[23] F. Hutter, M. Lo´pez-Iba´n˜ez, C. Fawcett, M. Lindauer, H. H. Hoos,K. Leyton-Brown, and T. Stu¨tzle. AClib: A benchmark library for algorithmconfiguration. In LION, pages 36–40. Springer, 2014. → pages 29, 39[24] M. Ja¨rvisalo, D. Le Berre, O. Roussel, and L. Simon. The international SATsolver competitions. AI Magazine, 33(1):89–92, 2012. → pages 19[25] E. Kazumori. Generalizing deferred acceptance auctions to allow multiplerelinquishment options. SIGMETRICS Performance Evaluation Review, 42(3):41–41, 2014. → pages 4[26] M. Kearns and L. Dworkin. A computational study of feasible repackings inthe FCC incentive auctions. CoRR, abs/1406.4837, 2014. URLhttp://arxiv.org/abs/1406.4837. Accessed 2016-05-09. → pages 5[27] A. R. KhudaBukhsh, L. Xu, H. H. Hoos, and K. Leyton-Brown. Satenstein:Automatically building local search sat solvers from components. → pages29[28] R. Knutson and T. Gryta. Verizon, AT&T May Face Bidding Limits inSpectrum Auction. Wall Street Journal, Apr. 2014. ISSN 0099-9660. URLhttp://www.wsj.com/articles/SB10001424052702304626304579510154106120342. Accessed2016-12-12. → pages 1[29] E. Kwerel, P. LaFontaine, and M. Schwartz. Economics at the FCC,2011–2012: Spectrum incentive auctions, universal service and intercarriercompensation reform, and mergers. Review of Industrial Organization, 41(4):271–302, 2012. → pages 4[30] S. Li. Obviously strategy-proof mechanisms. Available at SSRN 2560028,2015. → pages 455[31] C. Luo, S. Cai, W. Wu, and K. Su. Double configuration checking instochastic local search for satisfiability. In AAAI, 2014. → pages 40[32] A. K. Mackworth. Consistency in networks of relations. Artificialintelligence, 8(1):99–118, 1977. → pages 22[33] M. J. Marcus. Incentive auction: a proposed mechanism to rebalancespectrum between broadcast television and mobile broadband [spectrumpolicy and regulatory issues]. Wireless Communications, 20(2):4–5, 2013.→ pages 4[34] P. Milgrom and I. Segal. Deferred-acceptance auctions and radio spectrumreallocation. In Proc. of EC. ACM, 2014. → pages 2, 4[35] P. Milgrom, L. Ausubel, J. Levin, and I. Segal. Incentive auction rulesoption and discussion. Report for Federal Communications Commission.September, 12, 2012. → pages 4[36] T.-D. Nguyen and T. Sandholm. Optimizing prices in descending clockauctions. In Proc. of EC, pages 93–110. ACM, 2014. → pages 5[37] E. Nudelman, K. Leyton-Brown, G. Andrew, C. Gomes, J. McFadden,B. Selman, and Y. Shoham. Satzilla 0.9. Solver description, InternationalSAT Competition, 2003. → pages 25[38] S. Prestwich. Local search on sat-encoded colouring problems. InInternational Conference on Theory and Applications of SatisfiabilityTesting, pages 105–119. Springer, 2003. → pages 19[39] I. Savnik. Index data structure for fast subset and superset queries. InAvailability, Reliability, and Security in Information Systems and HCI, pages134–148. Springer, 2013. → pages 27[40] A. Vohra. On the near-optimality of the reverse deferred acceptancealgorithm. 2014. → pages 4[41] L. Xu, H. H. Hoos, and K. Leyton-Brown. Hydra: Automaticallyconfiguring algorithms for portfolio-based selection. In AAAI, pages210–216, 2010. → pages 2556

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0340850/manifest

Comment

Related Items