Fully Online Matching with General Stochastic Arrivals and Departures

A Novel Fully Online Matching Algorithm in Stochastic Environments In many modern applications, such as ride-sharing, participants arrive and depart dynamically, requiring quick decisions about who to match and when. In “Fully Online Matching with General Stochastic Arrivals and Departures,” Li, Wang, and Yan introduce a fully online matching framework that models these real-world dynamics. Each arrival follows a known identical and independent distribution over agent types, whereas the sojourn time is unknown in advance and follows type-specific distributions with known expectations. To address this, they propose a linear programming–based algorithm that guarantees a competitive ratio of at least 0.192 under mild conditions—more than 50% better than the state-of-the-art result of 0.125. They also establish several hardness results to highlight the intrinsic difficulty of the problem. Numerical experiments further confirm the effectiveness and efficiency of their algorithm, offering new insights for decision making in stochastic and dynamic environments.