On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium
From MaRDI portal
Publication:2670913
DOI10.1007/978-3-030-85947-3_7zbMath1492.91075arXiv2107.01471OpenAlexW3201960926MaRDI QIDQ2670913
Hanyu Li, Xiaotie Deng, Wenhan Huang, Zhaohua Chen, Yu-Hao Li
Publication date: 1 June 2022
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.01471
Theory of computing (68Qxx) Algorithmic game theory and complexity (91A68) Equilibrium refinements (91A11)
Related Items (2)
On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
Cites Work
- Unnamed Item
- Unnamed Item
- Worst-case equilibria
- Distributed methods for computing approximate equilibria
- A note on approximate Nash equilibria
- Polynomial algorithms for approximating Nash equilibria of bimatrix games
- New algorithms for approximate Nash equilibria in bimatrix games
- Uniqueness of solution in linear programming
- On the complexity of the parity argument and other inefficient proofs of existence
- Non-cooperative games
- On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium
- Distributed Methods for Computing Approximate Equilibria
- How bad is selfish routing?
- Settling the complexity of computing two-player Nash equilibria
- Nonsmooth Optimization
- 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
- Prediction, Learning, and Games
- Algorithmic mechanism design
This page was built for publication: On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium