Login
Talks & Seminars
How Intractable is the ``Invisible Hand'': Polynomial Time Algorithms for Market Equilibria
Vijay V. Vazirani, Georgia Tech University
Date & Time: January 7, 2003 11:30
Venue: CSE Seminar Hall
Abstract:
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. It has been customary to relegate such efficiency issues to the ``Invisible Hand'' of the market, a notion propounded by Adam Smith (Wealth of Nations, 1776). In the context of Algorithmic Game Theory, a nascent area attempting to address new issues arising from the Internet, we provide the first polynomial time algorithm for the linear version of a problem defined by Irving Fisher in 1891. Although the linear case provides an excellent starting point, it is too weak to capture some of the more attractive aspects of pricing mechanisms. To study algorithmic aspects associated with these, we define a new model which takes into consideration spending constraints among buyers, and extend the algorithmic ideas to it. Our algorithms are inspired by the primal-dual schema from combinatorial optimization. (First result joint with Devanur, Papadimitriou, and Saberi, and available at http://www.cc.gatech.edu/fac/Vijay.Vazirani) For queries about the talk, please contact sundar@cse.iitb.ac.in
Speaker Profile:
Vijay Vazirani is a Professor of CS at Georgia Tech. He currently works in the areas of Approximation Algorithms and Algorithmic Game Theory.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback