6 ms·

Finding Nash equilibria through simulation

111 points by ADavison2560 2y ago

ForOldHack 2y ago
Nash as in 'A Beautiful Mind' - Nash. https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr.
artimis 2y ago
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 https://en.wikipedia.org/wiki/Lyapunov_function in my Bachelor thesis https://github.com/Artimi/neng https://github.com/Artimi/neng to do that.
- 0cf8612b2e1e 2y ago
  Simulation is fun and understandable by many more than a block of math. Specially if using a more complex problem where there might not be an analytical solution.
  - tonyarkles 2y ago
    To take that a step further, problems with analytical solutions are fun to simulate because you can use the analytical solution to verify that your simulator is working correctly.
    - laurent_du 2y ago
      That's a good point, and I'd add that, in the opposite direction, running a simulation can be a good way to convince yourself that your analytical solution is correct.
abdullahkhalids 2y ago
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?
- worstspotgain 2y ago
  Assuming low transaction costs and no collusion shenanigans, markets converge in microeconomics even in the presence of market power (meaning producers are big enough that they're not effectively price-takers.) Using Game Theory here kind of complicates the analysis without bringing a lot to the table, unless you have some special conditions or requirements. If you have an overall demand curve and a marginal cost curve for each seller, you can find the equilibrium where each producer is at their profit-maximization point. In the standard micro textbooks this is the point where each producer's MR is equal to MC, i.e. a local maximum where the derivative of profit with respect to output is zero. [1] In the price-taker case this is easy, as the MR curve is flat. In the non-price-taker case you can just solve iteratively until the whole market converges. [1] https://en.wikipedia.org/wiki/Profit_maximization https://en.wikipedia.org/wiki/Profit_maximization
  - abdullahkhalids 2y ago
    I am precisely thinking of oligopolies where either formal collusion happens, or as we often see in the real world, prices going up, without any collusion. In the latter case, the players are using some strategy for switching prices, that leads ultimately to (game-theoretic) cooperation between them. My understanding is that this a multi-player multi-shot Game, and the methods of game theory can help us understand what the strategy in question is.
    - worstspotgain 2y ago
      Yep, that scenario is (somewhat naively) modeled as an infinitely-repeated Prisoner's Dilemma. The equilibrium in that game is just the monopoly price, i.e. MR=MC for the producers' aggregated MC curve. So you have the monopoly price at one end (infinitely repeated game, perfect monitoring, no antitrust risk) and the oligopoly price at the other. It's a bit of a castle of cards that's going to fail wildly depending on which assumption you break. If the game is finitely repeated, for instance, the equilibrium is the oligopoly price. One variant that's been in the news recently is rent-setting software. [1] Here the goal is not running afoul of antitrust. The problem is that it's partly a transaction cost effect, because landlords are publishing rents rather than targeting 100% occupancy (which would make deviating a lot more appealing than colluding for any landlord with less than ~50% of the market.) If antitrust is not an issue and compliance monitoring is the problem, look for OPEC research. [1] https://news.ycombinator.com/item?id=41163936 https://news.ycombinator.com/item?id=41163936
jsemrau 2y ago
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.
- passion__desire 2y ago
  Can you ask the agents to be lenient, or stringent or forgetful or forgiving ? And then have one group who participate in decision play against other group. The groups will have distribution of the properties I laid out before or other interesting properties. I have been desiring to know what would human like features do to prisoners dilemma strategies after watching veritasium video. What Game Theory Reveals About Life, The Universe, and Everything https://youtu.be/mScpHTIi-kM https://youtu.be/mScpHTIi-kM
cs702 2y ago
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) 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 https://www.youtube.com/watch?v=TUbfCY_8Dzs
- hinkley 2y ago
  There was a guy who used math to 'solve' the stock market in the 80's or maybe even the 70's, and he flew dark for quite some time before revealing how he did it. Presumably like Buffett, once people know what you're up to they start to adapt to your actions which changes the entire equation. If you can reduce feedback loops by getting good at, for instance, sneakily and quietly collecting a large position by many small increments under many different accounts, then you can get somewhere without being pulled into a giant spiral.
  - akira2501 2y ago
    > If you can reduce feedback loops by getting good at, for instance, sneakily and quietly collecting a large position by many small increments under many different accounts, then you can get somewhere without being pulled into a giant spiral. Implying that you otherwise have information or purchasing clairvoyance that other people cannot access which would make this approach more likely to payoff than not. Otherwise, it's a lot of effort for a small chance at reward, so why not just buy into an index?
    - hinkley 2y ago
      You understand that index funds only relatively recently won mindshare, right? Particularly in the eighties everyone thought they could beat the system. And there was so much inefficiency that they were often right. It’s also democratized with the drop in transaction fees. When I first looked at the stock market, they wanted $80 a trade, which is $190 adjusted for inflation. So you’re getting much more Law of Large Numbers effects today, smoothing things out.
someguy101010 2y ago
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-a-robot 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.
eclark 2y ago
I am currently trying to do this for poker in open source. https://github.com/elliottneilclark/rs-poker/pull/92 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)
t_mann 2y ago
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.
nadis 2y ago
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!
fifilura 2y ago
John Nash is portrayed by Russell Crowe in the movie "A beautiful Mind" https://www.imdb.com/title/tt0268978 https://www.imdb.com/title/tt0268978
Log_out_ 2y ago
Where in game theory would one model a nuclear armed country going bankrupt ala pakistan?
- Iwan-Zotow 2y ago
  And how this is relevant?

111 points by ADavison2560 2y ago

Nash as in 'A Beautiful Mind' - Nash. https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr.

artimis 2y ago

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 https://en.wikipedia.org/wiki/Lyapunov_function in my Bachelor thesis https://github.com/Artimi/neng https://github.com/Artimi/neng to do that.

0cf8612b2e1e 2y ago
Simulation is fun and understandable by many more than a block of math. Specially if using a more complex problem where there might not be an analytical solution.
- tonyarkles 2y ago
  To take that a step further, problems with analytical solutions are fun to simulate because you can use the analytical solution to verify that your simulator is working correctly.
  - laurent_du 2y ago
    That's a good point, and I'd add that, in the opposite direction, running a simulation can be a good way to convince yourself that your analytical solution is correct.

abdullahkhalids 2y ago

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?

worstspotgain 2y ago
Assuming low transaction costs and no collusion shenanigans, markets converge in microeconomics even in the presence of market power (meaning producers are big enough that they're not effectively price-takers.) Using Game Theory here kind of complicates the analysis without bringing a lot to the table, unless you have some special conditions or requirements. If you have an overall demand curve and a marginal cost curve for each seller, you can find the equilibrium where each producer is at their profit-maximization point. In the standard micro textbooks this is the point where each producer's MR is equal to MC, i.e. a local maximum where the derivative of profit with respect to output is zero. [1] In the price-taker case this is easy, as the MR curve is flat. In the non-price-taker case you can just solve iteratively until the whole market converges. [1] https://en.wikipedia.org/wiki/Profit_maximization https://en.wikipedia.org/wiki/Profit_maximization
- abdullahkhalids 2y ago
  I am precisely thinking of oligopolies where either formal collusion happens, or as we often see in the real world, prices going up, without any collusion. In the latter case, the players are using some strategy for switching prices, that leads ultimately to (game-theoretic) cooperation between them. My understanding is that this a multi-player multi-shot Game, and the methods of game theory can help us understand what the strategy in question is.
  - worstspotgain 2y ago
    Yep, that scenario is (somewhat naively) modeled as an infinitely-repeated Prisoner's Dilemma. The equilibrium in that game is just the monopoly price, i.e. MR=MC for the producers' aggregated MC curve. So you have the monopoly price at one end (infinitely repeated game, perfect monitoring, no antitrust risk) and the oligopoly price at the other. It's a bit of a castle of cards that's going to fail wildly depending on which assumption you break. If the game is finitely repeated, for instance, the equilibrium is the oligopoly price. One variant that's been in the news recently is rent-setting software. [1] Here the goal is not running afoul of antitrust. The problem is that it's partly a transaction cost effect, because landlords are publishing rents rather than targeting 100% occupancy (which would make deviating a lot more appealing than colluding for any landlord with less than ~50% of the market.) If antitrust is not an issue and compliance monitoring is the problem, look for OPEC research. [1] https://news.ycombinator.com/item?id=41163936 https://news.ycombinator.com/item?id=41163936

jsemrau 2y ago

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.

passion__desire 2y ago
Can you ask the agents to be lenient, or stringent or forgetful or forgiving ? And then have one group who participate in decision play against other group. The groups will have distribution of the properties I laid out before or other interesting properties. I have been desiring to know what would human like features do to prisoners dilemma strategies after watching veritasium video. What Game Theory Reveals About Life, The Universe, and Everything https://youtu.be/mScpHTIi-kM https://youtu.be/mScpHTIi-kM

cs702 2y ago

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) 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 https://www.youtube.com/watch?v=TUbfCY_8Dzs

hinkley 2y ago
There was a guy who used math to 'solve' the stock market in the 80's or maybe even the 70's, and he flew dark for quite some time before revealing how he did it. Presumably like Buffett, once people know what you're up to they start to adapt to your actions which changes the entire equation. If you can reduce feedback loops by getting good at, for instance, sneakily and quietly collecting a large position by many small increments under many different accounts, then you can get somewhere without being pulled into a giant spiral.
- akira2501 2y ago
  > If you can reduce feedback loops by getting good at, for instance, sneakily and quietly collecting a large position by many small increments under many different accounts, then you can get somewhere without being pulled into a giant spiral. Implying that you otherwise have information or purchasing clairvoyance that other people cannot access which would make this approach more likely to payoff than not. Otherwise, it's a lot of effort for a small chance at reward, so why not just buy into an index?
  - hinkley 2y ago
    You understand that index funds only relatively recently won mindshare, right? Particularly in the eighties everyone thought they could beat the system. And there was so much inefficiency that they were often right. It’s also democratized with the drop in transaction fees. When I first looked at the stock market, they wanted $80 a trade, which is $190 adjusted for inflation. So you’re getting much more Law of Large Numbers effects today, smoothing things out.

someguy101010 2y ago

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-a-robot 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.

eclark 2y ago

I am currently trying to do this for poker in open source. https://github.com/elliottneilclark/rs-poker/pull/92 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)

t_mann 2y ago

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.

nadis 2y ago

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!

fifilura 2y ago

John Nash is portrayed by Russell Crowe in the movie "A beautiful Mind" https://www.imdb.com/title/tt0268978 https://www.imdb.com/title/tt0268978

Log_out_ 2y ago

Where in game theory would one model a nuclear armed country going bankrupt ala pakistan?

Iwan-Zotow 2y ago
And how this is relevant?