Inapproximability results for constrained approximate Nash equilibria
type: Item
instance of: scholarly article
title: Inapproximability results for constrained approximate Nash equilibria
zbMATH Open document ID: 1400.68086
author: Argyrios Deligkas
author: John Fearnley
author: Rahul Savani
published in: Information and Computation
publication date: 2018-09-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 91A10
zbMATH DE Number: 6944931
zbMATH Keywords: approximate Nash equilibrium
zbMATH Keywords: constrained equilibrium
zbMATH Keywords: quasi-polynomial time
zbMATH Keywords: lower bound
zbMATH Keywords: exponential time hypothesis
MaRDI profile type: Publication
full work available at URL: j.ic.2018.06.001
OpenAlex ID: W2806555090
cites work: The Complexity of Computing a Nash Equilibrium
cites work: Nash and correlated equilibria: Some complexity considerations
cites work: New complexity results about Nash equilibria
cites work: ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
cites work: A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
cites work: Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
cites work: New algorithms for approximate Nash equilibria in bimatrix games
cites work: Distributed Methods for Computing Approximate Equilibria
cites work: A note on approximate Nash equilibria
cites work: Approximate well-supported Nash equilibria below two-thirds
cites work: Well supported approximate equilibria in bimatrix games
cites work: An Optimization Approach for Approximate Nash Equilibria
cites work: How Hard Is It to Approximate the Best Nash Equilibrium?
cites work: Q3191570
cites work: Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
cites work: On sparse approximations to randomized strategies and convex combinations
cites work: Inapproximability Results for Approximate Nash Equilibria
cites work: Can almost everybody be almost happy?
cites work: Two-query PCP with subconstant error
cites work: The PCP theorem by gap amplification
cites work: Non-cooperative games
cites work: On oblivious PTAS's for nash equilibrium
Wikidata QID: Q129723213
DOI: 10.1016/J.IC.2018.06.001
description: scientific article; zbMATH DE number 6944931