COMPUTER SCIENCE RESEARCH WEEK 2019

Economics and Computer Science of a Radio Spectrum Reallocation

Speaker
Dr Kevin Leyton-Brown, Professor, University of British Columbia
Contact Person
Dr Reza SHOKRI, Associate Professor, School of Computing
reza@comp.nus.edu.sg

08 Jan 2019 Tuesday, 10:00 AM to 11:30 AM

SR1, COM1-02-06

This is a distinguished talk as part of the NUS Computer Science Research Week 2019 (http://researchweek.comp.nus.edu.sg).

Abstract:

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 design of both the auction and of SATFC. Compared to typical market design settings, the auction design was particularly unconstrained, with flexibility in the definitions of participants' property rights, the goods to be traded, their quantities, and the outcomes the market should seek to achieve. Computational tractability was also a first-order concern. The design of SATFC was achieved via a data-driven, highly parametric, and computationally intensive approach we dub "deep optimization". 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.

Experiments on realistic problems showed that within the short time budget required in practice, SATFC solved more than 96% of the problems it encountered. Furthermore, simulations showed that the incentive auction paired with SATFC produced nearly optimal allocations in a restricted setting and achieved substantially better economic outcomes than other alternatives at national scale.

The talk starts with a tutorial on the preliminaries and the theoretical foundations of this topic.


Biodata:

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 various problems in artificial intelligence, notably the automated design and analysis of algorithms for solving hard computational problems.

He currently advises Auctionomics, AI21, and Qudos. He is a co-founder of Kudu.ug and Meta-Algorithmic Technologies. He was scientific advisor to UBC spinoff Zite until it was acquired by CNN in 2011. His past consulting has included work for Zynga, Trading Dynamics, Ariba, and Cariocas.