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

博弈论分析已经成为广泛学科的重要工具，包括经济学、政治学、运筹学和计算机科学。随着算法决策在整个经济中的影响越来越大，以及计算基础设施的相关改进，我们希望理解和控制的战略互动的性质变得越来越复杂。因此，博弈论分析的纯数学方法越来越需要有效的计算工具来补充，以深入研究它们。然而，尽管在过去的几十年里，计算博弈论取得了巨大的进步，但仍然存在许多重要的战略互动类别，其中没有可扩展的解决方案，特别是在不完全信息存在的情况下的推理，这涉及参与者对他人偏好的不确定。例如，通常用于在线设置的组合拍卖，以及许多防御者和攻击者之间的安全策略交互，都没有有效的通用分析技术。我们的目标是通过利用深度学习革命，特别是用于函数表示和基于梯度的优化的无数高效工具，显著提高分析此类多方交互的技术水平，这些工具可用于解决此类大型复杂问题。具体来说，虽然基于梯度的方法取得了一些进展，但在实践中，它们被限制在具有完全信息的情况下，要么是一次，两个人的Stackelberg博弈，比如由单个大公司主导的市场决策，要么是零和博弈（包括那些信息不完全的）。我们的研究将更多地利用现代深度神经网络架构的表征能力来开发平衡近似算法，这些算法可以显着扩展可大规模分析的类别，其中许多提出的进展专门针对在不完整信息存在的情况下自动发现和利用对称性和稀疏性。此外，该项目将有助于开发博弈论建模和分析的本科和研究生课程，并将支持研究生和本科生在经济学和计算方面的跨学科研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.