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

Online Market Equilibrium with Application to Fair Division

Author

Listed:
  • Yuan Gao
  • Christian Kroer
  • Alex Peysakhovich

Abstract

Computing market equilibria is a problem of both theoretical and applied interest. Much research to date focuses on the case of static Fisher markets with full information on buyers' utility functions and item supplies. Motivated by real-world markets, we consider an online setting: individuals have linear, additive utility functions; items arrive sequentially and must be allocated and priced irrevocably. We define the notion of an online market equilibrium in such a market as time-indexed allocations and prices which guarantee buyer optimality and market clearance in hindsight. We propose a simple, scalable and interpretable allocation and pricing dynamics termed as PACE. When items are drawn i.i.d. from an unknown distribution (with a possibly continuous support), we show that PACE leads to an online market equilibrium asymptotically. In particular, PACE ensures that buyers' time-averaged utilities converge to the equilibrium utilities w.r.t. a static market with item supplies being the unknown distribution and that buyers' time-averaged expenditures converge to their per-period budget. Hence, many desirable properties of market equilibrium-based fair division such as no envy, Pareto optimality, and the proportional-share guarantee are also attained asymptotically in the online setting. Next, we extend the dynamics to handle quasilinear buyer utilities, which gives the first online algorithm for computing first-price pacing equilibria. Finally, numerical experiments on real and synthetic datasets show that the dynamics converges quickly under various metrics.

Suggested Citation

  • Yuan Gao & Christian Kroer & Alex Peysakhovich, 2021. "Online Market Equilibrium with Application to Fair Division," Papers 2103.12936, arXiv.org, revised Oct 2021.
    • Handle: RePEc:arx:papers:2103.12936
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. E. Eisenberg, 1961. "Aggregation of Utility Functions," Management Science, INFORMS, vol. 7(4), pages 337-350, July.
    2. Arnsperger, Christian, 1994. "Envy-Freeness and Distributive Justice," Journal of Economic Surveys, Wiley Blackwell, vol. 8(2), pages 155-186, June.
    3. Kantorovich, Leonid V, 1989. "Mathematics in Economics: Achievements, Difficulties, Perspectives," American Economic Review, American Economic Association, vol. 79(6), pages 18-22, December.
    4. Yurii Nesterov & Vladimir Shikhman, 2018. "Computation of Fisher-Gale equilibrium by auction," LIDAM Reprints CORE 2972, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Varian, Hal R., 1974. "Equity, envy, and efficiency," Journal of Economic Theory, Elsevier, vol. 9(1), pages 63-91, September.
    6. Santiago R. Balseiro & Omar Besbes & Gabriel Y. Weintraub, 2015. "Repeated Auctions with Budgets in Ad Exchanges: Approximations and Design," Management Science, INFORMS, vol. 61(4), pages 864-884, April.
    7. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    8. Herbert E. Scarf, 1967. "On the Computation of Equilibrium Prices," Cowles Foundation Discussion Papers 232, Cowles Foundation for Research in Economics, Yale University.
    9. 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.
    10. Christian Kroer & Alexander Peysakhovich, 2019. "Scalable Fair Division for 'At Most One' Preferences," Papers 1909.10925, arXiv.org.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Luofeng Liao & Christian Kroer, 2023. "Statistical Inference and A/B Testing for First-Price Pacing Equilibria," Papers 2301.02276, arXiv.org, revised Jun 2023.
    2. Devansh Jalota & Yinyu Ye, 2022. "Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements," Papers 2205.00825, arXiv.org, revised Jan 2023.
    3. Luofeng Liao & Christian Kroer & Sergei Leonenkov & Okke Schrijvers & Liang Shi & Nicolas Stier-Moses & Congshan Zhang, 2024. "Interference Among First-Price Pacing Equilibria: A Bias and Variance Analysis," Papers 2402.07322, arXiv.org.
    4. Luofeng Liao & Yuan Gao & Christian Kroer, 2022. "Statistical Inference for Fisher Market Equilibrium," Papers 2209.15422, arXiv.org.

    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. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    2. Luofeng Liao & Yuan Gao & Christian Kroer, 2022. "Statistical Inference for Fisher Market Equilibrium," Papers 2209.15422, arXiv.org.
    3. Vincent Conitzer & Christian Kroer & Debmalya Panigrahi & Okke Schrijvers & Nicolas E. Stier-Moses & Eric Sodomka & Christopher A. Wilkens, 2022. "Pacing Equilibrium in First Price Auction Markets," Management Science, INFORMS, vol. 68(12), pages 8515-8535, December.
    4. Yuan Gao & Christian Kroer, 2020. "Infinite-Dimensional Fisher Markets and Tractable Fair Division," Papers 2010.03025, arXiv.org, revised Apr 2021.
    5. 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.
    6. 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.
    7. Erdmann, Anett & Arilla, Ramón & Ponzoa, José M., 2022. "Search engine optimization: The long-term strategy of keyword choice," Journal of Business Research, Elsevier, vol. 144(C), pages 650-662.
    8. Cole, Richard & Tao, Yixin, 2021. "On the existence of Pareto Efficient and envy-free allocations," Journal of Economic Theory, Elsevier, vol. 193(C).
    9. Jalota, Devansh & Pavone, Marco & Qi, Qi & Ye, Yinyu, 2023. "Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms," Games and Economic Behavior, Elsevier, vol. 141(C), pages 223-260.
    10. Mengzhou Zhuang & Eric (Er) Fang & Jongkuk Lee & Xiaoling Li, 2021. "The Effects of Price Rank on Clicks and Conversions in Product List Advertising on Online Retail Platforms," Information Systems Research, INFORMS, vol. 32(4), pages 1412-1430, December.
    11. Yukihiro Nishimura, 2008. "Envy Minimization In The Optimal Tax Context," Working Paper 1178, Economics Department, Queen's University.
    12. Paul Oslington, 2012. "General Equilibrium: Theory and Evidence," The Economic Record, The Economic Society of Australia, vol. 88(282), pages 446-448, September.
    13. Hana Choi & Carl F. Mela & Santiago R. Balseiro & Adam Leary, 2020. "Online Display Advertising Markets: A Literature Review and Future Directions," Information Systems Research, INFORMS, vol. 31(2), pages 556-575, June.
    14. Suksompong, Warut, 2018. "Approximate maximin shares for groups of agents," Mathematical Social Sciences, Elsevier, vol. 92(C), pages 40-47.
    15. Zikun Ye & Dennis J. Zhang & Heng Zhang & Renyu Zhang & Xin Chen & Zhiwei Xu, 2023. "Cold Start to Improve Market Thickness on Online Advertising Platforms: Data-Driven Algorithms and Field Experiments," Management Science, INFORMS, vol. 69(7), pages 3838-3860, July.
    16. He, Yinghua & Li, Sanxi & Yan, Jianye, 2015. "Evaluating assignment without transfers: A market perspective," Economics Letters, Elsevier, vol. 133(C), pages 40-44.
    17. Ashish Goel & Reyna Hulett & Benjamin Plaut, 2018. "Markets Beyond Nash Welfare for Leontief Utilities," Papers 1807.05293, arXiv.org, revised Dec 2019.
    18. Kranich, Laurence, 2020. "Resource-envy-free and efficient allocations: A new solution for production economies with dedicated factors," Journal of Mathematical Economics, Elsevier, vol. 89(C), pages 1-7.
    19. Zhaohua Chen & Mingwei Yang & Chang Wang & Jicheng Li & Zheng Cai & Yukun Ren & Zhihua Zhu & Xiaotie Deng, 2022. "Budget-Constrained Auctions with Unassured Priors: Strategic Equivalence and Structural Properties," Papers 2203.16816, arXiv.org, revised Feb 2024.
    20. Christian Arnsperger & David Croix, 1996. "Envy-minimizing unemployment benefits," Review of Economic Design, Springer;Society for Economic Design, vol. 2(1), pages 119-146, December.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

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