Double-oracle sampling method for Stackelberg Equilibrium approximation in general-sum extensive-form games
This addresses efficient equilibrium computation in complex game theory for AI and security applications, though it is incremental as it builds on existing sampling and optimization techniques.
The paper tackles approximating Strong Stackelberg Equilibrium in general-sum sequential games by proposing a generic simulation-based method that interleaves Monte Carlo Tree Search sampling and Leader strategy building. It shows the method achieves optimal Leader strategies in most test cases, with better time scalability and lower memory requirements compared to MILP/LP-based methods.
The paper presents a new method for approximating Strong Stackelberg Equilibrium in general-sum sequential games with imperfect information and perfect recall. The proposed approach is generic as it does not rely on any specific properties of a particular game model. The method is based on iterative interleaving of the two following phases: (1) guided Monte Carlo Tree Search sampling of the Follower's strategy space and (2) building the Leader's behavior strategy tree for which the sampled Follower's strategy is an optimal response. The above solution scheme is evaluated with respect to expected Leader's utility and time requirements on three sets of interception games with variable characteristics, played on graphs. A comparison with three state-of-the-art MILP/LP-based methods shows that in vast majority of test cases proposed simulation-based approach leads to optimal Leader's strategies, while excelling the competitive methods in terms of better time scalability and lower memory requirements.