Quasi-Perfect Stackelberg Equilibrium

Alberto Marchesi, Gabriele Farina, Christian Kroer, Nicola Gatti, Tuomas Sandholm

---

Abstract

Equilibrium refinements are important in extensive-form (i.e., tree-form) games, where they amend weaknesses of the Nash equilibrium concept by requiring sequential rationality and other beneficial properties. One of the most attractive refinement concepts is quasi-perfect equilibrium. While quasi-perfection has been studied in extensive-form games, it is poorly understood in Stackelberg settings—that is, settings where a leader can commit to a strategy—which are important for modeling, for example, security games. In this paper, we introduce the axiomatic definition of quasi-perfect Stackelberg equilibrium. We develop a broad class of game perturbation schemes that lead to them in the limit. Our class of perturbation schemes strictly generalizes prior perturbation schemes introduced for the computation of (non-Stackelberg) quasi-perfect equilibria. Based on our perturbation schemes, we develop a branch-and-bound algorithm for computing a quasi-perfect Stackelberg equilibrium. It leverages a perturbed variant of the linear program for computing a Stackelberg extensive-form correlated equilibrium. Experiments show that our algorithm can be used to find an approximate quasi-perfect Stackelberg equilibrium in games with thousands of nodes.

---

Bibtex entry

@inproceedings{Marchesi19:Quasi, title={Quasi-Perfect Stackelberg Equilibrium}, author={Marchesi, Alberto and Farina, Gabriele and Kroer, Christian and Gatti, Nicola and Sandholm, Tuomas}, booktitle={AAAI Conference on Artificial Intelligence}, year={2019} }