  This paper presents a new research direction for the Min-cost Perfect
Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In
the original version of this problem, we are given an $n$-point metric space,
where requests arrive in an online fashion. The goal is to minimise the
matching cost for an even number of requests. However, contrary to traditional
online matching problems, a request does not have to be paired immediately at
the time of its arrival. Instead, the decision of whether to match a request
can be postponed for time $t$ at a delay cost of $t$. For this reason, the goal
of the MPMD is to minimise the overall sum of distance and delay costs.
Interestingly, for adversarially generated requests, no online algorithm can
achieve a competitive ratio better than $O(\log n/\log \log n)$ (Ashlagi et
al., APPROX/RANDOM'17).
  Here, we consider a stochastic version of the MPMD problem where the input
requests follow a Poisson arrival process. For such a problem, we show that the
above lower bound can be improved by presenting two deterministic online
algorithms, which, in expectation, are constant-competitive. The first one is a
simple greedy algorithm that matches any two requests once the sum of their
delay costs exceeds their connection cost, i.e., the distance between them. The
second algorithm builds on the tools used to analyse the first one in order to
obtain even better performance guarantees. This result is rather surprising as
the greedy approach for the adversarial model achieves a competitive ratio of
$\Omega(m^{\log \frac{3}{2}+\varepsilon})$, where $m$ denotes the number of
requests served (Azar et al., TOCS'20). Finally, we prove that it is possible
to obtain similar results for the general case when the delay cost follows an
arbitrary positive and non-decreasing function, as well as for the MPMD variant
with penalties to clear pending requests.
