CS Paper Radar

Stability in stochastic hypergraph matching III: general reneging

Doan Dai Nguyen, Ana Bušić

cs.DM math.PR ·submitted 2026-09-14 13:20 UTC · v1

Abstract

In many real-life matching problems, waiting agents might abandon before being matched, such as patients deceasing before receiving organs, passengers/drivers cancelling ride requests, or raw materials/intermediary products degrading in production lines. This poses the need for incorporating reneging in stochastic matching models. In this work, we consider matching models on hypergraphs with batch arrivals and general-weight matchings. Since our model allows fractional weights, we may not be able to talk about individual items, and thus reneging is not required to be independent between items of the same class. For the simplicity sake's, we assume items arrive at discrete time. We show that stability depends on the exact nature of reneging, in stark contrast with the non-reneging case where it depends on the arrivals only through the arrival rates. To our best knowledge, this is the first such sensitivity result in stochastic matching. We uncover a new stabilising mechanism which exists neither in the non-reneging case nor in the graph case, which explains why incorporating reneging in stochastic matching is not straightforward. Together with balancing mechanism as hinted in the online assignment framework for the non-reneging case, it gives a criterion necessary and sufficient for stability. Finally, whilst verifying stability is a hard problem, we give a family of MaxWeight-type policies parameterised by $\varepsilon > 0$, which are maximally stabilising for all $\varepsilon$ sufficiently small. Unfortunately there is no effective bound for $\varepsilon$, but we show how to adjust its value during implementation.

Comment
43 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching

cs.GT cs.DS ·2026-09-28 ·Arghya Chakraborty, Varun Gupta
similarity 0.65
Abstract · Appearing in WINE 2026

In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the users care only about receiving service (matched vs. unmatched) and not which offline resource serves them, while the platform's objective is to maximize total matching reward. This captures applications such as ride-sharing where the users primarily care about being matched to a ride while the platform internalizes the cost of dispatching a distant driver; dispatching homogeneous service requests to heterogeneous servers (cloud/edge routing); and assigning customer requests to a pool of providers with different flexibility (e.g., English-only vs. bilingual agents). Our main question is: \textit{Is constant-competitive matching possible for incentive-compatible, random-order edge-weighted matching on complete bipartite graphs?} Motivated by the LP-based treatment of incentive compatibility in the classical secretary problem by Buchbinder et al., we impose a constraint that the ex ante probability of selection is equalized across all arrival positions. We answer our main question in the affirmative and propose the first constant-competitive algorithm for incentive compatible edge-weighted random-order online matching on complete bipartite graphs. The competitive ratio of our algorithm is parameterized by the imbalance factor $k := n/m$ -- where $n$ and $m$ are the numbers of online and offline nodes, respectively, and $k$ is a positive integer. In particular, we obtain a competitive guarantee of the form $c_k - O(1/\sqrt{m})$ where $c_1 \approx 0.162$ and $c_k \to 0.02308\ldots$ as $k \to \infty$. We also present algorithms with strictly improved competitive ratio of $\approx 0.07 + O(1/m)$ for the binary-weighted case ($0$-$1$ rewards).

0.05

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

cs.DS cs.CCcs.GTecon.TH+1 ·2026-10-09 ·Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon
benchmarktheory similarity 0.61
Abstract

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.

0.39

Online Matching in Convex Bipartite Graphs

cs.DS ·2026-09-04 ·Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu
similarity 0.59
Abstract · 29 pages

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs under irrevocable decisions and adversarial arrivals. We first show that convexity alone does not improve the classic worst-case guarantee of 1-1/e, achieved by Ranking. We then consider the uniform-length model, in which every online request has exactly d consecutive offline neighbors. We propose Flip, which uses one random bit to commit ex-ante to either earliest-feasible assignment or latest-feasible assignment. Although either natural deterministic policy can waste capacity and be asymptotically only 1/2-competitive, we show that their randomized mixture is 2/3-competitive. This guarantee is tight for Flip and remains valid against a semi-adaptive adversary that observes the selected policy before choosing the arrival order. We also prove that no randomized online algorithm can achieve a competitive ratio strictly larger than 3/4 in the uniform-length model.

0.10

Computational Hardness of Online Stochastic Matching

cs.DS cs.CCcs.GT ·2026-11-17 ·Yifeng Teng, Zongjun Yang
theory similarity 0.59
Abstract

In the online stochastic matching problem on a bipartite graph, offline vertices are given in advance, and online requests arrive sequentially from known distributions, each matched immediately and irrevocably to a free neighbor or rejected. Computational hardness results of the optimal online strategy have been known only for instances where online vertices have a fixed arrival order [Papadimitriou et al., 2024]. For random-order arrivals or even i.i.d. arrivals, it has been long open since the problem was proposed [Feldman et al., 2009]. In this paper, we give the first computational hardness results for online stochastic matching with random-order arrivals. In particular, we prove that for known i.i.d. arrivals, computing the online optimum is APX-hard, ruling out a Polynomial-Time Approximation Scheme unless P = NP, even in unweighted graphs with two offline neighbors per online vertex. For random-order arrivals, even when there is only one offline node (i.e., the prophet secretary setting), computing the optimal online policy is #P-hard, resolving an open problem since [Dütting et al., 2023].

0.24

Matching in Random-Order Streams via Historical Deletion Bounds

cs.DS ·2026-11-12 ·Alireza Farhadi, Mohammadtaghi Hajiaghayi, Mohammad Mahdavi
theory similarity 0.59
Abstract · 38 pages, including appendices

We study maximum matching when the edges of a fixed graph arrive in a uniformly random order. For any fixed $\varepsilon>0$, we give a one-pass algorithm that achieves, with high probability over the arrival order, approximation ratios of $0.71295$ for unweighted graphs and $0.71295-\varepsilon$ for weighted graphs, using near-linear space with an explicit charge for weight precision. Both approximation ratios hold for bipartite and general graphs. The algorithm does not require the stream length or the weight range in advance. The main structural ingredient is a historical deletion inequality for weighted matchings. The deletion price of a vertex set is the decrease in maximum matching weight when that set is removed. We bound the sum of these prices for pairwise disjoint vertex sets, even when each price is evaluated at a different stage as edges are added to the graph. Applied to the usual unfolding of integer weights, it transfers a bipartite cardinality certificate to an original weighted matching, even when the original graph is not bipartite. This transfer preserves the approximation coefficient. We combine this transfer with a refined analysis of fractional matchings in the two auxiliary graphs arising in the transfer theorem. An exact rational linear-programming certificate proves the stated constant for every feasible graph profile. The approximation guarantees and the new structural results are formally verified in Lean.

0.41

Online Matching with Arbitrary Stochastic Rewards

cs.DS math.OC ·2026-11-02 ·Rajan Udwani
benchmark similarity 0.59
Abstract

Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.

0.07

Degree Stability of Parallel Greedy Matching in Random Graphs

cs.DM cs.DSmath.PR ·2026-10-18 ·Vishvajeet N, Shrinidhi Teganahally Sridhara
hot direction similarity 0.59
Abstract · 49 pages

We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for $Θ(\log^{1+ε} n)$ rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of $\mathbb{G}(n,p)$ yields $O(1)$ variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for $Ω(\log^{1+ε} n)$ rounds.

0.27

Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

cs.DS ·2026-09-22 ·Sara Ahmadian, Edith Cohen, Mohammad Roghani
benchmark similarity 0.58
Abstract

Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.

0.08