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.