# Information Science and Technology Seminar

Tuesday
February 14, 2012
4:00 PM

**A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities**

**Speaker:**Vijay Vazirani, College of Computing, Georgia Tech

**Location:**Annenberg 105

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.<br><br>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 utilities. Our result settles the relevant subcase of 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.<br><br>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.<br><br>For the linear case, Eaves had asked for a combinatorial interpretation of his algorithm. We provide this and use it to get a particularly simple proof of the fact that the set of equilibrium prices is convex.<br><br>(This is joint work with Jugal Garg, Ruta Mehta and Milind Sohoni.)

**Series**Information Science and Technology Seminar

**Contact:** Sydney Garstang at x4555 sydney@caltech.edu