@article{DELIGKAS201840,
    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Ω˜(log⁡n) 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.},
    Author = {Deligkas, Argyrios and Fearnley, John and Savani, Rahul},
    File = {main (0) (0) - a - a - l.pdf},
    ISSN = {0890-5401},
    Journal = {Information and Computation},
    Keywords = {Approximate Nash equilibrium, Constrained equilibrium, Quasi-polynomial time, Lower bound, Exponential time hypothesis},
    Pages = {40 - 56},
    Title = {Inapproximability results for constrained approximate Nash equilibria},
    URL = {http://www.sciencedirect.com/science/article/pii/S0890540118301123},
    Volume = {262},
    Year = {2018},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0890540118301123},
    bdsk-url-2 = {https://doi.org/10.1016/j.ic.2018.06.001},
    date-added = {2019-04-12 08:05:21 +0200},
    date-modified = {2019-04-12 08:05:21 +0200},
    doi = {10.1016/j.ic.2018.06.001}
}

@article{DELIGKAS201840, 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Ω˜(log⁡n) 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.}, Author = {Deligkas, Argyrios and Fearnley, John and Savani, Rahul}, File = {main (0) (0) - a - a - l.pdf}, ISSN = {0890-5401}, Journal = {Information and Computation}, Keywords = {Approximate Nash equilibrium, Constrained equilibrium, Quasi-polynomial time, Lower bound, Exponential time hypothesis}, Pages = {40 - 56}, Title = {Inapproximability results for constrained approximate Nash equilibria}, URL = {http://www.sciencedirect.com/science/article/pii/S0890540118301123}, Volume = {262}, Year = {2018}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0890540118301123}, bdsk-url-2 = {https://doi.org/10.1016/j.ic.2018.06.001}, date-added = {2019-04-12 08:05:21 +0200}, date-modified = {2019-04-12 08:05:21 +0200}, doi = {10.1016/j.ic.2018.06.001} }