Computing approximate Nash equilibria in polymatrix games

DOI10.1007/S00453-015-0078-7MaRDI QIDQ513277zbMATH OpenOpenAlexFDO

Authors Argyrios Deligkas, John Fearnley, Rahul Savani, P. 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

approximate Nash equilibriagradient descentBayesian gamespolymatrix games

Mathematics Subject Classification ID

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

Recommendations

• Computing approximate Nash equilibria in polymatrix games
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• Computing exact and approximate Nash equilibria in 2-player games
• Approximating Nash equilibria in tree polymatrix games
• Computing constrained approximate equilibria in polymatrix games

Cites work

• A decomposition algorithm for N-player games
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• A note on approximate Nash equilibria
• An optimization approach for approximate Nash equilibria
• Approximate Nash Equilibria for Multi-player Games
• Approximate Nash equilibria in anonymous games
• Approximate well-supported Nash equilibria in symmetric bimatrix games
• Bayesian Equilibria of Finite Two-Person Games with Incomplete Information
• Computing Nash equilibria by iterated polymatrix approximation
• Computing approximate Nash equilibria in polymatrix games
• Equilibria of Polymatrix Games
• Inapproximability of NP-complete variants of Nash equilibrium
• Inapproximability of Nash equilibrium
• New algorithms for approximate Nash equilibria in bimatrix games
• New complexity results about Nash equilibria
• On minmax theorems for multiplayer games
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of approximating a Nash equilibrium
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computing a Nash equilibrium
• The complexity of non-monotone markets
• Well supported approximate equilibria in bimatrix games

Cited in

(16)

• Computing exact and approximate Nash equilibria in 2-player games
• Approximating Nash equilibria in tree polymatrix games
• PPAD-complete pure approximate Nash equilibria in Lipschitz games
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• On perfect Nash equilibria of polymatrix games
• Computing approximate Nash equilibria in polymatrix games
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
• Nash equilibria in perturbation-stable games
• Computing Nash equilibria by iterated polymatrix approximation
• The Computation of Approximate Generalized Feedback Nash Equilibria
• Lipschitz continuity and approximate equilibria
• PPAD-complete approximate pure Nash equilibria in Lipschitz games
• Zero-sum polymatrix games: a generalization of minmax
• Approximate Nash Equilibria for Multi-player Games
• Computing constrained approximate equilibria in polymatrix games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513277)