nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Computing Constrained Approximate Equilibria in Polymatrix Games

verfasst von : Argyrios Deligkas, John Fearnley, Rahul Savani

Erschienen in: Algorithmic Game Theory

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper studies constrained approximate Nash equilibria in polymatrix games. We show that is \(\mathtt {NP}\)-hard to decide if a polymatrix game has a constrained approximate equilibrium for 9 natural constraints and any non-trivial \(\epsilon \). We then provide a QPTAS for polymatrix games with bounded treewidth and logarithmically many actions per player that finds constrained approximate equilibria for a wide family of constraints.

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 Robustness Among Multiwinner Voting Rules

Nächstes Kapitel Group Activity Selection on Graphs: Parameterized Analysis

Given probability distributions \(\mathbf {x} \) and \(\mathbf {x} '\), the TV distance between them is \(\max _i \{ |\mathbf {x} _i - \mathbf {x} '_i| \}\). The TV distance between strategy profiles \(\mathbf {s} =(s_1, \ldots , s_n)\) and \(\mathbf {s} '=(s'_1, \ldots , s'_n)\) is the maximum TV distance of \(s_i\) and \(s'_i\) over all i.

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

Babichenko, Y., Barman, S., Peretz, R.: Simple approximate equilibria in large games. In: Proceedings of the EC, pp. 753–770 (2014)

Barman, S., Ligett, K.: Finding any nontrivial coarse correlated equilibrium is hard. In: Proceedings of EC, pp. 815–816 (2015)

Barman, S., Ligett, K., Piliouras, G.: Approximating Nash equilibria in tree polymatrix games. In: Hoefer, M. (ed.) SAGT 2015. LNCS, vol. 9347, pp. 285–296. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48433-3_22CrossRef

Bilò, V., Mavronicolas, M.: The complexity of decision problems about Nash equilibria in win-lose games. In: Serna, M. (ed.) SAGT 2012. LNCS, pp. 37–48. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33996-7_4CrossRef

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)

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

Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)MathSciNetCrossRef

Bonifaci, V., Di Iorio, U., Laura, L.: The complexity of uniform Nash equilibria and related regular subgraph problems. Theor. Comput. Sci. 401(1–3), 144–152 (2008)MathSciNetCrossRef

10.

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

11.

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

12.

Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 57 (2009). Article No. 14MathSciNetCrossRef

13.

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

14.

Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J., Jurdziński, M., Savani, R.: Distributed methods for computing approximate equilibria. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 15–28. Springer, Heidelberg (2016). doi:10.1007/978-3-662-54110-4_2CrossRef

15.

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

16.

Czumaj, A., Fasoulakis M., Jurdziński, M.: Approximate plutocratic and egalitarian Nash equilibria. In: Proceedings of AAMAS, pp. 1409–1410 (2016)

17.

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

18.

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

19.

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

20.

Deligkas, A., Fearnley, J., Igwe, T.P., Savani, R.: An empirical study on computing equilibria in polymatrix games. In: Proceedings of AAMAS, pp. 186–195 (2016)

21.

Deligkas, A., Fearnley, J., Savani, R.: Inapproximability results for approximate Nash equilibria. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 29–43. Springer, Heidelberg (2016). doi:10.1007/978-3-662-54110-4_3CrossRef

22.

Deligkas, A., Fearnley, J., Savani, R., Spirakis, P.G.: Computing approximate Nash equilibria in polymatrix games. Algorithmica 77(2), 487–514 (2017)MathSciNetCrossRef

23.

Elkind, E., Goldberg, L.A., Goldberg, P.W.: Nash equilibria in graphical games on trees revisited. In: Proceedings of EC, pp. 100–109 (2006)

24.

Elkind, E., Goldberg, L.A., Goldberg, P.W.: Computing good Nash equilibria in graphical games. In: Proceedings of EC, pp. 162–171 (2007)

25.

Fearnley, J., Goldberg, P.W., Savani, R., Sørensen, T.B.: Approximate well-supported Nash equilibria below two-thirds. In: Serna, M. (ed.) SAGT 2012. LNCS, pp. 108–119. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33996-7_10CrossRef

26.

Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 554–566. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47672-7_45CrossRef

27.

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

28.

Greco, G., Scarcello, F.: On the complexity of constrained Nash equilibria in graphical games. Theor. Comput. Sci. 410(38–40), 3901–3924 (2009)MathSciNetCrossRef

29.

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

30.

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

31.

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

32.

Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26(4), 573–590 (2001)MathSciNetCrossRef

33.

Ortiz, L.E., Irfan, M.T.: FPTAS for mixed-strategy Nash equilibria in tree graphical games and their generalizations. CoRR, abs/1602.05237 (2016)

34.

Ortiz, L.E., Irfan, M.T.: Tractable algorithms for approximate Nash equilibria in generalized graphical games with tree structure. In: Proceedings of AAAI, pp. 635–641 (2017)

35.

Rubinstein, A.: Inapproximability of Nash equilibrium. In: Proceedings of STOC, pp. 409–418 (2015)

36.

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

Titel: Computing Constrained Approximate Equilibria in Polymatrix Games
verfasst von: Argyrios Deligkas
John Fearnley
Rahul Savani
Verlag: Springer International Publishing
Buch: Algorithmic Game Theory
Print ISBN: 978-3-319-66699-0

Electronic ISBN: 978-3-319-66700-3

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-66700-3_8

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"

Premium Partner