We investigate the computation of equilibria in extensive-form games when ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by hardness results on normal-form correlated equilibria, we investigate whether it is pos- sible to compute normal-form coarse correlated equilibria efficiently. We show that an optimal (e.g., social welfare maximizing) normal- form coarse correlated equilibrium can be computed in polynomial time in two-player games without chance moves, and that in gen- eral multi-player games (including two-player games with chance) the problem is NP-hard. For the two-player case, we provide both a polynomial-time algorithm based on the ellipsoid method and a column generation algorithm based on the simplex method which can be efficiently applied in practice. We also show that the pric- ing oracle employed in the column generation procedure can be extended to games with two players and chance.

(2019). Computing optimal ex ante correlated equilibria in two-player sequential games . Retrieved from http://hdl.handle.net/10446/229379

Computing optimal ex ante correlated equilibria in two-player sequential games

Coniglio, Stefano;Gatti, Nicola
2019

Abstract

We investigate the computation of equilibria in extensive-form games when ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by hardness results on normal-form correlated equilibria, we investigate whether it is pos- sible to compute normal-form coarse correlated equilibria efficiently. We show that an optimal (e.g., social welfare maximizing) normal- form coarse correlated equilibrium can be computed in polynomial time in two-player games without chance moves, and that in gen- eral multi-player games (including two-player games with chance) the problem is NP-hard. For the two-player case, we provide both a polynomial-time algorithm based on the ellipsoid method and a column generation algorithm based on the simplex method which can be efficiently applied in practice. We also show that the pric- ing oracle employed in the column generation procedure can be extended to games with two players and chance.
Celli, Andrea; Coniglio, Stefano; Gatti, Nicola
File allegato/i alla scheda:
File Dimensione del file Formato  
2019-AAMAS.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 1.3 MB
Formato Adobe PDF
1.3 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229379
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 3
social impact