Metraipolis › archive › dc_4bbf0cd531da

Longest-Queue Policies in Dynamic Matching with Abandonments — arXiv:2611.01431

Source

arXiv (en)

Original

https://arxiv.org/abs/2611.01431

License (as archived)

CC0-1.0

Archived

2026-11-03T18:45:25.305Z

SHA-256 of the archived text

399525d3ba083288b6e1829bca7bf9be909c431fc70e379d38a97acf3d89c73d

Stable URL of this page

https://metraipolis.com/documento/dc_4bbf0cd531da

How to cite

Longest-Queue Policies in Dynamic Matching with Abandonments — arXiv:2611.01431 — arXiv (en), https://arxiv.org/abs/2611.01431 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4bbf0cd531da (Metraipolis archive dc_4bbf0cd531da, sha256 399525d3ba083288b6e1829bca7bf9be909c431fc70e379d38a97acf3d89c73d)

@misc{dc4bbf0cd531da,
  title = {Longest-Queue Policies in Dynamic Matching with Abandonments — arXiv:2611.01431},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01431},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4bbf0cd531da; sha256 399525d3ba083288b6e1829bca7bf9be909c431fc70e379d38a97acf3d89c73d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01431. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Theoretical Economics (econ.TH); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2611.01431 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:14:37.759Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).