arXiv preprint ·
Sublinear Metric Distortion for Matching
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.