Assistant Professor

点击翻译按钮获取中文摘要

Recent years have seen a convergence of ideas and research goals between Computer Science and Economics. Computer Science enabled the development of a new genre of computational platforms that require economic as well as engineering thinking for their proper design and study; primary examples are those systems created and enabled by the Internet. Economics brought to the discussion quantitative models and tools useful to analyze these systems. At the same time, it became clear that the computational nature of these models and tools is crucial for them to be used to study systems with thousands or even millions of interacting individuals. Motivated by this realization, computer scientists have taken in the past decade a fresh, computational look at Game Theory and Economics. One major focus is Algorithmic Mechanism Design, in which we seek for computational efficient systems that are so cleverly designed that users’ selfish behavior helps advance the designer's objectives. The goal of this proposal is to enrich Algorithmic Mechanism Design from two directions that – to the PI’s opinion – has not been sufficiently explored in the literature. We aim (i) to understand how the complexity of an auction affects its performance, and (ii) to apply Algorithmic Mechanism Design to systems beyond auctions. Algorithmic Mechanism Design has mainly focused on optimal auction design for various objectives so far. However, the optimal auction is usually complicated and thus hard to implement in practice. The first half of this proposal aims to understand how the complexity of an auction affects its performance, and propose new simple practical auctions with provable performance guarantees. I will employ tools from Theoretical Computer Science and Applied Probability (1) to search for simple and (nearly-) optimal auctions in certain basic and fundamental multi-item multi-bidder settings, (2) to identify settings where the optimal auctions have simple formats, and (3) to study the computational complexity of finding a Bayes-Nash equilibrium in simple non-truthful auction games for the combinatorial auction problem. The second part of this proposal aims to expand the applicability of Algorithmic Mechanism Design to settings beyond auctions. I will import concepts, ideas and techniques from Economics (1) to design mechanisms for data science – incentivizing workers to provide high quality data for statistical estimation with low cost, and (2) to design computational efficient mechanism for fair resource allocation.