Extensive-Form Perfect Equilibrium Computation in Two-Player Games
Authors: Gabriele Farina, Nicola Gatti
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of computing an Extensive-Form Perfect Equilibrium (EFPE) in 2-player games. This equilibrium concept refines the Nash equilibrium requiring resilience with respect to a specific vanishing perturbation, representing mistakes of the players at each decision node. The scientific challenge is intrinsic to the EFPE definition: it requires a perturbation over the agent form, but the agent form is computationally inefficient due to the presence of highly nonlinear constraints. We show that the sequence form can be exploited in a non-trivial way and that, for generalsum games, finding an EFPE is equivalent to solving a suitably perturbed linear complementarity problem. We prove that Lemke s algorithm can be applied, showing that computing an EFPE is PPAD-complete. In the notable case of zero-sum games, the problem is in FP and can be solved by linear programming. |
| Researcher Affiliation | Academia | Gabriele Farina Computer Science Department Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 1513, USA gfarina@cs.cmu.edu Nicola Gatti Dipartimento di Elettronica, Informazione e Bioingegneria Politecnico di Milano Piazza Leonardo da Vinci, 32 I-20133, Milan, Italy nicola.gatti@polimi.it |
| Pseudocode | Yes | Algorithm 1 procedure FIND-EFPE |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code for the described methodology. The arXiv link provided is for the paper itself, not source code. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve data splitting for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe specific hardware used for experiments. |
| Software Dependencies | No | The paper mentions 'Lemke s algorithm' and 'linear programming' but does not specify particular software or library names with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |