Vijay Vazirani colloquium, 12/01, 4pm
David Kempe
our next theory speaker will be Prof. Vijay Vazirani from Georgia Tech.
See below for title, abstract, bio, and all other relevant
information.
I'm looking forward to seeing many of you there.
Time: Tuesday, 12/01/2009, 4 PM - 5:30 PM
Location: SSL 150
Talk Title: Can Complexity Theory Ratify the "Invisible Hand of the Market"
Speaker: Prof. Vijay V. Vazirani, Georgia Tech
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.)
Speaker 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 algorithms for the classical maximum
matching problem (1980's), fundamental complexity-theoretic results obtained
using randomization (1980's), approximation algorithms for 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.
This 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.
--
David Kempe <dke...@usc.edu>