Approximate well-supported Nash equilibria below two-thirds

DOI10.1007/s00453-015-0029-3zbMath1347.91008arXiv1204.0707OpenAlexW1531609333MaRDI QIDQ329276

Rahul Savani, John Fearnley, Troels Bjerre Sørensen, Paul W. Goldberg

Publication date: 21 October 2016

Published in: Algorithmica, Algorithmic Game Theory (Search for Journal in Brave)

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

zbMATH Keywords

Nash equilibriabimatrix gameswell-supported approximate equilibria

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Noncooperative games (91A10) 2-person games (91A05) Approximation algorithms (68W25)

Related Items (16)

Approximate well-supported Nash equilibria below two-thirds ⋮ A Glimpse at Paul G. Spirakis ⋮ An algorithm for finding approximate Nash equilibria in bimatrix games ⋮ On the approximation performance of fictitious play in finite games ⋮ 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 ⋮ Distributed Methods for Computing Approximate Equilibria ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ A Metaheuristic Approach to Compute Pure Nash Equilibria ⋮ On the communication complexity of approximate Nash equilibria ⋮ Contiguous Cake Cutting: Hardness Results and Approximation Algorithms ⋮ Distributed methods for computing approximate equilibria ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ Lipschitz continuity and approximate equilibria ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Semidefinite Programming and Nash Equilibria in Bimatrix Games

Cites Work

• Approximate well-supported Nash equilibria below two-thirds
• Well supported approximate equilibria in bimatrix games
• A note on approximate Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• Non-cooperative games
• Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/3
• 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
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games

This page was built for publication: Approximate well-supported Nash equilibria below two-thirds