NSF-BSF: AF: Small: Algorithmic Game Theory: Equilibria and Beyond

美国公司和政府机构在极其复杂的环境中进行高风险拍卖，竞标者采用复杂的算法。代理人行为的策略方面需要对其不同的激励进行博弈论推理，而其庞大的数量和复杂的环境需要有效的算法。这项研究正在推进经济学和计算机科学交叉领域的基本问题，巩固了这些拍卖背后的理论基础。新的见解旨在为拍卖设计提供信息，从而改进和更稳健的拍卖，提高效率和收入。该教育计划包括针对本科生和研究生的课程开发和研究培训，以及促进早期职业研究人员（学生和博士后）的专业研讨会。具体的研究方向围绕着两个自然的问题，关于拍卖的设计和分析，以及战略代理人使用的更一般的系统：(i)代理人会收敛到平衡吗？这个项目采用了一种计算方法来解决这个问题，并询问在什么情况下平衡可以有效地计算。将特别强调可处理的、超越最坏情况的情况。（ii）如果代理不收敛到一个均衡，一个人应该如何建模他们的行为？在不同的行为模型下，对结果的质量有什么保证？例如，当对算法策略代理进行建模时，用越来越流行的常见机器学习算法（如无后悔算法）取代经典的（完全理性的）博弈论假设是很自然的。除了直接应用于机构设计之外，该研究还发展了计算复杂性和优化的基本联系。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

U.S. firms and government agencies run high-stakes auctions in exceedingly complex environments with sophisticated, algorithmic bidders. The strategic aspect of the agent behavior requires game-theoretic reasoning about their different incentives, and their large numbers and complex environment demand efficient algorithms. This research is advancing fundamental questions at the intersection of Economics and Computer Science, solidifying the theoretical foundations underlying these auctions. The new insights are intended to inform the design of auctions, leading to improved and more robust auctions, with better efficiency and greater revenue. The education plan incorporates course development and research training for both undergraduate and graduate students, as well as professional workshops that promote early-career researchers (students and postdocs). The specific research directions are centered around two natural questions regarding the design and analysis of auctions, and more generally systems used by strategic agents: (i) Will the agents converge to an equilibrium? This project takes a computational approach with respect to this problem and asks in what scenarios equilibria can be computed efficiently. A particular emphasis will be given to tractable, beyond-worst-case instances. (ii) If agents do not converge to an equilibrium, how should one model their behavior? What guarantees can be given on the quality of outcomes under alternative behavioral models? For example, when modeling algorithmic strategic agents, it is natural to replace classical (fully rational) game-theoretic assumptions with common machine-learning algorithms (such as no-regret algorithms) that have become increasingly popular. Beyond the immediate applications to mechanism design, the research is also developing fundamental connections to computational complexity and optimization.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.