Polynomial-time computation of exact correlated equilibrium in compact games

• 成果类型: Article
• 署名作者: Jiang, Albert Xin; Leyton-Brown, Kevin
• 署名单位: University of British Columbia
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.02.002
• 发表日期: 2015
• 页码: 347-359
• 关键词: Correlated equilibrium; Ellipsoid method; Separation oracle; Derandomization

摘要

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. (C) 2013 Elsevier Inc. All rights reserved.