Trembling-Hand Perfection in Extensive-Form Games with Commitment

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

---

Abstract

We initiate the study of equilibrium refinements based on trembling-hand perfection in extensive-form games with commitment strategies, that is, where one player commits to a strategy first. We show that the standard strong (and weak) Stackelberg equilibria are not suitable for trembling-hand perfection, because the limit of a sequence of such strong (weak) Stackelberg commitment strategies of a perturbed game may not be a strong (weak) Stackelberg equilibrium itself. However, we show that the universal set of all Stackelberg equilibria (i.e., those that are optimal for at least some follower response function) is natural for trembling-hand perfection: it does not suffer from the problem above. We also prove that determining the existence of a Stackelberg equilibrium—refined or not—that gives the leader expected value at least ν is NP-hard. This significantly extends prior complexity results that were specific to strong Stackelberg equilibrium.

---

Bibtex entry

@inproceedings{Farina18:Trembling, title={Trembling-Hand Perfection in Extensive-Form Games with Commitment}, author={Farina, Gabriele and Marchesi, Alberto and Kroer, Christian and Gatti, Nicola and Sandholm, Tuomas}, booktitle={ International Joint Conference on Artificial Intelligence (IJCAI)}, year={2018} }