RI: Medium: Techniques for Massive-Scale Strategic Reasoning: Imperfect-Information Subgame Solving and Offering Guarantees in Simulation-Based Games

战略互动的模型主要是足够简单的，人类可以在头脑中或纸面上解决。然而，许多--可以说是最重要的--战略环境超出了人类的限制。其中一个类别就是规模太大的问题。其中包括具有实际重要性的环境中的现实的详细模型，以及许多娱乐环境。另一类是不提供规则，求解器只能访问用于练习的模拟器。这种设置出现在国防应用、实时策略设置、交易模拟等方面。本研究将显著提高这两类求解算法在最现实的背景下的可扩展性：多步不完全信息策略交互。尽管独立于应用程序，但这些技术对于包括谈判、业务、防御、拍卖、战略定价、网络安全、医药等在内的用例都是必需的--基本上所有的战略交互。成果将纳入《计算游戏求解》和《合作AI》两门新课程，并纳入本科生和研究生AI入门课程。从技术上讲，这项研究有三个主要方面。首先，该项目将设计、实施和测试用于子树求解的新的可伸缩技术，这是过去20年来在解决不完全信息广泛形式的战略环境方面最有影响力的发展。其次，当公共知识闭包(这是先前子博弈求解技术的起点)太大而无法计算时，该项目将设计、实现和测试用于子树求解的新型可伸缩技术。最后，该项目将设计、实现和测试在没有提供规则的情况下寻找均衡策略的技术，而求解器只能访问模拟器。现有技术无法在该设置中提供低可利用性或零可利用性的保证。最近的一项突破使这种保证得以提供，但要使这种方法具有可扩展性，还需要大量的新奇工作。这项研究将开发这样的技术。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Models of strategic interaction have mainly been simple enough for humans to solve in their heads or on paper. However, many - arguably most - important strategic settings lie beyond human limits. One such class is problems that are too large. These include detailed models of reality in settings of practical importance, as well as many recreational settings. Another class is where the rules are not provided, and the solver only has access to a simulator in which to practice. This setup occurs in defense applications, real-time strategy settings, trading simulations, etc. This research will significantly increase the scalability of solving algorithms for both classes in the most realistic setting: multi-step imperfect-information strategic interactions. Although application independent, these techniques are needed for use cases including negotiation, business, defense, auctions, strategic pricing, cybersecurity, medicine, and many more - essentially all strategic interactions. The results will be incorporated into two new courses: “Computational Game Solving” and “Cooperative AI”, and into the undergraduate and graduate introduction to AI courses. Technically, this research has three main prongs. First, the project will design, implement, and test novel scalable techniques for subtree solving, the most impactful development in solving imperfect-information extensive-form strategic settings in the last two decades. Second, the project will design, implement, and test novel scalable techniques for subtree solving when the common knowledge closure (which is the starting point of prior subgame-solving techniques) is too large to handle computationally. Finally, the project will design, implement, and test techniques for finding equilibrium strategies in settings where the rules are not provided, and the solver only has access to a simulator. Prior techniques have not been able to offer guarantees of low or zero exploitability in that setup. A recent breakthrough has enabled such guarantees to be provided, but significant novel work is required to make the approach scalable. This research will develop such techniques.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.