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

战略互动的模型基本上足够简单，人类可以在头脑中或在纸上解决。然而，许多--可以说是最重要的--战略环境超越了人类的极限。其中一类是太大的问题。这些包括在具有实际重要性的环境中的现实的详细模型，以及许多娱乐环境。另一类是不提供规则的类，求解器只能访问模拟器进行练习。这种设置发生在国防应用程序，实时策略设置，交易模拟等，这项研究将显着增加解决算法的可扩展性，为这两个类在最现实的设置：多步骤的策略信息的战略互动。 尽管这些技术独立于应用程序，但它们也是谈判、商业、防御、拍卖、战略定价、网络安全、医疗等用例所必需的--基本上是所有的战略互动。研究结果将被纳入两门新课程：“计算游戏解决”和“合作AI”，并纳入本科生和研究生介绍AI课程。从技术上讲，这项研究有三个主要方面。 首先，该项目将设计，实施和测试用于子树求解的新型可扩展技术，这是过去二十年来解决信息扩展形式战略环境中最具影响力的发展。 其次，该项目将设计，实施和测试新的可扩展技术，用于子树求解时，共同的知识闭包（这是以前的子博弈求解技术的起点）太大，无法处理计算。最后，该项目将设计，实施和测试在不提供规则的设置中寻找平衡策略的技术，并且求解器只能访问模拟器。现有技术还不能保证在该设置中低或零可利用性。最近的一项突破使这种保证得以提供，但需要大量的新工作，使这种方法可扩展。该奖项反映了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.