Distributed methods for computing approximate equilibria

DOI10.1007/s00453-018-0465-yzbMath1422.91052OpenAlexW2807823918WikidataQ129708042 ScholiaQ129708042MaRDI QIDQ666675

Michail Fasoulakis, Argyrios Deligkas, John Fearnley, Rahul Savani, Marcin Jurdziński, Artur Czumaj

Publication date: 11 March 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0465-y

zbMATH Keywords

communication complexityquery complexitybimatrix gamesapproximate Nash equilibria

Mathematics Subject Classification ID

Noncooperative games (91A10) 2-person games (91A05) Signaling and communication in game theory (91A28) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Communication complexity of approximate Nash equilibria ⋮ On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Lipschitz continuity and approximate equilibria

Cites Work

• Unnamed Item
• Approximate well-supported Nash equilibria below two-thirds
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Well supported approximate equilibria in bimatrix games
• A note on approximate Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• Communication complexity of approximate Nash equilibria
• On the communication complexity of approximate Nash equilibria
• Non-cooperative games
• Approximate Well-Supported Nash Equilibria in Symmetric Bimatrix Games
• Settling the complexity of computing two-player Nash equilibria
• An Optimization Approach for Approximate Nash Equilibria
• The Complexity of Computing a Nash Equilibrium

This page was built for publication: Distributed methods for computing approximate equilibria