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.