CAREER: Pushing the Boundaries of Learning Dynamics and Equilibrium Computation in Games: Control, Complexity, and Nonlinear Optimization

Many real-world settings involve the interaction of multiple agents with diverse goals and differing amounts of private information. These range from military and security settings, to auctions, to networks. Developing technology to find optimal behavior—also known as equilibrium—in these interactions has the potential of enabling more economically efficient auctions, enhance strategic reasoning in situations of conflict, and improve our ability to predict the evolution of complex multiagent systems. This proposal aims to advance our theoretical and practical understanding of equilibrium computation, improve the efficiency of computing various equilibrium notions, and enable the development of high-precision and practical methods across a variety of settings. This project also includes a comprehensive plan for incorporating the research into undergraduate and graduate courses, preparing students to tackle interdisciplinary challenges at the interface of optimization, game theory, and computer science. This project addresses several fundamental gaps in our current understanding of equilibrium computation and learning dynamics in multiagent interactions ("games"), with a bias towards focusing on techniques that will enable the construction of new state-of-the-art algorithms for equilibrium computation at scale. Concretely, it tackles four key technical challenges. 1) It refines the understanding of learning dynamics in games, employing tools from nonlinear dynamical systems to construct state-of-the-art algorithms with optimal regret guarantees. 2) It investigates the efficiency of computing equilibrium notions, such as correlated equilibria and its variants, in structured games like imperfect-information extensive-form games. 3) It seeks to overcome the limitations of current low-precision methods by developing practical algorithms for high-precision equilibrium computation. 4) It clarifies the computational complexity of nonconvex games by examining the role of constraints and extending recent advances. 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.