[cs702]

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]

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]

> 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]

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.

[wunused]

> [b] There's a great intro lecture on this by Papadimitriou himself at https://www.youtube.com/watch?v=TUbfCY_8Dzs

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.

[cs702]

Well, that's embarrassing. I watched the lecture a long while ago, and somehow my puny little organic brain misremembered the lecturer.

Thank you for the correction.

And apologies to Daskalakis!

[TacticalCoder]

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