AF: Small: Equilibrium Computation and Multi-Agent Learning in High-Dimensional Games

Yale University, New Haven CT

Investigators

Abstract

Over the last decade, Machine Learning (ML) has made significant strides in numerous applications. This success is largely attributed to the paradigm of training ML systems by minimizing a single loss function using efficient optimization algorithms. Yet, the landscape is shifting, with many emerging ML applications being better described as games played between multiple intelligent agents or algorithms. These games can be explicit, as seen in markets, traffic routing, game-solving systems (such as AlphaZero), and multi-agent Reinforcement Learning (RL) systems, or implicit, as in the case of generative adversarial networks, adversarial examples, robust optimization, and so on. While game theory offers a lens to understand these agent interactions, its classical form struggles to address challenges in contemporary ML applications. This is because traditional game theory often focuses on simpler, low-dimensional games, while ML frequently grapples with complex, high-dimensional ones. This project aims to provide a new theory for these complex, high-dimensional games, and as a result, offer new methods to analyze, train, and design multi-agent ML systems. This project includes an education plan that incorporates course development of both graduate and undergraduate courses, as well as training for graduate students and research opportunities for undergraduates. The first part of the project focuses on concave games, which encompass many that traditional game theory has studied, including all finite games. A game is concave if each agent chooses their strategy from a convex set, and their utility is a concave function in their own strategy. The investigator aims to develop optimal uncoupled algorithms for computing and learning equilibria in high-dimensional games. These games are common in ML applications, and the high-dimensionality often arises from numerous agents or complex available actions. Uncoupled algorithms require minimal knowledge about the game and little player coordination, making them especially suited for high-dimensional games and the preferred type of algorithms in practice. The second part of the project shifts focus to non-concave games, where agents may have non-concave utilities. The investigator plans to thoroughly reassess foundational solution concepts, given that conventional equilibrium existence often hinges on the concavity of utility functions. The main goal of this part is to identify appropriate solution concepts for non-concave games and understand their computational complexity. 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.