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

Asynchronous Proportional Response Dynamics in Markets with Adversarial Scheduling

Author

Listed:
  • Yoav Kolumbus
  • Menahem Levy
  • Noam Nisan

Abstract

We study Proportional Response Dynamics (PRD) in linear Fisher markets where participants act asynchronously. We model this scenario as a sequential process in which in every step, an adversary selects a subset of the players that will update their bids, subject to liveness constraints. We show that if every bidder individually uses the PRD update rule whenever they are included in the group of bidders selected by the adversary, then (in the generic case) the entire dynamic converges to a competitive equilibrium of the market. Our proof technique uncovers further properties of linear Fisher markets, such as the uniqueness of the equilibrium for generic parameters and the convergence of associated best-response dynamics and no-swap regret dynamics under certain conditions.

Suggested Citation

  • Yoav Kolumbus & Menahem Levy & Noam Nisan, 2023. "Asynchronous Proportional Response Dynamics in Markets with Adversarial Scheduling," Papers 2307.04108, arXiv.org, revised Jan 2024.
    • Handle: RePEc:arx:papers:2307.04108
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Shapley, Lloyd S & Shubik, Martin, 1977. "Trade Using One Commodity as a Means of Payment," Journal of Political Economy, University of Chicago Press, vol. 85(5), pages 937-968, October.
    2. Santiago R. Balseiro & Yonatan Gur, 2019. "Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium," Management Science, INFORMS, vol. 65(9), pages 3952-3968, September.
    3. J. M. Bonnisseau & M. Florig & A. Jofré, 2001. "Continuity and Uniqueness of Equilibria for Linear Exchange Economies," Journal of Optimization Theory and Applications, Springer, vol. 109(2), pages 237-263, May.
    4. Dvijotham, Krishnamurthy & Rabani, Yuval & Schulman, Leonard J., 2022. "Convergence of incentive-driven dynamics in Fisher markets," Games and Economic Behavior, Elsevier, vol. 134(C), pages 361-375.
    5. Sergiu Hart & Andreu Mas-Colell, 2013. "Simple Adaptive Strategies:From Regret-Matching to Uncoupled Dynamics," World Scientific Books, World Scientific Publishing Co. Pte. Ltd., number 8408, April.
    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. David Easley & Yoav Kolumbus & Eva Tardos, 2025. "Learning in Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners," Papers 2502.08597, arXiv.org.
    2. Meirowitz, Adam, 2005. "Deliberative Democracy or Market Democracy: Designing Institutions to Aggregate Preferences and Information," Papers 03-28-2005, Princeton University, Research Program in Political Economy.
    3. Dimitrios Tsomocos, 2003. "Equilibrium analysis, banking, contagion and financial fragility," FMG Discussion Papers dp450, Financial Markets Group.
    4. Menzio, Guido & Shi, Shouyong & Sun, Hongfei, 2013. "A monetary theory with non-degenerate distributions," Journal of Economic Theory, Elsevier, vol. 148(6), pages 2266-2312.
    5. Andrés Carvajal, 2018. "Arbitrage pricing in non-Walrasian financial markets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(4), pages 951-978, December.
    6. Toraubally, Waseem A., 2018. "Large market games, the law of one price, and market structure," Journal of Mathematical Economics, Elsevier, vol. 78(C), pages 13-26.
    7. Germano, Fabrizio, 2003. "Bertrand-edgeworth equilibria in finite exchange economies," Journal of Mathematical Economics, Elsevier, vol. 39(5-6), pages 677-692, July.
    8. Igor V. EVSTIGNEEVY & Thorsten HENS & Klaus Reiner SCHENK-HOPPE, 2010. "An evolutionary financial market model with a risk-free asset," Swiss Finance Institute Research Paper Series 10-36, Swiss Finance Institute.
    9. Amir, Rabah & Bloch, Francis, 2009. "Comparative statics in a simple class of strategic market games," Games and Economic Behavior, Elsevier, vol. 65(1), pages 7-24, January.
    10. Sjur Didrik Flåm, 2013. "Reaching Market Equilibrium Merely by Bilateral Barters," CESifo Working Paper Series 4504, CESifo.
    11. Munetomo Ando & Daisuke Oyama, 2002. "A model of a spatial economy with trading posts," Economics Bulletin, AccessEcon, vol. 18(1), pages 1-11.
    12. Ludovic A. Julien, 2017. "Hierarchical Competition and Heterogeneous Behavior in Noncooperative Oligopoly Markets," Post-Print hal-01637298, HAL.
    13. Yiding Feng & Brendan Lucier & Aleksandrs Slivkins, 2023. "Strategic Budget Selection in a Competitive Autobidding World," Papers 2307.07374, arXiv.org, revised Nov 2023.
    14. Bloch, Francis & Ghosal, Sayantan, 1997. "Stable Trading Structures in Bilateral Oligopolies," Journal of Economic Theory, Elsevier, vol. 74(2), pages 368-384, June.
    15. Shikhman, V. & Nesterov, Yu. & Ginsburgh, V., 2018. "Power method tâtonnements for Cobb–Douglas economies," Journal of Mathematical Economics, Elsevier, vol. 75(C), pages 84-92.
    16. Nikolas Tsakas & Dimitrios Xefteris & Nicholas Ziros, 2021. "Vote Trading in Power-Sharing Systems: A Laboratory Investigation," The Economic Journal, Royal Economic Society, vol. 131(636), pages 1849-1882.
    17. Jason Milionis & Christos Papadimitriou & Georgios Piliouras & Kelly Spendlove, 2022. "Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics," Papers 2203.14129, arXiv.org.
    18. 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.
    19. Pradeep Dubey & Martin Shubik, 1975. "A Theory of Money and Financial Institutions. Part 24. Trade and Prices in a Closed Economy with Exogenous Uncertainty, Different Levels of Information, Money and No Futures Markets," Cowles Foundation Discussion Papers 410R, Cowles Foundation for Research in Economics, Yale University.
    20. Barthélemy, Jean & Mengus, Eric & Plantin, Guillaume, 2024. "The central bank, the treasury, or the market: Which one determines the price level?," Journal of Economic Theory, Elsevier, vol. 220(C).

    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:2307.04108. 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.