Skip to content

Benchmarks

Jump to bottom
Tomáš Votroubek edited this page Sep 1, 2026 · 6 revisions

LogitNash.jl implements the same quantal response continuation as the current SOTA gambit-logit, but tries to improve on the speed and stability of. A representative slate of 22 distributions from GAMUT for six-player five-action games is shown below.

Single-thread race-to-lambda
  • The runtimes required to reach $\lambda = 10^6$ of 100 samples from the six-player five-action each GAMUT distribution running on a single thread of AMD EPYC 7543. The label below each distribution shows the ratio of median runtimes.
  • You cannot be more fair than to run a comparison based on the rules of the competitor. This benchmark was specified by Turocy (2005, Section 5 Table 3) and Nudelman et al. (2004, Experimental Results: Fig. 3 and 4). Everything is run with default settings unless stated otherwise.

Note that this is not a direct port of gambit-logit. The path following algorithm, as well as the profile encoding is different. Compare the path tracing behavior on the game of Bach or Stravinsky:

bach_or_stravinsky

In my experience, gambit-logit is the fastest and most repeatable solver out there, and is still under active development (last commit was 5 days ago). BaB methods unfortunately do not scale well on this problem and have extremely multimodal runtimes leading to frequent timeouts for moderately-sized games. It is also still the go-to comparison e.g. Ganzfried (2025), Fischer and Gupte (2023), and even the approximate solver Gemp et al. (2022) to name but a very few.

  • Ganzfried, S. (2025). Fast Complete Algorithm for Multiplayer Nash Equilibrium. In: Sinha, A., Fu, J., Zhu, Q., Zhang, T. (eds) Decision and Game Theory for Security. GameSec 2024. Lecture Notes in Computer Science, vol 14908. Springer, Cham. https://doi.org/10.1007/978-3-031-74835-6_6
  • 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
  • Ian Gemp, Rahul Savani, Marc Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, Andrea Tacchetti, Tom Eccles, and János Kramár. 2022. 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). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 507–515.

I still have to add a comparison to the following (if you know others, I would like to hear from you):

  • Černý, J., Das Gupta, S., & Kroer, C. (2026). Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 16752–16760. https://doi.org/10.1609/aaai.v40i20.38718

Clone this wiki locally