Polynomial-time computation of exact correlated equilibrium in compact games

DOI10.1016/j.geb.2013.02.002zbMath1318.91014arXiv1011.0253OpenAlexW2080665546WikidataQ60521613 ScholiaQ60521613MaRDI QIDQ2347787

Kevin Leyton-Brown, Albert Xin Jiang

Publication date: 8 June 2015

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.0253

zbMATH Keywords

correlated equilibriumderandomizationseparation oracleellipsoid method

Mathematics Subject Classification ID

Noncooperative games (91A10) Randomized algorithms (68W20)

Related Items (10)

The query complexity of correlated equilibria ⋮ Communication complexity of approximate Nash equilibria ⋮ From Duels to Battlefields: Computing Equilibria of Blotto and Other Games ⋮ Multilinear Games ⋮ Unnamed Item ⋮ Learning to play efficient coarse correlated equilibria ⋮ Committing to correlated strategies with multiple leaders ⋮ Achieving target equilibria in network routing games without knowing the latency functions ⋮ Correlated equilibrium of games in fuzzy environment ⋮ The Complexity of Contracts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Action-graph games
• Coherent behavior in noncooperative games
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Geometric algorithms and combinatorial optimization
• Subjectivity and correlation in randomized strategies
• Dual reduction and elementary games
• A global Newton method to compute Nash equilibria.
• Existence of sparsely supported correlated equilibria
• Reducibility among equilibrium problems
• Extensive-Form Correlated Equilibrium: Definition and Computational Complexity
• Settling the complexity of computing two-player Nash equilibria
• Correlated Equilibrium as an Expression of Bayesian Rationality
• Simplicial Variable Dimension Algorithms for Solving the Nonlinear Complementarity Problem on a Product of Unit Simplices Using a General Labelling
• Existence of Correlated Equilibria
• Linear Programming
• The Complexity of Computing a Nash Equilibrium
• Equilibrium Points of Bimatrix Games
• The Approximation of Fixed Points of a Continuous Mapping
• Computing correlated equilibria in multi-player games
• Computing correlated equilibria in multi-player games
• On a combinatorial game

This page was built for publication: Polynomial-time computation of exact correlated equilibrium in compact games