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.