Collaborative Research: AF: Small: Mechanisms with Predictions

半个多世纪以来，计算机科学中对算法进行数学分析的主要方法是“最坏情况分析”，即使用最坏的可能情况来评估算法的性能。从积极的方面来看，最坏情况保证提供了关于算法鲁棒性的有用信号。然而，众所周知，这种分析可能是不必要的悲观，经常导致没有信息的性能界限或不可能的结果，这些结果可能无法反映实践中出现的真正障碍。这些关键缺陷使得最坏情况分析变得不那么重要，尤其是考虑到机器学习的惊人进步，这些进步产生了非常有效的算法，其中大多数算法不承认任何非平凡的最坏情况保证。在最坏情况分析和机器学习算法之间的紧张关系的推动下，最近关于“带有预测的算法”的研究激增，旨在通过设计由机器学习预测指导的强大算法，实现两全其美。在这个项目中，目标是将这个学习增强框架扩展到算法分析之外，朝着在自利益代理存在的情况下设计机制的更高要求的任务（例如，出售商品的拍卖、选择候选人的选举或调度计算作业的政策）。与算法非常相似，机制遵循将输入转换为输出的一系列步骤，但设计机制更为复杂，因为它们的一些输入和输出可能由战略代理控制，其目标是最大化自己的效用。因此，一个机制要想有效，就必须考虑到参与主体的激励。本研究产生的学习增强机制将通过机器学习对代理偏好的预测得到增强，使它们能够克服过于悲观的不可能结果，并对机制设计领域产生变革性影响。一个理想的学习增强机制是，当它提供的预测是准确的，同时保持最优的最坏情况保证时，无论预测有多不准确，都能实现强大的性能保证。本项目考虑了算法机制设计文献中核心领域的学习增强机制的设计和分析，如拍卖设计、无货币机制设计（其中机制不允许使用货币奖励）和在线机制设计（其中机制需要以动态方式做出不可撤销的决策）。此外，该项目还考虑了分散设置，其中该机制诱导参与代理之间的博弈，并根据博弈的纳什均衡评估其质量。对于这些领域的不同规范问题，该项目探讨了预测在多大程度上能够提高社会福利和收入方面的性能保证，这是算法博弈论的两个标准目标。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

For more than half a century, the dominant approach for the mathematical analysis of algorithms in computer science has been "worst-case analysis", which evaluates their performance using the worst possible instances. On the positive side, a worst-case guarantee provides a useful signal regarding the robustness of an algorithm. However, it is well-known that this analysis can be unnecessarily pessimistic, often leading to uninformative performance bounds or impossibility results that may not reflect the real obstacles that arise in practice. These crucial shortcomings are making worst-case analysis less relevant, especially in light of the impressive advances in machine learning that give rise to very effective algorithms, most of which do not admit any non-trivial worst-case guarantees. Motivated by this tension between worst-case analysis and machine-learning algorithms, a surge of recent work on "algorithms with predictions" is aiming for the best of both worlds by designing robust algorithms that are guided by machine-learned predictions. In this project, the goal is to extend this learning-augmented framework beyond the analysis of algorithms, toward the more demanding task of designing mechanisms in the presence of self-interested agents (e.g., auctions for selling goods, elections for selecting candidates, or policies for scheduling computational jobs). Much like algorithms, mechanisms follow a sequence of steps that transform an input to an output, but designing mechanisms is more complicated because some of their input and output may be controlled by strategic agents whose goal is to maximize their own utility. Therefore, for a mechanism to be effective, it needs to account for the incentives of the participating agents. The learning-augmented mechanisms resulting from this research will be enhanced with machine-learned predictions regarding the preferences of the agents, allowing them to overcome overly pessimistic impossibility results and to have a transformative impact on the field of mechanism design.An ideal learning-augmented mechanism is one that achieves strong performance guarantees when the predictions it is provided with are accurate, while simultaneously maintaining optimal worst-case guarantees, irrespective of how inaccurate the predictions may be. This project considers the design and analysis of learning-augmented mechanisms in central areas of the algorithmic mechanism design literature, such as auction design, mechanism design without money (where the mechanism is not permitted to use monetary rewards), and online mechanism design (where the mechanism needs to make irrevocable decisions in a dynamic fashion). Furthermore, the project also considers decentralized settings, where the mechanism induces a game among the participating agents and its quality is evaluated over the Nash equilibria of the game. For different canonical problems in each of these areas, the project explores the extent to which predictions can enable improved performance guarantees with respect to social welfare and revenue, which are the two standard objectives in algorithmic game theory.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.