Optimal Metric Distortion for Matching on the Line

1 Introduction

Matching problems are prevalent in everyday life and have played a central role in (computational) social choice for multiple decades, starting from the pioneering works of Gale and Shapley [1962], Shapley and Scarf [1974], and Hylland and Zeckhauser [1979]. These works consider settings in which a set of n agents need to be matched to a set of n items (one-sided matching), or to another set of n agents (two-sided matching), in some fair and efficient manner with respect to the agents' preferences. Some important applications of these problems include college admissions [Gale and Shapley, 1962], national residency matching [NRMP, ; Roth, 1984; Roth and Peranson, 1999]), school choice [Abdulkadiro˘glu et al., 2005b; Abdulkadiro˘glu et al., 2005a], and organ exchange [UNOS, ; Roth et al., 2004].

To accurately capture the, often complicated, preferences of an agent over a discrete set of outcomes, the common approach is to use a Von Neumann-Morgenstern utility function which assigns a numerical value to each outcome, indicating how strongly it is liked or disliked [Von Neumann and Morgenstern, 1944]. Although the significance of these cardinal preferences of the agents is recognized in the classic literature on matching (e.g., [Hylland and Zeckhauser, 1979; Zhou, 1990; Bogomolnaia and Moulin, 2001]), most matching algorithms that have been proposed are ordinal: They ask each agent to report only their ranking over the outcomes from most- to least-preferred. This is motivated by the fact that it can be cognitively or computationally prohibitive for the agents to come up with these values, whereas simply ranking outcomes is an easier, often routine, task. However, given access only to this limited (ordinal) information regarding the agents' preferences, to what extent can one approximate social objectives which are functions of the cardinal values?

This is precisely the question studied in the vibrant literature of distortion in social choice, whose goal is to design ordinal algorithms with low distortion, i.e., strong worst case approximation guarantees with respect to cardinal social cost objectives (see [Anshelevich et al., 2021] for a recent survey). One of the most well-studied settings in this literature since its inception [Procaccia and Rosenschein, 2006] is that of metric distortion, where the agents' cardinal preferences correspond to distances in some metric space [Merrill III et al., 1999; Enelow and Hinich, 1984]. The metric distortion literature has been very successful in a plethora of different settings, leading to (near-)optimal distortion bounds. Examples include single-winner voting [Anshelevich et al., 2018; Gkatzelis et al., 2020; Kizilkaya and Kempe, 2022], multiwinner voting [Caragiannis et al., 2022], and probabilistic social choice [Feldman et al., 2016; Anshelevich and Postl, 2017; Charikar and Ramakrishnan, 2022; Charikar et al., 2024]. However, a notable exception that remains poorlyunderstood, despite its fundamental nature and wealth of applications, is the metric distortion of matching problems.

In the metric matching setting, agents and items are embedded in a metric space, and an agent's cost in a matching is the distance between them and their match. The distortion of the metric (one-sided) matching problem was first studied by Caragiannis et al. [2024] 1 who focused on the utilitarian social cost (the total cost) and, among other results, observed that the distortion of the well-known serial dictatorship algorithm is 2n-1 . For its randomized counterpart, the random serial dictatorship, they showed that its distortion is between n0.29 and n. Their work also implies a lower bound of 3 on the distortion of any (possibly randomized) ordinal algorithm with respect to the utilitarian social cost. More recently, Anari et al. [2023] achieved improvements on both fronts: They designed a deterministic algorithm with distortion O(n2 ) and complemented it with a lower bound of Ω(log n) on the distortion of any ordinal algorithm, even randomized ones. Despite these improvements, there is still a very large gap between the lower and the upper bound, and closing this gap is one of the main open problems in this literature.

1 The conference version of this paper was published in 2016.

In this paper, we resolve the metric distortion of the matching problem for the interesting case of the line metric, which has received a significant amount of attention, both because it models natural scenarios of interest, and because it gives rise to worst-case instances for many metric distortion settings.

In terms of motivating applications for the line metric, widely known as 1-Euclidean, one of the natural ones is the fact that it provides an abstraction of political or ideological beliefs along different axes, encompassed into a spectrum, e.g., between "left" and "right". This idea is inherent in the pioneering works of [Hotelling, 1929] and [Downs, 1957]. The line metric can also be used to capture preferences over policy issues, such as the extent to which a government should be involved in the economy, ranging from full involvement to zero intervention [Stokes, 1963]; see [Filos-Ratsikas et al., 2024] for a more elaborate discussion.

It turns out in most of the fundamental metric distortion settings mentioned above (namely, single-winner and multiwinner voting), the best possible distortion on the line metric is either the same as or within a small constant from the best possible distortion on any metric. In the metric matching problem, however, this is not the case; the lower bound of Ω(logn) shown by Anari et al. [2023] requires a highly involved tree metric. In particular, this lower bound does not rule out the existence of an algorithm with constant distortion on the line. Is a such a constant achievable?

Our main result provides a positive answer to this question by providing an ordinal algorithm that achieves a distortion of 3 with respect to the well-known k-centrum cost (for different values of k ∈ {1, . . . , n}), which is equal to the sum of the k largest agent costs [Tamir, 2001]; see also [Han et al., 2023]. This objective naturally interpolates between the maximum (egalitarian) cost when k = 1 and the utilitarian social cost when k = n. In fact, we show that this distortion is the best possible for each of these cost functions and even for randomized algorithms, which fully resolves this question.

Informal Theorem 1. There is a deterministic ordinal algorithm for the metric one-sided matching problem on the line that simultaneously achieves a distortion of 3 with respect to the k-centrum cost for all k ∈ {1, . . . , n}. This distortion is the best possible for any ordinal algorithm, including randomized ones.

This result provides a clear, asymptotic separation between the distortion of one-sided matching on the line metric and its distortion in more general metric spaces.

Building on our main result above, we then consider the distortion of the metric two-sided matching problem. Despite the ubiquitous nature of this problem, it is perhaps surprising that, to the best of our knowledge, its metric distortion has not been considered prior to our work. For this setting, we prove a seemingly surprising result, namely that, using only ordinal information, we can construct a matching that exactly minimizes the k-centrum cost.

Informal Theorem 2. There is an optimal (i.e., with distortion 1) deterministic ordinal algorithm for the metric twosided matching problem on the line.

From a technical standpoint, what enables us to improve from a distortion of 3 in the one-sided matching case to achieving optimality in the two-sided matching setting is the additional information that we have from the preferences of the agents on the other side. We explore this further and show that an optimal matching can be computed using even less information about the ordinal preferences of the agents, which is acquired by appropriate queries.

1.1 Further RelatedWork

Prior to the work of Anari et al. [2023], Anshelevich and Zhu [2021] considered the metric one-sided matching problem as part of a class of more general facility assignment problems, and showed a bound of 3 on the distortion of ordinal algorithms for the social cost and the maximum cost objectives, but under the restriction that the item locations in the metric space are known. Other works [Anshelevich and Zhu, 2019; Anshelevich and Sekar, 2016b; Anshelevich and Sekar, 2016a] considered related matching settings where the goal is to maximize the metric utilities of the agents rather than minimizing their costs.

In the non-metric setting, where the agents are assumed to have normalized utilities over the items, the best possible distortion for one-sided matching has been identified for both deterministic [Amanatidis et al., 2022] and randomized algorithms [Filos-Ratsikas et al., 2014]. The distortion of onesided matching (and generalizations of it) has also been studied when more information can be elicited via queries [Amanatidis et al., 2022; Amanatidis et al., 2024; Ma et al., 2021; Latifian and Voudouris, 2024; Ebadian and Shah, 2025]. The query models in those works are inherently different from the one we consider here, as they elicit cardinal information, on top of the ordinal preferences which are considered to be known. In contrast, our queries in the two-sided model elicit only ordinal information about the agents' preferences on each side.

2 Preliminaries

For any positive integer ℓ, let [ℓ] = {1, . . . , ℓ}. An instance of our problem consists of a set of n agents A = {a1, . . . , an} and a set of n items G = {g1, . . . , gn}. We assume that agents and items are located on distinct points on the same line metric 2 , and let d(a, g) denote the distance between any agent a and item g. Let ≻a be the ordinal preference of agent a over the set of items G, such that g ≻a g′ implies d(a, g) ≤ d(a, g′ ). Let ≻:= (≻a)a∈A be the ordinal profile consisting of the ordinal preferences of all agents. Note that many different distance metrics may induce the same ordinal preferences for the agents. We write d▷≻ to denote the event that the metric d is consistent to the ordinal profile ≻. We also denote by top(a) the favorite item of agent a, that is, top(a) ≻a g for every g ∈ G \ {top(a)}. Let plu(g) be the plurality score of an item g ∈ G, which is equal to the number of agents whose favorite item is g, i.e., plu(g) = |{a ∈ A : top(a) = g}|.

2 The assumption that agent and item locations are all distinct is without loss of generality: it suffices to assume that agent's ordinal

Our goal is to choose a matching M between the agents and the items. Given such a matching, we denote by M(a) the item matched to agent a, and by M(g) the agent matched to item g. We evaluate the quality of a matching using a variety of social cost measures, captured by the k-centrum cost. Given some k ∈ [n], the k-centrum cost of a matching M is the sum of the k largest distances between the agents and their matched items, among all agents:

where maxq returns the q-th largest value. Note that this captures the two most well-studied social cost functions, the egalitarian and the utilitarian social cost, as special cases. Specifically, SCn(M|d) = ∑a d(a,M(a)) corresponds to the utilitarian social cost, which evaluates on the total cost over all agents, while SC1(M|d) = maxa d(a, M(a)) corresponds to the egalitarian social cost, which focuses on the agent that suffers the largest cost. In general, smaller values of k put more emphasis on fairness by focusing on the least happy agents. When the metric d is clear from context, we will simplify our notation and write SCk(M) instead of SCk(M|d).

A matching algorithm ALG takes as input an ordinal profile ≻ and computes a one-to-one matching ALG(≻) of the items to the agents. We want to design matching algorithms with as small distortion as possible. The distortion of a matching algorithm ALG with respect to the k-centrum cost SCk for some k ∈ [n] is the worst-case ratio over all possible ordinal profiles and consistent metrics between the objective value of the matching returned by the algorithm and the minimum possible objective value over all possible matchings:

M ∗ : A well-structured optimal matching

For each instance there may exist multiple matchings that minimize the k-centrum cost. Among these optimal matchings, we are particularly interested in one that greedily matches agents to items according to their true ordering on the line; the optimality of this matching is established in the following theorem. Throughout the paper, we denote this specific matching by M ∗ and refer to it simply as the optimal matching. Also, for each agent a we refer to M ∗ (a) as a's

preferences consistently tie-break over items with the same location.

optimal item. Due to space constraints, the proof of the following theorem (as well as of others in the rest of the paper) are omitted.

Theorem 2.1. Given the true ordering of all agents and items on the line, greedily matching the leftmost agent to the leftmost item leads to an optimal matching M ∗ with respect to SCk for all k ∈ [n].

A structural property

Given an ordinal profile ≻, we can observe some structure regarding the locations of the agents and the items on the line.

Lemma 2.2. If item gx is to the left of item gy, then all agents whose favorite item is gx are to the left of all agents whose favorite item is gy.

3 One-Sided Case: Optimal Distortion of 3

In this section we first prove that no algorithm can achieve a distortion better than 3 with respect to the k-centrum cost for any k ∈ [n], even if it is randomized. Then, we present an optimal (deterministic) algorithm that simultaneously guarantees a distortion upper bound of 3 with respect to all kcentrum costs.

3.1 Distortion Lower Bound for any Algorithm

Here we prove a lower bound on the distortion of matching algorithms, even randomized ones.

Theorem 3.1. For any k ∈ [n], no deterministic algorithm can achieve a distortion better than 3 with respect to the kcentrum cost SCk, and no randomized algorithm can achieve a distortion better than 3 - 2/n.

Proof. Consider an instance with n agents {a1, . . . , an} and n items {g1, . . . , gn}. The ordinal profile is such that all agents have the same ranking over the items: g1 ≻ . . . ≻ gn. For any i ∈ [n], let pi be the probability that agent ai is matched to item gn according to an arbitrary randomized matching algorithm. Without loss of generality, suppose that p1 ≤ 1/n; note that if the algorithm is deterministic, then p1 = 0.

Consider the metric spaces that are illustrated in Figure 1a for k = 1 and in Figure 1b for k ≥ 2, where ε > 0 is an infinitesimal. For any k ∈ [n], the optimal matching consists of the pairs (a1, gn) and (ai+1, gi) for i ∈ [n - 1], leading to a k-centrum cost of d(a1, gn) = 1. However, since the algorithm matches a1 to gn with probability p1, it matches agents in {a1, . . . , an} to gn with the remaining probability 1-p1. Whenever an agent in {a1, . . . , an} is matched to gn, the k-centrum cost of this matching is 3 - ε, thus leading to an expected k-centrum cost of

Consequently, the distortion is at least 3-ε for deterministic algorithms (since p1 = 0) and 3 - 2/n - ε for randomized algorithms, for any ε > 0.

3.2 Distortion-optimal Matching Algorithm

We now provide a deterministic algorithm that simultaneously achieves the optimal distortion of 3 with respect to SCk for any k ∈ [n]. Our algorithm consists of the following three key steps: The first one is to appropriately partition the items into two sets Gin and Gout using the ordinal preferences of the agents. The second step determines the true ordering (up to reversal) of the items in Gin, and it also uses this ordering to define an ordering over the set of agents. The third step matches the items in Gin to agents using the aforementioned orderings, and then arbitrarily matches the remaining items to the remaining agents. The rest of this section provides more details regarding the implementation of these steps. A description of the algorithm using pseudocode is given as Algorithm 1.

Step 1: Partitioning the items into Gin and Gout

Let G+ := {g ∈ G : plu(g) ≥ 1} be the subset of items in G that have a positive plurality score. By considering each agent's ranking of the items in G+, at most two items in G+ can be ranked last by the agents (these would be the two extreme items in G+, i.e., the leftmost and the rightmost one). We use gℓ and gr to denote these items, and without loss of generality 3 , we assume that the former is the leftmost item in G+ and the latter is the rightmost one. If every agent ranks the same item of G+ last, that means |G+| = 1 and gℓ = gr.

Since gℓ, gr ∈ G+, both of these items have at least one agent who ranks them at the top. Given two agents ai and aj such that top(ai) = gℓ and top(aj) = gr, we define the following subset of items:

We define (aℓ, ar) ∈ argmaxai,aj |Gin(ai, aj)| to be two agents that maximize the size of Gin(ai, aj), we henceforth partition the set of items into the following two sets:

In words, Gin consists of the items that either agent aℓ prefers over gr or agent ar prefers over gℓ, and Gout consists of all the remaining items. We remark that defining

3 Note that both the behavior of our algorithm and the analysis is invariant to the reversal of agent and item locations; so, we only fix gℓ to be the leftmost item to make the exposition more intuitive.

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.

(aℓ, ar) ∈ argmaxai,aj |Gin(ai, aj)| is vital to achieving a distortion of 3. If aℓ and ar were to be chosen arbitrarily among the agents whose favorite items are gℓ and gr, a distortion of 3 would not be achieved with respect to SCk for any k ∈ [n].

Note that if gℓ = gr, i.e., there is only one item in G+, then Gin = ∅ since no other item is preferred over that item.

Step 2(a): Ordering πg of the items in Gin

Although we cannot fully uncover the true ordering of all items in G given the ordinal preferences of the agents, we can extract the true ordering πg of the items in Gin ⊆ G using the algorithm of [Elkind and Faliszewski, 2014] which do so for a superset of Gin.

Lemma 3.3. The true ordering πg of the items in Gin can be computed.

Step 2(b): Ordering πa of the agents in A

Given the ordering πg of the items in Gin, we also define an ordering of all the agents in A based on what their top item is. Note that every agent's top item is in G+ which, by Lemma 3.2 is a subset of Gin, so by Lemma 2.2, πg implies a partial order over A. First, we let ˜πa be the partial ordering of the agents in A such that ˜πa(ai) = ˜πa(aj) if top(ai) = top(aj) and ˜πa(ai) > ˜πa(aj) if πg(top(ai)) > πg(top(aj)). Then, we define a total order πa by breaking the ties of the partial order in some arbitrary way.

Step 3: Matching agents to items using πa and πg

Our algorithm then determines how to match the items to agents starting with the items in Gin. It considers them based on the ordering πg and assigns them to the agents using the ordering of πa. Once all the items in Gin have been assigned, our algorithm arbitrarily matches the items in Gout to the agents that remain unmatched.

3.3 Analysis of ORDERMATCH

We now prove the main result of this section.

Theorem 3.4. ORDERMATCH achieves a distortion of 3 with respect to the k-centrum cost SCk for any k ∈ [n].

While our algorithm only has access to the ordinal preferences of the agents through ≻, our analysis in this section uses the exact locations of the agents and items along with the optimal matching M ∗ (e.g., to further partition the agents using this information, as well as to define a graph induced by each matching). For example, let Ain = {a ∈ A : M ∗ (a) ∈

Gin} be the set of agents whose optimal items (according to the optimal matching M ∗ ) are in Gin and Aout = A \ Ain be the set of all the remaining agents, i.e., the agents whose optimal items are in Gout.

Permutation graph PM induced by matching M

Given an instance with optimal matching M ∗ , we define the permutation-graph of any matching M as PM = (A,E), where each vertex corresponds to an agent in A, and each directed edge (ai, aj) exists in E if and only if M(ai) = M ∗ (aj) (i.e., there exists an edge from agent ai to the agent aj if and only if M assigns aj's optimal item to ai; note that it may be the case that ai = aj). In other words, this graph captures the permutation of items fromM ∗ to M. Note that for any given instance (i.e., for a fixed M ∗ ) every permutation graph PM corresponds to a unique matching M. Also, note that every vertex of a permutation-graph has in-degree and out-degree equal to 1 and PM is a collection of disjoint cycles.

To categorize some of the edges of this graph, we further refine the set of agents Ain as follows: Let Ax ⊆ Ain be the subset of agents in Ain whose favorite item is the xth-leftmost item in Gin. Due to Lemma 2.2, every agent in Ax is to the left of every agent in Ay for any x < y. We refer to an edge (ai, aj) ∈ E as forward if ai ∈ Ax and aj ∈ Ay for some x < y; backward if ai ∈ Ax and aj ∈ Ay for some x > y; internal if ai ∈ Ax and aj ∈ Ax; inward if ai ∈ Aout and aj ∈ Ain. See the example in Figure 2.

For any fixed instance, each graph PM corresponds to a distinct matching M, so we can also express the k-centrum cost of a graph PM and its corresponding matching M as:

We will now prove that the permutation graph PM of our algorithm has no backward edges and can be reduced to a permutation graph PM′ with no forward or backward edges with a weakly larger k-centrum cost for all k ∈ [n]. We will then prove the desired distortion of 3 for PM′ .

Lemma 3.5. If M is the matching computed by ORDERMATCH, then the induced graph PM does not include backward edges.

Proof. If Gin is empty (i.e., gℓ = gr), then PM cannot include any backward edges. If Gin is non-empty, then Lemma 3.3 shows that πg correctly orders the items in Gin from left to right. In the ordering πa, agents are ordered earlier than other agents if their favorite item is to the left of the favorite item of those other agents according to πg. For any x < y, Lemma 2.2 shows that all agents in Ax are to the left of all agents in Ay. Thus, the optimal item of every agent in Ax is to the left of the optimal item of every agent in Ay due to Theorem 2.1. Consequently, since all agents in Ax are matched to items before the agents in Ay, no agent in Ay can be matched to the optimal item of an agent in Ax, and thus there are no backward edges in PM.

Algorithm 2: REMOVEFORWARDEDGES

Input: Graph PM = (A, E) with no backward edges.

Output: Graph PM′ .

• 1 while there exists a forward edge in E do
• 2 Let (a3, a4) ∈ E be a forward edge such that top(a3) is weakly to the right of top(ai) for any other forward edge (ai, aj) ∈ E. Find a forward or inward edge (a1, a2) ∈ E such that top(a2) = top(a3) .

E ← E \ {(a1, a2), (a3, a4)}.

• 3 E ←E ∪ {(a1, a4), (a3, a2)}.
• 4 return PM′ ← (A,E).

Reduction to graphs without forward edges

If PM is the permutation-graph induced by the matching M computed by ORDERMATCH, Lemma 3.5 shows that this graph will not contain any backward edges. We now prove that, even though this graph can, in general, contain forward edges, we can without loss of generality assume that it does not. Specifically, we provide a reduction (REMOVEFORWARDEDGES) that takes as input any permutation-graph PM without backward edges and transforms it into a graph PM′ that contains neither forward nor backward edges, while ensuring that SCk(PM) ≤ SCk(PM′) for any k ∈ [n]. This reduction iteratively removes inward or forward edges from the graph and replaces them with other inward or internal edges, until no forward edges remain.

Theorem 3.6. Let M be the matching computed by ORDERMATCH when given an ordinal profile ≻. If its permutationgraph PM contains a forward edge, then there exists another matching M ′ whose permutation-graph PM′ does not contain any forward or backward edges, and has weakly larger k-centrum cost, i.e., SCk(M ′ ) ≥ SCk(M) for any k ∈ [n].

Bounding the cost of all remaining edges

Having addressed forward and backward edges, we now provide an upper bound for the cost of all remaining edges.

Lemma 3.7. Consider any permutation-graph PM = (A, E) without forward or backward edges. For any (ai, aj) ∈ E,

Proof Sketch. Since (ai, aj) is neither a forward nor a backward edge it could be an internal or inward edge, or it could also be the case that ai ∈ Ain and aj ∈ Aout, or both ai, aj ∈ Aout. In the appendix we prove the claimed inequality for each case separately. Here, we only prove the case of internal edges.

If (ai, aj) is an internal edge, both agents share the same favorite item, say g∗ . Using the triangle inequality and the fact that d(a, g∗ ) ≤ d(a, g) for any a ∈ {ai, aj} and g ∈ G, we have:

We can now prove the main result of this section.

Proof of Theorem 3.4. By Lemma 3.5, the permutationgraph of the matching returned by ORDERMATCH has no backward edges, and by Lemma 3.6, the k-centrum cost of this matching can be upper-bounded by the k-centrum cost of another matching whose permutation-graph has no forward or backward edges. We now show that for any matching M whose permutation-graph PM = (A, E) contains no forward or backward edges, we have SCk(M) = SCk(PM) ≤ 3 · SCk(M ∗ ) for all k ∈ [n]. Specifically, if we let Ek ⊆ E be the k edges (ai, aj) of E with the largest d(ai,M ∗ (aj)) cost, then

where the first inequality uses Lemma 3.7 for every edge in Ek and the subsequent equality breaks down the contribution of each edge (ai, aj) ∈ Ek to the contribution of ai and the contribution of aj. The final inequality uses the fact that: (i) all nodes have in- and out-degree 1 in any permutationgraph, so each agent a participates in at most two edges in Ek, (a, aj) and (ai, a), and (ii) the total cost of the k agents ai : (ai, aj) ∈ Ek (and that of the k agents aj : (ai, aj) ∈ Ek) is at most the total cost of the k maximum-cost agents.

4 Two-Sided Case: Reaching the Optimal Matching

In this section we consider a two-sided matching, in which instead of n agents that have preferences of n items, we have a set of n takers denoted by A and a set of n givers denoted by B. We have access to the ranking of each taker over the givers, and of each giver over the takers. We will refer to each of these sets as a side of the matching problem, and will use the term agent to refer to a taker or a giver.

We will show that using the ordinal rankings of the takers and the givers, we can compute an optimal matching. In particular, to do so, it suffices to show that we can recover the true ordering of the takers and the givers on the line. Then, we can greedily compute an optimal matching using Theorem 2.1 by considering one side as the items.

Theorem 4.1. For the two-sided matching problem on a line metric, we can compute an optimal matching with respect to the k-centrum cost SCk for any k ∈ [n].

Proof. We first show that we can recover the true relative ordering of the takers as well as the true relative ordering of the givers. We do so for the takers; the argument for the givers is symmetric. We consider two cases: Either all takers agree on their least-preferred giver, or there are two givers that appear at the bottom of the rankings of the takers.

In the first case, let b be the giver that appears at the bottom of every taker's ranking. We claim that all takers are on the same side of b. If not, then there is a taker i that is to the left of b and a taker j that is to the right of b. This implies that i weakly prefers b to top(j), which contradicts the fact that b is the least-preferred giver of all takers. Now, since all takers are on the same side of b, ≻b is the true ranking of the takers.

In the second case, let br and bℓ be the two extreme givers, and for the ease of exposition assume that br is to the right of bℓ. First, we claim that there is no giver to the left of bℓ, and similarly to the right of br. For the sake of contradiction, assume that there is a giver b to the left of bℓ, and let i be a taker with br ≻i bℓ. This means that this taker is to the right of bℓ, and hence br ≻i bℓ ≻i b, which contradicts the fact that only br and bℓ appear at the bottom of the takers' rankings.

Let Abℓ be the set of takers that have bℓ as their top choice. Since bℓ is the leftmost giver, all the takers to the left of it are in Abℓ . Hence, all the takers in A \ Abℓ are to the right of bℓ and to the right of all the takers in Abℓ . Consequently, the ordering ≻bℓ over A\Abℓ is the true ordering of these takers. Similarly, ≻br recovers the true ordering of Abℓ . By putting these two together, we have the true ordering of the whole set of takers.

Now that we have the true relative ordering of the takers and the givers, we can greedily match them to get the optimal matching M ∗ . The only issue is that these orderings are correct up to reversal and can be oriented in opposite directions. In other words, one ordering can be from left to right and the other from right to left. So, we have to make them consistent. We consider two cases depending on if at least one of the two sides have two different agents at the bottom of their lists (case 1), or both sides have the same (case 2).

Case 1. Assume that the takers have two different givers as their least preferred. Let a be an extreme taker (given the ordering of the takers, which we now know), and assume that a is the rightmost one. Then, a's least preferred giver must be the leftmost one. We use this information to give the same direction to the relative orderings of the takers and the givers.

Case 2. Here, each side has the same least-preferred agent in the other side. Let a be an extreme taker (according to the ordering of the takers), and assume that a is to the rightmost one. Then, a is to the same side of all the givers, and thus top(a) has to be one of the extreme takers. Hence, we order the givers so that top(a) is the rightmost one.

Now that the orderings are in the same direction we can greedily match them from left to right, thus computing the optimal matching M ∗ .

4.1 QueryModel

We now consider a setting where we are given some prior information about the preferences of the agents, and we can obtain further information by making specific types of queries. In particular, we consider two types of prior information:

• One-sided setting: We are given the complete ordinal preferences of the takers in A over the givers in B.
• Zero-knowledge setting: No initial information about the preferences of the agents is given.

Similarly, we consider two types of queries that we can make to gain more information:

• Full-preference queries: We ask an agent to reveal its ordinal preference over all the agents on the other side.
• Rank queries: We ask an agent to reveal its t-th preferred agent on the other side.

For each combination of prior information and type of queries as defined above, we are interested in pinpointing the number of queries that are sufficient to compute an optimal matching. Given that an optimal matching can be computed given for the two-sided matching problem as we showed above, we are essentially aiming to find out how many queries we need to make in each case to reveal the true ordering of the agents of each side on the line.

In the one-sided setting, n full-preference queries are clearly sufficient to compute the optimal matching as we would then have the ordinal preference of all agents, leading to the two-sided matching problem. We further show that this amount of such queries is necessary.

Theorem 4.2. In the one-sided setting, at least n - 1 fullpreference queries are required to compute an optimal matching.

Due to Theorem 4.2, since n-1 full-preference queries are required even when the whole ordering of one side is given, by applying the argument to each side independently, we obtain a lower bound of 2n - 2 on the number of required fullpreference queries for the zero-knowledge setting, which is nearly tight as 2n full-preference queries reveal the orderings of both sides of agents.

Corollary 4.3. In the zero-knowledge setting, we need at least 2n-2 full-preference queries to find the optimal matching.

Since we can simulate a full-preference query using at most n-1 rank queries, we can clearly compute an optimal matching by using at most n(n - 1) rank queries in the one-sided setting. In the following theorem, we show that we can do this using only 3n - 4 rank queries.

Theorem 4.4. In the one-sided setting, we can compute an optimal matching by making 3n - 4 rank queries.

For the zero-knowledge setting, we show that only a constant factor more rank queries are required to compute the optimal matching.

Theorem 4.5. In the zero-knowledge setting, we can find the optimal matching with 5n - 4 rank queries.

5 Conclusion and Future Directions

We showed a tight bound of 3 on the distortion of ordinal algorithms for the metric one-sided matching problem on the line with respect to the k-centrum cost, the sum of the klargest costs among all n agents, for any k ∈ [n]. We further showed that, for the two-sided matching problem, the ordinal preferences of the agents are sufficient to reveal their true ordering on the line which can then be used to compute an optimal matching; in fact, even less information is sufficient to achieve optimality.

Although we have resolved the distortion of matching on the line, there are several natural directions for future research. For example, it would be interesting to investigate the one-sided matching problem on the line using the learning-augmented framework [Lykouris and Vassilvitskii, 2021]. According to this framework, which was recently also used for the metric distortion of single-winner voting [Berger et al., 2024], the designer is provided with some (potentially inaccurate) prediction regarding the agents' cardinal preferences. The goal is to achieve an improved distortion whenever the prediction is accurate (known as consistency) while maintaining a good distortion even if the prediction is arbitrarily inaccurate (known as robustness). In our setting, the main question would be whether a consistency better than 3 can be combined with a robustness of 3.

For more general metrics, the distortion of the one-sided matching problem still remains wide open, and bridging the gap between the known lower bound of Ω(log n) and the upper bound of O(n2 ) for deterministic algorithms or the upper bound of O(n) for randomized algorithms is quite possibly one of the most challenging open questions in the distortion literature at the moment. To obtain positive results, as we did in this paper for the line metric, one could next consider other specific metric spaces, such as 2-dimensional Euclidean spaces or trees (on which the lower bound holds). Additionally, the two-sided matching problem has not been considered before our work under the metric distortion framework, and it is thus a natural problem to study for general metrics, especially as it seems to be somewhat easier than the one-sided variant (at least for the line, as we have shown).

Acknowledgments

Aris Filos-Ratsikas and Mohamad Latifian were supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/Y003624/1. Vasilis Gkatzelis and Emma Rewinski were supported by NSF CAREER award CCF2047907 and NSF grant CCF-2210502.