Metraipolis › archive › dc_fa271fb0fc78

Sublinear Metric Distortion for Matching — arXiv:2611.05777

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.05777
License (as archived): CC0-1.0
Archived: 2026-11-05T18:20:20.646Z
SHA-256 of the archived text: a0c9e9d0ee9da53765e26cec070fad22ccbb4df0c82657e9c7d6cc027067b293
Stable URL of this page: https://metraipolis.com/documento/dc_fa271fb0fc78

How to cite

Sublinear Metric Distortion for Matching — arXiv:2611.05777 — arXiv (en), https://arxiv.org/abs/2611.05777 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa271fb0fc78 (Metraipolis archive dc_fa271fb0fc78, sha256 a0c9e9d0ee9da53765e26cec070fad22ccbb4df0c82657e9c7d6cc027067b293)

BibTeX

@misc{dcfa271fb0fc78,
  title = {Sublinear Metric Distortion for Matching — arXiv:2611.05777},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05777},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa271fb0fc78; sha256 a0c9e9d0ee9da53765e26cec070fad22ccbb4df0c82657e9c7d6cc027067b293},
  year = {2026}
}

Archived text

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

We study metric distortion in one-sided matching. Given $n$ agents and $n$ items in an unknown metric space, our goal is to match agents to items so that the total distance between matched pairs is small. However, instead of direct access to the distances in the metric, we are only given each agent's ranking of the items by distance. What is the smallest worst-case approximation factor (called the distortion) that a mechanism can guarantee in expectation? Despite significant interest over the last decade, the best-known guarantee has been the $O(n)$ distortion of Random Serial Dictatorship since the beginning. We give a matching mechanism with distortion $O(n^{\log_4 3})$, the first sublinear upper bound. The key idea is to use a partial matching derived from a truncated version of either Random Serial Dictatorship or the Probabilistic Serial rule. We then complete this matching using a new, general-purpose cluster completion algorithm that ensures unmatched agents receive nearby items. Along the way, we pin down the optimal distortion of Random Serial Dictatorship and Probabilistic Serial up to logarithmic and constant factors, respectively, and give improved lower bounds for truthful mechanisms.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05777 — 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-05T18:14:18.992Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).