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 $$\\epsilon $$∈-NE $$\\delta $$﾿-SW: find an $$\\epsilon $$∈-approximate Nash equilibrium $$\\epsilon $$∈-NE that is within $$\\delta $$﾿ of the best social welfare achievable by an $$\\epsilon $$∈-NE. Our main result is that, if the randomized exponential-time hypothesis RETH is true, then solving $$\\left \\frac{1}{8} - \\mathrm {O}\\delta \\right $$18-O﾿-NE $$\\mathrm {O}\\delta $$O﾿-SW for an $$n\\times n$$n×n bimatrix game requires $$n^{\\mathrm {\\widetilde{\\Omega }}\\delta ^{\\varLambda } \\log n}$$nΩ~﾿﾿logn time, where $$\\varLambda $$﾿ is a constant. Building on this result, we show similar conditional running time lower bounds on a number of decision problems for approximate Nash equilibria that do not involve social welfare, including maximizing or minimizing a certain player's payoff, or finding approximate equilibria contained in a given pair of supports. We show quasi-polynomial lower bounds for these problems assuming that RETH holds, and these lower bounds apply to $$\\epsilon $$∈-Nash equilibria for all $$\\epsilon < \\frac{1}{8}$$∈<18. The hardness of these other decision problems has so far only been studied in the context of exact equilibria. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-662-54110-4_3 | WINE |
DocType | Volume | Citations |
Conference | abs/1608.03574 | 5 |
PageRank | References | Authors |
0.41 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Argyrios Deligkas | 1 | 19 | 7.43 |
| John Fearnley | 2 | 8 | 1.15 |
| Rahul Savani | 3 | 243 | 30.09 |