[AI Seminar] UPDATE: AI Seminar: Kevin Leyton-Brown, Apr. 28

Charlotte Yano yano at cs.cmu.edu
Wed Apr 22 14:00:37 EDT 2015

I now have the talk title and abstract.
Meetings are available on the 28th and 29th.

Kevin Leyton-Brown
University of British Columbia.
3:30pm, Apr. 28, 2015
GHC 6115

Incentive Auctions and Spectrum Repacking

This talk will discuss the FCC's upcoming "incentive auction", in which television broadcasters will be given the opportunity to sell their broadcast rights, remaining broadcasters will be repacked into a smaller block of spectrum, and the freed airwaves will be resold to telecom companies. The stakes for this auction are huge-projected tens of billions of dollars in revenue for the government-justifying the design of a special-purpose descending-price auction mechanism, which I'll discuss. An inner-loop problem in this mechanism is determining whether a given set of broadcasters can be repacked into a smaller block of spectrum while respecting radio interference constraints. This is an instance of a (worst-case intractable) graph coloring problem; however, stations' broadcast locations and interference constraints are all known in advance. Early efforts to solve this problem considered mixed-integer programming formulations, but were unable to reliably solve realistic, national-scale problem instances. We advocate instead for the use of a SAT encoding, paired with a wide range of techniques: constraint graph decomposition; novel caching mechanisms that allow reuse of partial solutions from related, solved problems; algorithm configuration; algorithm portfolios; and the marriage of local-search and complete solver strategies. Considering a set of realistic problems derived from auction simulations, we show that our approach solves virtually all within the short time budget required in practice.

Kevin Leyton-Brown is a professor of computer science at the University of British Columbia. 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 6,000 citations and an h-index of 33. He is the recipient of 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 competitions (2003-12).

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 two 4-year terms), and was program chair for the ACM Conference on Electronic Commerce (ACM-EC) in 2012. 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 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), Zynga, Inc., and Qudos, Inc. He is a co-founder of Kudu.ug and a new UBC spinoff, Meta-Algorithmic Technologies. In the past, he served as a consultant for Trading Dynamics Inc., Ariba Inc., Cariocas Inc., and was scientific advisor to UBC spinoff Zite Inc. until it was acquired by CNN in 2011.



Charlotte Yano
Building Curator
Administrative Associate II
Carnegie Mellon University, Computer Science Dept.
5000 Forbes Ave.
Pittsburgh, PA  15213
 cogs are for gears, not people.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/ai-seminar-announce/attachments/20150422/684b6032/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AI Seminar Kevin Leyton-Brown 2015.pdf
Type: application/pdf
Size: 412185 bytes
Desc: AI Seminar Kevin Leyton-Brown 2015.pdf
URL: <http://mailman.srv.cs.cmu.edu/pipermail/ai-seminar-announce/attachments/20150422/684b6032/attachment-0001.pdf>

More information about the ai-seminar-announce mailing list