AF: Small: New Directions in Algorithmic Game Theory

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

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 online auction websites, 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? To what extent can simple and practical solutions substitute for complex but theoretically justified solutions? Another example of a fundamental economic problem is fair division (as seen, for example, when dividing an estate among its heirs). What's the most sensible way of defining a "fair outcome," and how much work is required to find one? This research project will develop theory to help answer all of these questions. The research project also involves the mentoring of PhD students, innovation in graduate teaching, the dissemination of lecture videos and notes for graduate courses, and the teaching of algorithmic fundamentals through massive online open courses.The specific goals of the project are divided into four categories. The first set of goals seeks relatively simple solutions to economic design problems that provably approximate the theoretical optimum. The project includes two new directions for this area: the design of simple contracts for principal agent settings, and the design of resale-proof revenue-maximizing auctions. The second set of goals investigates the question of how to best learn near-optimal auctions from data, focusing on the important but unresolved algorithmic and strategic issues of the problem. The third set of goals develops complexity-theoretic barriers in economics, with specific applications to equilibria in markets with divisible goods, to extended formulations for the polytope of interim allocation rules, and to the inherent complexity of optimal prior-free digital goods auctions. The fourth set of goals concern fair division, where the goal is to distribute resources among competing players in a "fair" way, with a focus on the multi-party communication complexity of the problem with indivisible items.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.