Equilíbrio de Nash não pode ser alcançado

In 1950, John Nash — the mathematician later featured in the book and film “A Beautiful Mind” — wrote a two-page paper that transformed the theory of economics. His crucial, yet utterly simple, idea was that any competitive game has a notion of equilibrium: a collection of strategies, one for each player, such that no player can win more by unilaterally switching to a different strategy.

Nash’s equilibrium concept, which earned him a Nobel Prize in economics in 1994, offers a unified framework for understanding strategic behavior not only in economics but also in psychology, evolutionary biology and a host of other fields. Its influence on economic theory “is comparable to that of the discovery of the DNA double helix in the biological sciences,” wrote Roger Myerson of the University of Chicago, another economics Nobelist.


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. It’s “a very sweeping negative result,” Roughgarden said.

Economists often use Nash equilibrium analyses to justify proposed economic reforms, Myerson said. But the new result says that economists can’t assume that game players will get to a Nash equilibrium, unless they can justify what is special about the particular game in question. “If you’re trying to figure out if your game will easily find an equilibrium,” said Noam Nisan, a computer scientist at the Hebrew University, “it’s on you to provide the argument why it would be.”

[...]

“If this is going to take longer than the age of the universe,” said Sergiu Hart, a game theorist at the Hebrew University of Jerusalem, “it’s completely useless, of course.”

It might seem natural, almost obvious, that players will sometimes need to know everything about each other’s values to find a Nash equilibrium. The new paper shows, however, that this same limitation holds even if the players are willing to make do with an approximate Nash equilibrium — an important finding when it comes to real-world applications, in which an outcome that’s close to a Nash equilibrium is often good enough.

Fonte: aqui