Alex Slivkins talk, Friday, 10/16, 11am
David Kempe
we have another exciting theoretical CS talk coming up: Dr. Alex
Slivkins from Microsoft Research will be speaking on Truthful
Multi-Armed Bandit Mechanisms this Friday (10/16).
All the relevant information is below.
Looking forward to seeing many of you there.
Date: Friday, 10/16/2009
Time: 11:00am
Location: PHE 333
Speaker: Dr. Alex Slivkins (Microsoft Research SVC)
Title:
"Learning in a Pay-per-Click Auction:
Characterizing Truthful Multi-Armed Bandit Mechanisms"
ABSTRACT: We consider a multi-round auction setting motivated by
pay-per-click auctions for Internet advertising. In each round the
auctioneer selects an advertiser and shows her ad, which is then either
clicked or not. An advertiser derives value from clicks; the value of a
click is her private information. Initially, neither the auctioneer nor the
advertisers have any information about the likelihood of clicks on the
advertisements. The auctioneer's goal is to design a (dominant strategies)
truthful mechanism that (approximately) maximizes the social welfare.
If the advertisers bid their true private values, our problem is equivalent
to the "multi-armed bandit problem", and thus can be viewed as a strategic
version of the latter. In particular, for both problems the quality of an
algorithm can be characterized by "regret", the difference in social welfare
between the algorithm and the benchmark which always selects the same "best"
advertisement. We investigate how the design of multi-armed bandit
algorithms is affected by the restriction that the resulting mechanism must
be truthful. We find that truthful mechanisms have certain strong structural
properties -- essentially, they must separate exploration from exploitation
-- *and* they incur much higher regret than the optimal multi-armed bandit
algorithms. Moreover, we provide a truthful mechanism which (essentially)
matches our lower bound on regret.
Joint work with Moshe Babaioff (Microsoft Research SVC) and Yogi Sharma
(Cornell), published in ACM EC, 2009.
BIO:
Dr. Alex Slivkins is a researcher at Microsoft Research, Silicon Valley
Center. He received his PhD from Cornell University's CS department, advised
by Jon Kleinberg, and then was a Postdoc at Brown University, working with
Eli Upfal.
His research area is the design and analysis of algorithms. Specific topics
of interest include large networks, metric embeddings, online learning, and
mechanism design.
--
David Kempe <dke...@usc.edu>