Computing approximate Nash equilibria in polymatrix games

DOI10.1007/s00453-015-0078-7zbMath1358.91007OpenAlexW1648820898MaRDI QIDQ513277

Rahul Savani, Argyrios Deligkas, John Fearnley, Paul G. Spirakis

Publication date: 3 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0078-7

zbMATH Keywords

gradient descentpolymatrix gamesapproximate Nash equilibriaBayesian games

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Stochastic games, stochastic differential games (91A15)

Related Items (5)

A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ Lipschitz continuity and approximate equilibria

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate well-supported Nash equilibria below two-thirds
• A decomposition algorithm for \(N\)-player games
• New complexity results about Nash equilibria
• Computing Nash equilibria by iterated polymatrix approximation
• Well supported approximate equilibria in bimatrix games
• A note on approximate Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• Approximate Nash equilibria in anonymous games
• On the Complexity of Approximating a Nash Equilibrium
• Computing Approximate Nash Equilibria in Polymatrix Games
• Approximate Well-Supported Nash Equilibria in Symmetric Bimatrix Games
• Inapproximability of Nash Equilibrium
• On the Complexity of Nash Equilibria and Other Fixed Points
• A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• An Optimization Approach for Approximate Nash Equilibria
• Bayesian Equilibria of Finite Two-Person Games with Incomplete Information
• The Complexity of Computing a Nash Equilibrium
• Approximate Nash Equilibria for Multi-player Games
• The complexity of non-monotone markets
• Equilibria of Polymatrix Games

This page was built for publication: Computing approximate Nash equilibria in polymatrix games