TY - GEN

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

AU - Garg, Jugal

AU - Mehta, Ruta

AU - Sohoni, Milind

AU - Vazirani, Vijay V.

PY - 2012

Y1 - 2012

N2 - Using the powerful machinery of the linear complementarity problem 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 therst elementary proof of existence of equilibrium for this case, i.e., without using fixed point theorems. In 1975, Eaves [10] 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. 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 [24], which was based on the 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.

AB - Using the powerful machinery of the linear complementarity problem 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 therst elementary proof of existence of equilibrium for this case, i.e., without using fixed point theorems. In 1975, Eaves [10] 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. 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 [24], which was based on the 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.

KW - piecewise-linear concave utilities

KW - separable

UR - http://www.scopus.com/inward/record.url?scp=84862604976&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862604976&partnerID=8YFLogxK

U2 - 10.1145/2213977.2214068

DO - 10.1145/2213977.2214068

M3 - Conference contribution

AN - SCOPUS:84862604976

SN - 9781450312455

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1003

EP - 1015

BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing

T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12

Y2 - 19 May 2012 through 22 May 2012

ER -