When John Nash won the Nobel Prize in economics in 1994 for his contribution to game theory, it was for an elegant theorem. Nash had shown that in any situation where two or more people were competing, there would always be an equilibrium state in which no player could do better than he was already doing. That theorem has since been used to model all sorts of competitive systems, from markets to nuclear strategy to living creatures competing for finite resources.
“In some sense, it started not just game theory, but also modern economics,” says Christos Papadimitriou, a professor of computer science at Columbia University. Nash’s idea gave economists the ability to create hypotheses about market design, for instance. They could now ask what happened when a market reached equilibrium.
Nash’s theorem is also an essential component of game theory, which had first been developed by computing pioneer John von Neumann. “Games are a mathematical thought experiment and we study them just because we want to understand how strategic rational players would behave in situations of conflict,” Papadimitriou says. “And that’s important because all of society is full of such situations.”
Though Nash proved that at least one such Nash equilibrium existed for all games, what he did not do was predict how an equilibrium might be reached in a given situation. Was there, scientists wanted to know, an algorithm that would show players how to efficiently reach an equilibrium? After more than 65 years of researchers’ studying that question, the answer turns out to be no, there is not. That means economists had better start rethinking some of their models.
An Intractable Problem
“This is something important and consequential,” says Papadimitriou. “It undermines the widespread use of Nash equilibrium as the natural condition, what will happen in a game.”
It is not that Nash equilibria do not exist; they do. In some types of games, players converge on an equilibrium very quickly; in others, however, the result is out of reach. It might be calculated, but it would take longer to arrive at than the whole lifetime of the universe. “If even the fastest computers in the world cannot compute equilibrium, how would you expect a bunch of people—the market, a group of people—to do it?” Papadimitriou asks.
Nash’s theorem says that in a non-cooperative game with a finite number of players, each of whom has a finite number of possible moves called “strategies,” there exists a way for players to randomly choose strategies until they reach a point where there is no alternate strategy a player can use to improve his results. “Everyone’s as happy as can be with what they’re doing, given that everyone else is doing what they’re doing,” says Tim Roughgarden, a professor of computer science at Stanford University.
Take the game rock, paper, scissors, for example. If player A is playing rock more often, player B can beat him by playing paper more often. When player A notices that, he will switch to playing scissors more often, which will in turn cause player B to switch to playing rock. If, however, each player randomly makes each of the three moves a third of the time, they will both start winning in equal proportions, and neither will want to change what he is doing because it will not improve his odds.
In zero-sum games, where one person loses what the other wins, there is a natural process by which play converges to equilibrium, Roughgarden says. Each player knows his own set of strategies, and he knows what the other player has done in the past. By randomly choosing strategies, with a bias toward strategies that have worked well in the past, the players quickly find an approximate equilibrium, where a player would have very little incentive to do something different. The number of moves the players have to make to get there is a logarithm of their number of strategies. “If you and I each have a million strategies, we’re not going to have to play a million times to reach an approximate Nash equilibrium; we’re each going to have to play maybe 100 times,” he says.
The next logical question is what happens when the same algorithm is applied to a game that is not zero-sum? There, it turns out, the players can reach a weaker type of equilibrium. Perhaps, though, a different algorithm might work better. “It was not known whether or not there could be learning algorithms of this form which over just a sublinear number of steps could reach a Nash equilibrium,” says Roughgarden.
Even by inferring the motivations of other players from their moves, there is no way to compute even an approximate Nash equilibrium in polynomial time.
Papadimitriou, along with Costis Daskalakis of the Massachusetts Institute of Technology and Paul Goldberg of Oxford University, had shown in 2007 that for a class of games in which all players knew the payoff for each other, there is no polynomial-time algorithm for computing a Nash equilibrium under standard complexity assumptions. “If everybody knows the game, there is no way to compute a Nash equilibrium in the lifetime of the universe, if the world’s as complex as we think it is,” Papadimitriou says.
Aviad Rubinstein, a Ph.D. candidate under Papadimitriou, looked at what happened in situations where players do not know what benefits other players might get out of the game, making it more difficult to predict the other players’ strategies. Again, he found there was no way to compute the results in polynomial time, where the time it takes a computer to solve a problem grows as a polynomial function of the problem’s size.
Three Strikes
Rubinstein and Yakov Babichenko, a professor of economics at Technion, the Israel Institute of Technology, showed that even by inferring the motivations of other players from their moves, there was no way to compute even an approximate Nash equilibrium in polynomial time. Players would have to see most of the possible moves to infer motivation. It might work, but it would take too long.
The three results are essentially three strikes against the utility of the Nash equilibrium, Papadimitriou says. “Together they tell us a very consistent story, that the Nash equilibrium has very serious credibility problems as the right concept for game theory.”
Rubinstein, who earned his Ph.D. last year and is now a post-doctoral fellow at Harvard University, says there has long been a discussion about how relevant Nash’s theorem is to economics, because no one knows how to reach an equilibrium. Further, while an algorithm—if one could be found—would be seeking equilibrium, that is not what real players are out to achieve. “Real selfish players, they’re not trying to find equilibrium; they’re trying to maximize their payoff,” Rubinstein says. “If there’s no specially designed algorithm that finds an equilibrium, it’s even less likely that selfish players will somehow magically converge to an equilibrium.”
There are still open questions. Nash equilibria are a subset of a broader category of correlated equilibria. In a correlated equilibrium, both players have access to some public information that informs their moves. Rough-garden uses a traffic light as an example; if one driver approaching an intersection sees the light in his direction is green, he can assume the driver coming down the cross-street will see a red light, so he can base his decision to keep going on the knowledge that the other driver is being signaled to stop.
Rubinstein says that, although he and Bobichenko proved that finding Nash equilibria is hard, no one knows if the same is true for correlated equilibria. The Nash equilibrium problem is an issue of communication complexity; to calculate the equilibrium, the players would have to communicate almost everything about their strategies, and as the game gets larger, that would take practically forever. Perhaps, though, it is easier for correlated equilibria.
Because the set of correlated equilibria is larger, it should be easier to find one. “If you want to find a needle in a haystack, it’s hard, but if you have lots of needles it might become easy,” says Karthik C.S., a Ph.D. student at Weizmann Institute of Science in Israel. He and fellow student Anat Ganor presented a paper last year that looked at the difficulty of finding an approximate correlated equilibrium. “What we show in our paper is that for small approximation values, it’s not any easier,” Karthik says.
Even though Bobichenko’s and Rubinstein’s result is in some sense negative—they prove there is no easy way to find Nash equilibria—the theorists do not see that as a necessarily bad thing. “It says what you can’t hope to do and it guides you to directions that are going to be fruitful,” Roughgarden says. “Without that theory, you might waste an enormous amount of time trying to find efficient algorithms when people don’t think they exist.” Now researchers can focus on finding special cases where algorithms might work, as in zero-sum games, or look for ways to compromise on the results they can expect.
Economists will have to find some other basis on which to model markets, Rubinstein says. “It means you should be really careful about how you model selfish players,” he says. “For some problems, Nash equilibrium is just not the right model. We should find better models.”
Papadimitriou says he and other scientists are already looking for better ideas as to what economists should use in their models. He is delighted that this line of inquiry produced such solid results, and says computational theorists should be proud that it came from their field. “I started working on this in 1983, 35 years ago,” he says. “I thought this was one of these problems that we would never see solved.”
Further Reading
Babichenko. Y. and Rubinstein, A.
Communication complexity of approximate Nash equilibria, arXiv, 2016. https://arxiv.org/abs/1608.06580
Papadimitriou, C.H. and Roughgarden, T.
Computing Correlated Equilibria in Multi-Player Games, Journal of the ACM, July 2008 https://dl.acm.org/citation.cfm?id=1379762
Ganor, A. and C.S., Karthik
Communication Complexity of Correlated Equilibrium in Two-Player Games, Electronic Colloquium on Computational Complexity, 2017. https://arxiv.org/abs/1704.01104
Myerson, R.B.
Nash Equilibrium and the History of Economic Theory, Journal of Economic Theory, 37, 1999. https://www.aeaweb.org/articles?id=10.1257/jel.37.3.1067
Rubinstein, A.
Communication complexity of approximate Nash equilibria Institute for Advanced Study https://www.youtube.com/watch?v=hRV9chspWI0
Join the Discussion (0)
Become a Member or Sign In to Post a Comment