Safe Search for Stackelberg Equilibria in Extensive-Form Games

Chun Kai Ling, Noam Brown

Abstract

Stackelberg equilibrium is a solution concept in two-player games where the leader has commitment rights over the follower. In recent years, it has become a cornerstone of many security applications, including airport patrolling and wildlife poaching prevention. Even though many of these settings are sequential in nature, existing techniques pre-compute the entire solution ahead of time. In this paper, we present a theoretically sound and empirically effective way to apply search, which leverages extra online computation to improve a solution, to the computation of Stackelberg equilibria in general-sum games. Instead of the leader attempting to solve the full game upfront, an approximate "blueprint" solution is first computed offline and is then improved online for the particular subgames encountered in actual play. We prove that our search technique is guaranteed to perform no worse than the pre-computed blueprint strategy, and empirically demonstrate that it enables approximately solving significantly larger games compared to purely offline methods. We also show that our search operation may be cast as a smaller Stackelberg problem, making our method complementary to existing algorithms based on strategy generation.

Introduction

In a Stackelberg Equilibrium (SSE), a leader commits to a strategy, and a follower responds optimally. This framework is essential for security domains like infrastructure protection. However, applying search-based refinement—highly successful in zero-sum games like Chess—to general-sum Extensive-Form Games (EFGs) is challenging. Finding an SSE in EFGs is NP-hard, and offline solvers often fail to scale as game trees grow.

The primary hurdle for online search in general-sum games is "safety." Improving a strategy in a subgame might inadvertently alter the follower's incentives in earlier stages, potentially leading to a global outcome worse than the original plan. Naive search methods can fall into "traps" where local improvements cause the follower to avoid the subgame entirely.

The danger of naive search vs. safe bounds in a game tree.

Methodology: The Safe Search Framework

The authors propose a three-step framework to refine strategies online while maintaining global equilibrium integrity:

  1. Blueprint Preprocessing: An approximate "blueprint" strategy is computed offline. The algorithm determines the follower's Best-Response Values (BRVs) under this strategy.
  2. Generating Safety Bounds: As play reaches a subgame, the algorithm propagates follower payoff requirements from the root down. It establishes upper and lower bounds on the follower's expected value to ensure their optimal path through the entire game remains consistent with the leader's global expectations.
  3. Constrained Subgame Optimization: The current subgame is solved as a smaller SSE problem, constrained by the calculated safety bounds. This ensures the refined strategy is "safe," guaranteeing the leader's payoff is at least as good as the blueprint's.

This refinement is formulated as a Mixed-Integer Linear Program (MILP), allowing the use of high-performance solvers like Gurobi.

Experimental Evaluation

The framework was tested on synthetic Two-Stage Matrix Games, Goofspiel, and a general-sum variant of Leduc Hold’em (modified with a "rake" to encourage coordination). The results demonstrate significant improvements in scalability and performance.

Performance comparison of the search method against blueprint and full-game solvers.

In large-scale scenarios, such as Leduc Hold'em with 8 cards, traditional offline MILP solvers failed to even construct a model within three hours. In contrast, the Safe Search method efficiently provided improved strategies. In two-stage games, where full-game solvers failed to converge within 1,000 seconds, Safe Search achieved superior payoffs in just 100 seconds.

Conclusion and Future Work

This work introduces the first safe search algorithm for SSE in large sequential games. By treating search as a constrained, smaller SSE problem, the method inherits improvements from offline solver advancements while providing a theoretical safety guarantee. Future research will explore more sophisticated "slack" distribution for bounds and extending the framework to multi-follower environments.

Summary updated

Abstract

Stackelberg equilibrium is a solution concept in two-player games where the leader has commitment rights over the follower. In recent years, it has become a cornerstone of many security applications, including airport patrolling and wildlife poaching prevention. Even though many of these settings are sequential in nature, existing techniques pre-compute the entire solution ahead of time. In this paper, we present a theoretically sound and empirically effective way to apply search, which leverages extra online computation to improve a solution, to the computation of Stackelberg equilibria in general-sum games. Instead of the leader attempting to solve the full game upfront, an approximate "blueprint" solution is first computed offline and is then improved online for the particular subgames encountered in actual play. We prove that our search technique is guaranteed to perform no worse than the pre-computed blueprint strategy, and empirically demonstrate that it enables approximately solving significantly larger games compared to purely offline methods. We also show that our search operation may be cast as a smaller Stackelberg problem, making our method complementary to existing algorithms based on strategy generation.
BibTeX
@inproceedings{ling2021safe,
  author = {Chun Kai Ling and Noam Brown},
  title = {{Safe Search for Stackelberg Equilibria in Extensive-Form Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=L2SAJ1vEjbr},
}
Figure