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 game, a leader commits to a strategy first, and a follower responds optimally. This model underpins modern security AI, from scheduling airport patrols to preventing poaching. However, in extensive-form games—characterized by sequential moves, hidden information, and chance—finding the Strong Stackelberg Equilibrium (SSE) is NP-hard. Existing methods typically attempt to solve the entire game tree offline, but as game complexity grows, memory and time requirements explode, rendering these approaches impractical for large-scale scenarios.
This paper introduces a "safe search" method that combines a rough offline "blueprint" strategy with real-time online refinement. This approach scales leader-follower strategies to games far larger than previously possible while guaranteeing the leader performs no worse than their original plan.
Methodology: Safe Search Framework
The proposed framework shifts heavy computation from offline pre-computation to online "during-play" refinement through three main components:
- The Blueprint: An approximate strategy is computed offline, often using a simplified or abstracted version of the full game.
- Online Refinement: Upon reaching a specific subgame during play, the leader solves a localized optimization problem to refine their strategy for that specific context.
- Safety Bounds: To ensure search is "safe," the authors calculate upper and lower bounds on the follower's expected payoffs. In general-sum games, local strategy changes can alter follower behavior earlier in the game. These bounds ensure the follower’s best response remains consistent with blueprint assumptions, protecting the leader from accidental losses.
The refinement step is formulated as a Mixed-Integer Linear Program (MILP). Crucially, this constrained search can be transformed into a standard, smaller SSE problem, making it compatible with any existing SSE solver.
Experimental Evaluation
The approach was evaluated on three game types:
- Synthetic Two-Stage Games: General-sum matrix games where leader actions influence subsequent subgames.
- Goofspiel: A non-zero-sum card-bidding game where coordination can avoid ties.
- Leduc Hold’em: A simplified poker variant modified into a general-sum game by adding a "rake" (commission fee).
Key Insights
A critical finding is the "Unsafe Trap": "naive" search—optimizing within a subgame without considering the global tree—can lead to lower leader payoffs by triggering the follower to avoid that subgame entirely. By using safety bounds, the leader can improve their strategy locally without re-solving the global game, effectively decoupling subgame complexity from the rest of the tree. This makes the method a "force multiplier" for existing algorithms like strategy generation.
Results
Empirical results demonstrate significant gains in scalability and performance:
- Scalability: In large Leduc Hold’em variants (8 cards), traditional offline solvers failed to construct models within 3 hours, whereas Safe Search provided improvements over the blueprint in seconds.
- Memory Efficiency: For Goofspiel, the full-game solver required >50 GB of RAM, while the search-based approach used <5 GB.
- Performance Guarantee: The leader's utility is theoretically and empirically shown to be at least as good as the blueprint, and significantly better in large games.
Limitations and Future Work
The quality of the final strategy depends on a "reasonable" blueprint; extremely poor blueprints may result in overly restrictive safety bounds. Future work includes exploring more principled ways to "split the slack" (distribute payoff bounds) and extending safe online refinement to other equilibrium concepts in general-sum games.
Summary updated