An improved combinatorial polynomial algorithm for the linear arrow-debreu market

Ran Duan, Jugal Garg, Kurt Mehlhorn

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

Abstract

We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear ArrowDebreu model. For a market with n agents and integral utilities bounded by U, the algorithm runs in O(n7 log3(nU)) time. This improves upon the previously best algorithm of Ye by a factor of Ω(n). The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of Ω(n3). The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages90-106
Number of pages17
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Externally publishedYes
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume1

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'An improved combinatorial polynomial algorithm for the linear arrow-debreu market'. Together they form a unique fingerprint.

Cite this