  We initiate the study of online problems with set delay, where the delay cost
at any given time is an arbitrary function of the set of pending requests. In
particular, we study the online min-cost perfect matching with set delay
(MPMD-Set) problem, which generalises the online min-cost perfect matching with
delay (MPMD) problem introduced by Emek et al. (STOC 2016). In MPMD, $m$
requests arrive over time in a metric space of $n$ points. When a request
arrives the algorithm must choose to either match or delay the request. The
goal is to create a perfect matching of all requests while minimising the sum
of distances between matched requests, and the total delay costs incurred by
each of the requests. In contrast to previous work we study MPMD-Set in the
non-clairvoyant setting, where the algorithm does not know the future delay
costs. We first show no algorithm is competitive in $n$ or $m$. We then study
the natural special case of size-based delay where the delay is a
non-decreasing function of the number of unmatched requests. Our main result is
the first non-clairvoyant algorithms for online min-cost perfect matching with
size-based delay that are competitive in terms of $m$. In fact, these are the
first non-clairvoyant algorithms for any variant of MPMD. Furthermore, we prove
a lower bound of $\Omega(n)$ for any deterministic algorithm and $\Omega(\log
n)$ for any randomised algorithm. These lower bounds also hold for clairvoyant
algorithms. Finally, we also give an $m$-competititve deterministic algorithm
for uniform concave delays in the clairvoyant setting.
