Tuesday, 16:15 - 16:40 h, Room: MA 043


Ruta Mehta
LCP and Lemke-type algorithm for markets with production

Coauthors: Jugal Garg, Vijay V. Vazirani


Building on the works of Eaves and Garg, Mehta, Sohoni and Vazirani, we
obtain an LCP that captures exactly the set of equilibria for Arrow-Debreu
and Fisher markets with separable, piecewise-linear concave (SPLC)
utilities and SPLC production, and we also give a complementary pivot algorithm for finding an equilibrium. This answers a question asked by Eaves in 1975. As corollaries, we obtain a proof of PPAD-completeness, an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. Experiments show that our algorithm is practical.


Talk 3 of the invited session Tue.3.MA 043
"New LCP-based market equilibrium algorithms" [...]
Cluster 8
"Game theory" [...]


  Today, Payday Loans Ohio are legitimate, but there are illegal transactions that are still on the rise. In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.