[talks] Jonathan Schneider will present his FPO "Learning Algorithms in Strategic Environments" on Wednesday, 8/15/2018 at 1pm in CS 402.
Nicki Gotsis
ngotsis at CS.Princeton.EDU
Thu Aug 9 13:38:10 EDT 2018
Jonathan Schneider will present his FPO "Learning Algorithms in Strategic Environments" on Wednesday, 8/15/2018 at 1pm in CS 402.
The members of his committee are as follows: Adviser: Mark Braverman; Readers: Matt Weinberg and Omri Weinstein (Columbia); Examiners: Bernard Chazelle, Elad Hazan, and Mark Braverman.
A copy of his thesis is available upon request. Everyone is invited to attend his talk.
The talk abstract follows below.
Learning algorithms are often analyzed under the assumption their inputs are drawn from
stochastic or adversarial sources. Increasingly, these algorithms are being applied in strategic
settings, where we can hope for stronger guarantees. This thesis aims to understand the
performance of existing learning algorithms in these settings, and to design new algorithms that
perform well in these settings.
This thesis is divided into three parts. In Part I, we address the question of how agents
should learn to bid in repeated non-truthful auctions { and conversely, how should we design
auctions whose participants are learning agents.
In Part II, we study the dynamic pricing problem: the question of how should a large retailer
learn how to set prices for a sequence of disparate goods over time, based on observing demands
for goods at various prices. Previous work has demonstrated how to obtain O(log T) regret for
this problem. We show how to achieve regret O(log log T), which is tight. Our algorithm uses
ideas from integral geometry (most notably the concept of intrinsic volumes).
Finally, in Part III, we study how to learn the ranking of a set of N items from pairwise
comparisons that may be strategic or noisy. In particular, we design mechanisms for a variety of
settings (choosing the winner of a round-robin tournament, aggregating the top-K items under
the strong stochastic transitivity noise model) which outperform the naive rule of ranking items
according to the total number of pairwise comparisons won.
More information about the talks
mailing list