License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.12
URN: urn:nbn:de:0030-drops-183620
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18362/
Go to the corresponding LIPIcs Volume Portal

Fischer, Miriam ; Gupte, Akshay

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

pdf-format:
LIPIcs-SEA-2023-12.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{fischer_et_al:LIPIcs.SEA.2023.12,
  author =	{Fischer, Miriam and Gupte, Akshay},
  title =	{{Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18362},
  URN =		{urn:nbn:de:0030-drops-183620},
  doi =		{10.4230/LIPIcs.SEA.2023.12},
  annote =	{Keywords: Noncooperative n-person games, Nash equilibrium, Multilinear functions, Nonconvex problems, Mixed-integer optimization}
}

Keywords: Noncooperative n-person games, Nash equilibrium, Multilinear functions, Nonconvex problems, Mixed-integer optimization
Collection: 21st International Symposium on Experimental Algorithms (SEA 2023)
Issue Date: 2023
Date of publication: 19.07.2023
Supplementary Material: Dataset: https://github.com/economicsandcomputing/MultilinearNashEquilibria

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI