Skip navigation
Please use this identifier to cite or link to this item:
Title: Learning Algorithms in Strategic Environments
Authors: Schneider, Jonathan
Advisors: Braverman, Mark
Contributors: Computer Science Department
Keywords: algorithmic mechanism design
multi-armed bandits
online learning
Subjects: Computer science
Issue Date: 2018
Publisher: Princeton, NJ : Princeton University
Abstract: 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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Schneider_princeton_0181D_12730.pdf1.52 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.