A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
From MaRDI portal
Publication:6055559
DOI10.1137/23m1549237OpenAlexW4386686307MaRDI QIDQ6055559
Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis
Publication date: 29 September 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/23m1549237
Related Items (1)
Cites Work
- Unnamed Item
- Approximate well-supported Nash equilibria below two-thirds
- 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
- On the communication complexity of approximate Nash equilibria
- Non-cooperative games
- The complexity of computing a Nash equilibrium
- Approximate Well-Supported Nash Equilibria in Symmetric Bimatrix Games
- Distributed Methods for Computing Approximate Equilibria
- Empirical Distribution of Equilibrium Play and Its Testing Application
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- Communication Complexity (for Algorithm Designers)
- Settling the complexity of computing two-player Nash equilibria
- An Optimization Approach for Approximate Nash Equilibria
- Constant Rank Two-Player Games are PPAD-hard
- Inapproximability of Nash Equilibrium
- 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
This page was built for publication: A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
