Tutte seminar - Vijay Vazirani

New (Practical) Complementary Pivot Algorithms for Market  Equilibria

Abstract:

Complementary pivot algorithms, in the style of the simplex algorithm, tend to work well in practice despite having an exponential worst case behavior -- a case in point being the classic Lemke-Howson algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives a direct proof of membership of the problem in the class PPAD and yields deep structural insights, such as oddness of the number of equilibria.

Our first result accomplishes all of the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise linear concave utilities. Our second result extends this to markets with production.

Based on the following paper, and a recent joint work with Jugal Garg and Ruta Mehta: A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities (PDF).