Optimal Metric Distortion for Matching on the Line

Filos-Ratsikas, Aris; Gkatzelis, Vasilis; Latifian, Mohamad; Rewinski, Emma; Voudouris, Alexandros A.

doi:10.24963/ijcai.2025/429

Optimal Metric Distortion for Matching on the Line

Aris Filos-Ratsikas, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, Alexandros A. Voudouris

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3857-3865.

https://doi.org/10.24963/ijcai.2025/429

Keywords

Game Theory and Economic Paradigms: GTEP: Computational social choice
Game Theory and Economic Paradigms: GTEP: Mechanism design

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.

Aris Filos-Ratsikas, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, and Alexandros A. Voudouris. 2025. Optimal Metric Distortion for Matching on the Line. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3857–3865. https://doi.org/10.24963/ijcai.2025/429

@inproceedings{ijcai2025p429,
  title     = {Optimal Metric Distortion for Matching on the Line},
  author    = {Filos-Ratsikas, Aris and Gkatzelis, Vasilis and Latifian, Mohamad and Rewinski, Emma and Voudouris, Alexandros A.},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3857--3865},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/429},
  url       = {https://doi.org/10.24963/ijcai.2025/429},
}

TY  - CPAPER
TI  - Optimal Metric Distortion for Matching on the Line
AU  - Filos-Ratsikas, Aris
AU  - Gkatzelis, Vasilis
AU  - Latifian, Mohamad
AU  - Rewinski, Emma
AU  - Voudouris, Alexandros A.
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3857
EP  - 3865
DO  - 10.24963/ijcai.2025/429
UR  - https://doi.org/10.24963/ijcai.2025/429
ER  -