from Hacker News

Finding Nash equilibria through simulation

by ADavison2560 on 8/6/24, 5:13 PM with 28 comments

  • by cs702 on 8/6/24, 6:05 PM

    Cool and interesting. Thank you for sharing on HN.

    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

    I am currently trying to do this for poker in open source. https://github.com/elliottneilclark/rs-poker/pull/92

    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

    Nice! I'll have to read through this and use it to improve https://brev.dev/blog/how-to-win-a-2-player-game-of-are-you-... which was a similar exercise on a game slightly different than prisoners dilemma. I like being able to use "brute force" numerical methods to solve problems like this because they are often simpler to construct and exploit the fact that computers go brrr.
  • by abdullahkhalids on 8/6/24, 5:53 PM

    One of my goals is to understand markets through Game Theory. On the producer side, every player can hold, increase or decrease their price. And that changes the rewards for every other player.

    What are good references for this?

  • by artimis on 8/6/24, 5:50 PM

    Why have you chosen to simulate players if Nash Equilibrium can be computed analytically (or at least numerically)?

    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

    AlphaZero is arguably like those algorithms on steroids, probably worth a mention there. Even though the goal is a bit different, finding Nash equilibria for games like Go is probably still infeasible, but you also don't need that to beat humans.
  • by nadis on 8/6/24, 10:12 PM

    This is very cool! We've been exploring the idea of software simulation with what we're building (CodeYam) but I hadn't really thought a ton about applying simulation to find the Nash equilibria / for game theory. Nicely done!
  • by jsemrau on 8/6/24, 5:57 PM

    I was working on a local LLM ReAct agent that can play the prisoner's dilemma. The "thought" process was fascinating to watch. Not to anthropomorphize though.
  • by Log_out_ on 8/7/24, 4:43 PM

    Where in game theory would one model a nuclear armed country going bankrupt ala pakistan?
  • by ForOldHack on 8/6/24, 5:24 PM

    Nash as in 'A Beautiful Mind' - Nash.

    https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr.

  • by fifilura on 8/7/24, 9:02 AM

    John Nash is portrayed by Russell Crowe in the movie "A beautiful Mind"

    https://www.imdb.com/title/tt0268978