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

• 成果类型: Article; Early Access
• 署名作者: Simchi-Levi, David; Zheng, Zeyu; Zhu, Feng
• 署名单位: Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2023.02588
• 发表日期: 2025
• 关键词: online matching; Reusable Resources; network resources; decaying rewards; greedy-like policy; competitive ratio

摘要

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 greedylike 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.