University of British Columbia
3:30 p.m. • DC 1302
Abstract: This talk will discuss the FCC’s “incentive auction,” which proposes to give television broadcasters an opportunity to sell their broadcast rights, to repack remaining broadcasters into a smaller block of spectrum, and to resell the freed airwaves 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. We show that our approach solves virtually all of a set of problems derived from auction simulations within the short time budget required in practice.
Biography: Kevin
Leyton-Brown
is
a
professor
of computer
science at
the University
of
British
Columbia.
He
holds
a
PhD
and
MSc
from Stanford
University (2003;
2001)
and
a
BSc
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
7,000
citations
and
an h-index
of
35.
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
co-authors
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
is chair
of
the
ACM
Special
Interest
Group
on
Electronic
Commerce,
which
runs
the
annual Economics
and
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
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
is
currently
a
visiting
faculty
member
at
the
Simons
Institute
for
the
Theory
of
Computing;
previously,
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.