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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Neural Lyapunov Control for Discrete-Time Systems

离散时间系统的神经李亚普诺夫控制

• 发表时间: 2024-01
• 期刊: Advances in neural information processing systems
• 作者: Wu, Junlin;Clark, Andrew;Kantaros, Yiannis;Vorobeychik, Yevgeniy
• 通讯作者: Vorobeychik, Yevgeniy

Neural Lyapunov Control for Discrete-Time Systems

离散时间系统的神经李亚普诺夫控制

• 发表时间: 2023-12
• 期刊: Advances in neural information processing systems
• 作者: Wu, Junlin;Clark, Andrew;Kantaros, Yiannis;Vorobeychik, Yevgeniy
• 通讯作者: Vorobeychik, Yevgeniy

Computing an Optimal Pitching Strategy in a Baseball At-Bat

计算棒球击球中的最佳投球策略

• 发表时间: 2023-11
• 期刊: Florida AI Research Society Conference
• 作者: Douglas, Connor;Witt, Everett;Bendy, Mia;Vorobeychik, Yevgeniy
• 通讯作者: Vorobeychik, Yevgeniy

A Partially Supervised Reinforcement Learning Framework for Visual Active Search

用于视觉主动搜索的部分监督强化学习框架

• 发表时间: 2024-01
• 期刊: Advances in neural information processing systems
• 作者: Sarkar, Anindya;Jacobs, Nathan;Vorobeychik, Yevgeniy
• 通讯作者: Vorobeychik, Yevgeniy

Exact Verification of ReLU Neural Control Barrier Functions

ReLU 神经控制屏障函数的精确验证

• 发表时间: 2023-12
• 期刊: Advances in neural information processing systems
• 作者: Zhang, Hongchao;Wu, Junlin;Vorobeychik, Yevgeniy;Clark, Andrew
• 通讯作者: Clark, Andrew