Efficient Stackelberg Strategies for Finitely Repeated Games
share
We study the problem of efficiently computing optimal strategies in asymmetric leader-follower games repeated a finite number of times, which presents a different set of technical challenges than the infinite-horizon setting. More precisely, we give efficient algorithms for finding approximate Stackelberg equilibria in finite-horizon repeated two-player games, along with rates of convergence depending on the horizon T. We give two algorithms, one computing strategies with an optimal 1/T rate at the expense of an exponential dependence on the number of actions, and another (randomized) approach computing strategies with no dependence on the number of actions but a worse dependence on T of 1/T^0.25. Both algorithms build upon a linear program to produce simple automata leader strategies and induce corresponding automata best-responses for the follower. We complement these results by showing that approximating the Stackelberg value in three-player finite-horizon repeated games is a computationally hard problem via a reduction from the balanced vertex cover problem.
READ FULL TEXT