Online Matching with Delays and Size-Based Costs

In this study, we determine the competitive ratios of the OMDSC problem for fundamental and critical scenarios in which the penalty function takes only values of either $0$ or $1$. In the OMDSC problem, dividing a group into multiple smaller groups can reduce penalties. Therefore, it is sufficient to consider a modified penalty function obtained by optimally dividing a group into subgroups. With this modification, we classify penalty functions into three cases: (i) always $1$, (ii) $0$ if the size is a multiple of $k$, and (iii) all other scenarios.

In case (i), the OMDSC problem is equivalent to the TCP acknowledgment problem. Dooly et al. [14] proposed a $2$-competitive online algorithm that matches all remaining requests when the total waiting cost increases by $1$. For case (ii), we first examine natural algorithms that match all the remaining requests whenever a match incurs a positive cost, which we refer to as match-all-remaining algorithms. We demonstrate that every match-all-remaining algorithm is $\mathrm{\Omega }(\sqrt{k})$-competitive (Theorem 6). Consequently, to obtain an $o(\sqrt{k})$-competitive algorithm, we must consider both the timing and size of the requests to be matched. By carefully managing remaining requests, we propose an $O(\log k/\log \log k)$-competitive online algorithm (Theorem 8). We also prove that this competitive ratio is the best possible (Theorem 15). It is worth mentioning that the competitive ratio for case (ii) with $k=1$ is trivial (Theorem 3) and that with $k=2$ can be obtained from the results of Emek et al. [17]. For any penalty function in case (iii), we prove that no competitive online algorithm exists (Theorem 2). The results are summarized in Table 1. Furthermore, the competitive ratios for other typical penalty functions that are not restricted to take values of $0$ or $1$ are discussed in Section 2.3.

An online version of the matching problem was first introduced by Karp et al. [21]. In their study, arriving requests are matched immediately upon arrival, primarily focusing on bipartite matching. Additionally, research has been conducted to minimize matching costs, both in settings where vertices have determined costs and in settings that consider distances in a metric space. Mehta et al. [26] proposed an application to AdWords. Other applications, such as food delivery, have also been considered. For further details, please refer to [25, 15].

In applications such as online game matchmaking and ride-sharing services, service providers can delay user matches. Emek et al. [16] modeled this scenario as an MPMD problem. In this setting, the requests can be retained by incurring waiting costs. Several online algorithms have been proposed for solving the MPMD problem [1, 8, 3]. Subsequently, Melnyk et al. [27] extended the MPMD problem to the $k$-MPMD problem, which requires exactly matching the size $k$. To address this problem, deterministic and randomized algorithms have been proposed [27, 19].

Dooly et al. [14] introduced the TCP acknowledgment problem that involves acknowledging TCP packets. In this problem, the aim is to minimize the sum of the acknowledgment costs and the costs of delaying TCP packets. Optimal deterministic and randomized algorithms were proposed by Dooly et al. [14] and Karlin et al. [20], respectively. The TCP acknowledgment problem is equivalent to the OMDSC problem, where the penalty function falls under case (i). Conversely, the OMDSC problem can be viewed as a generalization of the acknowledgment cost of the TCP acknowledgment problem.

Various extensions of the TCP acknowledgment problem have been proposed [10, 7, 6, 9, 5, 11, 2, 29, 12]. In particular, Chen et al. [12] introduced the problem of an online weighted cardinality JRP with delays. Their model can handle penalties based on the size of the match. However, unlike in our study, their penalty function is restricted to monotonically nondecreasing. They proposed a constant-competitive algorithm to solve this problem.

The objectives of the MPMD and $k$-MPMD problems are to pair requests and form groups of exact size $k$, respectively. In contrast, the proposed OMDSC problem does not impose constraints on the number of requests in each group. Emek et al. [16] introduced a problem called MPMDfp, which allows the clearance of a request at a cost. The MPMDfp problem on a single source is equivalent to the OMDSC problem where the penalty function corresponds to case (ii) with $k=2$. Additionally, the MPMDfp problem on a single source can be reduced to an MPMD problem using two sources [16]. For MPMD on two sources, Emek et al. [17] proposed a deterministic algorithm, and He et al. [18] proposed a randomized algorithm (see Section 4 for more details).

Another approach to extend the MPMD problem is to modify waiting costs. Liu et al. [23] generalized the waiting costs from linear to convex. Other variations of waiting costs have also been studied [24, 4, 13]. Pavone et al. [28] investigated Online Hypergraph Matching with Deadlines problem. Although hypergraph matching does not impose constraints on group size, it differs from the OMDSC problem in that it employs deadlines instead of delays, and requests arrive at one at each unit of time.

In this section, we formally define the OMDSC problem. An instance of the problem is specified by a penalty function $f:{\mathbb{Z}}_{++}\to {ℝ}_{+}$ and $m$ requests $V=\{v_1,v_2,\mathrm{\dots },v_m\}$ that arrive in real time. Each request $v_i$ arrives at time $t_i$, where $0\le t_1\le t_2\le \mathrm{\cdots }\le t_m$ is assumed.

An online algorithm initially knows only the function $f$; it does not have prior knowledge of the arrival times or the total number of requests. Each request $v_i$ is revealed at time $t_i$. At each time $\tau$, the algorithm can match any subset $S_j$ of requests that appeared by time $\tau$ and have not yet been matched. The cost of matching requests in $S_j$ at time ${\tau }_j$ is defined as

where the first term represents the size cost and the second term represents the waiting cost. In addition, the waiting cost at time $\tau$ is defined as ${\sum }_{i:v_i\in V^{\prime }}(\tau -t_i)$, where $V^{\prime }$ is the set of unmatched but previously presented requests at that time.

The objective is to design an online algorithm that matches all requests while minimizing the total cost. We use the competitive ratio to evaluate the performance of the online algorithm. For a given instance $\sigma$, let $\mathrm{ALG}(\sigma )$ represent the cost incurred by the online algorithm and let $\mathrm{OPT}(\sigma )$ denote the optimal cost with prior knowledge of all requests in the instance. The competitive ratio of $\mathrm{ALG}$ for an instance $\sigma$ is defined as $\mathrm{ALG}(\sigma )/\mathrm{OPT}(\sigma )$, interpreting $0/0$ as $1$. In addition, the competitive ratio of $\mathrm{ALG}$ for a problem is defined as the supremum of the competitive ratios over all instances, that is, ${sup}_{\sigma }\mathrm{ALG}(\sigma )/\mathrm{OPT}(\sigma )$. We call an online algorithm $\rho$-competitive if the competitive ratio of that algorithm is $\rho$.

The competitive ratio defined above is the strict competitive ratio. We can also define the asymptotic competitive ratio as ${lim\; sup}_{\mathrm{ALG}(\sigma )\to \mathrm{\infty }}\mathrm{ALG}(\sigma )/\mathrm{OPT}(\sigma )$. However, in our problem, the strict and asymptotic competitive ratios of the optimal algorithm coincide. Indeed, if an algorithm is strictly $\rho$-competitive, then it is also asymptotically at most $\rho$-competitive by definition. Moreover, if no strictly $\rho$-competitive algorithm exists, we can construct an instance for each algorithm in which the strict competitive ratio is at least $\rho$. Thus, by repeatedly constructing and providing such instances, we can conclude that no algorithm has an asymptotic competitive ratio better than $\rho$. Hence, we only consider the strict competitive ratio hereafter.

This study focuses primarily on penalty functions that take values only of either $0$ or $1$. We discuss other penalty functions in Section 2.3. For such a binary penalty function $f$, we may be able to match $n$ requests with size cost $0$, even if $f(n)=1$, by appropriately partitioning the requests. For instance, if $f(2)=f(3)=0$ and $f(7)=1$, we can match $7$ requests with a size cost of $0$ by partitioning them into groups of sizes $2$, $2$, and $3$. We introduce a notation for the set of numbers of requests that can be matched with a size cost of $0$ as follows:

For example, if $f(1)=0$, then $B_f={\mathbb{Z}}_{++}$. Alternatively, if $f(1)=1$ and $f(2)=f(3)=0$, then $B_f={\mathbb{Z}}_{++}\setminus \{1\}$. We can interpret the size cost of matching $n$ requests as $0$ if $n\in B_f$ and $1$ if $n\notin B_f$.

We classify binary penalty functions into the following three types: (i) $B_f=\mathrm{\varnothing }$, (ii) $B_f=\{kn\mid n\in {\mathbb{Z}}_{++}\}$ for some $k\in {\mathbb{Z}}_{++}$, and (iii) all other scenarios. Case (i) is the situation in which the penalty for matching requests is always $1$ (i.e., $f(n)=1$ for all $n\in {\mathbb{Z}}_{++}$). Case (ii) is a situation in which a set of requests can be matched without a size cost only if the size is a multiple of $k=\min \{n\in {\mathbb{Z}}_{++}\mid f(n)=0\}$ (i.e., $f(k)=0$ and $f(n)=1$ for all $n\in {\mathbb{Z}}_{++}\setminus \{k{n}^{\prime }\mid n^{\prime }\in {\mathbb{Z}}_{++}\}$). This case is applicable in the context of an online gaming platform that hosts a $k$-players game, as described in Introduction.

If the range of the penalty function is $\{0,\mu \}$ with a positive real $\mu$, it can be treated as a binary penalty function by scaling the increase rates of the waiting costs $\mu$ times slower. This is because the cost of matching requests in $S_j$ at time ${\tau }_j$ can be expressed as $\mu \cdot \left(f(|S_j|)/\mu +{\sum }_{i:v_i\in S_j}({\tau }_j/\mu -t_i/\mu )\right)$. For example, if $\mu =60$ and the unit time is one minute in the original problem, the range of the penalty function can be treated as $\{0,1\}$ by adjusting the unit time to one hour. Let $\mu ,\lambda \in ℝ$ with and consider a penalty function that takes values of $0$ or within the range $[\mu ,\lambda ]$. By applying our $\rho$-competitive algorithm to the problem while treating positive penalties as if they were $\mu$, we can obtain a $(\rho \cdot \lambda /\mu )$-competitive algorithm. In addition, our impossibility result for case (iii) can be transferred in the same manner.

Another interesting penalty function is $f(n)=\lceil n/k\rceil$ for a specific integer $k$. This penalty function appears when a service can process up to $k$ requests simultaneously, and each processing costs a fixed amount. For this penalty function, an algorithm similar to that in (i) is $2$-competitive for any $k\ge 2$. We also prove that this competitive ratio is best possible for every $k\ge 2$ (see the full version [22]). For $k=1$, the algorithm that matches each request upon its arrival is $1$-competitive.

The objective of this subsection is to prove the following theorem.

According to Theorem 6, an $O(\alpha )$ ($=O(\log k/\log \log k)$)-competitive algorithm must consider both the timing and the size of requests to be matched. To address this requirement, we propose an algorithm that references the costs of other algorithms. The execution of the algorithm is divided into phases. In each phase, the goal is to ensure that any competing algorithm incurs a cost of at least $1$, while our algorithm’s cost remains at most $O(\alpha )$. We categorize competing algorithms based on the number of unmatched requests they carry over from the previous phase. As for the current phase, we assume that algorithms only perform matches of sizes that are multiples of $k$, since otherwise, their cost immediately reaches at least $1$. Furthermore, it is sufficient to focus on “greedy” algorithms that immediately match $k$ requests whenever at least $k$ unmatched requests exist.

The first phase starts at the beginning. In each phase, our algorithm runs with the following $k+2$ variables.

We will omit the argument $t$ when there is no confusion.

Note that, if $(k-i)$ unmatched requests are carried over to the current phase, the optimum cost incurred thus far within the phase is at least $\min \{1,W_i\}$. At the end of the phase, our algorithm ensures $W_i\ge 1$ for all $i\in {\mathbb{Z}}_k$. This means that any algorithm incurs a cost of at least $1$ per phase because matching a number of requests that is not a multiple of $k$ results in a cost of $1$.

During each phase, our algorithm recursively processes a subroutine $\text{recurring}({⟦p,q⟧}_k,l)$, which takes as parameters a cyclic interval ${⟦p,q⟧}_k$ and an integer $l$. When the subroutine is called, it ensures that $W_i\ge 1$ for all $i\notin {⟦p,q⟧}_k$ and $W_i\ge l/\alpha$ for all $i\in {⟦p,q⟧}_k$. In each iteration of the subroutine, the interval size $\left|{⟦p,q⟧}_k\right|$ is reduced by a factor of $\mathrm{\Theta }(1/\alpha )$ or $l$ is increased by one, with incurring cost at most $O(1)$. As a result, all $W_i$ reach at least $1$ after $O(\alpha )$ recursions by ${\alpha }^{\alpha }=k$.

At the beginning of each phase, the variables $W_0,W_1,\mathrm{\dots },W_{k-1}$, $s$, and $a$ are $0$ and $\text{recurring}({⟦0,k-1⟧}_k,\mathrm{\hspace{0.17em}0})$ is called. Throughout the phase, the algorithm updates the values of $W_0,W_1,\mathrm{\dots },W_{k-1}$, $s$, and $a$, appropriately. Moreover, if at least $k$ unmatched requests exist (i.e., $s-a\ge k$), it immediately matches $k$ of them.

We now describe the subroutine $\text{recurring}({⟦p,q⟧}_k,l)$. See Algorithm 1 for a formal description. Figure 1 illustrates lower bound of each $W_i$ at each line.

When $\text{recurring}({⟦p,q⟧}_k,l)$ is called, it is guaranteed that $p,q\in {\mathbb{Z}}_k$, $l\in \{0,1,\mathrm{\dots },\lceil \alpha \rceil \}$, $W_i\ge 1$ for all $i\notin {⟦p,q⟧}_k$, $W_i\ge l/\alpha$ for all $i\in {⟦p,q⟧}_k$, and $\overline{a}=p$ (recall that $\overline{a}\in {\mathbb{Z}}_k$ is the remainder of $a$ when divided by $k$, see also Figure 1). The recursion ends (line 3) when $\left|{⟦p,q⟧}_k\right|$ equals to $1$ or when $l$ is at least $\alpha$. Then, it matches all remaining requests and proceeds to the next phase.

At the beginning of each recursion, the algorithm waits until $W_{\overline{a}}$ increases by $2$ (line 2). Afterward, if $W_i\ge (l+1)/\alpha$ for all $i\in {⟦p,q⟧}_k$, it calls $\text{recurring}({⟦p,q⟧}_k,l+1)$ (Figure 1). Now, assume that for some $i\in {⟦p,q⟧}_k$. In this case, there exists a smaller interval ${⟦p^{\prime },q^{\prime }⟧}_k(\subseteq {⟦p,q⟧}_k)$ such that $W_i\ge (l+1)/\alpha$ for all $i\in {⟦p,q⟧}_k\setminus {⟦p^{\prime },q^{\prime }⟧}_k$ (Figure 1). The algorithm picks the smallest such cyclic interval ${⟦p^{\prime },q^{\prime }⟧}_k$ (line 6).

Next, it attempts to change $\overline{a}$ from $p$ to $p^{\prime }$ by matching $\overline{p^{\prime }-p}$ requests. To achieve this, it waits to satisfy $\overline{s}\in {⟦p^{\prime },p-1⟧}_k$ (see Figure 2) until $W_{\overline{a}}(=W_p)$ increases by $1/\alpha$ (line 7). If $W_{\overline{a}}$ increases by $1/\alpha$, then $W_i\ge (l+1)/\alpha$ holds for every $i\in {⟦p,q⟧}_k$ as we will show later (Figure 1). Consequently, the algorithm calls $\text{recurring}({⟦p,q⟧}_k,l+1)$ (line 8). Now, suppose that $\overline{s}$ in ${⟦p^{\prime },p-1⟧}_k$ at some point. In that case, it changes $\overline{a}$ from $p$ to $p^{\prime }$ by matching $\overline{p^{\prime }-p}$ requests (line 9 and see Figure 1).

Then, the algorithm waits until $W_{\overline{a}}(=W_{p^{\prime }})$ increases by $2$ (line 10). We consider two cases: ($\mathrm{♠}$) $W_i\ge (l+1)/\alpha$ for all $i\in {⟦p^{\prime },q^{\prime }⟧}_k$ (Figure 1) and ($\mathrm{♡}$) for some $i\in {⟦p^{\prime },q^{\prime }⟧}_k$ (Figure 1). In case ($\mathrm{♠}$), the algorithm attempts to move $\overline{a}$ from $p^{\prime }$ to $p$ to call $\text{recurring}({⟦p,q⟧}_k,l+1)$. To do this, the algorithm waits until $\overline{s}\in {⟦p,p^{\prime }-1⟧}_k$ (see Figure 2) or until $W_{\overline{a}}(=W_{p^{\prime }})$ increases by $1$ (line 12). If $W_{p^{\prime }}$ increases by $1$, then $W_i\ge 1$ holds for every $i\in {⟦p,p^{\prime }⟧}_k$ as we will show later (Figure 1). Then, it calls $\text{recurring}({⟦p^{\prime },q⟧}_k,l+1)$ (line 18). Otherwise, the algorithm changes $\overline{a}$ from $p^{\prime }$ to $p$ by matching $\overline{p-p^{\prime }}$ requests (line 14 and see Figure 1). Consequently, it calls $\text{recurring}({⟦p,q⟧}_k,l+1)$ (line 15). In case ($\mathrm{♡}$), $W_i$ becomes at least $1$ for $i$ in not a cyclic interval ${⟦p^{\prime },r⟧}_k$ (Figure 1). Then, the algorithm calls $\text{recurring}({⟦p^{\prime },r⟧}_k,l)$ (line 18).

After completing the call of recurring, we have $W_i\ge 1$ for all $i\in {\mathbb{Z}}_k$. Then, the algorithm moves to the next phase.

To analyze the competitive ratio of this algorithm, we present several lemmas. The value of $W_i$ changes continuously within each phase, and its rate of increase over time is given by $d{W}_i(t)∕dt=\overline{s(t)-i}$. The increase rate of $W_i$ for each $i$ is illustrated in Figure 3.

We demonstrate that if $W_p$ increases significantly while $W_i$ increases only slightly, then $W_p$ increases significantly during periods when $\overline{s-i}$ is small.