Math Proof Shows Computers Can't Perfectly Predict Human Choices

Imagine trying to predict how two rivals will split a market, bid at an auction, or play a hand of poker. Mathematicians call the stable answer a "Nash equilibrium" — a mix of choices where nobody can do better by changing their strategy alone. For decades, researchers hunted for faster ways to find that balance point, because it underpins how we model markets, negotiations, and even security.

A new paper by Noah Golowich, posted to the research site arXiv, shows that hunt is basically over. He proves a shortcut published back in 2003 — the Lipton-Markakis-Mehta algorithm — is about as fast as any method can ever be. In other words, the math says no future breakthrough will make this dramatically quicker. The numbers are brutal: if each player has N options, the time needed explodes as the game grows, and that holds whenever you want a fairly accurate answer — exactly the situation in real markets and games.

The catch is that this isn't an absolute guarantee. The proof rests on two famous unproven conjectures about what computers can and cannot do — assumptions nearly all researchers believe, but nobody has proven. Until those are settled, the wall is "almost certainly there" rather than "definitely there." Golowich also answers a decade-old open question about "free games," a simplified model used in logic and physics research.

So what does it mean for you? Mostly this: when an app promises a perfect prediction of a complex competitive situation, be skeptical. Some problems aren't waiting for a smarter programmer — they're baked-in hard.