104 COMMUNICATIONS OF THE ACM | JANUARY 2018 | VOL. 61 | NO. 1
consumed over 13 days of CPU time.
All solvers were again able to solve a large fraction of the problems they encountered: 99.902%, 99.765%, 99.7433%, and 98.031%
for SATFC, PicoSAT, Gurobi, and greedy respectively (including
trivial problems). The economic impact of these differences is
illustrated as shown in Figure 3 (right). In this graph, x- and y-axis
values correspond to unnormalized value loss and cost respectively. Each SATFC, Gurobi, and PicoSAT simulation again dominated its greedy counterpart in both efficiency and cost. Averaging
over all of our observations, reverse auctions based on greedy feasibility checking cost 3.550 times ($5.114 bn) more and lost 2.850
times as much ($2.030 bn) broadcaster value than those based
on SATFC. At the larger scale we also found that SATFC dominated
PicoSAT and Gurobi in every simulation: on average, PicoSAT
auctions cost 1.495 times ($987 million) more and lost 1.427
times as much ($469 million) value than SATFC auctions and
Gurobi auctions cost 2.195 times ($2.390 bn) more and lost
2.017 times as much ($1.117 bn) value then SATFC auctions.
7. CONCLUSION
Station repacking in the Incentive Auction is a difficult but
important problem, with progress translating into significant
gains in both government expenditures and social welfare.
We designed a customized solution to this problem using an
approach we dub deep optimization. Specifically, we drew on
a large parameterized design space to construct a strong portfolio of heuristic algorithms: SATFC 2. 3. 1, an open-source
solver that was used in the real auction. To evaluate it for this
paper, we conducted experiments with a new reverse auction
simulator. We found that replacing SATFC with an off-the-shelf feasibility checker resulted in both efficiency losses
and increased costs. It thus appears likely that our efforts
led to significant economic benefits to broadcasters, the US
government, and the American public.
Acknowledgments
We gratefully acknowledge support from Auctionomics and
the FCC; valuable conversations with Paul Milgrom, Ilya
Segal, and James Wright; help from Peter West in conducting
some of the experiments reported in Section 6; contributions (mostly in the form of code) from past research assistants Nick Arnosti, Guillaume Saulnier-Comte, Ricky Chen,
Alim Virani, Chris Cameron, Emily Chen, Paul Cernek; experimental infrastructure assistance from Steve Ramage; and
help gathering data from Ulrich Gall, Rory Molinari, Karla
Hoffman, Brett Tarnutzer, Sasha Javid, and others at the FCC.
This work was funded by Auctionomics and by Natural
Sciences and Engineering Research Council (NSERC) via a
Discovery Grant and an E. W.R. Steacie Fellowship; it was conducted in part at the Simons Institute for Theoretical
Computer Science at UC Berkeley.
Neil Newman, Alexandre Fréchette, and
Kevin Leyton-Brown ({newmanne,
afrechet, kevinlb}@ cs.ubc.ca), Department
of Computer Science, University of British
Columbia, Canada.
References
1. Aardal, K.I., Van Hoesel, S.P., Koster, A.M.,
Mannino, C., Sassano, A. Models and
solution techniques for frequency
assignment problems. Annals of
Operations Research 153, 1 (2007),
79–129.
2. Ansótegui, C., Sellmann, M., Tierney, K.
A gender-based genetic algorithm for
the automatic configuration of
algorithms. In Conference on
Principles and Practice of Constraint
Programming (CP) (2009), 142–157.
3. Cohen, D.A., Cooper, M.C., Escamocher, G.,
Živny`, S. Variable and value elimination
in binary constraint satisfaction via
forbidden patterns. Journal of
Computer and System Sciences 81, 7
(2015), 1127–1143.
4. Cramton, P., Lopez, H., Malec, D.,
Sujarittanonta, P. Design of the reverse
auction in the broadcast incentive auction.
Working Paper (2015), http://www.
cramton.umd.edu/papers2015-2019/
cramton-reverse-auction-design-fcc-comment-pn.pdf, 2015.
5. Di Gaspero, L., Schaerf, A. Easysyn++:
A tool for automatic synthesis of
stochastic local search algorithms.
In Conference on Engineering
Stochastic Local Search Algorithms
(SLS) (2007), 177–181.
6. Doraszelski, U., Seim, K., Sinkinson, M.,
Wang, P. Ownership concentration and
strategic supply reduction. Working
Paper, http://www.nber.org/papers/
w23034 23034, National Bureau of
Economic Research, January 2017.
7. FCC. Office of engineering and
technology releases and seeks comment
on updated OET- 69 software. FCC Public
Notice, DA 13-138, February 2013.
8. FCC. Information related to incentive
auction repacking feasibility checker.
FCC Public Notice, DA 14-3, 1 2014.
9. FCC. Repacking constraint files
(2015). http://data.fcc.gov/download/
incentive-auctions/Constraint_Files/,
2015. Accessed 2015-11-20.
10. FCC. Reverse auction opening prices
(2015). http://wireless.fcc.gov/
auctions/incentive-auctions/Reverse_
Auction_Opening_Prices_111215.xlsx,
2015. Accessed 2015-11-15.
11. Fréchette, A., Newman, N.,
Leyton-Brown, K. Solving the station
repacking problem. In: AAAI
Conference on Artificial Intelligence 8
(2016), 702–709. http://dl.acm.org/
citation.cfm?id=3015812.3015917,
3015917. Frechette:2016: S
SR:3015812.3015917.
12. Gebser, M., Kaufmann, B., Neumann, A.,
Schaub, T. clasp: A conflict-driven
answer set solver. In Logic
Programming and Nonmonotonic
Reasoning (2007), 260–265.
13. Gomes, C.P., Selman, B. Algorithm
portfolios. Artificial Intelligence 126,
1 (2001), 43–62.
14. Hoos, H.H. Programming by
optimization. Communications of the
ACM 55, 2 (Feb. 2012), 70–80.
15. Hutter, F., Hoos, H.H., Leyton-Brown, K.
Sequential model-based optimization
for general algorithm configuration. In
Learning and Intelligent Optimization
Conference (LION) (2011), 507–523.
16. Hutter, F., Hoos, H.H., Leyton-Brown, K.,
Stützle, T. ParamILS: an automatic
algorithm configuration framework.
Journal of Artificial Intelligence
Research 36, 1 (2009), 267–306.
17. Hutter, F., Lindauer, M., Bayless, S.,
Hoos, H., Leyton-Brown, K. Results of
the configurable SAT solver challenge
2014. Technical report, University of
Freiburg, Department of Computer
Science, 2014.
18. Hutter, F., López-Ibáñez, M., Fawcett,
C., Lindauer, M., Hoos, H.H.,
Leyton-Brown, K., Stützle, T. A Clib: A
benchmark library for algorithm
configuration. In Conference on
Learning and Intelligent Optimization
(LION) (Springer, 2014), 36–40.
19. Järvisalo, M., Le Berre, D., Roussel, O.,
Simon, L. The international SAT solver
competitions. Artificial Intelligence
Magazine 33, 1 (2012), 89–92.
20. Kadioglu, S., Malitsky, Y., Sellmann, M.,
Tierney, K. ISAC–instance-specific
algorithm configuration. In European
Conference on Artificial Intelligence
(ECAI) (2010), 751–756.
21. Kearns, M., Dworkin, L. A computational
study of feasible repackings in the
FCC incentive auctions. CoRR,
abs/1406.4837, 2014.
22. KhudaBukhsh, A. R., Xu, L., Hoos, H.H.,
Leyton-Brown, K. SATenstein:
Automatically building local search SAT
solvers from components. Artificial
Intelligence 232 (2016), 20–42.
23. Knutson, R., Gryta, T. Verizon, AT&T
may face bidding limits in spectrum
auction. Wall Street Journal (Apr.
2014). http://www.wsj.com/articles/SB
100014240527023046263045795101
54106120342. Accessed 2016-12-12.
24. Leyton-Brown, K. The viability of exact
feasibility checking. Talk at the
Stanford Institute for Economic Policy
Research Conference on the design of
the U.S. Incentive Auction for
reallocating spectrum bet ween
wireless telecommunications and
television broadcasting, February 2013.
25. Li, S. Obviously strategy-proof
mechanisms. Available at SSRN
2560028, 2015.
26. López-Ibáñez, M., Dubois-Lacoste, J.,
Pérez Cáceres, L., Stützle, T., Birattari, M.
The irace package: Iterated racing for
automatic algorithm configuration.
Operations Research Perspectives 3
(2016), 43–58.
27. Milgrom, P. Putting Auction Theory to
Work. Churchill Lectures in Economics.
Cambridge University Press, 2004.
28 Milgrom, P., Segal, I. Deferred-
acceptance auctions and radio
spectrum reallocation. In ACM
Conference on Economics and
Computation (EC) (2014), 185–186.
29. Monette, J.-N., Deville, Y., Van
Hentenryck, P. Aeon: Synthesizing
Scheduling Algorithms from
High-Level Models, 47 (Springer,
Boston, 2009), 43–59.
30. Newman, N., Leyton-Brown, K., Milgrom, P.,
Segal, I. Assessing economic
outcomes in simulated reverse clock
auctions for radio spectrum. Technical
report, abs/1706.04324 (2017). http://
arxiv.org/abs/1706.04324.
31. Nudelman, E., Leyton-Brown, K.,
Andrew, G., Gomes, C., McFadden, J.,
Selman, B., Shoham, Y. Satzilla 0.9.
Solver description, International SAT
Competition, 2003.
32. Westfold, S. J., Smith, D.R. Synthesis of
efficient constraint-satisfaction
programs. The Knowledge Engineering
Revie w 16, 1 (March 2001), 69–84.
33. Xu, L., Hoos, H.H., Leyton-Brown, K.
Hydra: Automatically configuring
algorithms for portfolio-based
selection. In AAAI Conference on
Artificial Intelligence (2010), 210–216.
34. Xu, L., Hutter, F., Hoos, H. H.,
Leyton-Brown, K. SATzilla:
portfolio-based algorithm selection
for SAT. Journal of Artificial
Intelligence Research 32 (June
2008), 565–606.
35. Zhang, C., Bengio, S., Hardt, M., Recht, B.,
Vinyals, O. Understanding deep learning
requires rethinking generalization. CoRR,
abs/1611.03530, 2016.
© 2018 ACM 0001-0782/18/1 $15.00