IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v71y2025i10p8908-8926.html
   My bibliography  Save this article

On Greedy-Like Policies in Online Matching with Reusable Network Resources and Decaying Rewards

Author

Listed:
  • David Simchi-Levi

    (Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Zeyu Zheng

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720)

  • Feng Zhu

    (Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

We build a unified modeling framework for classical online matching problems and emerging online matching problems with three additional practical features: reusable resources, network resources, and decaying rewards. For online matching problems in the unified framework, we provide a unified performance analysis tool for the greedy policy and its simple variants, which we refer to as greedy-like policies. We prove that greedy-like policies can achieve near-optimal performances for online matching problems in the unified framework, where the policy performance is measured by competitive ratios under adversarial environments. We then analyze several representative special classes of online matching problems, which incorporate additional realistic structural assumptions on top of the unified framework. Specifically, we consider online matching problems with each of the following three additional structures: (i) singleton resources with time-decaying rewards; (ii) network resources with accept/reject decisions; and (iii) network resources with interval-type bundles. We show that for these special classes of online matching problems, slight modifications to greedy-like policies can successfully utilize additional structural information to further enhance policy performances. This work may suggest that the greedy policy and its variants, despite its simplicity, can achieve reliable performances for a number of emerging online matching problems.

Suggested Citation

  • David Simchi-Levi & Zeyu Zheng & Feng Zhu, 2025. "On Greedy-Like Policies in Online Matching with Reusable Network Resources and Decaying Rewards," Management Science, INFORMS, vol. 71(10), pages 8908-8926, October.
    • Handle: RePEc:inm:ormnsc:v:71:y:2025:i:10:p:8908-8926
    DOI: 10.1287/mnsc.2023.02588
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2023.02588
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2023.02588?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
    ---><---

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    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:inm:ormnsc:v:71:y:2025:i:10:p:8908-8926. 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.