Computing an Extensive-Form Perfect Equilibrium in Two-Player Games
Abstract
Equilibrium computation in games is currently considered one of the most challenging issues in AI. In this paper, we provide, to the best of our knowledge, the first algorithm to compute a Selten's extensive-form perfect equilibrium (EFPE) with two--player games. EFPE refines the Nash equilibrium requiring the equilibrium to be robust to slight perturbations of both players' behavioral strategies. Our result puts the computation of an EFPE into the PPAD class, leaving open the question whether or not the problem is hard. Finally, we experimentally evaluate the computational time spent to find an EFPE and some relaxations of EFPE.
Cite
Text
Gatti and Iuliano. "Computing an Extensive-Form Perfect Equilibrium in Two-Player Games." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7867Markdown
[Gatti and Iuliano. "Computing an Extensive-Form Perfect Equilibrium in Two-Player Games." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/gatti2011aaai-computing/) doi:10.1609/AAAI.V25I1.7867BibTeX
@inproceedings{gatti2011aaai-computing,
title = {{Computing an Extensive-Form Perfect Equilibrium in Two-Player Games}},
author = {Gatti, Nicola and Iuliano, Claudio},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2011},
pages = {669-674},
doi = {10.1609/AAAI.V25I1.7867},
url = {https://mlanthology.org/aaai/2011/gatti2011aaai-computing/}
}