A strongly polynomial algorithm for linear exchange markets

Jugal Garg, László A. Végh

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

Abstract

We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly-polynomial Duan–Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges, i.e. pairs of agents and goods that must correspond to best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges, or if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Pages54-65
Number of pages12
ISBN (Electronic)9781450367059
DOIs
StatePublished - Jun 23 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States
CityPhoenix
Period6/23/196/26/19

Keywords

  • Linear Exchange Markets
  • Market Equilibria
  • Strongly Polynomial Algorithm
  • Z-Matrix

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A strongly polynomial algorithm for linear exchange markets'. Together they form a unique fingerprint.

  • Cite this

    Garg, J., & Végh, L. A. (2019). A strongly polynomial algorithm for linear exchange markets. In M. Charikar, & E. Cohen (Eds.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 54-65). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316340