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