Title: Simple vs. Optimal Mechanism Design
Advisor: Yang Cai
Other committee members:
Matt Weinberg (Princeton University)
In Mechanism Design, the goal is to design a mechanism/system such that a group of strategic agents, who are only interested in optimizing their own utilities, are incentivized to choose actions that also help achieve the designer’s objective. However, even in fairly basic settings, the theoretically optimal mechanisms are complex and randomized, while mechanisms used in practice are usually simple and deterministic. My work aims to resolve this discrepancy between theory and practice by studying the following questions: are the mechanisms used in practice close to optimal? Can we design simple mechanisms to approximate the optimal one? We show that in important settings such as multi-item auctions and two-sided markets, there are indeed simple and approximately optimal mechanisms.