Computing Constrained Approximate Equilibria in Polymatrix Games | SpringerLink
Skip to main content
Springer Nature Link
Log in

Computing Constrained Approximate Equilibria in Polymatrix Games

  • Conference paper
  • First Online:
Algorithmic Game Theory (SAGT 2017)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 10504))

Included in the following conference series:

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.

This work was supported by ISF grant 2021296 and EPSRC grant EP/P020909/1.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    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.

References

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  4. 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_22

    Chapter  Google Scholar 

  5. 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_4

    Chapter  Google Scholar 

  6. 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)

    Google Scholar 

  7. 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)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  9. 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)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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. 14

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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_2

    Chapter  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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_3

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

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

    Google Scholar 

  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_10

    Chapter  Google Scholar 

  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_45

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

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

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technion, Haifa, Israel

    Argyrios Deligkas

  2. University of Liverpool, Liverpool, UK

    John Fearnley & Rahul Savani

Authors
  1. Argyrios Deligkas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John Fearnley
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rahul Savani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Argyrios Deligkas .

Editor information

Editors and Affiliations

  1. University of Salento, Lecce, Italy

    Vittorio Bilò

  2. University of L'Aquila, L'Aquila, Italy

    Michele Flammini

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Deligkas, A., Fearnley, J., Savani, R. (2017). Computing Constrained Approximate Equilibria in Polymatrix Games. In: Bilò, V., Flammini, M. (eds) Algorithmic Game Theory. SAGT 2017. Lecture Notes in Computer Science(), vol 10504. Springer, Cham. https://doi.org/10.1007/978-3-319-66700-3_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-66700-3_8

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-66699-0

  • Online ISBN: 978-3-319-66700-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics