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

NSF-BSF：AF：小：算法博弈论：均衡及超越

• 批准号: 2112824
• 负责人: Aviad Rubinstein
• 金额: $ 50万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2112824&HistoricalAwards=false
• 关键词: NSF; BSF; AF; Small; Algorithmic

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.

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