Chaudhury, Bhaskar Ray ;
Mehlhorn, Kurt
Combinatorial Algorithms for General Linear ArrowDebreu Markets
Abstract
We present a combinatorial algorithm for determining the market clearing prices of a general linear ArrowDebreu market, where every agent can own multiple goods. The existing combinatorial algorithms for linear ArrowDebreu markets consider the case where each agent can own all of one good only. We present an O~((n+m)^7 log^3(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 ArrowDebreu markets. In particular we find instances where the ratio of the maximum to the minimum equilibrium price of a good is U^{Omega(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.
BibTeX  Entry
@InProceedings{chaudhury_et_al:LIPIcs:2018:9925,
author = {Bhaskar Ray Chaudhury and Kurt Mehlhorn},
title = {{Combinatorial Algorithms for General Linear ArrowDebreu Markets}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {26:126:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770934},
ISSN = {18688969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9925},
URN = {urn:nbn:de:0030drops99255},
doi = {10.4230/LIPIcs.FSTTCS.2018.26},
annote = {Keywords: Linear Exchange Markets, Equilibrium, Combinatorial Algorithms}
}
2018
Keywords: 

Linear Exchange Markets, Equilibrium, Combinatorial Algorithms 
Seminar: 

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Issue date: 

2018 
Date of publication: 

2018 