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

RI：小型：不完整信息的大规模博弈论推理

• 批准号: 2214141
• 负责人: Yevgeniy Vorobeychik
• 金额: $ 39.9万
• 依托单位: Washington University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-01 至 2025-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2214141&HistoricalAwards=false
• 关键词: RI; Small; Large; Scale; Game

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.

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

项目成果

A Partially Supervised Reinforcement Learning Framework for Visual Active Search

• DOI: 10.48550/arxiv.2310.09689
• 发表时间: 2023-10
• 期刊: ArXiv
• 作者: Anindya Sarkar;Nathan Jacobs;Yevgeniy Vorobeychik

Neural Lyapunov Control for Discrete-Time Systems

• DOI: 10.48550/arxiv.2305.06547
• 发表时间: 2023-05
• 期刊: ArXiv
• 作者: Junlin Wu;Andrew Clark;Y. Kantaros;Yevgeniy Vorobeychik

Exact Verification of ReLU Neural Control Barrier Functions

• DOI: 10.48550/arxiv.2310.09360
• 发表时间: 2023-10
• 期刊: ArXiv
• 作者: Hongchao Zhang;Junlin Wu;Yevgeniy Vorobeychik;Andrew Clark

Computing an Optimal Pitching Strategy in a Baseball At-Bat

• DOI: 10.32473/flairs.36.133346
• 发表时间: 2021-10
• 期刊: ArXiv
• 作者: Connor Douglas;Everett Witt;Mia Bendy;Yevgeniy Vorobeychik