New Market Models and Algorithms

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.

(The talk is self-contained and is meant for a general audience.)

Results on resource allocation markets are based on joint work with Kamal Jain:
http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/EG.pdf

and with Deeparnab Chakrabarty and Nikhil Devanur:
http://eccc.hpi-web.de/eccc-reports/2006/TR06-029/index.html