Trembling-Hand Perfection and Correlation in Sequential Games
Authors: Alberto Marchesi, Nicola Gatti5566-5574
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 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 ϵ 0) to a suitably defined trembling LP parametrized by ϵ, 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. |
| Researcher Affiliation | Academia | Alberto Marchesi, Nicola Gatti Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133, Milan, Italy alberto.marchesi@polimi.it, nicola.gatti@polimi.it |
| Pseudocode | No | The paper describes algorithmic approaches but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical contributions and does not use or provide access information for a publicly available or open dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper focuses on theoretical contributions and does not specify any hardware details used for running experiments. |
| Software Dependencies | No | The paper mentions general computational methods (LPs, algorithms) but does not provide specific software names with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical contributions and does not describe a specific experimental setup with hyperparameters or training configurations. |