IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2506.02852.html
   My bibliography  Save this paper

Proportional Response Dynamics in Gross Substitutes Markets

Author

Listed:
  • Yun Kuen Cheung
  • Richard Cole
  • Yixin Tao

Abstract

Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and constant elasticity of substitution utilities. We propose a natural generalization of proportional response for gross substitutes utilities, and prove that it converges to competitive equilibria in Fisher markets. This is the first convergence result of a proportional response style dynamics in Fisher markets for utilities beyond the homogeneous utilities covered by the Eisenberg-Gale convex program. We show an empirical convergence rate of $O(1/T)$ for the prices. Furthermore, we show that the allocations of a lazy version of the generalized proportional response dynamics converge to competitive equilibria in Arrow-Debreu markets.

Suggested Citation

  • Yun Kuen Cheung & Richard Cole & Yixin Tao, 2025. "Proportional Response Dynamics in Gross Substitutes Markets," Papers 2506.02852, arXiv.org.
    • Handle: RePEc:arx:papers:2506.02852
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2506.02852
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. William C. Brainard & Herbert E. Scarf, 2005. "How to Compute Equilibrium Prices in 1891," American Journal of Economics and Sociology, Wiley Blackwell, vol. 64(1), pages 57-83, January.
    2. E. Eisenberg, 1961. "Aggregation of Utility Functions," Management Science, INFORMS, vol. 7(4), pages 337-350, July.
    3. Fisher, Franklin M., 1972. "Gross substitutes and the utility function," Journal of Economic Theory, Elsevier, vol. 4(1), pages 82-87, February.
    4. 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.
    5. Cheng, Yukun & Deng, Xiaotie & Li, Yuhao & Yan, Xiang, 2024. "Tight incentive analysis of Sybil attacks against the market equilibrium of resource exchange over general networks," Games and Economic Behavior, Elsevier, vol. 148(C), pages 566-610.
    6. Rahul Garg & Sanjiv Kapoor, 2006. "Auction Algorithms for Market Equilibrium," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 714-729, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nikhil Garg & Ashish Goel & Benjamin Plaut, 2021. "Markets for public decision-making," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 56(4), pages 755-801, May.
    2. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    3. Sandomirskiy, Fedor & Ushchev, Philip, 2024. "The geometry of consumer preference aggregation," CEPR Discussion Papers 19100, C.E.P.R. Discussion Papers.
    4. Denizalp Goktas & Jiayi Zhao & Amy Greenwald, 2023. "T\^atonnement in Homothetic Fisher Markets," Papers 2306.04890, arXiv.org, revised Feb 2025.
    5. Ashish Goel & Reyna Hulett & Benjamin Plaut, 2018. "Markets Beyond Nash Welfare for Leontief Utilities," Papers 1807.05293, arXiv.org, revised Dec 2019.
    6. Mehdi Ghiyasvand & James B. Orlin, 2012. "A Simple Approximation Algorithm for Computing Arrow-Debreu Prices," Operations Research, INFORMS, vol. 60(5), pages 1245-1248, October.
    7. Taheri Tehrani, Mohammad & Afshin Hemmatyar, Ali Mohammad, 2019. "Welfare-aware strategic demand control in an intelligent market-based framework: Move towards sustainable smart grid," Applied Energy, Elsevier, vol. 251(C), pages 1-1.
    8. Jain, Kamal & Vazirani, Vijay V., 2010. "Eisenberg-Gale markets: Algorithms and game-theoretic properties," Games and Economic Behavior, Elsevier, vol. 70(1), pages 84-106, September.
    9. Moshe Babaioff & Noam Nisan & Inbal Talgam-Cohen, 2021. "Competitive Equilibrium with Indivisible Goods and Generic Budgets," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 382-403, February.
    10. Cheung, Yun Kuen & Cole, Richard & Devanur, Nikhil R., 2020. "Tatonnement beyond gross substitutes? Gradient descent to the rescue," Games and Economic Behavior, Elsevier, vol. 123(C), pages 295-326.
    11. Luofeng Liao & Christian Kroer, 2024. "Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions," Papers 2406.15522, arXiv.org, revised Mar 2025.
    12. Thorsten Hens & Beate Pilgrim & Janos Mayer, "undated". "Existence of Sunspot Equilibria and Uniqueness of Spot Market Equilibria: The Case of Intrinsically Complete Markets," IEW - Working Papers 188, Institute for Empirical Research in Economics - University of Zurich.
    13. Lilia Maliar & Serguei Maliar, 2005. "An Analytical Construction Of Constantinides¿ Social Utility Function," Working Papers. Serie AD 2005-25, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    14. Edward E. Schlee, 2001. "The Value of Information in Efficient Risk-Sharing Arrangements," American Economic Review, American Economic Association, vol. 91(3), pages 509-524, June.
    15. James Moore, 2010. "On aggregation and welfare analysis," Review of Economic Design, Springer;Society for Economic Design, vol. 14(1), pages 95-129, March.
    16. Javier Hervés-Estévez & Emma Moreno-García, 2018. "A limit result on bargaining sets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(2), pages 327-341, August.
    17. Jun Tong & Jian-Qiang Hu & Jiaqiao Hu, 2017. "A Computational Algorithm for Equilibrium Asset Pricing Under Heterogeneous Information and Short-Sale Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-16, October.
    18. Bruno Codenotti & Kasturi Varadarajan, 2005. "Market Equilibrium in Exchange Economies with Some Families of Concave Utility Functions," Computational Economics 0503001, University Library of Munich, Germany.
    19. Gabriel P. Andrade & Rafael Frongillo & Elliot Gorokhovsky & Sharadha Srinivasan, 2021. "Graphical Economies with Resale," Papers 2106.14397, arXiv.org.
    20. Robert W. Dimand, 2019. "Léon Walras, Irving Fisher and the Cowles Approach to General Equilibrium Analysis," Cowles Foundation Discussion Papers 2205, Cowles Foundation for Research in Economics, Yale University.

    More about this item

    Statistics

    Access and download statistics

    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:arx:papers:2506.02852. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.