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

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

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.