Quasi-Perfect Stackelberg Equilibrium


  • Alberto Marchesi Politecnico di Milano
  • Gabriele Farina Carnegie Mellon University
  • Christian Kroer Carnegie Mellon University
  • Nicola Gatti Politecnico di Milano
  • Tuomas Sandholm Carnegie Mellon University




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 quasiperfection 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.




How to Cite

Marchesi, A., Farina, G., Kroer, C., Gatti, N., & Sandholm, T. (2019). Quasi-Perfect Stackelberg Equilibrium. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2117-2124. https://doi.org/10.1609/aaai.v33i01.33012117



AAAI Technical Track: Game Theory and Economic Paradigms