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 an inherently algorithmic approach. Such a theory should not only address traditional market models but also define new models for some of the new markets.
In this two-talk series, I will give a feel for the exciting work going on on this front. 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.
Both talks are self-contained; the first is meant for a general audience and will be the Princeton CS department colloquium on Wednesday, Oct 4. The second will be at the Princeton theory lunch on Friday, Oct 6: http://www.cs.princeton.edu/theory/index.php/Main/TheoryLunch
1). Resource Allocation Markets
This talk 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
2). Spending Constraint Utilities, with Applications to the Adwords Market
This talk is based on:
http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/spending.pdf
BIO: Vijay Vazirani got his Bachelor's degree in Computer Science from MIT in 1979 and his PhD from the University of California at Berkeley in 1983. The central theme in his research career has been the design of efficient algorithms. In addition, he has also worked on complexity theory, cryptography, coding theory and game theory. In 2001 he published what is widely regarded as the definitive book on Approximation Algorithms; this book has been translated into Japanese, Polish and French. He is currently involved in editing a comprehensive volume on Algorithmic Game Theory. He is a Fellow of the ACM.