Journal article · 2026 · Open access

Optimal metric distortion for matching on the line

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

Artificial Intelligence, 361, 104630 · Published 7 October 2026 · DOI 10.1016/j.artint.2026.104630

Open PDFView at the publisherCite this paper

In brief

“Optimal metric distortion for matching on the line” is a 2026 journal article by Aris Filos-Ratsikas and 4 co-authors, published in Artificial Intelligence. OpenAlex counts 1 citations as of 16 November 2026, which puts it in the top 9% of works published in 2026 by citations. It is open access under a CC BY-NC-ND licence: the full text is free to read at Artificial Intelligence.

Citations
1
Most cited in
2026 (1)
Field-weighted impact
4.26
References
24
Authors
5

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.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Filos-Ratsikas, A., Gkatzelis, V., Latifian, M., Rewinski, E., & Voudouris, A. A. (2026). Optimal metric distortion for matching on the line. Artificial Intelligence, 361, 104630. https://doi.org/10.1016/j.artint.2026.104630

MLA 9

Filos-Ratsikas, Aris, et al. “Optimal metric distortion for matching on the line.” Artificial Intelligence, vol. 361, 2026, p. 104630. https://doi.org/10.1016/j.artint.2026.104630.

Chicago

Filos-Ratsikas, Aris, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, and Alexandros A. Voudouris. 2026. “Optimal metric distortion for matching on the line.” Artificial Intelligence 361: 104630. https://doi.org/10.1016/j.artint.2026.104630.

Harvard

Filos-Ratsikas, A. et al. (2026) ‘Optimal metric distortion for matching on the line’, Artificial Intelligence, 361, p. 104630. doi:10.1016/j.artint.2026.104630.

IEEE

A. Filos-Ratsikas, V. Gkatzelis, M. Latifian, E. Rewinski, and A. A. Voudouris, “Optimal metric distortion for matching on the line,” Artificial Intelligence, vol. 361, p. 104630, 2026, doi: 10.1016/j.artint.2026.104630.

BibTeX

@article{filosratsikas2026optimal,
  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.},
  journal   = {Artificial Intelligence},
  year      = {2026},
  volume    = {361},
  pages     = {104630},
  doi       = {10.1016/j.artint.2026.104630},
  url       = {https://doi.org/10.1016/j.artint.2026.104630}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Topic and keywords

Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems

  • metric distortion
  • one-sided matching
  • two-sided matching
  • ordinal preferences
  • social costs
  • approximation algorithms
  • query complexity
  • mechanism design

Work with this paper

Most-cited papers in Economics, Econometrics and Finance

All highly cited Economics, Econometrics and Finance papers

Questions about this paper

How do I cite this paper in APA style?

Filos-Ratsikas, A., Gkatzelis, V., Latifian, M., Rewinski, E., & Voudouris, A. A. (2026). Optimal metric distortion for matching on the line. Artificial Intelligence, 361, 104630. https://doi.org/10.1016/j.artint.2026.104630

How many times has this paper been cited?

1 times, according to OpenAlex on 16 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at Artificial Intelligence: sign in and open the PDF from this page.

Who wrote this paper?

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

What is the DOI of this paper?

10.1016/j.artint.2026.104630, permanently at https://doi.org/10.1016/j.artint.2026.104630. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 16 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.