The Stackelberg equilibrium solution concept describes optimal strategies to commit to: Player 1 (termed the leader) publicly commits to a strategy and Player 2 (termed the follower) plays a best response to this strategy (ties are broken in favor of the leader). We study Stackelberg equilibria in finite sequential games (or extensive-form games) and provide new exact algorithms, approximate algorithms, and hardness results for several classes of these sequential games.
The detailed analysis of the impact when the leader can commit to correlated strategies has, however, not been investigated sufficiently in the existing work. We address this extension and study the complexity for multiple subclasses of extensive-form games. Our results show that for many cases the problem of computing Stackelberg equilibria in correlated strategies is polynomial compared to the NP-hardness in behavioral strategies. Finally, these theoretical results have also practical algorithmic implications. An algorithm that computes a Stackelberg equilibrium in correlated strategies can be used to compute a Stackelberg equilibrium in behavioral strategies allowing a significant speed-up in computation time @cite_0 .
@cite_0
2480793474
Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive-Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.