A platform that matches riders, workers, or trading partners as they arrive faces a "quick or cheap" choice. Matching immediately keeps waits short but pairs people with poor partners. Waiting lets the pool fill up so better pairs appear, but everyone waits longer. Quick or Cheap? Breaking Points in Dynamic Markets proves that this trade-off can be a hard wall. When the cost of the best static matching among $n$ agents falls as $n^{-\delta}$ with $1<\delta\le 2$, no clearing schedule keeps both the cost penalty and the waiting penalty bounded. At the boundary $\delta=2$, their best balanced schedule still lets the penalties grow like $(\log A)^{1/3}$. Every schedule in that analysis clears the whole market at once: it waits until the pool is large enough, matches everyone, and starts again from an empty pool.
This proposal borrows the central trick of the nibble method from graph coloring. The nibble method colors a graph in many small rounds. Each round commits only a small random fraction of tentative choices, so the elements left uncolored keep a predictable, well-spread set of options. We propose clearing schedules that work the same way. At each epoch the platform computes a good matching on the current pool but commits only a random fraction $\varepsilon$ of its pairs. The pool never empties, and because the committed pairs are chosen at random, the agents left behind still look like a fair sample of arrivals. The question is whether the breaking point of Mertikopoulos et al. is a fact about dynamic markets or only about whole-market clearing. We would answer it with a proof in one direction or the other, backed by simulations that measure both penalties as the market grows.
Core Claim
Two failure modes compete, and we believe they explain the breaking point. Whole-market clearing pays a reset cost: right after each clearing the pool is thin, so agents arriving then either wait long or get matched poorly. The obvious fix is to clear partially by committing the cheapest pairs first. That fix pays a cost we call adverse selection of the residual. The agents left behind are disproportionately the hard-to-match ones, in isolated regions of type space, so newcomers face a pool that is worse than a fresh sample of the same size. This is the matching analogue of what the coloring literature calls "palette shock," where early greedy choices exhaust the options of the elements that remain.
The nibble avoids both. We define the residual discrepancy $D_t = \sup_{B} |\mu_t(B) - \nu(B)|$, where $\mu_t$ is the empirical type distribution of the waiting pool at epoch $t$, $\nu$ is the arrival distribution, and $B$ ranges over a fixed family of regions of type space. A nibble step takes a near-optimal matching $M_t$ of the current pool and commits each pair independently with probability $\varepsilon$. Our main conjecture is that, once arrivals are mixed in, this keeps $D_t$ concentrated near zero at every epoch. If that holds, the pool behaves like a fresh market of its steady-state size $N$. Each match then costs roughly what a static market of size $N$ would charge, while agents wait only about $N/\lambda$ on average, where $\lambda$ is the arrival rate (this follows from Little's law). The theorem we aim for has two possible outcomes. The first is that, at $\delta=2$, nibble clearing keeps both penalty ratios bounded, removing the $(\log A)^{1/3}$ growth. The second is that the impossibility extends to all partial-clearing policies, with residual concentration serving as the proof tool. Either outcome changes what the breaking point means.
Relation to Prior Work
The method comes from the nibble literature. Near-Optimal, Distributed Edge Colouring via the Nibble Method colors edges in rounds of tentative random choices and keeps the remaining palettes concentrated around their expectations. Online Edge Coloring Algorithms via the Nibble Method shows that random arrival order can simulate this sampling online. It also uses dummy "regularizing" nodes and edges to handle irregular instances, and we would reuse that device for unbalanced markets. Fast Discrepancy Minimization with Hereditary Guarantees and Spectral Sparsification by Deterministic Discrepancy Walk show that the choice of which elements to fix in each phase can be made deterministically while still controlling an imbalance measure. We use these as a template for a second variant that selects committed pairs to minimize $D_t$ instead of sampling them at random. None of these papers has costs, waiting, or a speed-versus-quality trade-off.
The motivation comes from the dynamic-market literature. Mertikopoulos et al. supply the model, the two penalty ratios, and the impossibility we test. Dynamic Bipartite Matching Market with Arrivals and Departures shows that being patient cuts the share of agents who leave unmatched from $\Theta(\log d/d)$ to $e^{-\Theta(d)}$ in balanced two-sided markets, where $d$ is market density. It also shows patience gives nothing in one-sided markets. That supports the view that the composition of the waiting pool, not just its size, drives the outcome.
Several competing algorithms constrain the proposal. Online Hypergraph Matching with Delays clears disjoint batches whose start times are randomly shifted. That is whole-market clearing with a reset, and it assumes every agent has the same deadline. Online Matching with Delays and Stochastic Arrival Times proves that a simple threshold rule is within a constant factor of the offline optimum under Poisson arrivals. That rule matches two agents once their combined waiting exceeds the distance between them. Because it is already a form of continuous partial clearing, it is the closest competitor and we treat it as one. The tree-embedding algorithms of Online Matching: Haste makes Waste! and Min-Cost Bipartite Perfect Matching with Delays target worst-case arrival sequences. Our setting is stochastic arrivals in a continuum of types.
One possible contradiction needs addressing. A constant competitive ratio against the offline optimum, as Mari et al. prove, does not conflict with penalty ratios that grow. Mertikopoulos et al. measure against idealized benchmarks: zero wait on one side, a static thick market on the other. So constant competitiveness is not evidence that the breaking point is avoidable.
Research Program
The theory has three steps. The first is a residual-concentration lemma. It would show that under Poisson arrivals with distribution $\nu$, nibble clearing with rate $\varepsilon$ keeps $D_t$ small with high probability throughout a horizon of $A$ arrivals. The proof would follow the round-by-round tracking used in Improved Bounds for Coloring Locally Sparse Hypergraphs, which controls how key quantities drift from round to round. The second step converts low discrepancy into a per-match cost of order $g(N)$, the static matching cost at pool size $N$. Combined with the Little's-law waiting bound, this yields both penalty ratios as functions of $N$ and $\varepsilon$. The third step either optimizes $N(A)$ to show bounded ratios at $\delta=2$, or locates exactly where the argument breaks and turns that failure into a lower bound covering all partial-clearing policies.
The empirical side requires building a simulator for continuum-type markets. Rather than assume how a cost family maps to $\delta$, we would measure the static cost $g(n)$ for each family and fit $\delta$ directly. The families would include the exponential cost model at $\delta=2$ used by Mertikopoulos et al.
Baselines
The naive reference point is greedy immediate matching: each arrival takes the cheapest available partner. It shows the "quick" extreme, with small waits and the worst cost ratio.
The strongest existing method for the question as posed is the balanced clearing schedule of Mertikopoulos et al., which clears the whole market when the short side reaches $\Theta(k^{1/2}(\log k)^{1/3})$. Their reported result is that, in the exponential cost model at $\delta=2$, the penalty ratios grow as $\Theta((\log A)^{1/3})$. We would run it with its threshold constant tuned on the same grid and seed budget as our $\varepsilon$ and $N$. Beating it means a statistically flat ratio curve as $A$ grows, where theirs rises.
The strongest competitor on the real mechanism is the threshold rule of Mari et al. and its variant, the Radius algorithm, which precomputes a matching radius at each location. Their reported competitive ratios are $16/(1-e^{-2})$ for the threshold rule and $8/(1-e^{-2})$ for the Radius algorithm. No reported empirical result was found on Lacuna for either rule in continuum-type markets. We would also tune a multiplier on the threshold, so the rule can trace its own cost-versus-wait curve. Beating it means that nibble clearing dominates the best of those curves at large $A$.
Randomized shifted batching from Pavone et al. is a third baseline. We would run it with the batch length tuned and with heterogeneous patience drawn from a departure model in the style of Kakimura and Zhu.
Two ablations isolate the key ingredient. The first commits the cheapest $\varepsilon$ fraction of pairs instead of a random one. If our claim is right, it should match the nibble on early cost but show rising $D_t$ and degrading cost over time. The second sets $\varepsilon=1$, which is whole-market clearing with the same trigger. Finally, the deterministic discrepancy-walk variant tests whether randomness itself matters or only the control of $D_t$.
Why not just…?
Why not just use the threshold rule, which already clears partially? This is the real threat. The threshold rule matches whichever pair crosses its trigger first, so it may already behave like a cheapest-first nibble or, more favorably, like a random one. The decisive measurement is $D_t$ under that rule. If its residual stays representative and its cost-versus-wait curve equals ours, then the nibble contributes only an analysis tool. In that case we would use the concentration lemma to prove the threshold rule's growth rates, rather than claim a new algorithm.
Why not just tune whole-market batching better? Mertikopoulos et al. already optimized over this class and proved that the breaking point holds within it. A better batching schedule cannot remove the growth. The $\varepsilon=1$ ablation confirms empirically that the reset, not the trigger rule, is what costs us.
Why not just commit the cheapest pairs and skip the randomness? Cheapest-first leaves outliers behind. The discrepancy and late-horizon cost measurements in the ablation test this directly. If cheapest-first shows no rise in $D_t$, the adverse-selection explanation is wrong, and the proposal reduces to the question of partial versus whole clearing.
Proposed Experiments
The synthetic experiments use markets of three kinds: types uniform on low-dimensional boxes, clustered mixtures (which stress outlier accumulation), and the exponential cost model. For each, we fit $\delta$ from measured static costs. We would sweep horizons $A$ across several orders of magnitude and report both penalty ratios, together with the fitted growth exponent of each against $\log A$.
For a realistic workload, we would replay pickup and dropoff coordinates from New York City taxi trips, the dataset studied in Exploring What not to Clean in Urban Data: A Study Using New York City Taxi Trips. We would add heterogeneous patience and measure departures alongside cost. We would also run one-sided markets to test whether nibble clearing escapes the result of Kakimura and Zhu that patience gives no benefit there, with dummy agents in the style of the regularizing gadgets used for imbalance.
Three outcomes are decisive. The first is whether, at $\delta=2$, nibble clearing's ratios stop growing while the balanced schedule's grow as $(\log A)^{1/3}$. The second is whether, for $\delta\in(1,2)$, any $\varepsilon$ and $N(A)$ keeps both ratios bounded. The third is whether the cost gap between random and cheapest-first nibbling tracks the gap in $D_t$. A yes on the third check with a no on the first two would point toward extending the impossibility to all partial-clearing policies. A yes on all three would show that the breaking point is an artifact of clearing the whole market at once.
References
- Quick or Cheap? Breaking Points in Dynamic Markets
- Near-Optimal, Distributed Edge Colouring via the Nibble Method
- Online Edge Coloring Algorithms via the Nibble Method
- Fast Discrepancy Minimization with Hereditary Guarantees
- Spectral Sparsification by Deterministic Discrepancy Walk
- Dynamic Bipartite Matching Market with Arrivals and Departures
- Online Hypergraph Matching with Delays
- Online Matching with Delays and Stochastic Arrival Times
- Online matching: haste makes waste!
- Min-Cost Bipartite Perfect Matching with Delays
- Improved Bounds for Coloring Locally Sparse Hypergraphs
- Exploring What not to Clean in Urban Data: A Study Using New York City Taxi Trips