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

David Simchi-Levi (), Zeyu Zheng () and Feng Zhu ()
Additional contact information
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

Management Science, 2025, vol. 71, issue 10, 8908-8926

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.

Keywords: online matching; reusable resources; network resources; decaying rewards; greedy-like policy; competitive ratio (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2023.02588 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:71:y:2025:i:10:p:8908-8926

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().