NSF-BSF: AF: Small: Mechanisms for Auctions and Markets - The Interplay of Incentives and Optimization

拍卖是算法博弈论的核心。从实际的角度来看，拍卖的重要性源于其在eBay等数字商务平台上的大量应用，在频谱拍卖等政府运营的大型项目上的应用，以及作为在线广告行业的基础。这种大型拍卖的出现，导致了设计能够处理大量数据的拍卖的必要性。从数学的角度来看，这是本项目的重点，拍卖提供了一个优雅的数学模型，使人们能够研究对市场设计至关重要的各种元素的交叉作用，如优化、激励、计算和信息理论的限制。实际上，算法机制设计的兴起可以归因于对可计算且足够强大的机制的需求，这些机制能够有效地处理玩家的动机。用于设计和分析大型系统的丰富的理论计算机科学工具箱是在拍卖环境中应用的完美候选人。该项目解决了组合拍卖中激励和优化目标的冲突。在某些情况下，从计算的角度来看，潜在的优化问题很容易解决，但却不可能正确地激励玩家。这里的一个例子是迈尔森和萨特思韦特提出的经典双边贸易问题。这个问题的小尺寸使得它在计算上没有挑战性。然而，考虑到代理的激励限制了适用的算法集。相比之下，组合拍卖涉及大量参与者和多种资源分配。在这种情况下，福利最大化的优化任务本身就具有挑战性。这个项目解决了几个基本环境中福利最大化的困难，以及调和现有算法技术与激励兼容性要求的困难。计算效率高的近似算法是否比激励兼容的近似算法更强大一直是广泛研究的主题。直到最近，两个家族之间的权力差距才首次显现出来。这个项目的目标是证明在没有这个要求的情况下，激励兼容机制和算法的力量之间存在显著的分离。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Auctions are at the epicenter of algorithmic game theory. From a practical perspective, the importance of auctions stems from their numerous applications, in digital-commerce platforms such as eBay, in huge government-run endeavors like the spectrum auctions, and as the basis for the online advertisement industry. The emergence of such huge auctions has led to the necessity of designing auctions that can handle vast amounts of data. From a mathematical point of view, which is the focus of this project, auctions present an elegant mathematical model that allows one to study the intersecting roles of various elements that are crucial for market design, such as optimization, incentives, and computational and information-theoretic limitations. Indeed, the rise of algorithmic mechanism design can be attributed to the demand for mechanisms which are computationally tractable and yet are powerful enough to properly handle the incentives of the players. The rich toolbox of theoretical computer science for designing and analyzing large-scale systems is a perfect candidate for applying in the context of auctions. This project addresses the clash of incentives and optimization objectives in combinatorial auctions. In some settings the underlying optimization problem is easy from a computational point of view, but it is impossible to incentivize the players properly. An example domain here is the classic bilateral trade problem introduced by Myerson and Satterthwaite. The small size of the problem makes it computationally unchallenging. However, taking into account the incentives of agents limits the set of applicable algorithms. In contrast, combinatorial auctions involve a large number of players and multiple resources to be allocated. In these settings, the optimization task of welfare maximization itself is challenging. This project addresses the difficulty of welfare maximization in several fundamental settings, as well as the difficulty of reconciling existing algorithmic techniques with the requirement of incentive-compatibility. Whether computationally efficient approximation algorithms are more powerful than their incentive-compatible counterparts has been the subject of extensive research. Only very recently, the first gap between the power of the two families was demonstrated. The goal of this project is to prove a significant separation between the power of incentive-compatible mechanisms and algorithms without this requirement.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.