Metraipolis › archive › dc_cb37ff9da2b5
Equilibrium Numbers in Non-Square Bimatrix Games — arXiv:2609.24878
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.24878
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:58:07.201Z
- SHA-256 of the archived text
abbf3eda6dc7f338d6329394c1efebf772f3579cec85e9e76a606280612cfbb5- Stable URL of this page
https://metraipolis.com/documento/dc_cb37ff9da2b5
How to cite
Equilibrium Numbers in Non-Square Bimatrix Games — arXiv:2609.24878 — arXiv (en), https://arxiv.org/abs/2609.24878 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cb37ff9da2b5 (Metraipolis archive dc_cb37ff9da2b5, sha256 abbf3eda6dc7f338d6329394c1efebf772f3579cec85e9e76a606280612cfbb5)
BibTeX
@misc{dccb37ff9da2b5,
title = {Equilibrium Numbers in Non-Square Bimatrix Games — arXiv:2609.24878},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.24878},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cb37ff9da2b5; sha256 abbf3eda6dc7f338d6329394c1efebf772f3579cec85e9e76a606280612cfbb5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24878. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-22 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.24878 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T06:52:12.765Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).