BEGIN:VCALENDAR PRODID:-//University of Illinois//Web Services Calendar//EN VERSION:2.0 CALSCALE:GREGORIAN BEGIN:VEVENT DTSTAMP:20120214T133740Z DTSTART;TZID=America/Chicago:20091109T120000 DTEND;TZID=America/Chicago:20091109T120000 SUMMARY:Professor Vijay Vazirani of Georgia Tech CREATED:20091102T130000Z DESCRIPTION:Title: Can Complexity Theory Ratify the Invisible Hand of the Market? Abs tract: It is not from the benevolence of the bu tcher\, 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 Nat ions\, 1776\, Adam Smith initiated the field of economics\, and his famo us quote provided this field with its central guiding principle. The pio neering work of Walras (1874) gave a mathematical formulation for this s tatement\, using his notion of market equilibrium\, and opened up the po ssibility of a formal ratification. Partial ratification came with the c elebrated Arrow-Debreu Theorem (1954)\, which established existence of e quilibrium in a very general model of the economy\; however\, an efficie nt mechanism for finding an equilibrium has remained elusive. The latter question was taken up in the earnest within theoretical computer scienc e a decade ago\, and attention soon gravitated on markets under piecewis e-linear\, concave utility functions. As it turned out\, the recent reso lution of this open problem did not yield the hoped-for mechanism\; howe ver\, it did mark the end of the road for the current approach. It is no w time to step back and plan a fresh attack\, using the powerful tools o f modern complexity theory and algorithms.After providing a summary of k ey developments through the ages and a gist of the recent results\, we w ill discuss some ways of moving forward. (Based in part on recent work w ith Mihalis Yannakakis.)Bio: Vijay Vazirani got his Bachelor's degree from MIT in 1979\, his Ph.D. from U.C. Berkeley i n 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 a lgorithms (1980's)\, some fundamental complexity-theoretic results obtai ned using randomization (1980's)\, approximation algorithms for some bas ic NP-hard optimization problems (1990's)\, and efficient algorithms for computing market equilibria (current). In 2001 he published what is wid ely 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 com prehensive volume on algorithmic game theory\; the co-edited volume appe ared in 2007. LAST-MODIFIED:20091102T130000Z LOCATION:2405 Siebel Center CATEGORIES:Lecture CONTACT:Mark Faust ORGANIZER:mfaust@illinois.edu URL:http://illinois.edu/calendar/detail/2654?key=2000010120000101147109 UID:147109@illinois.edu END:VEVENT END:VCALENDAR