Optimal Metric Distortion for Matching on the Line
Authors: Aris Filos-Ratsikas, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, Alexandros A. Voudouris
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1University of Edinburgh, UK 2Drexel University, USA 3University of Essex, UK |
| Pseudocode | Yes | A description of the algorithm using pseudocode is given as Algorithm 1. Algorithm 1: ORDERMATCH. Input: Sets A and G and ordinal profile Output: A matching M between A and G. 1 Identify the extreme items gℓand gr using . 2 Partition G into Gin and Gout according to (1). 3 Compute ordering πg over Gin and πa over A. 4 Match the ith item in πg to the ith agent in πa. 5 Arbitrarily match items in Gout to unmatched agents. |
| Open Source Code | No | The paper describes theoretical algorithms and their properties, but it does not contain any explicit statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper does not use empirical datasets for experiments. It operates on theoretical instances, such as "Consider an instance with n agents {a1, . . . , an} and n items {g1, . . . , gn}", which are conceptual setups for theoretical proofs rather than actual data collections. |
| Dataset Splits | No | The paper does not involve empirical experiments using specific datasets; therefore, it does not provide any information regarding dataset splits like training, validation, or test sets. |
| Hardware Specification | No | The paper is purely theoretical, focusing on algorithm design and mathematical proofs. It does not describe any empirical experiments that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper presents theoretical algorithms and their analysis. It does not describe any software implementations or provide specific software dependencies, such as programming languages or libraries with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and mathematical proofs, not empirical experiments. Consequently, it does not describe any experimental setups, hyperparameters, or training configurations. |