Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis

DOI10.1137/1.9781611973730.66zbMath1372.68112DBLPconf/soda/BravermanKW15OpenAlexW2399001773WikidataQ57568013 ScholiaQ57568013MaRDI QIDQ5363042

Omri Weinstein, Mark Braverman, Young Kun-Ko

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.66

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A note on hardness of computing recursive teaching dimension ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis