TY - GEN
T1 - On computability of equilibria in markets with production
AU - Garg, Jugal
AU - Vazirani, Vijay V.
PY - 2014
Y1 - 2014
N2 - Even though production is an integral part of the Arrow- Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. For markets with separable, piecewise-linear concave (SPLC) utilities and SPLC production, we obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria, and we further give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 [14]. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and odd- ness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm is practical. Also, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.
AB - Even though production is an integral part of the Arrow- Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. For markets with separable, piecewise-linear concave (SPLC) utilities and SPLC production, we obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria, and we further give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 [14]. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and odd- ness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm is practical. Also, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.
UR - http://www.scopus.com/inward/record.url?scp=84902094574&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902094574&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973402.98
DO - 10.1137/1.9781611973402.98
M3 - Conference contribution
AN - SCOPUS:84902094574
SN - 9781611973389
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1329
EP - 1340
BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PB - Association for Computing Machinery
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Y2 - 5 January 2014 through 7 January 2014
ER -