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


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" [...]


  Most online loan lenders allow getting Payday Loans New Jersey without visiting a bank, straight to your bank account. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.