PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon

arXiv:2610.12991v1cs.DScs.CCcs.GTecon.THmath.OC

TL;DR

Dynamic matching requires choosing whom to match while agents arrive and may abandon. This paper develops primal and dual approaches to static priorities, proving a polynomial-time policy achieves at least half of the omniscient benchmark.

  • Problem

    The central challenge is choosing matches while weighing their immediate rewards.

    Source: §1 · p. 3

  • Method

    The primal approach derives priority lists from tight LP constraints, while the dual assigns per-type values through a fixed-point equation and ranks matches by surplus.

    Source: §1.3 · pp. 8–9

  • Results

    At least half of the omniscient benchmark is achieved by a deterministic polynomial-time static priority policy.

    Source: §1.3 · p. 9, §7 · p. 33

  • Takeaways & Limitations

    The half-benchmark guarantee is the best possible guarantee for online policies.

    Source: §7 · p. 33

    Restricting allowed matches to M preserves a policy lower-bound certificate but does not necessarily provide a comparison with the omniscient benchmark.

    Source: §5.4 · p. 29

Abstract

from arXiv · show

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

1 Introduction

The paper studies polynomial-time static priority policies for dynamic matching under uncertain arrivals and abandonment, including primal and dual approaches that achieve a 1/2 guarantee. It characterizes a value-based dual policy through a fixed-point equation and connects the approaches through LP duality.

1 Introduction

  • Dynamic matching with abandonment models agents of different types arriving and waiting for compatible matches, while uncertain departures make both matching choices and timing consequential.Matching forecloses other possible pairings, while waiting can thicken the market but risks an agent abandoning before a better partner arrives.Source: §1 · pp. 3–4

1.1 Competitive Analysis and State of the Art

  • 0.192 was the best known guarantee for the general model before this work, while greedy and batching policies face scarcity and abandonment risks.These gaps motivate asking whether a simple, polynomial-time priority policy can achieve the best possible guarantee in full generality.Source: §1.1 · pp. 4–6

1.2 Main Result: Static Priority Policies Offer Optimal Guarantees

  • 1/2 of the omniscient benchmark is guaranteed by a polynomial-time static priority policy, and no online policy can guarantee more.This establishes an optimal competitive ratio of exactly 1/2 for the general model; the result extends to markets with arbitrarily many types on both sides, non-bipartite compatibility, and order-dependent rewards.Source: §1.2 · p. 6

1.3 Summary of the Techniques

  • A lower bound on the probability that some agent in a set is waiting supports a linear-programming sandwich that bounds policy reward below and the omniscient benchmark above.The availability bound is at least the expected number of waiting agents in the set times an explicit rate-dependent constant; its proof uses independence of irrelevant alternatives and the Slivnyak–Mecke formula.Source: §1.3 · pp. 7–8
  • The primal approach derives priorities from tight availability constraints, then prunes unused matches to obtain a suitable policy without lowering the program’s value.Diminishing returns makes tight sets nested, and polynomial-time pruning yields a policy whose reward is at least half the omniscient benchmark’s LP upper bound.Source: §1.3 · pp. 8–9
  • The values are the unique solution of a fixed-point equation that balances abandonment losses against estimated surplus, and the solution is efficiently computable in polynomial time.A damped version of the map contracts under a weighted norm, enabling a polynomial-time Ellipsoid-based algorithm.Source: §1.3 · p. 9
  • A tight dual certificate for LPLB(π) shows that its static priority policy earns at least half the omniscient benchmark, yielding a polynomial-time 1/2-competitive value-based policy.LPLB(π) lower-bounds the policy’s long-run average reward, and reversing its dual inequalities provides the benchmark upper-bound certificate.Source: §1.3 · p. 9
  • The primal and dual approaches connect through LPPOL(M): its optimal shadow prices equal the restricted fixed point vM when an optimal solution is suitable, but not necessarily otherwise.The restricted fixed point is always feasible for the dual; suitability makes the optimal shadow prices unique and equal to vM.Source: §1.3 · pp. 9–10
  • For allowed-match sets M with LPPOL(M) ≥ LPPOL(T × T), restricted value-based policies using vM earn at least half the omniscient benchmark and include both approaches.By complementary slackness, the primal policy ranks allowed matches by their scores under vM; it may differ from the unrestricted dual policy.Source: §1.3 · p. 10

2 Preliminaries

The preliminaries define a continuous-time matching model with Poisson arrivals, exponential abandonment, and type-dependent rewards, then formalize its hindsight benchmark. They introduce Poisson-process facts and a linear-programming relaxation that upper-bounds that benchmark.

2.1 Model and Notation

  • The model has finitely many types with independent Poisson arrivals, exponential sojourn times, and possibly asymmetric rewards for ordered pairs of types.Online policies use only information revealed so far and make irrevocable matches; availability depends on whether a present agent has already been matched.Source: §2.1 · pp. 10–11

2.2 Background on Poisson Processes

  • At each time, present agents of a type have a Poisson count, independent across types; Poisson arrivals also see the system's time-average state frequencies.The present-count result bounds availability under any policy because an agent can be available only while present.Source: §2.2 · p. 12

2.3 Benchmark and Guarantee

  • The omniscient benchmark matches optimally in hindsight after observing the realized arrivals and abandonments, and bounds every policy's performance.For each horizon, it is the expected maximum-weight matching value of the compatibility graph divided by the horizon.Source: §2.3 · p. 13
  • LPOMN upper-bounds the omniscient benchmark using match-rate variables, type-supply constraints, and constraints on matches requiring an earlier agent from a given type set.The constraints account for the fact that a match with a set requires some agent from that set to be present.Source: §2.3 · pp. 13–14

3 Static Priority Policies

Static priority policies rank acceptable partner types for each arriving type, then match an arrival to the highest-priority available type or let it wait. The section establishes a stochastic availability bound and uses policy properties to motivate LP-based approaches for finding high-reward priorities.

Static priority policies

  • A static priority policy gives each arriving type a strict order over acceptable partner types and matches to the highest-priority available type, or waits if none is available.A match always pairs a new arrival with a waiting agent.Source: §3 · pp. 14–15
  • In stationarity, priority-list prefix sets attain equality in the policy's availability constraint.The policy's long-run analysis uses expected available counts and match rates, with balance and availability properties.Source: §3 · pp. 15–16
  • For any type set S, the probability that at least one agent from S is available is at least γ_S times the expected number available from S.The bound is tight when agents in S are never matched; if availability is rare, the lemma's interpretation is that types in S must be matching at high rates.Source: §3 · pp. 16–17
  • The primal approach reads priorities from tight availability constraints in LPPOL(M), making tight sets prefixes of priority lists.A polynomial-time pruning procedure finds a suitable solution without lowering the program's value, and the resulting policy earns at least that value.Source: §3 · p. 18
  • The dual approach assigns each type an opportunity-cost value and prioritizes matches by reward minus the values of both types.A unique, polynomial-time-computable fixed point supplies values satisfying the dual conditions for the policy guarantee.Source: §3 · p. 18
  • The primal and dual approaches are mathematically linked through linear programming duality.The dual of LPPOL(M) assigns shadow prices to types and recovers the restricted fixed point.Source: §3 · p. 18

4 Primal Approach

The primal approach uses policy linear programs to identify a static priority policy and bound its reward. A polynomial-time construction yields a consistent policy earning at least half the omniscient benchmark.

4.1 A Novel Family of Linear Programs

  • The policy LP optimum is at least half the omniscient LP value, since halving any feasible omniscient solution yields a feasible policy-LP solution.Source: §4.1 · p. 20

4.2 Identifying a Policy and Bounding Its Performance

  • Consistency restricts matches to positive-rate pairs and makes tight availability sets prefixes; any consistent policy for an optimal solution earns at least its LP value.Source: §4.2 · p. 20

4.3 Finding a Suitable Solution

  • A polynomial-time construction yields a consistent static priority policy earning at least half the omniscient benchmark.Source: §4.3 · pp. 21, 23
  • Tight availability sets are nested, and suitability requires positive match rates for every type in each tight set; pruning zero-rate pairs preserves or increases LP value.Source: §4.3 · p. 22
  • Submodularity provides a separation oracle for exponentially many availability constraints, enabling polynomial-time solution of each policy LP and the pruning procedure.Source: §4.3 · pp. 22–23

5 Dual Approach

The dual approach assigns each type an opportunity-cost value and ranks matches by surplus, using linear-programming duality to certify static priority policies.

5.1 Value-Based Certificates

  • A policy-specific lower-bound linear program uses nonnegative type values and prefix weights to certify policy reward through weak duality.Source: §5.1 · pp. 24–26

5.2 Bounding the Omniscient Benchmark via Values

  • Reversing the certificate inequalities yields dual-feasible values that upper-bound the omniscient benchmark by twice their arrival-rate-weighted total.Source: §5.2 · p. 26

5.3 Satisfying Both Requirements via a Fixed Point

  • The values are the unique fixed point balancing abandonment value loss against estimated availability surplus; partner priorities follow reward minus the values of the matched types.Source: §5 · p. 23, §5.3 · pp. 27–28
  • For unrestricted matches, a polynomial-time-computable value-based static priority policy earns at least half the omniscient benchmark.Source: §5.3 · p. 28

5.4 Discussion: A Family of Optimally Competitive Value-based Policies

  • Properly chosen restricted match sets yield another half-competitive policy class, including the primal policy for Algorithm 1’s pruned set; arbitrary sets need not preserve the guarantee.Source: §5.4 · pp. 28–29

6 Primal Meets Dual: Connections and Computations

The section connects the primal LP and dual fixed-point approaches: under a suitable primal optimum, the same restricted fixed-point values explain the priorities and can be recovered through the dual LP. It also establishes polynomial-time computation of these values and the resulting policy.

6 Primal Meets Dual: Connections and Computations

  • The primal priorities and dual fixed-point values are directly connected: a suitable primal solution yields a policy that is value-based on the restricted match set.The primal approach reads priorities from tight availability constraints, while the dual approach uses fixed-point values; the connection also makes the LP dual an alternative way to compute the restricted fixed point.Source: §6 · pp. 29–30

6.1 Suitability and Recovering the Restricted Fixed Point via LP

  • LPPOL(M) has a suitable optimal solution if and only if its dual uniquely recovers the restricted fixed point vM and associated weights; arbitrary M need not have this property.For an arbitrary M, optimal dual values may fail to be a fixed point and the resulting value-based policy may earn less than LPPOL(M).Source: §6 · p. 30, §6.1 · p. 31

6.2 The Primal Policy Is a Value-Based Policy

  • Every static priority policy consistent with a suitable primal optimum is value-based on M: it accepts positive-score matches and ranks acceptable partners by decreasing score.For Algorithm 1’s set M, every pair has nonnegative score, and the policy may also accept zero-score matches.Source: §6.2 · pp. 31–32

6.3 Computing Values in Polynomial Time via LP

  • For the set M returned by Algorithm 1, the dual LP recovers vM and yields a consistent static priority policy satisfying (22), all computable in polynomial time.The dual can be solved with polynomially many nonzero weights; vM is restricted to M and need not solve the unrestricted fixed-point equation.Source: §6.3 · p. 32

7 Conclusion

The paper proves that a deterministic static priority policy computable in polynomial time earns at least half of the omniscient benchmark, the best possible guarantee for online policies. It closes by identifying further settings and objectives to study.

7 Conclusion

  • A deterministic static priority policy computable in polynomial time earns at least half of the omniscient benchmark, which is the best possible guarantee for online policies.The primal approach reads priorities from tight LP constraints, while the dual approach computes type values as a unique fixed point and ranks matches by score; both rely on the same availability lower bound.Source: §7 · p. 33
  • The authors propose that the availability bound and analysis tools may prove useful in other stochastic matching and resource-allocation problems where simple policies are desirable.Source: §7 · p. 33
  • The authors identify improving the ratio against the optimal online policy, learning unknown model parameters, and extending to broader arrivals, sojourn times, and time-varying rewards as future directions.Source: §7 · p. 33

Disclosure of AI Usage

The authors disclose that an AI system helped discover a proof later verified and simplified by the authors.

Disclosure of AI Usage

  • OpenAI’s Codex Astra first found the proof of Proposition 5.4 after prompting rounds; the authors verified and simplified it, and report that other results are their own.AI tools were otherwise used only to edit the writing.Source: Disclosure of AI Usage · p. 33

A Further Related Work

The related work distinguishes this model from adjacent matching, queueing, prophet-inequality, and allocation literatures. It emphasizes that the paper’s guarantee applies to every instance, without large-market or reward-structure assumptions.

A Further Related Work

  • Earlier dynamic-matching-with-abandonment work used LP bounds and randomized policies, while this paper extends subset availability constraints to the general model.Collina et al. (2020) and Aouad and Sarıta¸c (2022) introduced the model; AmaniHamedani et al. (2026) strengthened relaxations to subsets of waiting types.Source: A Further Related Work · p. 39
  • Adjacent prophet-inequality work studies richer feasibility constraints and pricing or online-rounding methods, while this paper uses static priorities for dynamic matching with abandonment.The paper frames its result as an analogue of the single-item half guarantee.Source: A Further Related Work · p. 39
  • Unlike asymptotic priority results or policies relying on reward conditions, this guarantee needs neither a large market nor structural assumptions on rewards and also covers thin markets.Aveklouris et al. (2025) establish asymptotic optimality under increasing patience hazard rates; Hu and Zhou (2022) require certain reward conditions.Source: A Further Related Work · pp. 40–41
  • Without abandonment, some static-priority results achieve hindsight optimality under network structure; with abandonment, even a single-good prophet setting caps online guarantees at half.Source: A Further Related Work · p. 41
  • Other literatures target different objectives or settings, including unmatched-agent rates, reusable resources, and application-specific questions such as fairness and empirical performance.The paper contrasts its multiplicative, every-instance guarantee with these related approaches.Source: A Further Related Work · pp. 40–41

B Poisson Processes: Definitions and Proofs

This appendix formalizes the Poisson-process tools used in the analysis and proves results about agent counts and the states observed at arrivals. Independent exponential sojourn times turn each type’s arrivals into a marked Poisson process.

B Poisson Processes: Definitions and Proofs

  • A Poisson process is defined by Poisson counts on measurable sets and independence of counts on disjoint sets; independent marks produce a process with rate λ(s)f(y).The appendix includes these definitions and marking property as background for the proofs.Source: B Poisson Processes: Definitions and… · pp. 41–42
  • Independent exponential sojourn times mark each type’s Poisson arrivals into a Poisson process of arrival-time and sojourn-time pairs.The resulting rate is given by the arrival rate multiplied by the sojourn-time density.Source: B Poisson Processes: Definitions and… · p. 42
  • At any fixed time, each type’s number of present agents is Poisson, and these counts are independent across types.Lemma 2.1 is derived by counting arrival-sojourn pairs corresponding to agents still present.Source: B Poisson Processes: Definitions and… · p. 42
  • The appendix proves Corollary 2.2 (PASTA) for online policies, including policies randomized independently of arrivals and sojourns.Its proof applies the history-based corollary conditionally on the policy’s independent randomization.Source: B Poisson Processes: Definitions and… · p. 43

C.1 Omitted Proofs from Section 2

The appendix proves that the omniscient benchmark is bounded above by LPOMN. Its constraints encode matching supply and the availability of agents who arrived earlier.

C.1 Omitted Proofs from Section 2

  • For every instance, the omniscient benchmark satisfies OMN ≤ LPOMN.The proof bounds any hindsight policy using supply and presence constraints.Source: §C.1 · p. 43
  • The OMN-Supply constraint follows because each type-j agent can be matched at most once, while expected type-j arrivals over time have rate λj.The proof takes expectations and divides by the time horizon.Source: §C.1 · pp. 43–44
  • The OMN-Presence constraint counts matches that pair an arriving type-j agent with an earlier type-i agent still present at arrival.The proof compares the type-i agents present with agents from a set S present at that time.Source: §C.1 · p. 44
  • At time s, type-i agent counts are independent Poisson variables with means at most λi/µi, providing the population bound used in the argument.Their means are λi/µi times (1 − e^(−µi s)).Source: §C.1 · p. 44

C.2 Omitted Proofs from Section 3

These proofs establish stationary-state properties of static priority policies, derive the stochastic availability bound used in the analysis, and show that an optimal LPPOL(M) solution can be realized by a consistent policy.

C.2 Omitted Proofs from Section 3

  • Every static priority policy induces an ergodic continuous-time Markov chain with a unique stationary distribution.The proof uses a drift argument to establish ergodicity and convergence to stationarity.Source: §C.2 · pp. 44–45
  • Static priority policies satisfy IIA: if an added agent remains available, the rest of the system reaches the same state as without that agent.The proof verifies this by comparing the systems under the same original arrivals and sojourn times.Source: §C.2 · p. 47
  • The IIA lemma yields a lower bound on the probability that some type in S is available, with equality when S is a priority prefix.The proof connects availability to the event that a type in S is present and matched, and establishes equality for prefixes.Source: §C.2 · pp. 45–48

C.3.1 Proofs from Section 4.2

  • A static priority policy consistent with an optimal LPPOL(M) solution earns at least the value of that linear program.The proof constructs a feasible point by combining the LP solution with the policy’s steady-state quantities.Source: §C.3.1 · pp. 49–50

C.3.2 Proofs from Section 4.3

The proofs establish structural properties of LPPOL(M) that characterize consistent priority policies and enable polynomial-time optimization. They also connect prefix weights to the dual program through weak duality.

C.3.2 Proofs from Section 4.3

  • For feasible (n, x), the relevant sets Pj(n, x) are nested, and condition (8) characterizes when the solution is suitable.The condition requires xij > 0 for each i in a set S ∈ Pj(n, x); these sets can be made prefixes of a consistent priority order.Source: §C.3.2 · pp. 50, 52
  • The proof establishes submodularity of Ψj, a structural property used to minimize the availability constraints efficiently.It derives this from the increasing, strictly supermodular set function f.Source: §C.3.2 · pp. 50–51
  • An optimal solution of LPPOL(M) can be computed in time polynomial in the input size.The proof uses a submodular-function minimization oracle to separate the exponentially many availability constraints.Source: §C.3.2 · p. 52

C.4.1 Proofs from Section 5.2

  • The Section 5.2 proof extends prefix weights by zero outside policy prefixes, making (v, z) feasible for DLPOMN and allowing weak duality to apply.The proof then uses the dual constraint and an algebraic sum involving γSρ(S).Source: §C.4.1 · pp. 52–53

C.4.2 Proofs from Section 5.3

The section proves that each restricted map has a unique nonnegative fixed point computable in polynomial time, and connects fixed points to static priority policies satisfying the stated constraints.

C.4.2 Proofs from Section 5.3

  • The damped map F_θ preserves the fixed points of F_M and is a contraction, enabling the existence and uniqueness proof.Its contraction factor is κ = 1 − 1/(8L^2) < 1.Source: §C.4.2 · pp. 55–56
  • Each restricted map F_M has a unique nonnegative fixed point v_M, computable in polynomial time.The proof uses a damped contraction and then recovers the fixed point exactly.Source: §C.4.2 · pp. 56–57
  • The fixed point can be approximated and then recovered exactly in polynomial time using the piecewise-affine structure of F_M.The proof combines contraction-based approximation with rational reconstruction.Source: §C.4.2 · pp. 56–57
  • A vector v satisfies the policy constraints for a static priority policy exactly when F(v) = v, with consistent policies using the constructed prefix weights.The policy ranks positive residual scores in nonincreasing order; zero-score matches may be placed last.Source: §C.4.2 · pp. 57–58

C.4.3 Proofs from Section 5.4

The proofs relate restricted fixed points and their prefix weights to feasible priority policies, while identifying a condition needed to transfer the unrestricted result. They also record complementary-slackness properties used in the proofs from Section 6.

C.4.3 Proofs from Section 5.4

  • For a priority policy consistent with v_M, the constructed fixed-point values and prefix weights satisfy the primal constraints with equality, yielding the stated policy bound.The proof establishes feasibility and applies Proposition 5.1.Source: §C.4.3 · p. 59
  • Excluded matches must have nonpositive scores under v_M for the unrestricted fixed point and restricted fixed point to agree.With this condition, removing excluded matches leaves the map unchanged at v_M, and policies rejecting zero-score matches can make the same decisions.Source: §C.4.3 · pp. 59–60

C.5 Omitted Proofs from Section 6

  • The omitted Section 6 proofs use complementary slackness: positive dual weights make availability constraints tight, and positive primal match variables make reward constraints tight.The dual constraints indexed by types hold with equality at every optimum.Source: §C.5 · p. 60

C.5.1 Proofs from Section 6.1

The section characterizes when the primal LP has a suitable optimal solution through the structure of optimal dual solutions. Under these conditions, the dual optimum is unique and consists of the restricted fixed point and its associated weights.

C.5.1 Proofs from Section 6.1

  • A suitable optimal solution to LPPOL(M) is equivalent to every optimal dual solution satisfying z* = Z^M(v*).These are the two conditions stated as equivalent in Proposition 6.1.Source: §C.5.1 · p. 60
  • When the conditions hold, the unique optimal dual solution consists of the restricted fixed point v_M and its associated weights Z^M(v_M).The proof identifies any optimal v* with v_M through the fixed-point equation.Source: §C.5.1 · pp. 60, 62
  • The optimal dual weights are the residual-score prefix weights, obtained as successive differences between distinct positive scores.The proof shows z* = Z^M(v*) for every nonempty subset, with other weights zero.Source: §C.5.1 · p. 61

C.5.2 Proofs from Section 6.2

The proofs connect policies consistent with a suitable primal solution to the restricted fixed point, then establish polynomial-time computation of a sparse optimal dual solution.

C.5.2 Proofs from Section 6.2

  • Every static priority policy consistent with a suitable optimal primal solution is also consistent with M and v_M.The proof uses complementary slackness to establish the policy's acceptance and ranking conditions.Source: §C.5.2 · p. 62
  • Positive residual scores induce ranked prefixes, linking the policy's priority ordering to the restricted fixed point's dual weights.The proof shows that these score-based prefixes have positive dual weight and are prefixes of the policy order.Source: §C.5.2 · p. 62

C.5.3 Proofs from Section 6.3

  • An optimal solution of DLPPOL(M) with polynomially many nonzero weights can be computed in polynomial time.The proof applies the ellipsoid method to the primal LP and obtains a basic optimal dual solution supported on polynomially many generated constraints.Source: §C.5.3 · p. 63

D Additional Examples

An example shows that an optimal dual-value vector need not yield a fixed point or a policy matching the primal LP’s value. Algorithm 1 removes the obstruction and produces a better policy in this instance.

D Additional Examples

  • Optimal DLPPOL values need not be a fixed point of F, so a policy constructed from them can earn less than LPPOL.In the example, the optimal primal solution is unsuitable because type 3 is in a tight availability set for type-2 arrivals despite x*32 = 0.Source: D Additional Examples · pp. 63–64
  • The value-based policy matches type-2 pairs at ≈0.0026 versus the primal LP’s ≈0.0281, losing valuable same-type opportunities by matching type-2 agents elsewhere.A type-2 pair requires one type-2 agent to remain available until another type-2 agent arrives.Source: D Additional Examples · p. 63
  • Algorithm 1 removes the obstruction by pruning zero-rate pairs, yielding a suitable restricted LP with value ≈1.083 and a policy earning ≈1.338.It first removes (3, 2), then (1, 1), (1, 2), (2, 1), and (2, 3).Source: D Additional Examples · p. 64
Loading 2610.12991v1…