Polynomial-time computation of exact correlated equilibrium in compact games
From MaRDI portal
Publication:2347787
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, but can be easily modified to efficiently compute approximate correlated equilibria. Currently, it remains unresolved whether the algorithm can be modified to compute an exact correlated equilibrium. We show that it can, presenting a variant of the Ellipsoid Against Hope algorithm that guarantees the polynomial-time identification of exact correlated equilibrium. Our new algorithm differs from the original primarily in its use of a separation oracle that produces cuts corresponding to pure-strategy profiles. As a result, we no longer face the numerical precision issues encountered by the original approach, and both the resulting algorithm and its analysis are considerably simplified. Our new separation oracle can be understood as a derandomization of Papadimitriou and Roughgarden's original separation oracle via the method of conditional probabilities. Also, the equilibria returned by our algorithm are distributions with polynomial-sized supports, which are simpler (in the sense of being representable in fewer bits) than the mixtures of product distributions produced previously; no tractable algorithm has previously been proposed for identifying such equilibria.
Recommendations
- Computing correlated equilibria in multi-player games
- Correlated equilibria in continuous games: characterization and computation
- The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game
- Computing correlated equilibria in multi-player games
- The Computational Complexity of Nash Equilibria in Concisely Represented Games
- The query complexity of correlated equilibria
- Computing constrained approximate equilibria in polymatrix games
- Efficient computation of equilibria for extensive two-person games
Cites work
- A global Newton method to compute Nash equilibria.
- Action-graph games
- Coherent behavior in noncooperative games
- Computing correlated equilibria in multi-player games
- Computing correlated equilibria in multi-player games
- Correlated Equilibrium as an Expression of Bayesian Rationality
- Dual reduction and elementary games
- Equilibrium Points of Bimatrix Games
- Existence of Correlated Equilibria
- Existence of sparsely supported correlated equilibria
- Extensive-form correlated equilibrium: definition and computational complexity
- Geometric algorithms and combinatorial optimization
- How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
- scientific article; zbMATH DE number 734955 (Why is no real title available?)
- scientific article; zbMATH DE number 1099369 (Why is no real title available?)
- scientific article; zbMATH DE number 3106184 (Why is no real title available?)
- Linear Programming
- On a combinatorial game
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Reducibility among equilibrium problems
- Settling the complexity of computing two-player Nash equilibria
- Simplicial Variable Dimension Algorithms for Solving the Nonlinear Complementarity Problem on a Product of Unit Simplices Using a General Labelling
- Subjectivity and correlation in randomized strategies
- The Approximation of Fixed Points of a Continuous Mapping
- The complexity of computing a Nash equilibrium
Cited in
(16)- The query complexity of correlated equilibria
- Learning to play efficient coarse correlated equilibria
- Correlated equilibrium of games in fuzzy environment
- Committing to correlated strategies with multiple leaders
- Achieving target equilibria in network routing games without knowing the latency functions
- Multilinear games
- Computation of correlated equilibrium with global-optimal expected social welfare
- Communication complexity of correlated equilibrium with small support
- From duels to battlefields: computing equilibria of Blotto and other games
- The complexity of contracts
- Computing correlated equilibria in multi-player games
- Correlated equilibria in continuous games: characterization and computation
- Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium
- Quantal response equilibrium as a structural model for estimation: the missing manual
- On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games
- Coarse correlated equilibria for continuous time mean field games in open loop strategies
This page was built for publication: Polynomial-time computation of exact correlated equilibrium in compact games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347787)
