Hello lovely people,
I would like to announce LogitNash.jl – a solver for finite multiplayer general-sum games, with the slightly provocative claim of finding a mixed Nash Equilibrium more than 100x faster than the state of the art (under fair and comprehensive benchmarks).
The iterative solver is based on the convergent theory of Turocy (2005), but optimized for speed and re-parametrized for better solution accuracy.
The algorithm is optimized for large dense games and solves a 4-player 66-action Blotto game (same as considered by ADIDAS, 290 MB encoded as F32) in around 12 seconds (on a ThinkPad Gen 2) to a relative maximal deviation incentive of less than 10^{-6}.
If you have suggestions for improvements or comparisons you would like to see, please get in touch.
P.S. If any of You experienced solver maintainers have tips and or lessons-learned for the final stable API, I would love to hear from you!
P.P.S. This is my first package, sorry if this isn’t how packages are meant to be announced.
Congratulations! This looks very impressive.
Thank you for sharing. It’s not at all my field, so I’m curious what this can be used for. What are typical applications of this?
Do you mean finite mixed Nash Equilibria in general?
It is a question of “how ‘people’ will act,” or which stable strategies exist in an interaction between multiple agents. You can answer this as long as you are able to describe their incentives exactly.
This is a huge requirement usually, but a natural property of what people would refer to as “games,” e.g. rock-paper-scissors, robots playing laser tag (Rosencrantz et al., 2003) etc. Even if you don’t know everything exactly, it can still be used to model behavior, e.g. things like security scenarios, and actually was originally invented as theory for pricing in an oligopolistic market.
The concept has also famously been butchered by the movie “A Beautiful Mind.”
The reason for creating this solver specifically is as a sub-solver for continuous games. Because finite games aren’t my field either . The applications there are things like adversarial classification, cybersecurity, or even modeling billiards if we go back to actual “games.”
Damn, I got sniped. I was literally about to release a package like this myself I’ll see if there’s any PRs I can make. Is it based on BifurcationKit.jl too?
No, everything is custom, but the tracking is loosely based on the theory from the papers and documentation that accompany HomotopyContinuation.jl, BifurcationKit.jl and Bertini.
Wow, now that You’re the second person to ask me that, I’m starting to think I missed an opportunity… The problem is that the variables have to be carefully handled in log-ratio space, which I did not think I could do with either package. The freedom of having complete control over each bit made it much easier to optimize. Luckily the non-specific continuation code can be written in like 100 loc. But I’ll have a closer look. Maybe I underestimated how modular they are. Thanks.
The code should be considered (is) public preview… I was developing it for use in my continuous game solver (before I benchmarked it). I think having a driving force for the design OTHER than speed, i.e. actually based on real world usage is quite important before moving forward.
Or at least that’s my excuse for the code quality…
Couldn’t you just hand off the logarithms to BifurcationKit.jl? Either way, when testing this I found an asinh transform seems to do a bit better, since it produces near-linear behavior near the tails rather than saturating (like probabilities) or blowing up.
. The applications there are things like adversarial classification, cybersecurity, or even modeling billiards if we go back to actual “games.”
I’ll see if there’s any PRs I can make. Is it based on BifurcationKit.jl too?