A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
From MaRDI portal
Publication:6075856
DOI10.1145/3606697arXiv2204.11525MaRDI QIDQ6075856
Michail Fasoulakis, Argyrios Deligkas, Evangelos Markakis
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2204.11525
Cites Work
- Unnamed Item
- Approximate well-supported Nash equilibria below two-thirds
- On mutual concavity and strategically-zero-sum bimatrix games
- Computing approximate Nash equilibria in polymatrix games
- Distributed methods for computing approximate equilibria
- Games of fixed rank: a hierarchy of bimatrix games
- Well supported approximate equilibria in bimatrix games
- Imitation games and computation
- A note on approximate Nash equilibria
- Polynomial algorithms for approximating Nash equilibria of bimatrix games
- New algorithms for approximate Nash equilibria in bimatrix games
- On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
- Random bimatrix games are asymptotically easy to solve (a simple proof)
- Inapproximability results for constrained approximate Nash equilibria
- Simple complexity from imitation games
- Non-cooperative games
- On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium
- The complexity of computing a Nash equilibrium
- Approximate Well-Supported Nash Equilibria in Symmetric Bimatrix Games
- Empirical Distribution of Equilibrium Play and Its Testing Application
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- Settling the complexity of computing two-player Nash equilibria
- An Optimization Approach for Approximate Nash Equilibria
- Constant Rank Two-Player Games are PPAD-hard
- Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem
- Sum-of-squares meets Nash: lower bounds for finding any equilibrium
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
- Rank-1 bimatrix games
- Nash equilibria in random games
- Approximating the existential theory of the reals
- A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
This page was built for publication: A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
