Computer Science/Discrete Mathematics Seminar I

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. These markets are computationally intensive, and this appears to be part of a much larger revolution in which algorithmic considerations are bound to have an impact. 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 within Algorithmic Game Theory. I will concentrate on the classical primal-dual paradigm which has yielded efficient, combinatorial algorithms for several market models. The primal-dual paradigm was given by Kuhn in 1955. This paradigm yielded exact algorithms (in the 1970's and 1980's) and approximation algorithms (in the 1990's) for numerous fundamental computational problems. Interestingly enough, the market equilibrium algorithms use this paradigm not in its usual setting of LP-duality theory but in the enhanced setting of KKT conditions and nonlinear convex programs.