Name
Abstract | ||
|---|---|---|
We study the problem of finding approximate Nash equilibria that satisfy certain conditions, such as providing good social welfare. In particular, we study the problem ϵ-NE δ-SW: find an ϵ-approximate Nash equilibrium (ϵ-NE) that is within δ of the best social welfare achievable by an ϵ-NE. Our main result is that, if the exponential-time hypothesis (ETH) is true, then solving (18−O(δ))-NE O(δ)-SW for an n×n bimatrix game requires nΩ˜(logn) time. Building on this result, we show similar conditional running time lower bounds for a number of other decision problems for ϵ-NE, where, for example, the payoffs or supports of players are constrained. We show quasi-polynomial lower bounds for these problems assuming ETH, where these lower bounds apply to ϵ-Nash equilibria for all ϵ<18. The hardness of these other decision problems has so far only been studied in the context of exact equilibria. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ic.2018.06.001 | Information and Computation |
Keywords | Field | DocType |
Approximate Nash equilibrium,Constrained equilibrium,Quasi-polynomial time,Lower bound,Exponential time hypothesis | Discrete mathematics,Decision problem,Combinatorics,Bimatrix game,Nash equilibrium,Mathematics | Journal |
Volume | Issue | ISSN |
262 | Part | 0890-5401 |
Citations | PageRank | References |
1 | 0.36 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Argyrios Deligkas | 1 | 19 | 7.43 |
| John Fearnley | 2 | 8 | 1.15 |
| Rahul Savani | 3 | 243 | 30.09 |