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


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.