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

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.

This paper was accepted by J. George Shanthikumar, data science.

Funding: The work of D. Simchi-Levi and F. Zhu is partially supported by the Massachusetts Institute of Technology Data Science Laboratory.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2023.02588.