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）如果代理不收敛到平衡，那么应该如何建模其行为？在替代行为模型下的结果质量可以提供什么保证？例如，当对算法战略代理进行建模时，自然而然地用常用的机器学习算法（例如No-Regret算法）替换经典（完全理性的）游戏理论假设，这些假设已变得越来越受欢迎。除了对机制设计的直接应用外，该研究还在建立与计算复杂性和优化的基本联系。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的影响评估标准，被认为值得通过评估来获得支持。