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

AF：小：算法博弈论、复杂性理论和学习理论之间的联系

• 批准号: 1524062
• 负责人: Tim Roughgarden
• 金额: $ 40万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1524062&HistoricalAwards=false
• 关键词: AF; Small; Connections; Between; Algorithmic

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.

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