In real-time service platforms—ranging from ride-hailing networks and online marketplaces to kidney exchange clearinghouses—operators face a continuous, high-stakes decision problem: Should a request be fulfilled immediately, or is it better to wait?
This question exposes a fundamental tension between spatial or structural efficiency and temporal urgency. Matching an agent immediately (a "greedy" or "just-in-time" strategy) minimizes their waiting time and eliminates the risk of them abandoning the system. However, it forces the system to operate with limited information, often leading to suboptimal global choices—such as dispatching a vehicle from far away or burning a rare resource. Conversely, holding onto requests to let the market "thicken" (a "batching" or "patient" strategy) provides a richer pool of options to find highly efficient, localized, or high-utility matches. But this patience comes at a cost: accumulated delay penalties, increased system congestion, and the risk that impatient participants will leave entirely.
Immediate Matching (Greedy) ───► Low Delay / Suboptimal Global Efficiency
Delayed Matching (Batching) ───► High Delay / Optimal Global Efficiency (Thick Market)
Understanding how to optimally navigate this trade-off requires analyzing how time, information, and constraints interact in dynamic environments.
The Cost of Waiting: Deadlines and Impatience
To model the temporal side of the trade-off, researchers characterize how systems penalize delay. In practice, this penalty manifests in two primary ways: continuous holding costs or hard deadlines.
Continuous Delay and Holding Costs
In many settings, every second an agent spends waiting degrades the system's performance linearly or non-linearly. In the Online Service with Delay (OSD) framework introduced by Azar et al. in Online Service with Delay, a server moves across a metric space to fulfill requests. The objective function directly sums the total distance traveled by the server (operational cost) and the total time requests spend waiting (delay cost).
When the system is non-clairvoyant—meaning it does not know when or where future requests will appear—balancing these costs becomes exceptionally challenging. As Touitou demonstrates in Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay, an algorithm must carefully meter its movements so that the cost of traveling to a distant location does not dwarf the accumulated delay penalties of the requests waiting there.
Hard Deadlines and Abandonment
In other markets, participants have a finite amount of patience and will exit the system if not matched within a certain window. This is often modeled as a "quitting function" or a hard deadline $d$.
For instance, Wang et al. in Real-Time Driver-Request Assignment in Ridesourcing incorporate rider impatience directly into the assignment loop, recognizing that delaying a match to find a closer driver might backfire if the rider cancels in the interim. Similarly, the hypergraph matching framework analyzed by Pavone et al. in Online Hypergraph Matching with Delays models multi-passenger ride pooling where each passenger tolerates a maximum delay before dropping out, forcing the platform to bound its batching windows.
The Benefit of Waiting: Market Thickness and Information
Why tolerate delay at all? The answer lies in the power of market thickness. Waiting allows a system to collect more data points, transforming an isolated, blind decision into a globally optimized choice.
In edge-weighted matching markets, delaying matches allows the system to discover higher-value edges. As explored by Ashlagi et al. in Edge Weighted Online Windowed Matching, waiting until an agent's absolute deadline mitigates the risk of making an early, irreversible, and ultimately suboptimal match. By holding out, the platform accumulates a denser graph, revealing combinations that yield significantly higher total utility.
This concept is vividly illustrated in kidney exchange networks. Ashlagi et al. show in Kidney Exchange in Dynamic Sparse Heterogenous Pools that in "thin" or sparse pools containing highly sensitized patients, matching immediately can leave hard-to-match patients stranded indefinitely. Allowing the pool to grow larger creates opportunities for complex 3-way cycles or altruistic donor chains that would be impossible to find in a real-time, myopic setup.
Thin Market (Immediate) Thick Market (Delayed)
○ ○ ○ ─── ○
│ │
○ ○ ○ ─── ○
(No compatible matches) (Cycles & chains emerge)
Furthermore, waiting preserves future flexibility. As Cadas et al. argue in Optimal Control of Dynamic Bipartite Matching Models, matching items greedily can exhaust critical resources or supply types, leaving the system unable to fulfill highly restrictive or high-priority requests that arrive just moments later.
Algorithmic Mechanisms for Balancing the Tradeoff
To reconcile these competing forces, researchers have engineered several distinct algorithmic paradigms.
1. Postponed and Preemptive Routing
One approach is to systematically delay matching until the last possible moment, or conversely, to serve requests preemptively based on spatial hierarchies.
- Postponed Greedy: In Edge Weighted Online Windowed Matching, the authors analyze a strategy that intentionally sits on requests, only matching them when they are on the verge of expiring. This maximizes the information available for each match.
- Preemptive Tree Forwarding: For metric space routing, Azar et al. design an algorithm that recursively "forwards" time on a hierarchical tree structure. This allows the server to serve nearby requests before they become critical, effectively clustering spatial locality with temporal urgency. Touitou extended this line of thought in Improved and Deterministic Online Service with Deadlines or Delay, providing deterministic algorithms that bound the competitive ratio on general metric spaces by carefully balancing travel distance against deadline penalties.
2. Adaptive and Demand-Aware Batching
Instead of using fixed intervals (e.g., batching requests every 5 seconds), modern frameworks dynamically scale the waiting window based on real-time supply and demand.
- Spatio-Temporal Clustering: Liu et al. implement a hierarchical framework in Spatio-Temporal Hierarchical Adaptive Dispatching for Ridesharing Systems that groups geographical areas by their "shareability." High-density areas get shorter windows because a thick market forms almost instantly, while low-density areas get longer windows to allow enough requests to accumulate for viable pooling.
- Predictive Departure Detection: In A Learning-Based Hybrid Decision Framework for Matching Systems with User Departure Detection, Zhou et al. introduce a framework that learns user departure patterns. If the system detects a high probability of imminent user abandonment, it switches to a "Greedy" mode to lock in the match; if the user is predicted to be patient, it switches to a "Patient" mode to wait for a higher-utility pairing.
3. Conservative Matching via LP Relaxations
When agent arrival and departure rates are highly heterogeneous and unannounced, myopic strategies fail. To counter this, Collina et al. propose an online algorithm in Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates that uses a continuous linear programming (LP) relaxation as a guide. The algorithm matches "conservatively," intentionally passing up mediocre immediate matches if the LP indicates that saving an agent for a future arrival will yield a higher expected global payoff.
When Does Greedy Suffice?
Given the complexity of these adaptive and predictive frameworks, an important theoretical counterpoint emerges: Is waiting always worth it?
Surprisingly, in homogeneous markets where agents are structurally similar, the benefits of waiting can evaporate. Gamarnik et al. demonstrate in Efficient Dynamic Barter Exchange that a simple, myopic greedy strategy—matching agents the second a valid exchange opens up—is near-optimal in homogeneous dynamic barter settings. Because the agents are interchangeable, waiting to build a larger pool does not meaningfully improve match quality, but it guarantees an increase in average waiting times.
Therefore, the sophisticated machinery of delayed, batch-based matching is primarily justified when the market is heterogeneous or sparse, where the variance in match quality or spatial distance is wide enough that the informational gain of waiting outweighs the certain penalty of time.
Key Foundational Work
Efficient Dynamic Barter Exchange (2017) — contributed 5 concept elements to this direction.
Kidney Exchange in Dynamic Sparse Heterogenous Pools (2013) — contributed 1 concept elements to this direction.
Online Service with Delay (2017) — contributed 1 concept elements to this direction.