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 .