TY - GEN
T1 - Combinatorial Algorithms for General Linear Arrow-Debreu Markets
AU - Chaudhury, Bhaskar Ray
AU - Mehlhorn, Kurt
N1 - Publisher Copyright:
© Bhaskar Ray Chaudhury and Kurt Mehlhorn.
PY - 2018/12
Y1 - 2018/12
N2 - We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu markets consider the case where each agent can own all of one good only. We present an Õ((n+m)7 log3(UW)) algorithm where n, m, U and W refer to the number of agents, the number of goods, the maximal integral utility and the maximum quantity of any good in the market respectively. The algorithm refines the iterative algorithm of Duan, Garg and Mehlhorn using several new ideas. We also identify the hard instances for existing combinatorial algorithms for linear Arrow-Debreu markets. In particular we find instances where the ratio of the maximum to the minimum equilibrium price of a good is UΩ(n) and the number of iterations required by the existing iterative combinatorial algorithms of Duan, and Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the two algorithms.
AB - We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu markets consider the case where each agent can own all of one good only. We present an Õ((n+m)7 log3(UW)) algorithm where n, m, U and W refer to the number of agents, the number of goods, the maximal integral utility and the maximum quantity of any good in the market respectively. The algorithm refines the iterative algorithm of Duan, Garg and Mehlhorn using several new ideas. We also identify the hard instances for existing combinatorial algorithms for linear Arrow-Debreu markets. In particular we find instances where the ratio of the maximum to the minimum equilibrium price of a good is UΩ(n) and the number of iterations required by the existing iterative combinatorial algorithms of Duan, and Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the two algorithms.
KW - Combinatorial algorithms
KW - Equilibrium
KW - Linear exchange markets
UR - http://www.scopus.com/inward/record.url?scp=85079487888&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079487888&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2018.26
DO - 10.4230/LIPIcs.FSTTCS.2018.26
M3 - Conference contribution
AN - SCOPUS:85079487888
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
A2 - Ganguly, Sumit
A2 - Pandya, Paritosh
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
Y2 - 11 December 2018 through 13 December 2018
ER -