[talks] Jieming Mao FPO Thursday June 14, 2018 10:00 CS 402

[Barbara A. Mooring]

Jieming Mao will present his FPO on Thursday June 14, 2018 at 10:00 in room CS 402.

Committee:
Mark Braverman, Adviser - Princeton University
Elad Hazan - Princeton University
Ran Raz - Princeton University

All are welcomed to attend.

Title: Algorithms in Strategic or Noisy Environments

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 envrionments.
In Part II (Chapter 4 and Chapter 5), we focus on combinatorial auctions which are a
natural testbed 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. In
this problem, even if the agents are perfectly incentivized, their reported comparison results
could still be noisy caused by reasons like limit of knowledge and subjective preferences. We
design algorithms which aggregate noisy comparisons to output the set of top items.

Barbara A. Mooring
Interim Graduate Coordinator
Computer Science Department
Princeton University