Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games
(J. Cerny, B. Bosansky, C. Kiekintveld)
In ACM Conference on Economics and Computation (ACM EC), 2018.
This is the author's version of the work.
Download
Abstract
Dynamic interaction appears in many real-world scenarios where players are able to observe (perhaps
imperfectly) the actions of another player and react accordingly. We consider the baseline representation
of dynamic games—the extensive form—and focus on computing Stackelberg equilibrium
(SE), where the leader commits to a strategy to which the follower plays a best response. For oneshot
games (e.g., security games), strategy-generation (SG) algorithms offer dramatic speed-up by
incrementally expanding the strategy spaces. However, a direct application of SG to extensive-form
games (EFGs) does not bring a similar speed-up since it typically results in a nearly-complete
strategy space. Our contributions are twofold: (1) for the first time we introduce an algorithm that
allows us to incrementally expand the strategy space to find a SE in EFGs; (2) we introduce a
heuristic variant of the algorithm that is theoretically incomplete, but in practice allows us to find
exact (or close-to optimal) Stackelberg equilibrium by constructing a significantly smaller strategy
space. Our experimental evaluation confirms that we are able to compute SE by considering only a
fraction of the strategy space that often leads to a significant speed-up in computation times.
