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.

游戏理论分析一直是各种各样的学科的关键工具，包括经济学，政治科学，运营研究和计算机科学。随着整个经济中算法决策的影响不断增加，以及计算基础设施的相关改进，我们希望理解和控制的战略互动的性质变得越来越复杂。结果，纯粹需要通过有效的计算工具来完成游戏理论分析的纯数学方法，以深入研究它们。然而，尽管在过去几十年中，计算游戏理论的进展巨大，但仍有重要的战略互动类别，这些互动尚无可扩展的解决方案方法，尤其是在存在不完整的信息的情况下推理，这涉及参与者对他人偏好不确定的参与者。例如，在在线环境中常用的组合拍卖以及许多防御者和攻击者在安全性中的策略互动，没有有效的通用分析技术。 Our goal is to significantly advance the state of the art in analyzing such multiple 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市场中的决策以一家大型公司或零和零游戏为主导（包括具有不完美信息的游戏）。我们的研究将更加严格地利用现代深度神经元网络体系结构的代表力，以开发同等的近似算法，这些算法显着扩展了可以大规模分析的类别，并且在存在不足信息的情况下，旨在自动发现和利用对称性和稀疏性的许多拟议进步。此外，该项目将有助于开发有关游戏理论建模和分析的本科生和毕业课程，并将支持经济学和计算领域的研究生和本科跨学科研究。该奖项反映了NSF的法定任务，并通过评估该基金会的知识级别的智力和广泛的影响来审查CRITERIA。