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, August.
    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. d'Aspremont, Claude & Dos Santos Ferreira, Rodolphe & Gerard-Varet, Louis-Andre, 1997. "General Equilibrium Concepts under Imperfect Competition: A Cournotian Approach," Journal of Economic Theory, Elsevier, vol. 73(1), pages 199-230, March.
    2. Dirk Bergemann & Alessandro Bonatti & Nicholas Wu, 2023. "Managed Campaigns and Data-Augmented Auctions for Digital Advertising," Cowles Foundation Discussion Papers 2359, Cowles Foundation for Research in Economics, Yale University.
    3. 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.
    4. Dimitrios Tsomocos, 2003. "Equilibrium analysis, banking, contagion and financial fragility," FMG Discussion Papers dp450, Financial Markets Group.
    5. 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.
    6. Georgios Piliouras & Ryann Sim & Stratis Skoulakis, 2021. "Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update," Papers 2111.14737, arXiv.org, revised Jun 2022.
    7. 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.
    8. Martin Shubik, 1980. "Perfect or Robust Noncooperative Equilibrium: A Search for the Philosophers Stone?," Cowles Foundation Discussion Papers 559, Cowles Foundation for Research in Economics, Yale University.
    9. Jean Gabszewicz & Giulio Codognato, 1991. "Équilibres de Cournot-Walras dans une économie d'échange," Revue Économique, Programme National Persée, vol. 42(6), pages 1013-1026.
    10. Martin Shubik, 1976. "Theory of Money and Financial Institutions. Part 34. A Multiperiod Trading Economy with Fiat Money, Bank Money and an Optimal Bankruptcy Rule," Cowles Foundation Discussion Papers 441, Cowles Foundation for Research in Economics, Yale University.
    11. 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.
    12. Dubey, Pradeep & Geanakoplos, John, 2003. "Monetary equilibrium with missing markets," Journal of Mathematical Economics, Elsevier, vol. 39(5-6), pages 585-618, July.
    13. Germano, Fabrizio, 2003. "Bertrand-edgeworth equilibria in finite exchange economies," Journal of Mathematical Economics, Elsevier, vol. 39(5-6), pages 677-692, July.
    14. Dubey, Pradeep & Sahi, Siddharta & Shubik, Martin, 1993. "Repeated trade and the velocity of money," Journal of Mathematical Economics, Elsevier, vol. 22(2), pages 125-137.
    15. Luofeng Liao & Christian Kroer, 2024. "Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions," Papers 2406.15522, arXiv.org, revised Aug 2024.
    16. 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.
    17. 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.
    18. Gersbach, Hans & Zelzner, Sebastian, 2022. "Why Bank Money Creation?," CEPR Discussion Papers 17753, C.E.P.R. Discussion Papers.
    19. Sjur Didrik Flåm, 2013. "Reaching Market Equilibrium Merely by Bilateral Barters," CESifo Working Paper Series 4504, CESifo.
    20. Codognato, Giulio, 2000. "Cournot-Nash Equilibria in Limit Exchange Economies with Complete Markets: A Comparison between Two Models," Games and Economic Behavior, Elsevier, vol. 31(1), pages 136-146, April.

    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.