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

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

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.