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: http://www.cc.gatech.edu/~vazirani/SPLC.pdf