SPEAKER: Vijay V. Vazirani

TIME: Wednesday 12-1pm, November 29, 2006

PLACE: NSH 1507

TITLE: New Market Models and Algorithms

ABSTRACT:
The notion of a ``market'' has undergone a paradigm shift with
the Internet -- totally new and highly successful markets
have been defined and launched by companies such as Google,
Yahoo!, Amazon, MSN and Ebay. Another major change is the
availability of massive computational power for running these 
markets in a centralized or distributed manner. 

In view of these new realities, the study of market equilibria,
an important, though essentially non-algorithmic, theory within 
Mathematical Economics, needs to be revived and rejuvenated with 
new models, ideas, and an inherently algorithmic approach. 

In this talk, I will give a feel for the exciting work going on 
on this front and present new results on resource allocation 
markets. Interestingly enough, this work has also contributed 
handsomely to the theory of algorithms itself. In particular, 
the highly successful primal-dual schema from exact and 
approximation algorithms, which was so far used for combinatorially 
solving special classes of linear programs, has been extended to 
solving nonlinear convex programs. 


This talk is meant for a general audience. 
It is based on the following three papers:

http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/adwords.pdf

http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/EG.pdf

http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/EG2.pdf