Metraipolis › archive › dc_e1930fd6bad4

Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching — arXiv:2609.36311

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.36311
License (as archived)
CC0-1.0
Archived
2026-10-07T17:25:49.453Z
SHA-256 of the archived text
1be552dc8adca773bf4eedcf4f4c6deeb1e81c8bb6fb7b83f38ac7c6bb2b7c72
Stable URL of this page
https://metraipolis.com/documento/dc_e1930fd6bad4

How to cite

Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching — arXiv:2609.36311 — arXiv (en), https://arxiv.org/abs/2609.36311 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e1930fd6bad4 (Metraipolis archive dc_e1930fd6bad4, sha256 1be552dc8adca773bf4eedcf4f4c6deeb1e81c8bb6fb7b83f38ac7c6bb2b7c72)
BibTeX
@misc{dce1930fd6bad4,
  title = {Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching — arXiv:2609.36311},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.36311},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e1930fd6bad4; sha256 1be552dc8adca773bf4eedcf4f4c6deeb1e81c8bb6fb7b83f38ac7c6bb2b7c72},
  year = {2026}
}

Archived text

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

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).

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-30 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.36311 — 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-10-07T16:57:11.425Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).