The goal of this research project is to develop new results in theoretical computer science that are useful for reasoning about fundamental economic problems. For example, consider the problem of selling items in an auction --- such as collectables on eBay, wireless spectrum to telecommunication companies in a government auction, or sponsored links to advertisers through a search engine auction. How can a seller use past experience to design better auctions? For example, how can a search engine use its treasure trove of past bids to optimize its keyword auctions? How much better is such an optimized solution compared to a generic one? This research project will develop theory to help answer all of these questions. For another example, a basic tenet of economics is that perfect markets clear --- goods are priced in a way that supply equals demand. A fundamental problem is to understand when such "market equilibria" are guaranteed to exist. This research project will develop theory that uses impossibility results from theoretical computer science (for computer algorithms) to deduce impossibility results in economics (for market equilibria). The research project also involves the mentoring of PhD students, innovation in graduate teaching, the dissemination of lecture videos and notes for graduate courses, the teaching of algorithmic fundamentals through massive online open courses, and the organization of both traditional and new meetings for the presentation and discussion of cutting-edge research.
The PI will pursue a broad research agenda developing connections between algorithmic game theory, complexity theory, and learning theory, guided by the central problems in these fields. The first set of goals aims to understand when there exist mechanisms, such as simple combinatorial auctions, with equilibrium performance guarantees as good as those achieved by state-of-the-art approximation algorithms. The second set of goals will advance the state-of-the-art in lower bounds for the worst-case equilibrium performance of mechanisms. The third set of goals applies computational complexity in novel ways to prove (conditional) impossibility results for other basic concepts in algorithmic game theory, including Walrasian equilibria and Borders-type polyhedral characterizations of optimal mechanisms. The fourth set of goals applies the methodology of learning theory to auction design, for example by identifying the amount of data that is necessary and sufficient to achieve near-optimal revenue.
