RI: Small: Large-Scale Game-Theoretic Reasoning with Incomplete Information

Game-theoretic analysis has been a crucial tool across a broad array of disciplines, including economics, political science, operations research, and computer science. With the increased impact of algorithmic decision-making throughout the economy and the associated improvement in computing infrastructure, the nature of strategic interactions that we wish to understand and control has become increasingly complex.

As a result, purely mathematical methods for game-theoretic analysis need increasingly to be complemented by effective computational tools to study them in depth. However, despite dramatic progress in computational game theory over the last several decades, there remain important broad classes of strategic interactions for which no scalable solution approaches exist, particularly, reasoning in the presence of incomplete information, which involve participants that are uncertain about the preferences of others.

For example, combinatorial auctions, commonly used in online settings, and strategic interactions in security among many defenders and attackers, have no effective general-purpose analysis techniques. Our goal is to significantly advance the state of the art in analyzing such multiparty interactions by taking advantage of the deep learning revolution—in particular, the myriad of highly effective tools for function representation and gradient-based optimization that can be used to grapple with large, complex problems like these.

Specifically, while there has been some progress in gradient-based methods, they have been restricted in practice to situations with complete information that are either one-shot, two-player Stackelberg games, like decision-making in markets dominated by a single large firm, or zero-sum games (including those with imperfect information). Our research will leverage more heavily the representational power of modern deep neural network architectures to develop equilibrium approximation algorithms that significantly extend the class that can be analyzed at scale, with many of the proposed advances specifically aimed at automatically discovering and leveraging symmetry and sparsity in the presence of incomplete information.

Additionally, this project will contribute to developing undergraduate and graduate curricula on game-theoretic modeling and analysis, and will support graduate and undergraduate interdisciplinary research in economics and computation.

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.