Communications of the ACM
What Computer Science Can Teach Economics
Some common game-theoretical problems are so hard to solve that they can't accurately represent what happens in the real world, says Constantinos Daskalakis, an assistant professor in MITs Computer Science and Artificial Intelligence Laboratory.
Credit: Satyen Kale / Yahoo! Research
Professor Constantinos Daskalakis in the Massachusetts Institute of Technology's Computer Science and Artificial Intelligence Laboratory is applying the theory of computational complexity to game theory. He argues that some common game-theoretical problems are so challenging that solving them would take the lifetime of the universe, and thus they fail to accurately represent what occurs in the real world.
In game theory a "game" represents any mathematical model that associates different player strategies with different results. Daskalakis' doctoral thesis disputes the assumption that finding the Nash equilibrium for every game will allow the system's behavior to be accurately modeled. In the case of economics, the system being modeled is the market.
Daskalakis' thesis illustrates that for some games, the Nash equilibrium is so difficult to calculate that all the world's computing resources could never find it in the universe's lifetime. In the real world, market rivals tend to calculate the strategies that will maximize their own outcomes given the current state of play, rather than work out the Nash equilibria for their specific games and then adopt the resulting tactics. However, if one player changes strategies, the other players will change strategies in response, driving the first player to shift strategies again, and so on until the feedback pathways eventually converge toward equilibrium. Daskalakis contends that feedback will not find the equilibrium faster than computers could calculate it.
From MIT News
View Full Article
Abstracts Copyright © 2009 Information Inc., Bethesda, Maryland, USA 
No entries found