Trembling-Hand Perfection in Extensive-Form Games with Commitment

Trembling-Hand Perfection in Extensive-Form Games with Commitment

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

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 233-239. https://doi.org/10.24963/ijcai.2018/32

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 v is NP-hard. This significantly extends prior complexity results that were specific to strong Stackelberg equilibrium.
Keywords:
Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems