Trembling-Hand Perfection and Correlation in Sequential Games

Authors

  • Alberto Marchesi Politecnico di Milano
  • Nicola Gatti Politecnico di Milano

DOI:

https://doi.org/10.1609/aaai.v35i6.16700

Keywords:

Game Theory, Equilibrium

Abstract

We initiate the study of trembling-hand perfection in sequential (i.e., extensive-form) games with correlation. We introduce the extensive-form perfect correlated equilibrium (EFPCE) as a refinement of the classical extensive-form correlated equilibrium (EFCE) that amends its weaknesses off the equilibrium path. This is achieved by accounting for the possibility that the players may make mistakes while following recommendations independently at each information set of the game. After providing an axiomatic definition of EFPCE, we show that one always exists since any perfect (Nash) equilibrium constitutes an EFPCE, and that it is a refinement of EFCE, as any EFPCE is also an EFCE. Then, we prove that, surprisingly, computing an EFPCE is not harder than finding an EFCE, since the problem can be solved in polynomial time for general n-player extensive-form games (also with chance). This is achieved by formulating the problem as that of finding a limit solution (as $\epsilon \rightarrow 0$) to a suitably defined trembling LP parametrized by $\epsilon$, featuring exponentially-many variables and polynomially-many constraints. To this end, we show how a recently developed polynomial-time algorithm for trembling LPs can be adapted to deal with problems having an exponential number of variables. This calls for the solution of a sequence of (non-trembling) LPs with exponentially-many variables and polynomially-many constraints, which is possible in polynomial time by applying an ellipsoid against hope approach.

Downloads

Published

2021-05-18

How to Cite

Marchesi, A., & Gatti, N. (2021). Trembling-Hand Perfection and Correlation in Sequential Games. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5566-5574. https://doi.org/10.1609/aaai.v35i6.16700

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms