Incentive Auctions and Spectrum Repacking: A Case Study for "Deep Optimization"
University of British Columbia
Over 13 months in 2016--17 the US Federal Communications Commission conducted an "incentive auction" to repurpose radio spectrum from broadcast television to wireless internet. In the end, the auction yielded $19.8 billion USD, $10.05 billion USD of which was paid to 175 broadcasters for voluntarily relinquishing their licenses across 14 UHF channels. Stations that continued broadcasting were assigned potentially new channels to fit as densely as possible into the channels that remained. The government netted more than $7 billion USD (used to pay down the national debt) after covering costs (including retuning). A crucial element of the auction design was the construction of a solver, dubbed SATFC, that determined whether sets of stations could be "repacked" in this way; it needed to run every time a station was given a price quote.
This talk describes the process by which we built SATFC and its impact on the auction. We adopted an approach we dub "deep optimization", taking a data-driven, highly parametric, and computationally intensive approach to solver design. More specifically, to build SATFC we designed software that could pair both complete and local-search SAT-encoded feasibility checking with a wide range of domain-specific techniques, such as constraint graph decomposition and novel caching mechanisms that allow for reuse of partial solutions from related, solved problems. We then used automatic algorithm configuration techniques to construct a portfolio of eight complementary algorithms to be run in parallel, aiming to achieve good performance on instances that arose in proprietary auction simulations. We found that within the short time budget required in practice, SATFC solved more than 95% of the problems it encountered. Furthermore, simulation results showed that the incentive auction paired with SATFC produced nearly optimal allocations in a restricted setting and substantially outperformed other alternatives at national scale.
Kevin Leyton-Brown is a professor of Computer Science at the University of British Columbia and an associate member of the Vancouver School of Economics. He holds a PhD and M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). He studies the intersection of computer science and microeconomics, addressing computational problems in economic contexts and incentive issues in multiagent systems. He also applies machine learning to the automated design and analysis of algorithms for solving hard computational problems.
He has co-written two books, "Multiagent Systems" and "Essentials of Game Theory," and over 100 peer-refereed technical articles; his work has received over 8,000 citations and an h-index of 37. He is the recipient of UBC's 2015 Charles A. McDowell Award for Excellence in Research, a 2014 NSERC E.W.R. Steacie Memorial Fellowship—previously given to a computer scientist only 10 times since its establishment in 1965—and a 2013 Outstanding Young Computer Science Researcher Prize from the Canadian Association of Computer Science. He and his coauthors have received paper awards from JAIR, ACM-EC, AAMAS and LION, and numerous medals for the portfolio-based SAT solver SATzilla at international SAT solver competitions (2003–15).
He has co-taught two Coursera courses on "Game Theory" to over half a million students, and has received awards for his teaching at UBC—notably, a 2013/14 Killam Teaching Prize. He is chair of the ACM Special Interest Group on Electronic Commerce, which runs the annual Economics & Computation conference. He serves as an associate editor for the Artificial Intelligence Journal (AIJ), ACM Transactions on Economics and Computation (ACM-TEAC), and AI Access; serves as an advisory board member for the Journal of Artificial Intelligence Research (JAIR, after serving as associate editor for eight years); and was program chair for the ACM Conference on Electronic Commerce (ACM-EC) in 2012. In 2016 he was a visiting researcher at Microsoft Research New England and a visiting professor at Harvard's EconCS group. Previously, he spent the fall of 2015 at the Simons Institute for the Theory of Computing at UC Berkeley, and split his 2010–11 sabbatical between Makerere University in Kampala, Uganda and the Institute for Advanced Studies at Hebrew University of Jerusalem, Israel. He currently advises Auctionomics, Inc. (and through them, the Federal Communications Commission) and Qudos, Inc. He is a co-founder of Kudu.ug and Meta-Algorithmic Technologies. In the past, he served as a consultant for Zynga, Inc., Trading Dynamics Inc., Ariba Inc., Cariocas Inc., and was scientific advisor to UBC spinoff Zite Inc. until it was acquired by CNN in 2011.