Umesh
Vazirani
University
of
California,
Berkeley
Making
Google
Richer:
Optimal
Algorithms
for
the
AdWords
Auction
Abstract: This
year
the
combined
advertising
revenues
of
Google
and
Yahoo
is
expected
to
rival
the
combined
prime-time
ad
revenues
of
America's
three
big
television
networks,
ABC,
CBS,
and
NBC.
The
key
to
this
revolution
in
advertising
is
an
innovative
auction
run
by
the
search
engine
companies.
Companies'
bids
for
search
keywords
determine
which
ads
are
displayed
during
Internet
searches.
There
are
a
number
of
algorithmic
and
game
theoretic
issues
that
arise
in
this
context.
In
particular,
the
problem
of
maximizing
revenue
in
such
keyword
auctions
can
be
formulated
as
an
online
computational
problem.
I
will
describe
two
simple
algorithms
that
achieve
optimal
performance.
The
proofs
of
performance
of
these
algorithms
rely
on
a
new
linear
programming
based
technique
called
tradeoff
revealing
family
of
LPs,
which
I
will
briefly
touch
upon.
The talk is based on joint work with Aranyak Mehta, Amin Saberi and Vijay Vazirani.
Biography: Umesh Vazirani is a Professor in the Computer Science Division of the Department of Electrical Engineering and Computer Science at UC Berkeley. He received an NSF Presidential Young Investigator Award in 1987 and the Friedman Mathematics Prize in 1985. He has written the book, An Introduction of Computational Learning Theory (with Michael Kearns), and currently is at the forefront of research in the area of quantum computing.
Professor Vazirani is a Director of the Berkeley Quantum Information and Computation Center (BQIC).