Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Optimal Metric Distortion for Matching on the Line
31 Jan 2025
Abstract
We study the distortion of one-sided and two-sided matching problems on the
line. In the one-sided case, $n$ agents need to be matched to $n$ items, and
each agent's cost in a matching is their distance from the item they were
matched to. We propose an algorithm that is provided only with ordinal
information regarding the agents' preferences (each agent's ranking of the
items from most- to least-preferred) and returns a matching aiming to minimize
the social cost with respect to the agents' true (cardinal) costs. We prove
that our algorithm simultaneously achieves the best-possible approximation of
$3$ (known as distortion) with respect to a variety of social cost measures
which include the utilitarian and egalitarian social cost. In the two-sided
case, where the agents need be matched to $n$ other agents and both sides
report their ordinal preferences over each other, we show that it is always
possible to compute an optimal matching. In fact, we show that this optimal
matching can be achieved using even less information, and we provide bounds
regarding the sufficient number of queries.
Metrics
4 Record Views
Details
- Title
- Optimal Metric Distortion for Matching on the Line
- Creators
- Aris Filos-RatsikasVasilis GkatzelisMohamad LatifianEmma RewinskiAlexandros A Voudouris
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991022026419304721