Events Calendar

CS Colloq: Dr. Vazirani

Speaker: Prof. Vijay V. Vazirani, Georgia Tech
Host: Prof. Shanghua Teng, Prof. David Kempe
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.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.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Front Desk