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

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

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.