New algorithms for approximate Nash equilibria in bimatrix games
From MaRDI portal
Publication:1041233
DOI10.1016/j.tcs.2009.09.023zbMath1180.91020OpenAlexW2072656810MaRDI QIDQ1041233
Hartwig Bosse, Evangelos Markakis, Jaroslaw Byrka
Publication date: 1 December 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.023
Noncooperative games (91A10) 2-person games (91A05) (n)-person games, (n>2) (91A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (27)
On Nash-Equilibria of Approximation-Stable Games ⋮ Computing equilibria: a computational complexity perspective ⋮ Approximate well-supported Nash equilibria below two-thirds ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ An algorithm for finding approximate Nash equilibria in bimatrix games ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ On the approximation performance of fictitious play in finite games ⋮ 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 ⋮ Distributed Methods for Computing Approximate Equilibria ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ Parameterized two-player Nash equilibrium ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ Distributed methods for computing approximate equilibria ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ Lipschitz continuity and approximate equilibria ⋮ Well supported approximate equilibria in bimatrix games ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximate Nash Equilibria for Multi-player Games ⋮ A note on approximate Nash equilibria ⋮ Polynomial algorithms for approximating Nash equilibria of bimatrix games ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium ⋮ Lipschitz Continuity and Approximate Equilibria ⋮ New algorithms for approximate Nash equilibria in bimatrix games ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Cites Work
- 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 sparse approximations to randomized strategies and convex combinations
- Non-cooperative games
- Reducibility among equilibrium problems
- The complexity of computing a Nash equilibrium
- On the Complexity of Nash Equilibria and Other Fixed Points
- An Optimization Approach for Approximate Nash Equilibria
- Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
- Approximate Equilibria for Strategic Two Person Games
This page was built for publication: New algorithms for approximate Nash equilibria in bimatrix games
