Finding Nash equilibria through simulation
coe.psu.ac.th
coe.psu.ac.th
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
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?
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.
Just a point of correction, this lecture is by Constantinos Daskalakis and not Christos Papadimitriou. Both were authors on the PPAD work that you refer to, however.
Thank you for the correction.
And apologies to Daskalakis!
Yeah: when the optimal solution for everybody involves picking decisions at random times, trying to find a closed formula can very quickly degenerate into madness even for very simple problems (where, say, the correct solution would happen to be, for each player "go left x% of the time, go right y% of the time, do nothing z% of the time"). Just Monte-Carlo the thing and find the Nash equilibrium that way.
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)
What are good references for this?
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.
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.
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.
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.
I once took a course that was mostly based on these two textbooks
- Noncooperative Game Theory: An introduction for Engineers and Computer Scientists (Hespanha)
- Population Games and Evolutionary Dynamics (Sandholm)
Not sure if they are the best place to start but they are definitely solid references that cover game theory (but not much econ). The first one is mostly an introduction to game theory, while the second one is more about what you called "multi-player multi-shot" earlier in this thread, though there is quite a bit of overlap between the two.
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.
I've used optimization of https://en.wikipedia.org/wiki/Lyapunov_function in my Bachelor thesis https://github.com/Artimi/neng to do that.
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