TL;DR
This paper demonstrates that a prominent algorithm for computing correlated equilibria in games, proposed by Papadimitriou and Roughgarden, fails to guarantee exact solutions, even for small, symmetric games. The authors identify a fundamental algebraic obstruction and propose a modified approach that can compute approximate correlated equilibria.
What Problem Does This Paper Address?
The paper tackles the problem of efficiently computing correlated equilibria in games. Correlated equilibria are a fundamental concept in game theory, representing a set of recommendations for players that no player has an incentive to deviate from. While algorithms exist for finding Nash equilibria, computing correlated equilibria, especially in "succinctly-represented" games (where the game's description is compact, not explicitly listing all payoffs), is more challenging. The Papadimitriou-Roughgarden (PR) algorithm, based on the ellipsoid method and a separation oracle, was proposed as an efficient way to compute these equilibria. However, this paper investigates a claim that this algorithm might not always compute exact correlated equilibria as intended, even for games with specific properties like symmetry.
Methods
The authors employ a combination of theoretical analysis and counterexample construction.
- Counterexample Construction: They devise a specific three-player symmetric game where they prove that no rational exchangeable equilibrium exists. An exchangeable equilibrium is a specific type of correlated equilibrium relevant for symmetric games. This counterexample is crucial for demonstrating the failure of algorithms that rely on rational outputs.
- Algorithmic Analysis: The core of their critique lies in analyzing the PR algorithm's reliance on the ellipsoid method and a separation oracle (the Hart-Schmeidler oracle). They identify a "positive feedback loop" in the algorithm's analysis, where attempts to fix issues with coefficient sizes lead to larger coefficients, requiring even larger initial bounds, and so on.
- Repair and Approximation: To address the identified issues, they propose a modified algorithm. This approach uses bounds on the dual variables to ensure that the ellipsoid algorithm's run is valid for the modified problem. This leads to the computation of ε-correlated equilibria, which are approximate solutions, rather than exact ones.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Rationality is Key: The existence of a rational exchangeable equilibrium is not guaranteed, even for simple symmetric games. This is a critical insight that undermines algorithms relying on rational outputs.
- The "Positive Feedback Loop": The PR algorithm's analysis suffers from a self-perpetuating problem where fixing coefficient size issues leads to even larger coefficients, making it impossible to guarantee correctness with finite precision or finite iterations.
- Symmetry is Not Enough: While the PR algorithm is designed to work with symmetric games, the paper shows that even when exploiting symmetry, the core problem persists. Explicit symmetry-breaking is needed to avoid the issues.
- Approximation is Achievable: While exact solutions might be elusive for certain games or algorithms, the paper demonstrates that ε-correlated equilibria can be computed efficiently. This suggests a trade-off between exactness and computational feasibility.
Key Results
- The paper presents a three-player symmetric game for which no rational exchangeable equilibrium exists. This serves as a counterexample to the claim that the Papadimitriou-Roughgarden algorithm can compute exact rational exchangeable equilibria.
- They pinpoint a flaw in the analysis of the PR algorithm, showing that the ellipsoid method's run on a modified dual problem does not guarantee infeasibility due to potential issues with coefficient sizes and the choice of initial ellipsoid.
- A corrected algorithm is proposed that can compute ε-correlated equilibria in polynomial time, where ε is a small positive value. This means approximate solutions are achievable efficiently.
Limitations and Future Work
- Exactness vs. Approximation: The paper concludes that exact correlated equilibria might not be computable efficiently for all succinct games. The proposed fix yields ε-correlated equilibria, highlighting that strict positivity of ε is inherent to the corrected analysis.
- Open Questions: The complexity of computing exact exchangeable equilibria for symmetric two-player games remains an open question. The paper also suggests that an algorithm that can compute exact correlated equilibria without explicitly breaking symmetry is unlikely.
- Succinct Games: While the paper focuses on succinct games, the counterexample itself is a small, explicit game, demonstrating the fundamental issue even without the complexity of succinct representation.
Summary updated