A Heavy Traffic Theory of Matching Queues

Motivated by emerging applications in online matching platforms and marketplaces, we study a matching queue. Customers and servers that arrive in a matching queue depart as soon as they are matched. It is known that a matching queue without an external control is unstable, and so we study its behavior for a general state-dependent control. Whereas state-dependent control is an effective lever to regulate the throughput and delay, it often comes at a cost for matching platforms in practice. Optimizing this fundamental trade-off motivates the use of small amounts of control, so we study a matching queue in an asymptotic regime in which the state-dependent control decreases to zero. Unlike the heavy traffic regime in classical queues, there are two different ways the control can be sent to zero: via a magnitude scaling parameter $ϵ$ that goes to zero and a time scaling parameter $\tau$ that goes to infinity. Depending on the cost of control, we show that the rates of $ϵ$ and $\tau$ that optimize the trade-off between delay and cost of control could correspond to three different regimes. As we traverse these regimes, we observe a phase transition in the limiting distribution of the matching queue. We show that a low cost of control corresponds to the regime $ϵ\tau \to 0$, and we call it the delay-driven regime. The limiting behavior in this regime is an asymmetrical Laplace distribution. On the other hand, $ϵ\tau \to \infty$ is the cost-driven regime corresponding to a high cost of control in which the limiting behavior is either a uniform or a truncated exponential distribution. We christen the in-between regime of $ϵ\tau \to (0,\infty )$ the hybrid regime in which the limiting behavior is a Gibbs distribution. These results are obtained by novel generalizations of the transform method, in which each regime requires new ideas. The hybrid regime employs inverse Fourier transforms, whereas the other two regimes engineer multiple complex exponential test functions.

Funding: This work was supported by the National Science Foundation [Grants CMMI-2140534 and EPCN-2144316].