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


  There are three major facts that should be watched out for in all payday loans in the United States. The new drug with unique properties was developed to help men to get rid of all sexual disorders, and its name is Cialis Super Force. Now you do not have to buy two different medications to solve sexual problems.