• This forum is specifically for the discussion of factual science and technology. When the topic moves to speculation, then it needs to also move to the parent forum, Science Fiction and Fantasy (SF/F).

    If the topic of a discussion becomes political, even remotely so, then it immediately does no longer belong here. Failure to comply with these simple and reasonable guidelines will result in one of the following.
    1. the thread will be moved to the appropriate forum
    2. the thread will be closed to further posts.
    3. the thread will remain, but the posts that deviate from the topic will be relocated or deleted.
    Thank you for understanding.​

Math: In Game Theory, No Clear Path to Equilibrium

Introversion

Pie aren't squared, pie are round!
Kind Benefactor
Super Member
Registered
Joined
Apr 17, 2013
Messages
10,642
Reaction score
14,865
Location
Massachusetts
John Nash’s notion of equilibrium is ubiquitous in economic theory, but a new study shows that it is often impossible to reach efficiently.

Quanta Magazine said:
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.

...