Fully Online Matching with Stochastic Arrivals and Departures

Zihao Li, Hao Wang, Zhenzhen YanAAAI 2023 · DOI

Abstract

This paper introduces a novel framework for matching agents who arrive and depart a system stochastically, a scenario common in ride-sharing and kidney exchanges. The authors propose an LP-based algorithm, SAM (Scaling and Matching), which achieves a guaranteed competitive ratio of at least 0.155. Extensive simulations demonstrate that SAM significantly outperforms standard greedy and batching baselines, particularly in realistic sparse-graph scenarios, achieving empirical competitive ratios between 0.5 and 0.6.

Introduction

Online matching is a classic problem in algorithmic design, traditionally modeled as bipartite matching where one side of the market is fixed while the other arrives sequentially. However, real-world applications like ride-sharing and online gaming matchmaking are "fully online": every participant is transient, and the timing of both arrivals and departures is stochastic. This paper, presented at AAAI-23, tackles this "Fully Online Matching" problem where the clock is always ticking for every agent in the system.

Problem Formulation

The core challenge in fully online matching is twofold:

  1. Stochastic Arrivals: The sequence of incoming agents is unknown; only the general probability distribution of agent "types" is available.
  2. Stochastic Departures: When an agent arrives, their "sojourn time" (the duration they remain in the system) is unknown. The algorithm only knows the expected (mean) wait time for that agent's type.

Decision-makers must balance the immediate reward of matching an agent now against the potential for a higher-value match later, knowing that waiting carries the risk of the agent departing the system empty-handed.

The SAM Algorithm

The authors introduce the SAM (Scaling and Matching) algorithm, which leverages a Linear Programming (LP) benchmark. This LP estimates the maximum expected reward an offline, clairvoyant optimal policy could achieve, serving as a "north star" for the online decision process.

SAM is designed to be distribution-free, meaning it does not require knowledge of the exact probability distribution of sojourn times—only their means. This makes the algorithm robust to the noise typically found in real-world data. When a new agent arrives, SAM uses probabilities derived from the LP, scaled by a parameter $\gamma$, to decide whether to match with an existing agent or wait. This scaling helps manage the risk of departures while aiming for high-value future connections.

Experimental Evaluation

The study utilized synthetic datasets with 100 agent types and varying edge densities ($q$) to evaluate SAM against several baselines: Randomized Compatibility Policy (RCP), a simple Greedy algorithm (GRD), and a Batching algorithm (BAT).

Figure 1: Performance of SAM and baselines across different arrival distributions and graph densities (q).

As shown in Figure 1, SAM (specifically the version with $\gamma=0.5$, labeled SAM0.5) consistently outperforms the baselines across Geometric, Binomial, and Poisson departure distributions. The performance gap is most significant in sparse graphs (low $q$). In these settings, greedy algorithms often fail by matching "flexible" agents to mediocre arrivals, whereas SAM's LP-guided strategy "saves" them for rare, high-value future connections.

Figure 2: Robustness of the SAM algorithm across varying distribution parameters (PG, NB, LP).

Figure 2 highlights SAM's robustness. While the performance of baselines like GRD can be highly sensitive to the specific parameters of the arrival and departure distributions (such as the mean sojourn time), SAM maintains a high and stable Empirical Competitive Ratio (ECR) across a wide range of conditions.

Key Insights and Results

  • Theoretical Guarantee: The authors prove a lower bound for the competitive ratio of 0.155 under mild conditions. This is a robust "worst-case" guarantee for a highly difficult stochastic environment.
  • Empirical Performance: In practice, SAM achieves ECRs between 0.5 and 0.6, outperforming the best baselines by at least 10%.
  • Hardness Gaps: The research proves that no online algorithm can exceed a competitive ratio of $2/3$, and no algorithm based on this specific LP can exceed $1/3$, defining the theoretical limits of the problem.
  • Efficiency: SAM is computationally efficient, with an average runtime per arrival of less than a millisecond, making it viable for real-time deployment.

Conclusion

The SAM algorithm provides a powerful, robust solution for fully online matching problems. By combining an LP-based global view with a strategic scaling mechanism, it effectively manages the uncertainties of stochastic arrivals and departures. Future work may explore non-stationary arrival rates and attempt to close the gap between current theoretical bounds and the absolute limits of the problem.

Summary updated

BibTeX
@inproceedings{li2023fully,
  author = {Zihao Li and Hao Wang and Zhenzhen Yan},
  title = {{Fully Online Matching with Stochastic Arrivals and Departures}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26417},
}
Figure