[HN Gopher] Finding Nash equilibria through simulation
___________________________________________________________________
Finding Nash equilibria through simulation
Author : ADavison2560
Score : 52 points
Date : 2024-08-06 17:13 UTC (5 hours ago)
(HTM) web link (coe.psu.ac.th)
(TXT) w3m dump (coe.psu.ac.th)
| ForOldHack wrote:
| Nash as in 'A Beautiful Mind' - Nash.
|
| https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr.
| artimis wrote:
| 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.
| 0cf8612b2e1e wrote:
| 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 wrote:
| 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.
| abdullahkhalids wrote:
| 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 wrote:
| 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
| abdullahkhalids wrote:
| 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 wrote:
| 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
| abdullahkhalids wrote:
| I understand what the standard econ calculus based models
| are. I am a physicist, and we do the same thing where we
| were really good at modelling systems with small number
| of particles, or very large number of particles. For
| small, you can just enumerate all the options, and for
| large you take the limit to infinity [1], which yields
| calculus based models.
|
| But a lot of interesting real world systems operate in
| the intermediate scenario, and I know from physics how 1
| or infinity models can fail badly at describing the
| complexities of intermediate sized systems. In fact,
| there is a lot of work going on today in various branches
| of physics in this type of modelling and theory building,
| because we now have the computational power to understand
| such systems.
|
| What I am saying about economics are not my original
| thoughts. I have heard several mathematicians/economists
| talk about this briefly. I am just looking for the right
| reference to learn it properly.
| photonthug wrote:
| Rent-setting as you mention came to my mind immediately
| as well. Planet money has a good piece on a related topic
| https://www.npr.org/2023/02/06/1154775118/ice-cream-ben-
| jerr... .
|
| This stuff really opened my eyes to the idea that old-
| school conceptions of things like collusion, and even
| classic game theoretic ideas of perfect and complete
| information, all seem to need radical updates for the
| tightly connected and algorithmic times and economies
| that we live in.
|
| It seems almost unavoidable that all markets are
| generally going to move towards both complete and perfect
| information. We see that this is still somewhat
| asymmetric, because sellers are more organized because
| they have more capital, and they can generally afford to
| hold rather than sell whenever they don't like the
| market. But in the limit, buyers do catch up a bit,
| because at least they can browse lots of listings for
| stuff like housing. Meanwhile in the labor market, the
| (mostly American) taboo against discussing compensation
| with coworkers is slowly going away, and there's stuff
| like glassdoor, and laws that require stating some kind
| of range for compensation, etc. In terms of cards on the
| table, people generally can't keep secrets, since we need
| to account for practically every expense over 10k.
| Corporations might have an easier time in some cases, but
| large organizations leak, so I doubt whether they can
| really hide the fact that they are ramping up for a new
| chip factory or whatever. So getting a fair price for
| anything seems likely to get harder, and prices for
| everything go up.
|
| I'm not versed enough in the topics to really even
| articulate a good question here, but particularly with
| more things being algorithmically determined more of the
| time, perhaps open information is not as good for markets
| as we thought. Even the relatively straightforward
| classical idea of a monopoly is starting to feel dated,
| because if I can own only 10% of 10 key industries and
| use that to meltdown the whole economy because of the
| interconnectedness, then focusing on monopolies has
| little effect on market stability and consumer choice
| anyway.
|
| Back to the topic of collusion though, maybe the simplest
| thing is to remove the idea of intent when this stuff is
| getting litigated. Do we even _care_ that collusion
| should be some kind of conspiracy with intent? Or do we
| just dislike the effects and so we want it to never
| happen? Because in the future human "intent" is going to
| continue to disappear completely while everyone says
| "look, the computers decided". There's no cigar-smoking
| cabal planning stuff in dark rooms anymore because those
| guys are out golfing. No email chain with a smoking gun,
| because all that stuff is itself an inefficiency that
| profit-optimizing algorithms will increasingly be working
| around.
| jsemrau wrote:
| 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 wrote:
| 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
| cs702 wrote:
| 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
| hinkley wrote:
| 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.
| someguy101010 wrote:
| 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.
| eclark wrote:
| 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)
| t_mann wrote:
| 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 wrote:
| 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!
___________________________________________________________________
(page generated 2024-08-06 23:00 UTC)