Title:
Can Complexity Theory Ratify the “Invisible Hand of the Market”?
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.
Partial 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 latter question 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.)
Bio:
Vijay Vazirani got his Bachelor's degree from MIT in 1979, his Ph.D. from U.C. Berkeley in 1983, and is currently Professor of Computer Science at Georgia Tech. His research career has been centered around the design of algorithms, together with work on complexity theory, cryptography, coding theory, and game theory.
He is best known for his work on efficient matching algorithms (1980's), some fundamental complexity-theoretic results obtained using randomization (1980's), approximation algorithms for some basic NP-hard optimization problems (1990's), and efficient algorithms for computing market equilibria (current).
In 2001 he published what is widely viewed as the definitive book on approximation algorithms. The book has been translated into Japanese, French and Polish, and Persian and Chinese translations are forthcoming. In 2005 he initiated work on a comprehensive volume on algorithmic game theory; the co-edited volume appeared in 2007.
LOCATION:2405 Siebel Center UID:20091124T1647101@ece.uiuc.edu DTSTAMP:20091124T164710 CONTACT:Mark Faust CATEGORY:Lecture END:VEVENT END:VCALENDAR