Why We Can’t Always Reach Nash Equilibrium Efficiently
We all know that John Nash’s economic findings on equilibrium in game theory revolutionized economics and won him the Nobel Prize. While there is no doubt that Nash’s contributions to economic theory were groundbreaking, the article I found demonstrates how attaining Nash Equilibrium efficiently is often impossible in practice. Professor Tim Roughgarden from Stanford University mentions how micro economists always assume that people reach equilibrium, “but there isn’t always a satisfying explanation of why [they] will be at Nash equilibrium as opposed to just groping around for one.” Additionally, the article explains how mathematicians and computer scientists — such as Aviad Rubenstein and Yakov Babichenko — have proven that no collection of adapting strategies responding to previous games, regardless of their creativity, will “converge efficiently to even an approximate Nash equilibrium for every possible game.” Everyone seems to agree that this is a negative result, but important to explain clearly. And it makes sense because while Nash proved that an equilibrium existed for a game with any number of players (say 100), he never showed how to calculate such an equilibrium, which only solidifies the proof that some scenarios may never realistically reach Nash Equilibrium; it may only live in theory.
I mainly chose this article because it provided insight into a question that I had never really pondered. In class, we learned how to calculate Nash Equilibrium, but we were ultimately dealing with simple payoff matrices that were easy to calculate by hand or by inspection. But, thinking about how to calculate an equilibrium for hundreds or thousands of players seems almost impossible (at least efficiently that is). Additionally, we always like to connect our material in networks to the real world. While we can clearly see some industries attaining Nash Equilibrium, we realize that these industries have a relatively small number of players. Thus, I found it extremely eye-opening that professors have proven how efficiently reaching Nash Equilibrium is sometimes actually impossible. I truly gained a lot of new information from reading this article’s perspective and findings, and it made the whole idea of Nash Equilibrium that much more interesting.
https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/