Communications of the ACM

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.