Fully Online Matching with General Stochastic Arrivals and Departures

We study a fully online matching problem with general stochastic arrivals and departures. In this model, each online arrival follows a known identical and independent distribution over a fixed set of agent types. Its sojourn time is unknown in advance and follows type-specific distributions with known expectations. The goal is to maximize the weighted reward from successful matches. To solve this problem, we propose a linear program (LP)–based algorithm whose competitive ratio is lower bounded by 0.192 under mild conditions. To demonstrate the challenges of the problem, we further establish several hardness results. In particular, we show that no online algorithm can achieve a competitive ratio better than $1/2$ in this model, and if using our LP as a benchmark for competitive ratio analysis, no algorithm can achieve a better ratio than $1/3$. When no assumptions are made regarding the sojourn time distributions, we demonstrate that it is impossible to achieve a positive competitive ratio for the general case using our LP as a benchmark for competitive ratio analysis. We further extend our model to accommodate general sojourn times under Poisson arrivals and demonstrate a better competitive ratio compared with state-of-the-art results derived under Poisson arrivals and departures, a special case of our general settings. Finally, we demonstrate the effectiveness and efficiency of our algorithm numerically.

Funding: This work was supported by the School of Physical and Mathematical Sciences Collaborative Research Award and the Singapore Ministry of Education Tier 1 [Grant RG20/23].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2023.0190.