AF: Small: New Directions in Algorithmic Game Theory

该研究项目的目标是开发理论计算机科学的新成果，这些成果对基本经济问题的推理有用。 例如，考虑在拍卖中出售物品的问题-如在线拍卖网站上的收藏品，政府拍卖中电信公司的无线频谱，或通过搜索引擎拍卖到广告商的赞助链接。 卖家如何利用过去的经验来设计更好的拍卖？ 在何种程度上，简单和实际的解决办法可以取代复杂但理论上合理的解决办法？另一个基本经济问题的例子是公平分配（例如，在继承人之间分配遗产时）。 什么是定义“公平结果”的最明智的方式，以及需要做多少工作才能找到一个？这个研究项目将发展理论来帮助回答所有这些问题。 该研究项目还涉及博士生的导师指导、研究生教学的创新、研究生课程的讲座视频和笔记的传播，以及通过海量在线开放课程教授算法基础知识，项目的具体目标分为四类。 第一组目标寻求经济设计问题的相对简单的解决方案，可证明接近理论最优。该项目包括这一领域的两个新方向：设计简单的合同委托代理设置，和设计的转售证明收入最大化拍卖。 第二组目标研究了如何从数据中最好地学习接近最优拍卖的问题，重点是这个问题的重要但尚未解决的算法和战略问题。 第三组目标发展了经济学中的复杂性理论障碍，具体应用于可分割商品市场的均衡，扩展了临时分配规则的多面体公式，以及最优无优先级数字商品拍卖的固有复杂性。第四组目标涉及公平分配，目标是以“公平”的方式在竞争参与者之间分配资源，重点关注不可分割项目问题的多方沟通复杂性。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.