Online Matching with Delays and Stochastic Arrival Times

Consider a platform where independent agents arrive at random times and need to be matched into pairs, eventually after waiting for some time. This, for example, models job markets, gaming platforms, kidney exchange programs, etc. The platform decides how to match agents together while optimizing two conflicting objectives: the quality of the matching produced, and the total waiting time of the agents. This can be modeled as an online problem called Min-cost Perfect Matching with Delays (MPMD). In the case when agents arrive in an adversarial order, no online algorithm can achieve a constant-competitive ratio. In this paper, we study a realistic case where agents’ arrival times follow some stochastic assumptions, and we present two matching mechanisms, which give constant-competitive solutions. The first one is a simple greedy algorithm in which agents act in a distributed manner requiring only local communication. The second one builds global analysis tools in order to obtain even better performance guarantees. This result is surprising as the greedy approach cannot achieve a competitive ratio better than $$O(m^{\log 1.5 + \varepsilon })$$ in the adversarial model, where m denotes the number of agents. Finally, we extend our results to the general delay cost case, the clearing requests with penalty case, and the asymmetric distance case.