One sided matching achieves sublinear metric distortion with new method

Sublinear Metric Distortion for Matching

Computer Science and Game TheoryDiscrete MathematicsData Structures and Algorithms

Summary

Matching people to items based on how close they are is hard when only orderings of preferences are known, not exact distances. Previous methods guaranteed a total distance within a factor proportional to the number of people, which can be very large. The authors introduce a new matching method that improves this to grow slower than the number of agents, the first time this has been done. Their approach cleverly combines partial pickings with a clustering technique to ensure unmatched people get nearby items. They also clarify how well commonly used methods perform and give limits on truthful methods.

What this means in practice

  • For marketplace platform developers: Design matching algorithms that assign items to agents based on ranked preferences with better guarantees on overall closeness even without knowing exact distances.
  • For online service matching teams: Improve user-item assignment methods where only preference rankings are available, reducing total mismatch in large-scale recommendation or allocation systems.

Authors

Moses Charikar, Alireza Haqi, Jabari Hastings, Yichen Huang, Prasanna Ramakrishnan

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.