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?
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.
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
