CS Paper Radar

Decentralized Dynamic Stable Matching

Jing Chen, Mengtong Gao, Zhenhe Zhang

cs.DC ·submitted 2026-10-30 15:47 UTC · v2

Abstract

We study decentralized computing of the player-optimal stable matching under unannounced player arrivals and departures. Without a common clock, arrival/departure events information, or direct communication, players can only make individual proposals to arms and observe individual accept/reject outcomes. We measure mismatch cost --- the number of rounds in which the realized matching differs from that round's POSM, as the time horizon $T$ grows. For known preferences, we develop a deterministic polynomial-time self-calibrating protocol with mismatch cost $O(t_*+K^2\log T)$, greatly improving the existing upper-bound $O(T^{1-1/K}(\log T)^{2/K})$. $K$ is the number of arms and $t_*$ the last event time in the problem instance. Each player runs the protocol using their own local time and proposal-outcome history, without knowing~$t_*$ or $T$. More generally, configuring our protocol with a non-decreasing polynomial-time-computable function $g(t)=Ω(t)$ yields mismatch cost $O(g(t_*) + K^2 N_g(T))$, where $N_g(T)$ counts iterations of $t\mapsto t+g(t)$ below $T$. $g(t)$ reflects the protocol's convergence speed. The relationship between $g(t)$ and~$N_g(T)$ reflects the tradeoff between convergence speed and asymptotic mismatch cost. We show that any randomized protocol with convergence speed $g(t)\geq 1$ has worst-case expected cost $Ω(t_* + N_g(T))$. Thus, up to a $K^2$ factor, our protocol with $g(t)=t$ is optimal among protocols with convergence speed $O(t_*)$. For unknown preferences on both sides, each player and arm observe their own sampled utilities after being matched. We develop a decentralized learning protocol with expected mismatch cost $O(t_*+K^4Δ_{\mathrm{min}}^{-2}\log T)$, where $Δ_{\min}$ measures the preference gaps. A complementary static-setting lower-bound adapted from the literature shows that dependencies on $T$ and $Δ_{\min}$ are tight.

Closest papers

Nearest neighbours by meaning across the whole index.

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.67
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.37

A General Framework for Matching with Delays

cs.DS ·2026-10-15 ·Sara Ahmadian, Shuchi Chawla, Ravi Kumar, Manish Purohit, Shirley Zhang
theory similarity 0.65
Abstract

We present a simple deterministic $O(\log n)$-competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, where $n$ is the (unknown) number of requests. This improves upon the recent $O(\log^5 n)$-competitive algorithm of Dufay and Wattenhofer (SODA 2026) and nearly matches the $Ω(\log n / \log \log n)$ randomized lower bound of Ashlagi et al. (APPROX 2017). Our algorithmic framework rests on two ingredients: an online moat-growing process that grows active dual variables at a deliberately slowed constant rate $α< 1$ to control temporal asymmetry, and a delayed eligibility rule that matches requests in the same dual component only after their waiting time is proportional to their time-expanded distance. The framework extends naturally to arbitrary concave delay functions, maintaining an $O(\log n)$ competitive ratio, and to $k$-way matching with delays, yielding an $O(k \log n)$-competitive deterministic algorithm.

0.48

Impatience Makes Matching NP-Hard

cs.CC cs.DS ·2026-11-15 ·Chen Yan, Sushil Mahavir Varma
similarity 0.62
Abstract · 35 pages, 2 figures

Motivated by emerging applications such as online marketplaces and quantum switches, we study a dynamic bipartite matching model with impatient agents, where the two sides represent customers and suppliers. Agents of each type arrive according to an independent Poisson process, and the platform decides which pairs of agents to match. The agents are possibly impatient and may leave the system if not matched before their patience expires. The platform aims to maximize throughput, i.e., the number of matches per unit time. In this paper, we reveal an interesting phase transition in the computational hardness of throughput maximization. In particular, we show that approximating the optimal long-run throughput within a sufficiently small fixed relative error is NP-hard, even when all agents have rate-one exponential patience. This result implies a computational barrier to constructing near-optimal, efficiently executable matching policies that induce a matching process with fast mixing. On the other hand, when all agents on at least one side have infinite patience, we provide a simple polynomial-time algorithm that maximizes the throughput.

0.28

Computational Hardness of Online Stochastic Matching

cs.DS cs.CCcs.GT ·2026-11-17 ·Yifeng Teng, Zongjun Yang
theory similarity 0.62
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

Improved Bounds for Online Matching with Random Edge Arrivals

cs.DS ·2026-11-10 ·Yilong Feng, Haolong Li, Zonghan Yang
similarity 0.62
Abstract

We study the unweighted online matching problem with random edge arrivals, where each edge arrives at an independent time drawn uniformly from $[0,1]$, and the algorithm must immediately and irrevocably accept or reject it while maintaining a matching. Guruganesh and Singla (IPCO, 2017) first broke the $1/2$ barrier of the naive Greedy algorithm by giving a $(1/2+\varepsilon)$-competitive algorithm for a small constant $\varepsilon>0$, a guarantee that has remained the best known for nearly a decade. We give a simple three-phase algorithm that achieves a competitive ratio of $0.5445$ by deliberately rejecting selected early edges to reserve their endpoints for later matching opportunities. With a different choice of parameters, the same algorithm is $0.5535$-competitive on triangle-free graphs, including bipartite graphs. We also establish competitive ratio upper bounds below $0.6964$ for general graphs and $0.7043$ for bipartite graphs via exact rational evaluation of an optimal-policy recurrence on fixed graphs, even when the input graph is known up to isomorphism.

0.22

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

cs.DS ·2026-09-22 ·Sara Ahmadian, Edith Cohen, Mohammad Roghani
benchmark similarity 0.61
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

From Preference to Reciprocity: Decentralized Matching with Empirically Grounded LLM-agent Based Modeling

cs.LG cs.AI ·2026-09-28 ·Wangxuan Fan, Xiaoyu Nie, Zhoutian Shi, Xiangcheng Meng, Shipei Zeng +3 more
similarity 0.61
Abstract

Bipartite matching is a fundamental problem in game theory and market design. Classical approaches such as Gale--Shapley assume complete preferences and centralized computation, whereas many real-world matching processes are decentralized, asynchronous, and shaped by sequential interaction under limited information. We propose a dynamic bipartite matching framework that combines large language model (LLM) agents with contextual bandits. In a simulated Chinese marriage market, economically grounded LLM agents evaluate locally encountered candidates, while agent-specific Logistic-UCB models learn reciprocal acceptance from realized proposal outcomes. The mechanism therefore separates two decisions---\emph{whom do I like?} and \emph{who is likely to like me back?}---without requiring ex ante market-wide preference rankings. We first validate LLM-induced mate preferences against the empirical conditional-logit reference across multiple LLM backbones. In the $50\times50$ matching experiment, Bandit-UCB achieves the highest mean mutual welfare (56.01 versus 54.87 for Gale--Shapley), a smaller gender rank gap than the classical baselines, and the fewest blocking pairs among the LLM-ABM policies. Learned acceptance models show economically interpretable gender-differentiated associations, while counterfactual setups reveal no systematic unilateral advantage from prior search knowledge. Overall, these results support the advantages of decentralized matching with LLM-based behavioral modeling and online learning under incomplete information for economic simulation and computational social science research.

0.26

Online Matching in Convex Bipartite Graphs

cs.DS ·2026-09-04 ·Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu
similarity 0.61
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