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.
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.
> 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?
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.
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.
> So, as games get larger and more complex -- say, with rules and payoffs that evolve over time -- finding equilibria can become... intractable
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)
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.
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.
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.
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.
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.
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.
> 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.
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.
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.
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.
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.
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!
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.
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
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