Polynomial-time computation of exact correlated equilibrium in compact games

Albert Xin Jiang and Kevin Leyton-Brown

Games and Economic Behavior, 2015, vol. 91, issue C, 347-359

Abstract: In a landmark paper, Papadimitriou and Roughgarden described a polynomial-time algorithm (“Ellipsoid Against Hope”) for computing sample correlated equilibria of concisely-represented games. Recently, Stein, Parrilo and Ozdaglar showed that this algorithm can fail to find an exact correlated equilibrium. We present a variant of the Ellipsoid Against Hope algorithm that guarantees the polynomial-time identification of exact correlated equilibrium. Our algorithm differs from the original primarily in its use of a separation oracle that produces cuts corresponding to pure-strategy profiles. Our new separation oracle can be understood as a derandomization of Papadimitriou and Roughgarden's original separation oracle via the method of conditional probabilities. We also adapt our techniques to two related algorithms that are based on the Ellipsoid Against Hope approach, Hart and Mansour's communication procedure for correlated equilibria and Huang and von Stengel's algorithm for extensive-form correlated equilibria, in both cases yielding efficient exact solutions.

Keywords: Correlated equilibrium; Ellipsoid method; Separation oracle; Derandomization (search for similar items in EconPapers)
JEL-codes: C63 C72 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825613000249
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:91:y:2015:i:c:p:347-359

DOI: 10.1016/j.geb.2013.02.002

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().