Title: A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
Speaker: Vijay Vazirani, Georgia Institute of Technology
The simplest way to describe our result is by analogy with the Lemke-Hawson complementary pivot algorithm for 2-player Nash equilibrium. This path-following algorithm gives a direct proof of membership of the problem in the class PPAD, and is a practical algorithm despite PPAD-completeness of the problem. It also yields deep structural insights, such as oddness of the number of equilibria.
Our algorithm accomplishes the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise-linear concave utilities. Our key steps are deriving an LCP that captures the set of equilibria of the market, and solving it using Lemke's algorithm; the latter involves showing that the polyhedron associated with the LCP has no secondary rays.
Our result answers an open problem of Eaves from 1975 and a recent open problem of Vazirani and Yannakakis.
Based on the following joint paper with Jugal Garg, Ruta Mehta and Milind Sohini: http://www.cc.gatech.edu/~vazirani/SPLC.pdf