Can Complexity Theory Ratify the Invisible Hand of the Market?
Vijay Vazirani
College of Computing
Georgia Tech
Wednesday, Feb 24, 2010
4:30 - 5:30 PM
Terman Engineering Center, Room 453
Abstract:
"It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no part of his intention."
--Adam Smith, 1776.
With his treatise, *The Wealth of Nations*, 1776, Adam Smith initiated the field of economics, and his famous quote provided this field with its central guiding principle. The pioneering work of Walras (1874) gave a mathematical formulation for this statement, using his notion of market equilibrium, and opened up the possibility of a formal ratification.
Mathematical ratification came with the celebrated Arrow-Debreu Theorem (1954), which established existence of equilibrium in a very general model of the economy; however, an efficient mechanism for finding an equilibrium has remained elusive.
The question of algorithmic ratification was taken up in the earnest within theoretical computer science a decade ago, and attention soon gravitated on markets under piecewise-linear, concave utility functions. As it turned out, the recent resolution of this open problem did not yield the hoped-for mechanism; however, it did mark the end of the road for the current approach. It is now time to step back and plan a fresh attack, using the powerful tools of modern complexity theory and algorithms.
After providing a summary of key developments through the ages and a gist of the recent results, we will discuss some ways of moving forward.
(Based in part on recent work with Mihalis Yannakakis.)
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html