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

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.