Exchangeable equilibria contradict exactness of the Papadimitriou-Roughgarden algorithm

Pablo A. Parrilo

TL;DR

This paper demonstrates that a prominent algorithm for computing correlated equilibria in games, the "Ellipsoid Against Hope" algorithm, fails to guarantee exact solutions even for small, symmetric games. The authors identify a fundamental algebraic obstruction and propose a modified algorithm that can compute approximate correlated equilibria efficiently, but exact computation remains an open challenge.

What Problem Does This Paper Address?

The paper tackles the problem of efficiently computing correlated equilibria in games. Correlated equilibria are a generalization of Nash equilibria that can lead to better outcomes for players. While Nash equilibria are distributions over independent player strategies, correlated equilibria allow for joint distributions where players are recommended strategies, and these recommendations are correlated. This correlation can be exploited to achieve outcomes not possible with independent strategies.

The challenge lies in the computational complexity of finding these equilibria, especially for games with many players or strategies. The "Ellipsoid Against Hope" algorithm, proposed by Papadimitriou and Roughgarden, aimed to efficiently compute correlated equilibria for "succinctly-represented" games (games where the description is much smaller than the full payoff matrix). This algorithm was based on a proof of existence for correlated equilibria using linear programming and the ellipsoid method. However, this paper shows that the algorithm's claim of exactness is flawed, even when considering simplified cases like symmetric games and ignoring efficiency concerns.

Methods

The authors' approach is multi-faceted:

  • Counterexample Construction: They construct a specific three-player symmetric game where no rational exchangeable equilibrium exists. An exchangeable equilibrium is a correlated equilibrium that is a convex combination of symmetric product distributions. The existence of such a game directly contradicts the claim that the Papadimitriou-Roughgarden algorithm can compute rational exchangeable equilibria.
  • Analysis of the Ellipsoid Algorithm: They delve into the mechanics of the Ellipsoid Against Hope algorithm, specifically focusing on how it uses a separation oracle (the Hart-Schmeidler oracle) and the ellipsoid method to find feasible solutions. They pinpoint an error in the original analysis that incorrectly assumes that a modified linear program derived from the ellipsoid cuts will also be infeasible. The core issue is that the coefficients in the modified problem can become arbitrarily large, requiring a larger initial ellipsoid and potentially invalidating the algorithm's guarantees.
  • Repairing the Algorithm: They propose a modified algorithm that addresses the identified flaw. This involves introducing explicit bounds on the dual variables in the linear program. This modification allows them to guarantee the computation of ε-correlated equilibria (where players can improve their utility by at most ε by deviating) in polynomial time.

Datasets

Not discussed in the paper. The paper focuses on theoretical game theory and algorithm analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Algebraic Obstruction: The paper reveals an underlying algebraic obstruction that prevents algorithms relying on the Hart-Schmeidler separation oracle and finite-precision arithmetic from computing exact correlated equilibria, even with arbitrary time. This is a fundamental limitation of the approach.
  • Symmetry is Not Enough: The authors show that even restricting the problem to symmetric games and seeking symmetric equilibria doesn't save the original algorithm. The counterexample demonstrates that rational exchangeable equilibria might not even exist in such settings.
  • The "Positive Feedback Loop": A key insight is the "positive feedback loop" in the original algorithm's analysis. The process of generating cuts and forming a new linear program can lead to larger coefficients, which in turn requires a larger initial ellipsoid, potentially leading to even larger coefficients, and so on. This makes it difficult to guarantee feasibility of the modified problem.
  • ε-Approximation as a Solution: The paper shows that by relaxing the requirement from exact correlated equilibria to ε-correlated equilibria, a polynomial-time algorithm can be constructed. This highlights the trade-off between exactness and computational efficiency.

Key Results

  • Counterexample: A three-player symmetric game is presented that has no rational exchangeable equilibrium, invalidating the claim of the Papadimitriou-Roughgarden algorithm for such cases.
  • Algorithm Failure: The paper demonstrates that the Ellipsoid Against Hope algorithm can fail to compute exact correlated equilibria due to issues with coefficient growth and the ellipsoid method's reliance on problem data.
  • ε-Correlated Equilibria: A corrected algorithm is presented that can compute ε-correlated equilibria in polynomial time, where ε can be made arbitrarily small by increasing computational resources.

Limitations and Future Work

  • Exactness vs. Approximation: The primary limitation is that the corrected algorithm only guarantees ε-correlated equilibria, not exact ones. The paper suggests that computing exact correlated equilibria for succinct games might be fundamentally hard.
  • Open Questions: The complexity of computing exact exchangeable equilibria for symmetric two-player games remains an open question. The authors also leave open the possibility of more clever approaches to avoid the "positive feedback loop" in the original algorithm, though they deem it unlikely.
  • General Games: While the paper focuses on symmetric games for its counterexample, the critique of the algorithm's analysis is more general. However, the proposed fix for ε-correlated equilibria is presented in the context of succinct games with the polynomial expectation property.

Summary updated

BibTeX
@misc{parrilo2010exchangeable,
  author = {Pablo A. Parrilo},
  title = {{Exchangeable equilibria contradict exactness of the Papadimitriou-Roughgarden algorithm}},
  year = {2010},
  eprint = {1010.2871},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1010.2871},
}
Figure