Sublinear Metric Distortion for Matching

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Sublinear Metric Distortion for Matching

# 概要
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…

# 原典
https://arxiv.org/abs/2611.05777

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。