A Longest-Queue Rule for Matching Markets Where Agents Can Leave

Matching under impatience

In their preprint, Siqi He, Yehua Wei and Jiaming Xu study a market where each match joins agents of two distinct, compatible types. The compatibility network can be bipartite, with two separate sides, or more general, including networks containing triangles.

Agents arrive through type-specific Poisson processes. Each has an independently drawn exponential patience time, which the decision maker cannot observe before abandonment. Matching earns a reward; waiting incurs holding costs; leaving unmatched incurs an abandonment penalty. Queues begin empty.

The objective also includes a terminal cost. When the operating horizon ends, the model charges the expected future holding and abandonment costs of all remaining agents, assuming no further matching. This convention matters: agents left waiting at the deadline do not disappear from the accounting.

Optimization first, a simple rule afterward

The proposed policy is not simply “match with the longest available queue.” Before operations begin, it solves the dual of a fluid linear program. This deterministic relaxation replaces random arrivals and departures with continuous flows, producing an upper bound on every admissible policy’s expected net value per unit time.

The dual assigns a shadow value to each agent type. Types with positive shadow values are called critical. A compatible pair is designated a good match when its adjusted reward equals the sum of its two shadow values. Adjusted rewards incorporate both the matching reward and the holding and abandonment costs avoided through matching.

Those classifications remain fixed throughout the horizon. At each arrival, the policy:

• Considers only available partners forming good matches.
• Prioritizes critical partners, choosing the type with the longest queue.
• Otherwise selects an available noncritical good partner, if one exists.
• Leaves the arriving agent waiting if no good partner is available.

Ties follow a deterministic rule fixed beforehand. Unlike scheduled-review approaches, the policy makes decisions at arrivals and requires no review interval.

What the authors prove

The analysis increases every arrival rate by the same market-size factor, s, while keeping the other model parameters fixed. Performance is measured against the fluid upper benchmark, assumed positive, rather than against a simulated estimate of an optimal policy.

The strongest result requires a general position gap, or GPG. This condition means the fluid program has a unique optimal dual solution that remains optimal under sufficiently small changes to arrival rates.

Under GPG, the authors prove an approximation ratio of at least 1 − C/s for every scale s ≥ 1 and horizon T ≥ 1. The constant C does not depend on either scale or horizon, although it depends on the underlying instance. The guarantee therefore approaches one as volume grows, without requiring the operating horizon to grow too. This is a bound on the relative gap: the absolute loss in expected net value per unit time is bounded independently of s, not shown to vanish as 1/s.

Without GPG, the authors establish a weaker bound of at least 1 − C/√s. Both statements are bounds on expected performance, not promises about every individual realization.

The proof focuses on critical queues. Using the dual solution, the authors express the loss relative to the benchmark entirely through critical agents still waiting at the deadline and critical agents lost through abandonment. Noncritical queues can be large without contributing to this particular regret expression. Under GPG, the longest-queue rule keeps the expected critical-queue norm bounded independently of market size and time, while the benchmark grows proportionally with s.

Numerical evidence and its scope

The authors compare their policy with matching-rate-based and priority-ordering policies that act at scheduled reviews. They test three networks, scales from 10 to 200 in increments of 10, and 100 independent replications per scale over a horizon of 100.

Two networks are bipartite, with four types on each side; one satisfies GPG and one does not. The third is non-bipartite, with ten types and 24 compatible pairs, and satisfies GPG. The authors report higher approximation ratios for their policy across all tested scales and review intervals. Fitted convergence slopes in the bipartite cases are consistent with their theoretical rates.

These experiments concern specified model instances, not field deployments. The guarantees rely on Poisson arrivals, exponential patience and the stated terminal-cost convention. The faster rate additionally requires GPG; it is not a universal consequence of choosing long queues.