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

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

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.