Research



Below is a short description of some research directions I'm currently pursuing, along with some of my representative papers on these topics. For full publication list see here.

Algorithmic Mechanism Design: When real people interact with algorithms, they impose additional constraints beyond the algorithm's speed, storage, and correctness. For instance, real people have their own incentives that may misalign with the designer's goal - for this reason, they may choose not to follow a protocol as asked of them. Real people also behave more predictably in simple and transparent interactions, so this motivates formally considering the simplicity of algorithms deployed in these settings when measuring their quality. Below is a non-exhaustive list of domains where this kind of reasoning is necessary.

Auction Design: Every auction designer has an objective - perhaps to make as much revenue as possible. But participants in an auction have their own objectives - to get the goods they like the most and to pay as little as possible for receiving them. It turns out to be much more difficult (both conceptually and computationally) to design auctions that properly account for these incentives than to just solve the underlying algorithmic problems. Much of my work in this area aims to understand the structure of optimal auctions, and when the simple auctions we see every day are approximately optimal. [CDW 13], [BILW 14], [CDW 16]

Cryptocurrencies: Cryptocurrencies involve a peer-to-peer network that directly decides an allocation of money, so incentive issues naturally arise in additional to other security concerns. One issue is the following: cryptocurrencies propose a protocol for participants in the network to follow. Based on this, they will receive some monetary reward for doing so. But there is no way to force participants to follow the desired protocol - they might deviate if it will result in increased revenue. Indeed, such profitable deviations have already been discovered for the Bitcoin protocol. [CKWN 16]

Crowdsourcing: When problems are too big for a single entity to solve, a popular approach is to crowdsource - outsource the work to several small sources and aggregate the results. Of course, this raises its own issues: "the crowd" doesn't necessarily care about the quality of your solution, they only care about their own effort and reward. So you must cleverly incentivize workers to put in effort to complete these tasks well. These considerations also motivate new "traditional" algorithmic questions. [BMW 16]

Algorithmic Game Theory: Whereas Algorithmic Mechanism Design focuses on the designing systems with incentives in mind, Algorithmic Game Theory more broadly studies the interaction of real people in computational systems. For example, whether or not it's possible to design "better" systems, it's important to understand the quality of existing systems, or whether there's a need for centralized design at all. [FILW 14], [SSW 16]

Online Algorithms: Often, we must make irrevocable decisions today with limited information about how things will play out tomorrow. My own work has focused largely on online selection problems, where you are trying to select the best element(s) of a set. The catch is that elements are revealed to you one at a time, and you must immediately and irrevocably decide whether to accept or reject with uncertainty about whether better elements might arrive in the future. [KW12], [AKW 14]