Stationary Strong Stackelberg Equilibrium in Discounted Stochastic Games

Abstract

In this work, we study Stackelberg equilibria for discounted stochastic games. We consider two solution concepts for these games: stationary strong Stackelberg equilibrium (SSSE) and fixed point equilibrium (FPE) solutions. The SSSE solution is obtained by explicitly solving the Stackelberg equilibrium conditions, whereas the FPE can be computed efficiently using value or policy iteration algorithms. However, previous work has overlooked the relationship between these two different solution concepts. Here, we investigate the conditions for existence and equivalence of these solution concepts. Our theoretical results prove that the FPE and SSSE exist and coincide for important classes of games, including myopic follower strategy and team games. This, however, does not hold in general, and we provide numerical examples where one of SSSE or FPE does not exist, or when they both exist, they differ. Our computational results compare the solutions obtained by value iteration, policy iteration, and a mathematical programming formulations for this problem. Finally, we present a discounted stochastic Stackelberg game for a security application to illustrate the solution concepts and the efficiency of the algorithms studied.