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 16], [EFFTW 17], [BMSW 18]

Combinatorial Auctions: Consider a set of players who wish to allocate a set of items amongst themselves in a way that maximies the welfare. That is, each player has a valuation function over subsets of items, and they wish to jointly maximize the sum of players' values for the set she receives. More specifically, they would like to do so with as little communication as possible. Such problems are fairly well-understood in the absence of incentives, but what if players selfishly want to maximize their own value and may manipulate a proposed communication protocol? [BMW 18]

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], [KGCWF 18]

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]

Algorithms Under Uncertainty: 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]