Combinatorial Algorithms for General Linear Arrow-Debreu Markets

Bhaskar Ray Chaudhury, Kurt Mehlhorn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
EditorsSumit Ganguly, Paritosh Pandya
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770934
DOIs
StatePublished - Dec 2018
Externally publishedYes
Event38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 - Ahmedabad, India
Duration: Dec 11 2018Dec 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume122
ISSN (Print)1868-8969

Conference

Conference38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
Country/TerritoryIndia
CityAhmedabad
Period12/11/1812/13/18

Keywords

  • Combinatorial algorithms
  • Equilibrium
  • Linear exchange markets

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Combinatorial Algorithms for General Linear Arrow-Debreu Markets'. Together they form a unique fingerprint.

Cite this