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 general-sum 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. Our algorithms also allow one to find a Nash equilibrium when players cannot perfectly control their moves, being subject to a given execution uncertainty, as is the case in most realistic physical settings.

Extensive-form perfect equilibrium computation in two-player games

Farina, Gabriele;Gatti, Nicola
2017-01-01

Abstract

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 general-sum 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. Our algorithms also allow one to find a Nash equilibrium when players cannot perfectly control their moves, being subject to a given execution uncertainty, as is the case in most realistic physical settings.
2017
31st AAAI Conference on Artificial Intelligence, AAAI 2017
Artificial Intelligence
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1035867
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 8
social impact