by ADavison2560 on 8/6/24, 5:13 PM with 28 comments
by cs702 on 8/6/24, 6:05 PM
As Nash proved, under very general conditions (e.g., payoffs are finite), in every game there's always at least one equilibrium, i.e., at least one fixed point.
Alas, as Papadimitriou proved in the 90's, finding Nash equilibria is PPAD-complete.[a][b]
So, as games get larger and more complex -- say, with rules and payoffs that evolve over time -- finding equilibria can become... intractable: There will always exist at least one Nash equilibrium, but you'll never be able to reach it. Simulation may well be the only way to model such games.
---
[a] https://en.wikipedia.org/wiki/PPAD_(complexity)
[b] There's a great intro lecture on this by Papadimitriou himself at https://www.youtube.com/watch?v=TUbfCY_8Dzs
by eclark on 8/6/24, 7:02 PM
Find the Nash equilibrium for poker with an exact set of cards and a deck. There's a fun arena-based tree structure that should allow finding the optimal strategy for different bet sizes, etc. One of the most challenging parts of finding the equilibrium is ensuring the simulation has no edge cases where value is lost.
There's a bug somewhere, and the game state isn't matching the second time through a tree node. (I'd pay a bounty to whoever can get it finished)
by someguy101010 on 8/6/24, 6:42 PM
by abdullahkhalids on 8/6/24, 5:53 PM
What are good references for this?
by artimis on 8/6/24, 5:50 PM
I've used optimization of https://en.wikipedia.org/wiki/Lyapunov_function in my Bachelor thesis https://github.com/Artimi/neng to do that.
by t_mann on 8/6/24, 7:59 PM
by nadis on 8/6/24, 10:12 PM
by jsemrau on 8/6/24, 5:57 PM
by Log_out_ on 8/7/24, 4:43 PM
by ForOldHack on 8/6/24, 5:24 PM
by fifilura on 8/7/24, 9:02 AM