Computing an Extensive-Form Perfect Equilibrium in Two-Player Games

Authors

  • Nicola Gatti Politecnico di Milano
  • Claudio Iuliano Politecnico di Milano

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.

Downloads

Published

2011-08-04

How to Cite

Gatti, N., & Iuliano, C. (2011). Computing an Extensive-Form Perfect Equilibrium in Two-Player Games. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 669-674. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7867

Issue

Section

AAAI Technical Track: Multiagent Systems