Longest-Queue Policies in Dynamic Matching with Abandonments

Siqi He, Yehua Wei and Jiaming Xu

Papers from arXiv.org

Abstract: We study a dynamic two-way matching market in which agents of heterogeneous types arrive over time, wait to be matched according to a compatibility network, and abandon the system if their random patience expires. The decision maker collects match rewards and pays holding and abandonment costs, and seeks to maximize the expected net value over a finite horizon. We evaluate policies by their approximation ratio against a fluid benchmark, the optimal value of a linear-programming relaxation that upper bounds the expected net value of every policy. Under a general position gap (GPG) condition, which requires the unique optimal dual solution of this linear program to remain optimal under small perturbations of the arrival rates, we propose a longest-queue policy. The policy first uses this dual solution to identify a set of good match types and a set of critical agent types. Upon each arrival, it considers only good matches and matches the arrival to the critical partner with the longest queue subject to availabilities. In the high-volume regime, in which arrival rates are scaled by s, we prove that the policy attains an approximation ratio of at least 1-O(1/s) at every scale s >= 1 and every horizon T >= 1, so the ratio tends to 1 as s goes to infinity.

Date: 2026-11
References: Add references at CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2611.01431 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2611.01431

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().