Document Open Access Logo

Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games

Authors Miriam Fischer, Akshay Gupte

PDF
Thumbnail PDF

File

LIPIcs.SEA.2023.12.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Miriam Fischer
  • Department of Computing, Imperial College London, UK
Akshay Gupte
  • School of Mathematics, The University of Edinburgh, UK

Funding

  • Fischer, Miriam: Supported by a PhD scholarship from DeepMind.

Acknowledgements

This research was initiated as part of the MSc dissertation of the first author in the School of Mathematics at the University of Edinburgh.

Cite As Get BibTex

Miriam Fischer and Akshay Gupte. Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SEA.2023.12

Abstract

We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Exact and approximate computation of equilibria
  • Theory of computation → Nonconvex optimization
Keywords
  • Noncooperative n-person games
  • Nash equilibrium
  • Multilinear functions
  • Nonconvex problems
  • Mixed-integer optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Xi Chen and Xiaotie Deng. Settling the complexity of computing two-player Nash equilibrium. Journal of the ACM, 56(3):1-57, 2009. URL: https://doi.org/10.1145/1516512.1516516.
  2. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. URL: https://doi.org/10.1137/070699652.
  3. Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, and Rahul Savani. An empirical study on computing equilibria in polymatrix games. In Proceedings of the 16st International Conference on Autonomous Agents and Multiagent Systems, AAMAS '16, pages 186-195, 2016. Google Scholar
  4. Robert Fourer, David M. Gay, and Brian W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. Cengage Learning, 2nd edition, 2002. Google Scholar
  5. Ian Gemp, Rahul Savani, Marc Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, Andrea Tacchetti, Tom Eccles, and János Kramár. Sample-based approximation of Nash in large many-player games via gradient descent. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS '22, pages 507-515. International Foundation for Autonomous Agents and Multiagent Systems, 2022. URL: https://arxiv.org/abs/2106.01285.
  6. Srihari Govindan and Robert Wilson. A global newton method to compute Nash equilibria. Journal of Economic Theory, 110(1):65-86, 2003. URL: https://doi.org/10.1016/S0022-0531(03)00005-X.
  7. Srihari Govindan and Robert Wilson. Computing Nash equilibria by iterated polymatrix approximation. Journal of Economic Dynamics and Control, 28(7):1229-1241, 2004. URL: https://doi.org/10.1016/S0165-1889(03)00108-8.
  8. C. E. Lemke and J. T. Howson, Jr. Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics, 12(2):413-423, 1964. URL: https://doi.org/10.1137/0112033.
  9. O.L. Mangasarian and H. Stone. Two-person nonzero-sum games and quadratic programming. Journal of Mathematical Analysis and Applications, 9(3):348-355, 1964. URL: https://doi.org/10.1016/0022-247X(64)90021-6.
  10. Richard D. McKelvey, Andrew M. McLennan, and Theodore L. Turocy. Gambit: Software tools for game theory, version 16.0.2. URL: http://www.gambit-project.org.
  11. John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951. URL: https://doi.org/10.2307/1969529.
  12. Eugene Nudelman, Jennifer Wortman, Yoav Shoham, and Kevin Leyton-Brown. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS '04, pages 880-887, USA, 2004. IEEE Computer Society. Google Scholar
  13. Ryan Porter, Eugene Nudelman, and Yoav Shoham. Simple search methods for finding a Nash equilibrium. Games and Economic Behavior, 63(2):642-662, 2008. URL: https://doi.org/10.1016/j.geb.2006.03.015.
  14. Joachim Rosenmüller. On a generalization of the lemke-howson algorithm to noncooperative n-person games. SIAM Journal on Applied Mathematics, 21(1):73-79, 1971. URL: https://doi.org/10.1137/0121010.
  15. Nick V. Sahinidis. BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual. http://www.minlp.com/downloads/docs/baron%20manual.pdf, 2017.
  16. Thomas Sandholm, Andrew Gilpin, and Vincent Conitzer. Mixed-integer programming methods for finding Nash equilibria. In Proceedings of the 20th National Conference on Artificial Intelligence - Volume 2, AAAI'05, pages 495-501. AAAI Press, 2005. Google Scholar
  17. Rahul Savani and Bernhard von Stengel. Hard-to-solve bimatrix games. Econometrica, 74(2):397-429, 2006. URL: https://doi.org/10.1111/j.1468-0262.2006.00667.x.
  18. Theodore L. Turocy. Answer to question regarding time limits of algorithms in gambit. URL: https://github.com/gambitproject/gambit/issues/261#issuecomment-660894391.
  19. Theodore L. Turocy. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, 51(2):243-263, 2005. Special Issue in Honor of Richard D. McKelvey. Google Scholar
  20. G. van der Laan, A. J. J. Talman, and L. van der Heyden. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Mathematics of Operations Research, 12(3):377-397, August 1987. Google Scholar
  21. Robert Wilson. Computing equilibria of n-person games. SIAM Journal on Applied Mathematics, 21(1):80-87, 1971. URL: https://doi.org/10.1137/0121011.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact