IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v71y2023i2p487-505.html
   My bibliography  Save this article

A Strongly Polynomial Algorithm for Linear Exchange Markets

Author

Listed:
  • Jugal Garg

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801)

  • László A. Végh

    (Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom)

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—that is, pairs of agents and goods that must correspond to the 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.

Suggested Citation

  • Jugal Garg & László A. Végh, 2023. "A Strongly Polynomial Algorithm for Linear Exchange Markets," Operations Research, INFORMS, vol. 71(2), pages 487-505, March.
    • Handle: RePEc:inm:oropre:v:71:y:2023:i:2:p:487-505
    DOI: 10.1287/opre.2021.2258
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2021.2258
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2021.2258?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:71:y:2023:i:2:p:487-505. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.