nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Inapproximability Results for Approximate Nash Equilibria

verfasst von : Argyrios Deligkas, John Fearnley, Rahul Savani

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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) \)-NE \(\mathrm {O}(\delta )\)-SW for an \(n\times n\) bimatrix game requires \(n^{\mathrm {\widetilde{\Omega }}(\delta ^{\varLambda } \log n)}\) 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}\). The hardness of these other decision problems has so far only been studied in the context of exact equilibria.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Distributed Methods for Computing Approximate Equilibria

Nächstes Kapitel Multilinear Games

While the proof in [6] produces a lower bound for 0.8-NE \((1 - \mathrm {O}(\epsilon ))\)-SW, this is in a game with maximum payoff \(\mathrm {O}(1/\epsilon )\). Therefore, when the payoffs in this game are rescaled to [0, 1], the resulting lower bound only applies to \(\epsilon \)-NE \(\epsilon \)-SW.

Although the paper claims that they obtain a \(n^{\mathrm {\widetilde{O}}(\log n)}\) lower bound, the proof reduces from the low error result from [1] (cf. Theorem 36 in [2]), which gives only the weaker lower bound of \(n^{\text {poly}(\epsilon ) \log (n)^{1 - o(1)}}\).

Here \(\mathrm {\widetilde{\Omega }}(\log n)\) means \(\mathrm {\Omega }(\frac{\log n}{(\log \log n)^c})\) for some constant c.

If |Y| is not even, then we can create a new free game in which each question in |Y| appears twice. This will not change the value of the free game.

Aaronson, S., Impagliazzo, R., Moshkovitz, D.: AM with multiple Merlins. In: Proceedings of CCC, pp. 44–55 (2014)

Aaronson, S., Impagliazzo, R., Moshkovitz, D.: AM with multiple Merlins. CoRR, abs/1401.6848 (2014)

Austrin, P., Braverman, M., Chlamtac, E.: Inapproximability of NP-complete variants of Nash equilibrium. Theory Comput. 9, 117–142 (2013)MathSciNetCrossRefMATH

Bilò, V., Mavronicolas, M.: A catalog of \(\exists \mathbb{R} \)-complete decision problems about Nash equilibria in multi-player games. In: Proceedings of STACS, pp. 17:1–17:13 (2016)

Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate Nash equilibria in bimatrix games. Theoret. Comput. Sci. 411(1), 164–173 (2010)MathSciNetCrossRefMATH

Braverman, M., Kun-Ko, Y., Weinstein, O.: Approximating the best Nash equilibrium in \(n{}^{{o}}\) \({}^{\text{(log}\,{n)}}\)-time breaks the exponential time hypothesis. In: Proceedings of SODA, pp. 970–982 (2015)

Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games Econ. Behav. 63(2), 621–641 (2008)MathSciNetCrossRefMATH

Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J., Jurdziński, M., Savani, R.: Distributed methods for computing approximate equilibria. In: Proceedings of WINE (2016)

Czumaj, A., Fasoulakis, M., Jurdziński, M.: Approximate Nash equilibria with near optimal social welfare. In: Proceedings of IJCAI, pp. 504–510 (2015)

10.

Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009)MathSciNetCrossRefMATH

11.

Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate Nash equilibria. In: Proceedings of EC, pp. 355–358 (2007)

12.

Daskalakis, C., Mehta, A., Papadimitriou, C.H.: A note on approximate Nash equilibria. Theoret. Comput. Sci. 410(17), 1581–1588 (2009)MathSciNetCrossRefMATH

13.

Fearnley, J., Goldberg, P.W., Savani, R., Sørensen, T.B.: Approximate well-supported Nash equilibria below two-thirds. In: Proceedings of SAGT, pp. 108–119 (2012)

14.

Feder, T., Nazerzadeh, H., Saberi, A.: Approximating Nash equilibria using small-support strategies. In: Proceedings of EC, pp. 352–354 (2007)

15.

Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In: Proceedings of ICALP, pp. 554–566 (2015)

16.

Gilboa, I., Zemel, E.: Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. 1(1), 80–93 (1989)MathSciNetCrossRefMATH

17.

Hazan, E., Krauthgamer, R.: How hard is it to approximate the best Nash equilibrium? SIAM J. Comput. 40(1), 79–91 (2011)MathSciNetCrossRefMATH

18.

Kontogiannis, S.C., Spirakis, P.G.: Well supported approximate equilibria in bimatrix games. Algorithmica 57(4), 653–667 (2010)MathSciNetCrossRefMATH

19.

Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of EC, pp. 36–41 (2003)

20.

Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286–295 (1951)MathSciNetCrossRefMATH

21.

Rubinstein, A.: Settling the complexity of computing approximate two-player Nash equilibria. In: Proceedings of FOCS, pp. 258–265 (2016)

22.

Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. Internet Math. 5(4), 365–382 (2008)MathSciNetCrossRefMATH

Titel: Inapproximability Results for Approximate Nash Equilibria
verfasst von: Argyrios Deligkas
John Fearnley
Rahul Savani
Verlag: Springer Berlin Heidelberg
Buch: Web and Internet Economics
Print ISBN: 978-3-662-54109-8

Electronic ISBN: 978-3-662-54110-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-54110-4_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"