Skip navigation
Please use this identifier to cite or link to this item:
Title: Algorithms in Strategic or Noisy Environments
Authors: Mao, Jieming
Advisors: Braverman, Mark
Contributors: Computer Science Department
Subjects: Computer science
Issue Date: 2018
Publisher: Princeton, NJ : Princeton University
Abstract: Algorithms are often used to interact with agents. When the input is collected from agents instead of being directly given, designing algorithms becomes more challenging. Two main challenges arise here: (i) agents may lie to maximize their own utility functions and we need to take their incentives into account (ii) the uncertainty in agents' behavior makes the input appear to be noisy. In this thesis, we study these two challenges in several contexts: the multi-armed bandit problem, combinatorial auctions and rank aggregation. Our goal is to understand how these strategic and noisy factors make the problem harder and to design new techniques which make algorithms robust against these factors. In Part I (Chapter 2 and Chapter 3), we study multi-armed bandit algorithms in strategic environments where rewards are decided by actions taken by strategic agents. We show that traditional multi-armed bandit algorithms could fail and we also develop multi-armed bandit algorithms which achieve good performance in strategic environments. In Part II (Chapter 4 and Chapter 5), we focus on combinatorial auctions which are natural testbeds for truthful mechanisms. We characterize the power of truthful mechanisms in several settings and make progress in understanding whether truthful mechanisms are as powerful as algorithms. In Part III (Chapter 6, Chapter 7 and Chapter 8), we study the top-k ranking problem with comparisons collected from agents. Due to limit of knowledge and subjective preferences, even perfectly incentivized agents could provide noisy comparison results. We design algorithms which aggregate noisy comparisons to output the set of top-k items.
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 
Mao_princeton_0181D_12656.pdf1.35 MBAdobe PDFView/Download

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