AF: Small: Connections Between Algorithmic Game Theory, Complexity Theory, and Learning Theory

该研究项目的目标是开发理论计算机科学的新成果，这些成果对基本经济问题的推理有用。 例如，考虑在拍卖中出售物品的问题-如eBay上的收藏品，政府拍卖中电信公司的无线频谱，或通过搜索引擎拍卖到广告商的赞助链接。 卖家如何利用过去的经验来设计更好的拍卖？ 例如，搜索引擎如何利用其过去出价的宝库来优化其关键字拍卖？ 这样一个优化的解决方案比一般的解决方案好多少？ 这个研究项目将发展理论来帮助回答所有这些问题。 再举个例子，经济学的一个基本原则是，完美的市场是透明的--商品的价格是以供求平衡的方式确定的。 一个基本问题是要理解这种“市场均衡”何时保证存在。 本研究项目将开发理论，使用理论计算机科学（计算机算法）的不可能性结果来推导经济学（市场均衡）中的不可能性结果。该研究项目还涉及博士生的指导，研究生教学的创新，研究生课程的讲座视频和笔记的传播，通过大规模在线开放课程教授算法基础知识，以及组织传统和新的会议来介绍和讨论前沿研究。PI将追求广泛的研究议程，发展算法博弈论，复杂性理论和学习理论，在这些领域的中心问题的指导下。 第一组目标的目的是了解，当存在的机制，如简单的组合拍卖，与平衡性能保证所取得的最先进的近似算法一样好。 第二组目标将推进最坏情况下的机制的均衡性能的下限的最先进的。 第三组目标以新颖的方式应用计算复杂性来证明算法博弈论中其他基本概念的（条件）不可能性结果，包括瓦尔拉斯均衡和最优机制的边界型多面体特征。 第四组目标将学习理论的方法论应用于拍卖设计，例如通过确定实现接近最优收入所必需和足够的数据量。

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.