**Tuesday, 15:45 - 16:10 h, Room: MA 043**

**Jugal Garg**

A complementary pivot algorithm for markets under separable piecewise-linear concave utilities

**Coauthors: Ruta Mehta, Milind Sohoni, Vijay V. Vazirani**

**Abstract:**

Using the powerful machinery of the LCP and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case. As a corollary, we obtain the first elementary proof of existence of equilibrium for 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 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 in PPAD.

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

For the linear case, Eaves had asked for a combinatorial interpretation of his algorithm. We provide this and it yields a particularly simple proof of the fact that the set of equilibrium prices is convex.

Talk 2 of the invited session Tue.3.MA 043

**"New LCP-based market equilibrium algorithms"** [...]

Cluster 8

**"Game theory"** [...]