ARC Colloquium: Ruta Mehta, IIT, Bombay

Abstract: Using the powerful machinery of the linear complementarity problem and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Fisher and Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case.

In 1975, Eaves had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave case. Our result settles his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.

We also prove that SPLC markets have an odd number of equilibria (up to scaling), hence matching the classical result of Shapley (1974), which was based on the Lemke-Howson algorithm and shows a similar fact about Nash equilibria of a 2-person bimatrix game.

 (This is joint work with Jugal Garg, Milind Sohoni and Vijay V. Vazirani.)


Event Details


  • Thursday, December 1, 2011
    3:30 pm
Location: Klaus 1116W, Georgia Tech, Atlanta GA

For More Information Contact

Elizabeth Ndongi