Erica Klarreich in Quartz:
When players are at equilibrium, no one has a reason to stray. But how do players get to equilibrium in the first place? In contrast with, say, a ball rolling downhill and coming to rest in a valley, there is no obvious force guiding game players toward a Nash equilibrium.
“It has always been a thorn in the side of microeconomists,” said Tim Roughgarden, a theoretical computer scientist at Stanford University. “They use these equilibrium concepts, and they’re analyzing them as if people will be at equilibrium, but there isn’t always a satisfying explanation of why people will be at Nash equilibrium as opposed to just groping around for one.”
If people play a game only once, it is often unreasonable to expect them to find an equilibrium. This is especially the case if — as is typical in the real world — each player knows only how much she herself values the game’s different outcomes, and not how much her fellow players do. But if people can play repeatedly, perhaps they could learn from the early rounds and rapidly steer themselves toward an equilibrium. Yet attempts to find such efficient learning methods have always come up dry.
“Economists have proposed mechanisms for how you can converge [quickly] to equilibrium,” said Aviad Rubinstein, who is finishing a doctorate in theoretical computer science at the University of California, Berkeley. But for each such mechanism, he said, “there are simple games you can construct where it doesn’t work.”
Now, Rubinstein and Yakov Babichenko, a mathematician at the Technion-Israel Institute of Technology in Haifa, have explained why. In a paper posted online last September, they proved that no method of adapting strategies in response to previous games — no matter how commonsensical, creative or clever — will converge efficiently to even an approximate Nash equilibrium for every possible game.
More here.