Bi-Criteria Metric Distortion
Authors: Kiarash Banihashem
Diptarka Chakraborty
Shayan Chashm Jahan
Iman Gholami
MohammadTaghi Hajiaghayi
Mohammad Mahdavi
Max Springer
Venue: ICLR 2026 Poster (2026)
Keywords: Social Choice Theory
Metric Distortion
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We show that selecting a small committee improves approximation guarantees over single-winner selection in metric distortion, achieving optimal cost in line metrics but not in tree or 2-D metrics.

Abstract: Selecting representatives based on voters' preferences is a fundamental problem in social choice theory. While cardinal utility functions offer a detailed representation of preferences, voters often cannot precisely quantify their affinity towards a given candidate. As a result, modern voting systems rely on ordinal rankings to simplistically represent preference profiles. In quantifying the suboptimality of solutions due to the loss of information when using ordinal preferences, the metric distortion framework models voters and candidates as points in a metric space, with distortion bounding the efficiency loss. Prior works within this framework use the distance between a voter and a candidate in the underlying metric as the cost of selecting the candidate for the given voter, with a goal of minimizing the sum (utilitarian) or maximum (egalitarian) of costs across voters. For deterministic election mechanisms selecting a single winning candidate, the best possible distortion is known to be 3 for any metric, as established by Gkatzelis, Halpern, and Shah (FOCS'20). In contrast, for randomized mechanisms, distortions cannot be lower than $2.112$, as shown by Charikar and Ramakrishnan (SODA'22), and there exists a mechanism with a distortion guarantee of $2.753$, according to Charikar, Ramakrishnan, Wang, and Wu (SODA'24 Best Paper Award). Our work asks: can one obtain a better approximation compared to an optimal candidate by selecting a committee of $k$ candidates ($k \ge 1$), where the cost of a voter is defined to be its distance to the closest candidate in the committee? We affirmatively answer this question by introducing the concept of bi-criteria approximation within the metric distortion framework. In the line metric, it is possible to achieve optimal cost with only $O(1)$ candidates. In contrast, we also prove that in both the two-dimensional and tree metrics -- which naturally generalize the line metric -- achieving optimal cost is impossible unless all candidates are selected. These results apply to both utilitarian and egalitarian objectives. Our results establish a stark separation between the line metric and the 2D or tree metric in the context of the metric distortion problem.

Published as a conference paper at ICLR 2026
BI-CRITERIA METRIC DISTORTION
Kiarash Banishashem', Diptarka Chakraborty", Shayan Chashm Jahan', Iman Gholami', MohammadTTaghi Hajiaghay'', Mohammad Mahdavi', Max Springer
DDpaarmment of Computer Science, University of Maryland, College Park, MD 20742, USA Schooo of Computing, National University of Singapore, Singapore
DDepartment of Computer Science, Princeton University. Princeton NJ 08540, USA (k (kiarash, schjahan, Ogholamis hajiagha, mahdavi @umd. edu edu
di diptarka@nus.. edu. sg
ABSTRACT
Selecting representatives based on voters' preferences fundamental problem in social choice theory. While cardinal utility functions offer detailed represen- tation of preferences, voters often cannot precisely quantify their affinity towards given candidate. As a result, modern voting systems rely ordinal rankings to simplistically represent preference profiles. In quantifying the suboptimality solutions due to the loss of information when using ordinal preferences, the met- ric distortion framework models voters and candidates as points in metric space, with distortion bounding the efficiency loss. Prior works within this framework use the distance between a voter and candidate in the underlying metric as the cost of selecting the candidate for the given voter, with goal of minimizing the sum (utilitarian) or maximum (egalitarian) of costs across voters. For determin- istic election mechanisms selecting single winning candidate. the best possible distortion is known to be 3 for any metric, as established by Gkatzelis, Halpern, and Shah (FOCS'20 20). In contrast, for randomized mechanisms, distortions can- not be lower than 2.112, as shown by Charikar and Ramakrishnan (SODA'22), and there exists a mechanism with a distortion guarantee of 2. 2,753, according to Charikar, Ramakrishnan, Wang, and Wu (SODA'24 24 Best Paper Award). Our work asks: can one obtain a better approximation compared to an optimal candidate by selecting committee of k candidates (A: 2 1), where the cost of voter is defined to be its distance to the closest candidate in the committee? We affirma- tively answer this question by introducing the concept of bi-criteria approximation within the metric distortion framework. In the line metric, it is possible to achieve optimal cost with only O(1) candidates. In contrast, we also prove that in both the two-dimensional and tree metrics which naturally generalize the line metric achieving optimal cost is impossible unless all candidates are selected. These results apply to both utilitarian and egalitarian objectives. Our results establish a stark separation between the line metric and the 2D or tree metric in the context of the metric distortion problem.
INTRODUCTION
One of the fundamental challenges in the social choice theory is elect representatives based on voters' preferences, ideally represented by cardinal utility functions that assign numerical values to each outcome. However, in most real-world scenarios, voters only provide ordinal information, such as preference orders among outcomes/candidates This raises a natural question of how worse, if at all, a voting mechanism performs when given ordinal information rather than cardinal information. Procaccia & Rosenschein (2006) introduced the notion of distortion to measure such an efficiency loss how different voting rules respond to the lack of cardinal information. Many practical vot- ing scenarios can be formulated by considering both voters and candidates lying on metric space Enelow Hinich, 1984). The distance to candidate locations determines voters' cardinal prefer- ences for candidates voters rank candidates based on ascending distance, with the closest candidate being the most preferable and the farthest candidate being the least preferable. The worst-case be- havior of any ordinal preference order-based voting rule/mechanism is captured by the notion of

---

Published as a conference paper at ICLR 2026
metric distortion, introduced by AAnshelevich et al. (2018). A voting mechanism, without access to the actual distances among the set of voters and candidates, seeks to minimize a specific cost func- tion. which depends on the distances. Distortion is defined with respect to this cost: for any voting mechanism f. it is the worst-case ratio, over all instances, between the cost of f's solution and the optimal cost.
Given a single fixed candidate, the cost for a voter is defined as its distance from the given candi- date. Then, the overall cost is set to be an objective that combines these values across all the voters. Depending on the specific context in the literature, the following two objectives have widely been considered: a utilitarian objective, which aims to minimize the total individual costs for all voters, and an egalitarian cost, which minimizes the maximum cost experienced by any voter. Different variants of the metric distortion problem under the above objective functions have received signif- icant attention, e.g. Goel et al. (2017); Kempel (2020); Giaatzllis et al. 22020) Anagnostides et al. (2022) ; Kizilkaya & Kempe (2023a).
For the classical metric distortion problem, it is known that distortion of can be achieved for any metric. Further, it is widely known that the candidate chosen by any deterministic method cannot achieve distortion factor of less than 3, even in a line metric. In other words, without knowing the exact distances, it is not possible to obtain a better than 3-approximation of the optimal cost. This leads to intriguing question: Can we obtain a better approximation (distortion) by selecting more than one candidate? Specifically, assume that the algorithm is allowed to choose k > candidates, and we the cost for each voter to be its distance the closest chosen candidate. Can we design an algorithm for which the overall cost (either utilitarian or egalitarian) is at most times the cost of optimal candidate for some a < 3?
In this paper, we answer the above question affirmatively. We not only attain better distortion by al- lowing the selection of more than one candidate but, in fact, attain optimal cost with (11 candidates for the line metric. Additionally, we present several lower-bound constructions that demonstrate im- possibility results for the line, tree, and 2D Euclidean metrics. Our findings establish matching upper and lower bounds for these cases. Furthermore, our results establish a separation between the line metric and the 2D Euclidean (and tree) metrics in the context of the metric distortion problem.
Our work introduces bi-criteria perspective to metric distortion, which, to our knowledge, has not been considered before. The pursuit of improved bi-criteria approximation results for various classical optimization problems has already been well-investigated in the literature. Indeed, when the metric is known, and the goal is to pick k candidates that minimize the overall cost across voters, the election problem becomes instance of either the k-median or the k-center clustering (for the utilitarian and egalitarian objective, respectively). For these problems, numerous (constant- factor) approximation algorithms are known which select up ((k) centers (instead of k centers), e.g. |Feldman et al. (2007); Weil (2016); Alamdari & Shmoys (2018). Therefore, it is quite natural explore similar question in the metric distortion problem, where the underlying metric is not directly given.
Our work additionally extends the existing line of research k-committee elections Faliszewski ctt al. (2017); Elkind et al. (2017); CCragianniis et al. (2022), which also select a committee of k candidates and aim to minimize some loss function across all voters. The key distinction is that we consider a single candidate as our baseline for calculating distortion, while these works consider baseline of i candidates (see Section 1.2). Specifically, for the utilitarian cost we consider (i.e., the sum of distances of voters to their closest candidate in the committee), [Cragiinnis et al.] (2022) show that the ratio of the cost for any deterministic method compared to the cost of an optimal committee can be unbounded in the worst case. This result fails to suggest choice of candidates, as all possible choices are the same in the worst case. In contrast, we show that by using our bascline, one can make meaningful distinction between different choices even though the underlying metric is unknown.
Our contribution. Our first result shows that when the underlying metric is a line, a committee of two candidates can achieve a I-distortion of one under the sum-cost objective. Here, 1-distortion refers to the worst-case ratio between the cost of the selected committee and the cost of an optimal single-winner candidate. For any voting rule f, its distortion, or more specifically, Iddistortion is
cost (f())
1 1-distortion(f) := sup sup
E d
OPT
2

---

Published as a conference paper at ICLR 2026
where the cost function cost in the above definition could be either cost, costm depending on the context. other words, the I-distortion compares the cost of the mechanism to the cost of an optimal candidate in the worst case.
In fact, we will prove a stronger result by showing that it is possible to output a list of two candidates that always contains optimal one. Formally, prove the following theorem.
An algorithm for the 2-committee utilitarian election the line metric exists that guarantees the choice of an optimum candidate in the elected committee. Consequently, the 1- distortion of the algorithm is 1.
Theorem 1.
We further show that when the metric is not line, one can obtain distortion of m--1'
There exists an algorithm for the (m - 1) committee utilitarian election on the general metric that obtains a 1 I-distortion of, at most, + 2/m 1). Additionally, no algorithm can obtain a I-distortion better than 2/(m n - 1) when choosing m candidates, even if the metric space is 2D Euclidean or tree metric.
Theorem 2.
We further study the max-cost objective, showing that one can obtain 1-distortions of 1, 1.5, and 2 using sets of size four, three, and two, respectively.
Theorem 3. For any k {2, 3, 4), there exists algorithm for the k-committee egalitarian election on the line metric, which obtains a 1 I-distortion at most 3 h/2. Furthermore, no algorithm can obtain I-distortion better than k/2.
For the max-cost objective, even though there exists algorithm that selects one candidate with a distortion of 3, we show that no algorithm can achieve a 1-distortion better than 3, even when choosing committee of candidates.
Theorem 4. There is algorithm for the (m cocommiitee egalitarian election 2D Euclidean metric such that can obtain a I-distortion better than 3.
is important note that the obtained lower bounds apply deterministic algorithms.
Table State-of-the-Art; blue bounds are results of this paper.
Metric
Committee Size
Objective
Upper-Bound Lower-Bound
Space
(Out of m)
2
1
1"
ID
1
3b
3
Sum
2D Tree Metrie
m
+
1
m-1
m-
2 4
1
ID
3
1.5
1.5
Max
2
2
2
1
3
3
2D
3
Implied Anshelevich & Postl (0077).
From Anshelevich et al. (2018).
From Gkatzelis et al. (2020).
1.1 TECHNICAL OVERVIEW
Upper bound results. Our approach to the bi-criteria metric distortion problem builds upon the foundational result by Elkind & Faliszewski (2014), who demonstrated that the ordering of voters and candidates can be deduced from ordinal preferences
line metric. We use this established ordering for upper bound results, enabling to develop algorithms that select small committees achieving optimal or near-optimal distortion relative to the single-winner benchmark. We employ a distinct method to prove this ordering, which facilitates extensions of our results more complex
3

---

Published as a conference paper at ICLR 2026
C4
114
23
93
(a) The instance To
C4
C3
(b) Is: Instance with voter vy and candidate es moved
Figure 1: Figures of the lower bound instances. In (a), all candidates are located on the line -t, with voters with matching y-coordinates on the line x = 0. In (b), voter V/ and candidate C3. are moved to the line f, while keeping the same y-coordinate.
settings and yields improved outcomes in these generalized spaces. For the sake of completeness and to provide clear foundation for understanding the remainder of our solution, we present detailed exposition of this method in Section
Finally, to achieve the optimal solution for the sum objective with two candidates, we select candi- dates immediately to the left and right of any median voter. This approach follows from the result in/Anshelevich & Postl (2017). with detailed explanation provided in Section In contrast, achiev- ing a I-distortion of for the max objective requires a different strategy. We begin by identifying the leftmost and rightmost voters, whose distance is denoted by D. For the single-winner case, lower bound of D/2 is known. Then, depending on whether we use 2, 3, or 4 candidates, we place them accordingly to achieve 1-distortion of 2, 1.5, and 1, respectively.
Lower bound results. In Section we provide various lower bounds for different settings. For the sum objective, we begin by presenting an example showing that any mechanism for choosing committee of size & cannot achieve bounded distortion, even when compared an optimal choice of [log(k 1)] + candidates. This example relies on a binary tree structure with k+ leaves, where each candidate corresponds a leaf in the tree. The set of voters is the same as the candidates. Then, for any candidate, we construct an instance where the candidates whose lowest common ancestor with this candidate the tree is given vertex are close cluster. By selecting one representative for each cluster, we obtain a set of candidates of size [log(k: (k + 1)] + 1, for which the total cost can be made arbitrarily small. In contrast, any solution excluding this candidate will incur a constant cost. Notably, these instances lie on the real line, demonstrating that the lower bound applies even for the line metric.
Next, we present examples in the 2D Euclidean metric space and tree metric space, where achieving a 1-distortion better than 1 + 2
m-1 for the sum objective is not possible even when choosing m candidates. To argue that, we consider a set of m candidates and m voters. Then, we create m + instances Io, 11, Im. Each of them is distinct in terms of voters' and candidates' exact locations; however, they are indistinguishable in terms of voters' preference orderings (that are available as input any voting mechanism). See Figure [ to have idea about the construction of the base instance Io and instances Ij for each voter j. We show that not selecting any particular candidate would result in one of the above m + election instances to attain a 1-distortion of at least 1 + -
This example highlights a drastic contrast between the line metric and higher-dimensional metrics. While a 1-distortion of one can be achieved on the line with just two candidates, this is not possible in higher dimensions, even when selecting all but one candidate. We also present a similar example for the objective, demonstrating that achieving 1-distortion better than 3 is impossible in the 2D Euclidean metric, even when selecting m candidates. Finally, we provide examples showing that positive results for the 1-distortion of the max objective on the line are tight.
4

---

Published as a conference paper at ICLR 2026
1.2
RELATED WORKS
The metric distortion framework has been central in analyzing single-winner voting. Gkatzelis et al. (2020) proved that any deterministic mechanism must have distortion at least 3, later simplified by Kizilkaya & Kempe (2023b). While it was conjectured that randomization could improve to 2, this
was disproved by Charikar & Ramakrishnan (2022) and Pulyassary & Swamy (202I). Recently, Charikar et al. (2024b) achieved 2.753 with randomization. Separately, |Anshelevich et al. (2024)
showed that if threshold approval sets are known, distortion can be reduced to 1 + v2.
In the k-committee election problem (the single-winner election being a special case with k 1), the aim is to select k candidates from pool of candidates based on ordinal preferences provided by n voters. For any mechanism f. its distortion is defined as the worst-case ratio (across all instances) of the cost of the solution produced by f compared to the optimal cost. When the cost for a voter is considered as the sum of distances to all committee members, Goel et al. (2018) showed that the problem reduces to the single-winnel election.
On the other hand. Caragiannis et al. (022)) considered a general cost function - each voter's cost is the distance to the q-th (for some integer y 2 1) nearest committee member. They identified a trichotomy: For y S 1//3, the distortion is unbounded; for E (t/3,k/2) it is (n)); and for q k/2, the problem reduces the single-winner election. As an immediate corollary, for the 2-committee election, with each voter's cost being its distance to the nearest committee member (i.e.. g = 1), we get distortion of (n). Further, with the same cost function, for the k-committee election when & 2 3, the distortion is unbounded (even for the line metric). However, when the positions of candidates are known, for is m Chen et al. (2020) demonstrated that single-vote rules achieve a distortion of 3 and provided matching lower bound.
One of the most basic werre both voters and candidates are positioned on a real line- has already garnered significant attention in computational social choice theory. Strict preference profiles, with voters and candidates on a real line (also known as 1-D Euclidean). exhibit many in- triguing properties, including being single-peaked and single-crossing (Black [948, Mirrlees 1977 Escoffier et al. 2008). Given a preference profile and the order of voters, deciding whether it is 1-D Euclidean be done in polynomial time (Elkind & Faliszewski| 2014). Furthermore, if the input preference order is consistent with I-D Euclidean, [Bkindd & Faliszewski (2014) provides an efficient construction of a mapping realizing that. Very recently, Fotakis al. (2024) studied the k-committee election problem on the 1-D Euclidean metric by allowing a few distance queries in addition to the voters' preference orders.
One closely related question to the problem of optimal candidate selection is the facility location problem Mahdian et al. (2006), where the goal is place facilities at locations in a metric space to minimize the cost of serving agents. Unlike the candidate selection problem, where candidates are restricted to a fixed set, facilities in the facility location problem can be placed anywhere in the space Feldman et al. (2016). Another related concept is the Condorcet winning set: a set of candidates such that no other candidate is preferred by at least half the voters over every member of the set Elkind et al. (2015). The Condorcet dimension, defined as the minimum cardinality of Condorcet winning set, is known to be at most logarithmic in the number of candidates, partially reaffirmed by CCragiannis et al. (2024). In the metric ranking framework. Lassota et al. (2024) demonstrated that the Condorcet dimension is at most three under the Manhattan or &o norms. Recently, Charikarr al. (2024a) showed that Condorcet sets of size six always exist.
2 PRELIMINARIES
Metric space. Let us consider domain X' and a distance function d' X' x X R. We call (X, d) a metric space if the distance function d satisfies the following properties:
Positive definite: For all x, E X, d(x, w) 2 O. and d(z, y) = iff r = y.
Symmetry: For all x, E X, d( = d(y,
Triangle inequality: For all x, v, X, d(x, y) S d(x, 2) + d(z.v).
In this paper, we consider
5

---

Published as a conference paper at ICLR 2026
Line metric (1-D Euclidean metric): The domain is X' R, and for any two points
p: 9 E R, their distance is d(p, q) p - g).
2D Euclidean metric: The domain is = IR, and for any two points p = (px. p
(g): E R their distance is d(p.
||l 2| == V(n qx)² + (py oy)²
Tree Metric:
The domain is set of vertices V, and there exists a weighted tree T such that for any pair of vertices u, E V. the distance d(u, v) du, v), where dr (u, denotes the total weight of the path between and in T.
Election. An election instance & - (V, C) consists of a set V = f......,, Un } of voters and a set (ci...., Gm. of m candidates. Each voter 2s E V has linear order >5 over the candidates, where Cj > indicates that voter prefers Cj over preference of voter ot. Furthermore, > (>1,...,>> is called the preference profile of the voters. Additionally, the j-th candidate in the ordinal preference of voter is denoted by rij.
We refer to >; as the ordinal
We consider the voters and candidates to lie the same metric space (X,, Rd). For ease of exposition, we extend the notion of distance d to be defined directly the set of voters and candidates instead of the points they occupy the underlying space X. We say (distance) metric is consistent with an election instance & = (V, (V),,)) denoted as d E, when for any voter Us Cj > Ck if d(v,, o2) I d(e,,c,)
Social cost. Let us consider an election instance (V, and a distance metric t E. Let / - (E, d) denote the instance & with d being its underlying distance metric. For any subset of candidates $ S C, and a voter u E V, we use d(v, S) to denote the distance between the voter v to its nearest neighbor in S, i... d(,,S) == min.es d(u, c).. In this paper, we focus the following two social costs:
Sum-cost (Utilitarian objective): For any subset of candidates S S C, its sum-cost, denoted by cost,(S, I) is defined as cost. == Vvev d(v,
Max-cost (Egalitarian objective): For any subset of candidates S C C, its max-cost, (S, denoted by costm (S, T)
is defined as cs I) == max.ev d(u,S).
When it is clear from the context, we drop and simply use cost,(S) and cS)
Voting rule and distortion. A (deterministic) voting rule (also referred to as mechanism) f a function that maps an election instance & to subset of candidates S. We use algorithms and mechanisms interchangeably throughout this paper. In this paper, we compare the cost of voting rule that selects k-sized committee with the cost of optimal single candidate. We call a single candidate Cups optimal
(Com min cos
cEC
Throughout the paper, we use OPT (ost( to refer to the cost of an optimal single candidate. To capture how good a voting rule is in the worst case, the notion of distortion is used. For any voting rule f, its distortion, or more specifically, I-distortion is defined as
cost(f(E))
1-distortionn() = sup sup dog
OPT
where the cost function cost the above definition could be either cost, or cost,, depending on the context. In other words, the 1-distortion compares the cost of the mechanism the cost of an optimal candidate in the worst case.
3 UPPER BOUNDS ON DISTORTION FACTOR
Upper bounds for sum-cost. We study the sum objective, where the cost of candidate set is the sum of distances from voters to their closest selected candidate. On the line metric, using the order- ings from Section Al we show that committee of size two always contains optimal candidate.

---

Published as a conference paper at ICLR 2026
Theorem 5. There exists voting rule for the 2-committee election for the sum-cost objective, on the line metric, such that the resulting committee includes an optimal candidate. Consequently, the 1-distortion of the voting rule is 1.
We proceed in two steps. First, we show that it is always possible to select three candidates such that one optimal candidate is guaranteed be included. Second, we show that one of these three candidates can be safely discarded without ever removing that optimal candidate.
For the sum of distances, the median voter the "balance point": moving a candidate toward the median decreases distance to the majority more than it increases it to the minority. Thus, an optimal candidate can be slid toward the median without increasing cost until becomes one of the two candidates adjacent to the median voter (for an even number of voters, we fix either middle voter as the median). Note that the proofs of all lemmas and theorems appear in Appendix B.I
Lemma 6. When considering the sum of distances objective and the candidates and voters located on the real line, one of the candidates directly to the right or left of the median voter will be an optimal candidate.
Using only ordinal information, order voters and candidates and discard candidates never closest to any voter. Let c be the candidate closest to the median voter, and take the candidates immediately to the left and right of in the candidate ordering. By Lemma 6 the optimal candidate is the first candidate to the left or right of the median and must belong to this triple.
Lemma 7. There exists voting rule for the 3-committee election on the line metric such that the resulting committee includes an optimal candidate.
To prove Theorem 5 let the three candidates in order on the line be C1, C2, C3 and partition voters into three contiguous groups according which of these is closest (this partition is determined by ordinal preferences). If more voters lie to the right of 02 than to the left, replacing 63 by 02 cannot increase the sum of distances, so 02 least as good cx: symmetrically, if the left side heavier, ea is at least as good as C1. Thus, one extreme is never strictly better than the middle candidate, and we can drop it while still retaining a 2-set containing an optimal candidate.
For general metric, we show that choosing k = m 1 candidates suffices to obtain 1-distortion 1 + m- The rule looks only at each voter's top-ranked candidate and selects all but the least popular top choice. If the optimal single candidate is among these
winners, the distortion is 1; otherwise, it is the unique excluded candidate, only voters ranking it first are affected. There are a few such voters by construction. Each can be rerouted, via a nearby voter whose favorite is selected, to an elected candidate with bounded extra distance, leading to total cost at most a factor M-I of the optimum.
2
Theorem 8. There exists a voting rule choosing m - out of m candidates achieving a 1-distortion of T-T for the sum-cost objective.
Upper bounds for max-cost. We now consider the max-cost objective, where the cost of candi- date set is the maximum distance of any voter to her closest selected candidate. Our benchmark is the best single candidate. We show that two, three, and four candidates suffice guarantee distortions 2, 3/2, and 1, respectively.
Throughout this section, we use the leftmost and rightmost voters, denoted ey and v,, identified using Section A Since we only use each voter's top candidate, ties cause no ambiguity. Proof details are in Appendix B.2
ij and v, are far apart, no single candidate can be close to both: wherever the candidate is placed, least one of ot or u, is at distance of at least d(vi, 222
Lemma 9. If the distance between t and u, is D (i.c., D d(vi,,,)), then the cost for the optimal single candidate OPT satisfies OPT > D T
Thus, the "span" d(vi, u4) forces any single candidate to incur max-cost at least D/2.
From the orderings of Section A we know how voters and candidates interleave the line. When voters form a single block with no candidate strictly between i and vr, at is the first candidate immediately the left of all voters and e, the first the right, and choosing {ct, Gr } is optimal.
7

---

Published as a conference paper at ICLR 2026
20PT
OPT
Um
Figure 2: While the pair {ct c cannot achieve optimal I-distortion, it guarantees a I-distortion of
OPT
OPT
Cr
Cr
Figure 3: When er and c, are between and uy4 {a, Gr3 is optimal.
Lemma 10. If there candidates placed between ts and uy, voting rule that selects et and Cr, achieves a 1 distortion 1.
The nontrivial case is when at least candidate lies between d/ and er, which assume from now on. Then any optimal single candidate Copt must also lie between ey and Gy; otherwise it is at least d( Uy) away from one extreme voter.
Now ey and er act as "anchors" for all voters. For any voter e between them we have d(u, v) + d(v, v,) D d,),, By Lemma OPT 2 D/2, every voter is within distance OPT of least one of ip or Ur-
Lemma 11. d((ur 0,) = D, then for every voter u, either d(v, ur) S OPT or d(v, 14) s OPT.
This yields a 2-approximation:
Theorem 12. For any election on the line metric, let vy and vy- be the leftmost and rightmost voters, and a and Gr be the closest candidates and er, respectively. Then, voting rule / that outputs the set {et, Gr satisfies -ii storsttorooonoo < 2 with respect to the max-cost objective.
Indeed, d(v,, q) S OPT and d(u,, c,) < OPT by definition, and Lemma 11 guarantees that every other voter v is within distance OPT of at least one of or ty. Going via that extreme and then to q or o, adds most another OPT, all voters are within 20PT of {e,, c. The pair {at, c, need give distortion when q lies left of t c, right of e,: some voters between and may then be far from both a and c,, even though Cupt sits the middle.
Conversely, if c and c, both lie between and (FigureB). then fa, cr is optimal. In this case, d(p,cc) a)) max(d(v, uz), OPT), d(v, S max(d(v, u,),
and by Lemma IT each voter is within distance OPT of i or fr so
d(v, et) < OPT or d(u, c.) S OPT.
To handle the general case, we "push" the selected candidates inward by adding more candidates. Adding one candidate just inside one extreme yields 3/2-approximaatinn adding one near each side gives distortion 1.
Theorem 13. For any election & on the line metric, there exists a voting rule to select three candi- dates, which achieves 1-distortion of 3/2 with respect to the max-cost objective.
We start from immediately to the left c, and consider C {c,, Cc,,c,,c cy, c.). Any voter strictly outside the interval between Cj and the rightmost candidate in {cr, c, has her nearest candidate in C' by construction. For voters in the middle region, the distance between сj and that rightmost candidate at most 30PT (via and Cap), so any voter between them is at a distance at most 30PT/2 from one of them.
and their closest candidates Cr2 Cy. Using the candidate ordering, we add d
Theorem 14. For any election on the line metric, there exists a voting rule to select four candi- dates, which achieves l-distortion of with respect to the max-cost objective.
For the 4-candidate rule, we symmetrize. From et and cy. let of be the next candidate to the right of and e/. the next to the left of c,. Let of be the one in (a,c() c() lying to the right of vy and et the one
8

---

Published as a conference paper at ICLR 2026
in fcr, 4 lying to the left of u,. Consider {ci, c,, Cr,,,, c,). Every voter the left of dj right of of has her closest candidate among these four. the central part of the line, qi G, Cope lie between of and tr since by and er within distance OPT of Copt. we have d(c;; ct) S 20PT. so any voter between them is within distance at most OPT of one of them. Thus, every voter is within OPT of the selected four, giving distortion 1.
4 LOWER BOUNDS ON DISTORTION FACTOR
Lower bounds for sum-cost. We now give lower hounds for distortion under the sum-cost objec- tive. First, we extend the lower bound of Caraagiian et al. (2022) show that bounded distortion is impossible for general k, even if we may select w(k) candidates. The construction already works on the line metric. We encode each voter and candidate by an bi binary string (with k = 2 1), define preferences so that voter prefers candidates with longer common prefixes, and embed these strings on line via a base-3 expansion where bits agreeing with fixed "special" candidate receive large weight and later bits are downweighted by E.
Theorem 15. For k 2 there exists an instance for the k-committee election on the line (with respect to the sum-cost) where no voting rule choosing & candidates can achieve a bounded distortion even when compared to an optimal choice of [log2 + 1)1 + 1 candidates.
Any rule picking exactly k 2 candidates must omit some candidate cr. We place voter U/- the same point cG- and arrange all other candidates that every selected candidate is at distance 2(3-²) from u--. Thus any k-sized committee omitting C-- incurs a constant cost for ur, independent of In contrast, we build "covering" committee of size l + 1: c₁- plus one candidate for each bit position where others first diverge from b;-. Since discrepancies beyond that position are downweighted by E, every voter has committee member at distance O by shrinking E, the optimal cost can be made arbitrarily small. A k-sized committee excluding C;- thus pays constant cost, whereas a O(log -sized committee has cost tending to 0, making the distortion unbounded.
Next, we construct instances in the plane and on tree metrics where rule excluding at least one out of m candidates can guarantee 1-distortion strictly less than 1 1+ m-I
Theorem 16. For any number of candidates m and any > O, there exist instances of the (m 1)- committee election problem in the 2D Euclidean metric for which no voting rule can guarantee 1-distortion factor less than + m-1
Theorem 17. For any number of candidates m and any 0, there exist instances of the (m 1)- committee election problem with tree metrics for which no voting rule can guarantee a l-distortion factor less than m-1
The proofs of Theorems 16 and 17 share the same idea. We construct m + 1 metric instances Jo....,Im with identical candidate rankings but very different distances. In lo. all candidates lic one vertical line and all voters candidate c,. For each j E [m]. instance Iú moves uj and Cj far to the right, leaving all other points fixed; this preserves ordinal preferences, so any rule using only rankings must output the same (m - 1u-subtet on all instances.
parallel line, each voter is closest to the "matching"
In 1j. excluding ej greatly increases cost: Uy is now at distance of about & from every selected candidate, whereas including only e keeps all voters within a distance of roughly é + 1. Summing voters, any (m -)-oommiteee omitting ey has cost on the order of (m + 1)6, while the optimal cost is about (m () 1). Thus
(m 1)e
(m- ()( 1) R3 1+
m
and by choosing large enough (as function of make the deviation from this limit smaller than E. The tree-metric version embeds the same "left vs. far-right" geometry into a tree (c.g., via long paths or star) with the same effect.
Lower bounds for the max-cost We now bound the distortion for the max-cost objective. In 2D Euclidean space, when selecting m out of candidates, cannot guarantee distortion less than 3, matching the distortion when selecting only one candidate. For the line metric, we then show that our algorithms that select & 2 and & = 3 candidates are tight.

---

Published as a conference paper at ICLR 2026
Theorem 18. Any deterministic algorithm for the k-committee election (with respect to the max- cost) that selects at most l < m candidates out of m candidates must have a I-distortion of at least 3 E for any E >> 0.
We define + plane instances Io..... I'm with identical ordinal preferences. In Io. all candidates lie on one vertical line, all voters on parallel line, and each voter 8; ranks a first. For Ij. we push ej and vy far to the right so that vi is at a distance of about 3 from every candidate except Cj. while all other distances (and rankings) are unchanged. Any deterministic, ordinal rule must choose the same committee C' on all these instances. Since h < m, some candidate Cj is not chosen; in 1T, the max-cost of C' is then driven by uy. who sees all selected candidates at distance of about 34, whereas the optimal solution picks Cj, keeping everyone within a distance of roughly + 1. Hence
cost co,tm(C,T, (Pjm({j)
3
3.
E+1
and for large& the distortion is at least 3 e.
Theorem 19. Any deterministic algorithm for the 2-committee election (with respect the max- cost) when voters and candidates are located on a line must have 1-distortion of at least 2 - e for any 0.
For Theorem 19 we consider three voters and three candidates on a line with the cyclic preferences
C1 C2 > Cs. U/ : C2 C1 C3: U/s : C3 C2 > C1- We realize these rankings by three different metric instances on the line. In each instance, exactly one candidate is "good center" with max distance at most 1 to every voter, and for each of the other two candidates, some voter is at distance 2 - E. Thus, in one instance, Cj is uniquely optimal, in another C2. and in the third c3- Any deterministic 2-committee rule based only on rankings must output the same pair on all three instances. Whichever candidate it omits is uniquely optimal in one instance, where any 2-committee excluding it has max-cost at least 2 E, whereas the optimal committee including it has cost 1.
Theorem 20. Any deterministic algorithm for the 3-committee election (with respect to the max- cost) when voters and candidates are located on a line must have a 1-distortion of at least 3/2 - E for any 8 > 0.
The proof of Theorem 20 uses four voters and four candidates on a line. We fix a symmetric pref- erence profile where U1 02 strongly favor Cı, C2 and v3, strongly favor c3, Ca, and build four line instances J,,..., 14 realizing these rankings but with different locations: in I,, candidate e; is well- centered, at distance at most 2 from every voter, whereas voter v, is at distance at least 3 - 2s from all other candidates. Thus, in L,, the optimal max-cost is at most 2, achieved by including c, while any committee excluding e, must incur max-cost at least 3 2= because of 24 Any deterministic 3-committee rule must omit at least one candidate and cannot distinguish between the four instances by rankings alone, so for some T; it omits the uniquely good candidate. In that instance, its distortion is at least 25
-, showing that our upper bound of 3/2 for the line metric with k = 3 is tight.
CONCLUSION AND FUTURE WORK
In this paper, we initiate the study of the metric distortion problem under a bi-criteria approximation framework, namely whether one can match the cost of the optimal single candidate using only a fixed number of candidates. For the line metric, we show this is achievable: two candidates suffice for the utilitarian objective and four for the egalitarian objective, and for the latter we also give smooth trade-off between committee size and approximation factor. We complement these results with matching lower bounds, establishing tightness on the line and showing that equally strong guarantees fail in richer metrics such as the 2D Fuclidean plane or tree metrics.
Looking ahead, several directions remain. One is to fully characterize the metric spaces in which a constant-size committee can achieve optimal I-distortion. Beyond this structural question, is also natural to determine whether, in general metrics beyond the line, one attain I-distortion strictly better than the best achievable single-winne bound. Another direction is to investigate whether randomized mechanisms can improve guarantees in settings where deterministic mechanisms cannot attain optimal I-distortion. One can also explore metric distortion and the k-committee election problem within this bi-criteria framework when only limited cardinal information is available.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work is partially supported by DARPA expMath, ONR MURI 2024 award on Algorithms, Learning, and Game Theory, Army-Research Laboratory (ARL) grant W911NF2410052, NSF AF:Small grants 2218678, 21 2114269, 2347322. Diptarka Chakraborty was supported in part by an MoE AcRF Tier grant (TI 25 251RES2303) and a Google South & South-East Asia Research Award.
REFERENCES
Soroush Alamdari and David Shmoys. A bicriteria approximation algorithm for the k-center and k- median problems. In Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers 15, pp. 66-75. Springer, 2018.
Toannis Anagnostides, Dimitris Fotakis, and Panagiotis Patsilinakos. Dimensionality and coordi- nation in voting: The distortion of stv. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 4776-4784, 2022.
Elliot Anshelevich and John Postl. Randomized social choice functions under metric preferences. Journal of Artificial Intelligence Research, 58:797-827, 2017.
Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264:27-51, 2018.
Elliot Anshelevich, Aris
Christopher Jerrett, and Alexandros Voudouris. Improved metric distortion via threshold approvals. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 9468, 2024.
Duncan Black. On the rationale of group decision-making. Journal of political economy, 56(1): 23-34, 1948.
Ioannis Caragiannis, Nisarg Shah, and Alexandros A Voudouris. The metric distortion of multiwin- ner voting, Artificial Intelligence, 313: 2022.
Joannis Caragiannis, Evi Micha, and Jannik Peters. Can few decide for many? the metric distortion of sortition. In Proceedings of the 41st International Conference on Machine Learning, ICML 24. JMLR.org, 2024.
Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for randomized social choice. In Proceedings of the 2022 Annual ACM-SIAN Symposium on Discrete Algorithmm (SODA). pp. 2986-3004. SIAM, 2022.
Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang. Six candidates suffice to win a voter majority. arXiv preprini arXiv:2411.03332 2024a.
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu. Breaking the metric voting distortion barrier. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1621-1640. SIAM, 2024b.
Xujin Chen, Minming Li, and Chenhao Wang. Favorite-candidate voting for eliminating the least popular candidate in metric space. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp. 1894-1901, 2020.
Edith Elkind and Piotr Faliszewski. Recognizing 1-euclidean preferences: An alternative approach. In International Symposium on Algorithmic Game Theory, pp. 146-157. Springer, 2014.
Edith Elkind, Jérôme Lang, and Abdallah Saffidine. Condorcet winning sets. Social Choice and Welfare, 44(3):493-517 2015.
Edith Elkind, Piotr Faliszewski, Piotr Skowron, and Arkadii Slinko. Properties of multiwinner voting rules. Social Choice and Welfare, 48:599-633 632, 2017.

---

Published as a conference paper at ICLR 2026
James M Enelow and Melvin J Hinich. The spatial theory of voting: An introduction. CUP Archive, 1984.
Bruno Escoffier, Jéröme Lang, and Meltem Öztürk. Single-peaked consistency and its complexity. In ECAI 2008, pp. 366-370. IOS Press, 2008.
Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A challenge for social choice theory. Trends in computational social choice, 74(2017):27-47, 2017.
Dan Feldman, Amos Fiat, Micha Sharir, and Danny Segev. Bi-criteria linear-time approximations for generalized k-mmenn/median/centee: In Proceedings of the twenty-third annual symposium on Computational geometry, pp. 19-26. 2007.
Michal Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. In Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 269-286, 2016.
Dimitris Fotakis, Laurent Gourvès, and Panagiotis Patsilinakos. On the distortion of committee election with 1-euclidean preferences and few distance queries. arXiv preprint arXiv:2408. 1755, 2024.
Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion con- jecture. In 2020 IEEE s Annual Symposium on Foundations of Computer Science (FOCS), pp- 1427-1438. IEEE, 2020.
Ashish Goel, Anilesh K Krishnaswamy, and Kamesh Munagala. Metric distortion social choice rules: Lower bounds and fairness properties. In Proceedings of the 2017 ACM Conference Economics and Computation, pp. 287-304, 2017.
Ashish Goel, Reyna Hulett, and Anilesh K Krishnaswamy. Relating metric distortion and fairness of social choice rules. In Proceedings of the 13th Workshop Economics of Networks, Systems and Computation, pp. 1-1, 2018.
David Kempe. An analysis framework for metric voting based on Ip duality. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 2079-2086, 2020.
Fatih Erdem Kizilkaya and David Kempe. Generalized veto core and practical voting rule with optimal metric distortion. In Proceedings of the 24th ACM Conference on Economics and Com- putation, pp. 913 936-936,720 2023a.
Fatih Erdem Kizilkaya and David Kempe. Plurality veto: A simple voting rule achieving optimal metric distortion, 2023b. URL httthtt/s///xiiv www.oorg//bbbaoeeee /2006.2262222222 07098
Alexandra Lassota, Adrian Vetta, and Bernhard von Stengel. The condorcet dimension of metric spaces. arXiv preprint arXiv:4410009201, 2024.
Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. Approximation algorithms for metric facility location problems. SIAM Journal on Computing, (6(2):11-4332 2006.
James A Mirrlees. An exploration in the theory of optimum income taxation. The review of economic studies, 38(2): 1971.
Ariel D Procaccia and Jeffrey S Rosenschein. The distortion of cardinal preferences in voting. In
International Workshop Cooperative Information Agents, pp. 317-331. Springer, 2006.
Haripriya Pulyassary and Chaitanya Swamy. On the randomized metric distortion conjecture. arXiv preprint arXiv:2111.08663 2021.
Dennis Wei. A constant-factor bi-criteria approximation guarantee for k-means++. Advances in
neural information processing systems, 29, 2016.
12

---

Published as a conference paper at ICLR 2026
A LINE METRIC ELECTION: THE ORDER OF CANDIDATES AND VOTERS
In this section, we present an algorithm to determine the order of candidates and voters for any line metric election instance & C) based on the voters' preference profiles. This step is essential for establishing the upper bounds discussed in Section 3 Moreover, this approach may prove useful for future research, it offers general method for obtaining the total order of candidates and voters, as explained below.
This algorithm focuses specific subset of candidates with properties useful for the purposes of this paper and potential future work on line metric distortion. This subset has the following property:
Definition 21 (Core). In election & (V, +,), subset A S C' is called core if for any voter 2/2 E V, any candidate ej E A, and any candidate c E C A, we have > Ck-
Also, we are able to retrieve the order of voters based on this subset of candidates. Therefore, we define the following notation:
Definition 22. For a subset of candidates A C C, the order of voters with respect to A is a sequence of voters such that voter 2 become beforev, in S, if the preference order of candidates A by U; is lexicographically no greater than the preference order of candidates in A by 2' when is sorted according to some fixed order SA.
Consequently, the main theorem of this section is the following:
Theorem 23. For election & (,) the line metric such that d D> E, There exists an algorithm that identifies:
1. A core subset of candidates C*:;
2. The order of C candidates, denoted as Sc; and
3. The order of voters with respect to C*, denoted as Sv.
Based on Theorem 23 the algorithm introduced this section determines the order only for a subset C", referred to the determined candidates, rather than for all candidates. It expands C* iteratively and establishes the order of candidates within C By the end of the algorithm, C" forms subset of candidates.
Additionally, for some voters with similar preferences, it may be impossible to distinguish whether they the right left; thus, they are considered be at the same point. These properties of the voter and candidate order retrieved by the algorithm are accounted for in the analysis and other sections of this paper. Overall, obtaining the order of voters and candidates with this level of accuracy remains significant for the intended purposes.
The algorithm consists of three parts. The first part, referred as SplitLine, involves dividing the line into two halves and determining whether each candidate occurs on the left right side Candaaaddaaeeee
(some remain undetermined). The second part, referred to of candidates in each half and merges the sorted lists to obtain total ordering. The final part, referred as SortVoters, determines the ordering among the voters based on the retrieved order of candidates. Algorithm demonstrates how these three components contribute to sorting the candidates and voters.
finds the order
ALGORITHM 1: Sort candidates and voters
Input: Election instance E.
Output: Sequence So as the order of determined candidates and sequence Sy the order of voters.
Function SortCandi worrtcannidrreeerdvotttrtt (E (V)
(L, I7) <- SplitIine((
Se SortCandidates(>1..
Sy SortVoters(E,Se)
return SS)
13

---

Published as a conference paper at ICLR 2026
SplitLine. In this part, we first find pivot to split the line that point. To achieve this, introduce the following definitions. We arbitrarily choose the first voter as the pivot voter, associated with two pivot candidates follows.
Definition 24 (Pivot Voter and Candidates). The voter is called the pivol voter. Additionally, the two nearest candidates to the pivot voter are called the pivot candidates. Without loss of generality, assume that e1 and C2 the two nearest candidates to the pivot voter v1, with e₁ positioned to the left of C2- Note that C1 and 22 may both be on the same side of U1.
Finally, the point where the line is split defined as follows:
Definition 25 (Pivot Point), The midpoint of the line segment between the two pivot candidates is called the pivot point, denoted by p. Let L and R be the subsets of candidates on the left and right sides of p. respectively.
Finally, we aim determine whether candidate belongs to L or R. Therefore, we formally define determined and undetermined candidates as follows:
Definition 26 (Determined Candidates). A candidate is determined if is known whether the can- didate belongs to L or R based Definition 25 Otherwise, the candidate is undetermined. Let C = LU R be the set of determined candidates
Initially, based on Definition 24 we know that e₁ and 02 E R. Thus, C' = (2), Then, in multiple iterations, we expand 7, and Rt by adding as many candidates possible. Therefore, at the end each iteration, we update C' such that C = L R again. We also ensure that C always forms consecutive subset of candidates on the line. The process for determining new candidates in each iteration is as follows:
If there exists voter et such that two candidates с and e satisfy ek b-s Cj. where oj E C but Cj E C", then we can determine C 's membership as follows:
If both ei and 62 are closer to vy than ct, then, if ej is in L, e would be R, and vice versa.
Otherwise, C would be in L if c1 is closer to and c would be in R if is closer to
Algorithm is pseudocode for the function Determi ne, ne, which determines a candidate the above conditions hold and adds it to the corresponding set. Algorithm 3 determines many candidates as possible in each iteration while maintaining the succession of the determined candidates (see (see for proofs). We call these candidates Cnew- At the end of the iteration, merges Cnew into C*, It is important to note that we do not add each point immediately to C*; instead, we merge them all at the end. This approach ensures that C* remains a consecutive list of candidates, which crucial for our analysis.
The output of this procedure is L and R, which represent the determined candidates on the left and right sides of the pivot point p. respectively.
AL.GORITHM 2: Determine candidate with determined candidate a voter's ordinal preference
Input:
Ordinal preference of voter vs, denoted by >;; candidates cy and c. where e > Cy. Cj is determined, but cı is not; two sets L and R containing currently determined candidates on the left and right sides of the pivot point respectively; and pivot candidates and cz.
Output: Updated sets L and R including candidate Ck.
Function Determirs (> Cjj Ge; T., R, c1, e2)
c1 >5 Ck and 02 > then Add to T if cy R; otherwise, add C to R
eise
Add cs to ef >; ex: otherwise, add cs. to R
end
return (L, R)
SortCandidates.
The goal of this part is to sort the candidates in and R. We know that L lies to the left of p. and R lies the right of p, where p is the midpoint of the segment connecting the
14

---

Published as a conference paper at ICLR 2026
ALGORITHM 3: Determine Candidates
Input: Election instance &.
Output: Two subsets L and At of candidates, where candidates are on the left and right the pivot point respectively.
Function Splitline (E (V)C,>));
{
- {02]
C (2)
repeat
Cnew
while 3(8, C,, ci) : on X e and cu # and ej E do R, cı, 02)
(L, R) + Det
Cnew + Cnew U {ot}
end C U Cnew until Cnew return (L,R) R)
11
13
Consequently, in the ordinal preference of U1, candidates L with higher preferences are positioned to the right of those with lower pref- erences. Similarly, candidates R with higher preferences lower preferences. By combining these two observations, we can sort the candidates based on their positions along the line. Algorithm presentss
Two nearest candidates of Ui (see Definitions 24 and 25
positioned to the left of those with
presents the pseudocode for this approach.
ALGORITHM 4: Sort determined candidates
Input: Preference order of th. denoted >-1, and R, candidates on the left and the right side of pivot Output: Sequence Sc, sorted candidates in T. and R by their position left to right.
Function SortCand dates (>-1, T., R):
Sc is an empty sequence candidates for i.frm to m do
Let ej be the i-th candidate in the preference order of vı, i.e., 1, if c; L then
Add с the extreme left Sc
else if c, then
Add C2 to the extreme right of Sc
end
10
end
11
return Sc
SortVoters. This part focuses on sorting voters given the sorted determined candidates. The key observation is that voter who prefers one candidate over another tends to be closer to the candidate they prefer more. Consequently, we have a method to compare two voters. For a pair of voters vs and ej. assume l is the smallest index where the ordinal preferences of o and V/ differ. the left side vy if > is on the left side > Recall that the notation > p.g represents the q-th candidate in the preference order of voter Upp If -, and - not determined, assuming v; and vi are at the same position does not affect the further analysis (see Sections A.I). Algorithms and illustraasss how function SortVoters works.
is on
A.1 ANALYSIS
This part focuses on verifying that the order of candidates and voters has been correctly calculated.
First, recall that the algorithm returns the sequence Sc the order of candidates (Line of Algo- rithm T This sequence contains only determined candidates, denoted as C = LU R. Additionally, in Line 4f of Algorithm
calculate the order of voters based on Sc-
is important to note that for the remainder of this section, lemmas consider a specific line metric election instance.
15

---

Published as a conference paper at ICLR 2026
ALGORITHM 5: Compare two voters based on determined candidates
Input: Two voters e; and Uj. preference profile > and order of determined candidates Sc.
Output: An integer in [-1, -1 if left of Vy, 0 if they share the same position, and if is right ey.
Function comparevoters (v,, Ug >, Sc):
Let & be the min index where the preference orders of ny and by differ, i.e., the smallest kt E [mm] such that >. if no such exists iik not Se then
return
else s. appears before j in Se then
return-1
else
return
end
ALGORITHM 6: Sort vaters
Input:
Election instance &, and order of determined candidates Sc.
Output: Sequence of all voters from left right Sv.
Function SortVoters (E = (V, C, >), Sc)
Let Sy be the sorted elements using comparison function CompareVoters
return Sv
First, the following lemma demonstrates that a prefix of a voter's ordinal preference forms a consec- utive subsequence of candidates.
Lemma 27. For any voter vy V and < k: m, the most preferred candidates of voter us form
a consecutive subsequence of candidates.
Proof. Assume the condition does not hold for voter e and some k. Since any single candidate forms consecutive subsequence, we must have & > 2. Let denote the k most preferred candidates by the voter 8y By assumption, there exist two candidates C₁2 Cr E such that a candidate Cm E C' A lies between them.
Assume without loss of generality that ej is to the left cm and c, is to the right of cm Further, suppose v; is located the left of Cm- Since cn & A, we must have Gr >0;; Cm- However, since the candidates are arranged in a line, it follows that Cm Toz Cr. which is contradiction (illustrated in Figure
C
Cyn
Figure 4: This figure is the illustration of the succession of nearest of any voter.
Corollary 28. ei and 02 are consecutive.
Next, recalling the definitions of determined and undetermined candidates (Definition 26). the fol- lowing lemma formally proves that the function Determin ne in Algorithm 2 correctly determines an undetermined candidate.
Lemma 29. Assume that C* is consecutive subset of determined candidates, including e₁ and c2- If there exists voter vi and candidates c, E C and c* & C* such that C& > Cj. then the function Determine correctly determines Ck.
Proof. Let consider two cases regarding the positioning of cı C22 and e₁ in the ordinal preference of v;-
Case 1: Both ei and 62 positioned before eg in the ordinal preference of o;-
16

---

Published as a conference paper at ICLR 2026
Without loss of generality, assume that Cj is in R. We use proof by contradiction to show that Oj: is in L. Assume that çj is in R. Consider the prefix of the ordinal preference of o ending with Cg- By Lemma 27 they must form consecutive set of candidates. Therefore, Cj must be the right side of cs- However, since C* consists of consecutive candidates, c would necessarily be positioned on the right side of cj. Because of the contradiction conclude Cg is in L (illustrated in Figure5)
G
02
Ch
Cj
Ck
61
Figure 5: For a voter v; we have ei >; Ck. 02 >3 CR. and CR > Cbs then on and ej cannot both be in the same side of p. The figure above illustrates this contradiction, while the one below shows that they can be on opposite sides.
Case 2: At least one of e and 02 is positioned after eg in the ordinal preference of 04--
Without loss of generality, assume that C1 precedes C2 in the ordinal preference of u, Consider the prefix of the ordinal preference v2 that contains ei and og but not c2. By Lemma 27 this prefix must form a consecutive sequence of candidates, meaning 62 cannot lie between and cg. If ca were in R. C2 would lie between 61 and Cj. as Gj and C2 are consecutive.
This contradiction implies that eı is in L (illustrated in Figure 6).
Ck
C2
Figure 6: For voter Ui if we have C1 >; and c >; C22 then is in L. The figure above illustrates that if o were in R, then e2 would be in the consecutive subsequence of e and ck. which is a contradiction. On the other hand, the one below shows that Cg must be in L.
As explained in Lemma secutive. The following lemma shows that the beginning of each iteration, C* is consecutive subsequence of candidates.
29 determining a new candidate works if the current set of C* con-
Lemma 30. In Algorithm 3 at the beginning of each iteration (Line 5). all determined candidates, denoted as C*, form consecutive subsequence of all candidates.
Proof. Let CJ be the set of determined candidates at the beginning of the i-th iteration. We prove that for any Of is consecutive subsequence. Ci (2), satisfies the condition. (Corollary 28
In the (i 1)-th iteration (i > 2). for any voter uj, let last, be the least preferred candidate of 0j in Ch Then, by Lemma 29 by the end of iteration - 1, any candidate C such that C₁ > last, is determined. The set of candidates e for which C > last, is denoted by Py; note that C; C P,- As P, is a prefix of the ordinal preference of uy, by Lemma 27 P, is a consecutive subsequence of Pz.
candidates. Also Pj contains e and ca because (c1, C
17

---

Published as a conference paper at ICLR 2026
Since C - Uew (Line 11 and Cnew = (P, Ci-1), have C; = U observe that union of intersecting intervals is always an interval (this can be seen from a straight- forward inductive argument). Since Pj for all j contain {e1, 02). follows that C is a consecutive subsequence as well.
P.. However,
Next, show that C* is core subset of candidates.
Lemma 31. By the end of the algorithm 3 C* is core, i.e., for any voter ui candidate cj E C* Ck C", we have Ej > Ck-
Proof. Assume otherwise that C2 > G, Then, we can determine C using ej and voter uy according to Lemma 29 and consequently, Algorithm cannot have terminated at this point. Therefore, > C for any voter 84.
We now demonstrate that the function SortCandidates in Algorithm 4 returns the determined candidates in sorted order from left to right.
Lemma 32. The procedure SortCandi dates correctly sorts determined candidates, denoted as C U R from left to right.
Proof. Recall that sets L and R contain determined candidates (Definition 26). Now, consider the ordinal preference of v1. For any pair of candidates c, Cj. L. show that d c1) S d(cy,c)) c1) if
C, >> Cj.
There are two cases:
Cj is on the right side of v1 (Figure 7): we have:
d(cr, d(ej, e d(ei, 01) d(ci,vi) d(c), + d(ci,v)
d(c,, v1) d(c
Cj is on the left side of 01 (Figure RD; have:
d(c.,a) d(g, (1) d(c,, 01) + d(c1, v1) d(cj, 01) d(c1,e)) v1)
= d(c;, 01) - d(ej,
Therefore, we have:
d(c,,r)) dic + d(c; un) S d(cj,v))
Based on the definition of ordinal preference, we have d(c, v1) s d(c;,v) if a ej. Conse- quently d(c,, c1) S ((),,e) i >1 Cj.
Similarly, for any pair of candidates c,, C E R. we can show that d(c,, S 02) if X e.gj.
d(c,.c)
d(ci c1)
Cj
0
d(ci, v1)
d(c,, v1)
d(e,, v1)
Figure 7: Illustration of the scenario where is positioned to the right of e1.
The procedure SortCandin Candidates dates processes candidates according to > adding them to the left of Sc if they are L and to the right otherwise. Therefore, So contains candidates in the correct order from left right.
18

---

Published as a conference paper at ICLR 2026
d(c).
(())
d(c
Cj
d(cs, 01)
d(c,,
Figure 8: Illustration of the scenario where (j is positioned to the left of 01.
Next, show the correctness of the function Sort Lemma 33. The procedure VortVorers finds the order of voters with respect to the determined candidates.
Proof. By Lemma 32 we have the order among the determined candidates. Assume that for candi- date Gi, order.; the index of e; from left right. As SplitLine determines prefix for each candidate, for a voter ti, we let sequence sorted; = order ordery ordery,,, where is the number of determined candidates. Now, we can compare voters' sorted sequences lexicograph- ically. A voter with a smaller sorted is on the left side of voter with larger sorted. It is important highlight that this approach may result in ties among some voters in the ordering.
Next, we prove Theorem 23
Proof of Theorem 23 By Lemma 31 Algorithm [ first determines core subset of candidates. Then, according to Lemma 32 it finds the correct order for this subset. Lastly, Lemma 33 demon- strates that the algorithm establishes correct order with respect the order of determined candi- dates. Therefore, Algorithm correctly identifies all three, the theorem follows.
A.2 FIND THE EXACT ORDER OF VOTERS
In this part, we extend the order result by proving that it is possible to determine the exact order of all voters, formally:
Theorem 34. For any election & consistent with line metric, it is possible determine the ordering of the voters along the line. Furthermore, one can derive an ordering of the candidates that is consistent with this metric.
Algorithm determines the order for subset C* of candidates. Consequently, the first [C*| candidates in any voter's preference order are C*, By examining the candidate at [C*[++-th position in each voter's ranking, observe two cases.
There exists unique candidate such that every voter ranks e, in the (IC*I+1) position.
There exist two candidates, e; and cj. such that for each voter, the candidate in the (IC*) + 1)-th position either & or Gj-
is important to note that no more than two different candidates can appear in that position.
In the first case, does not create any distinctions between voters, as removing this column from the preference profile has effect.
In the second case, we can make the following assumptions:
First, if all voters, based on our prior knowledge, are in the same position, we assume c; is to the left of cj. Otherwise, there voters Up and vy for whom we know they not in the same position, with one preferring o; and the other preferring cj. This allows us to determine the order between e; and cj-
19

---

Published as a conference paper at ICLR 2026
Second, when the candidates in C* are excluded, the candidates c; and сy appear consecu- tively on the line.
Excluding candidates in C² these two conditions enable us to re-run Dartaanddattesddvvver
leading to more determined candidates and more accu- rate order of voters. Furthermore, this process can be extended by recursively running the algorithm the remaining candidates until candidates remain. At that point, any voters who do not share the same preference orders will be distinguished, and the result will be the exact order of the voters.
Algorithm 7 outlines this approach in pseudo-code. In this pseudo-code, the notations > and (1) represent the preference order of all voters and voter Vi respectively, starting from the I-th index. Additionally, denotes the concatenation of sequences, and set operators can be applied to sequences well. It is also important to note that for SplitLine, determined candidates at the beginning. This is not explained in Algorithm but it can be applied by replacing the first three lines of Algorithm 3 with the input of and R as the determined candidates.
input L and R as the
ALGGRRITM 7: Find the exact order of voters
Input: Election instance = CV,
Output: Sequence Sy as the exact order of voters.
Function WindVotersOrder
(V,C,))): (Sc.Sv) + SorrCanaiiieeeecceooeorrrrr
C
Se
L-
|Sc| +
while C + do
Can t for E C' Fe, such that > Gi}
CCaal = then
C c Cirst
1+1
continue
11
end (et,c,)= <- Cuus
if all voters in Sy do not have equal positions then
Let Ups vy be two voters with different positions Sy such that > e, and - Cj Swap a and cy if up is on the right side of 0q
15
end {c} R {c:}
17
18
19
(I, R) + splitLLne((V,CC>>>) R)
20
Ser + SortCandidattss(>>>>>> , R)
21
Se (Sor D) Sc (Ser n R))
Sy Sortvoters(E,
23
- Se
24
1 + ++ See
end
26
return Sv
Analysis. Now, we focus on the correctness of the approach explained earlier. Recalling the defi- nition of core candidates (Definition 21}. define the covering range as follows:
Definition 35 (Covering Interval). We define the range [7. r] as the covering interval for election = (V, C, >) and a core subset of candidates C* it is the smallest interval that includes C* V.
We first show that this interval does not contain any other candidates.
Lemma 36. For an election & = (V, C, >) and core subset of candidates C*,, [[,r] be the covering interval. Any candidate E C' C* lies outside the range [1, r).
Proof. Assume, for the sake of contradiction, that there exists a candidate C; & C" lying within the interval [t, r). We consider three cases:
20

---

Published as a conference paper at ICLR 2026
m
C2
2/2
|
Cbackup
Figure 9: This figure illustrates the preference profile. Each row represents the preference order of voter. The first [C7*] cells in each row form the set C while the candidates in the next column form the set Chackup-
If all voters the left side of Cts exist cj C* in range (c, rl. Then, any voter prefers Cj to cs which contradicts C to be a core.
If all candidates in C are on the right side of c. then there exists voter in range [1, c;) such that es prefers & to all candidate in C* which contradiction.
Otherwise. exists candidate Cj E C on the left side of c; and voter on the right side of G. we know v, prefers c; to Cj which is contradiction.
Consequently, all candidates in C C outside r).
Next, we assume the preference profile be a table with n rows and columns, where each row the preference order of each voter, ordered by priority from left to right. Figure@jillustrates
Then, we define backup candidates as those appearing in the columns immediately following a core subset of candidates (Figure 9
Definition 37 (Backup Candidates). For an election & = (V, x) and core subset of candidates C* let the backup subset of candidates be defined as
Obackup = {or E C' Bu, such that "110++11== c...
This means that candidate c; belongs to Chackup if there exists voter who ranks e; in the ([C*) 1)-th position.
First, we show that backup subset of candidates either has one candidates.
Lemma 38. For election (V, C)> and subset C* that does not cover C, let Cbackup be the backup subset of candidates. Then:
Chackmup E (1, 2). and
iff iif(Chokuppl = 2, all candidates between the two elements of Chackup form C*
Proof. Let [1, be the interval including all V U C*. By Lemma 36 no candidates of Chackup is within interval [1, r]. Assume that on one side of the interval r. there exist two candidates of Obackup- We refer to them c; and ej and assume, without loss of generality, that they are located in (-oo, 1), and is to the left c. Then, for any voter v e V, e would prefer e; to cj which contradicts ey being included in Cbackup illustrated in Figure 10
21

---

Published as a conference paper at ICLR 2026
(a) This case cannot happen as all voters prefer c, Cy-
Ck
(b) This case can happen without any issues.
Figure 10: Illustration on the number of elements in Cbackup
Consequently, each side has at most one candidate in Checkup- Furthermore, by the same argument, no candidate in C (C* U Cbackup) can be positioned between the two candidates of Chackup
(V, and core subset C* that does not cover C, let Chackoup be the backup subset of candidates that has two candidates. Then, Chockup is consecutive subsequence of C*C*
Corollary 39. For an election
Lemma 40. For an election & (V,C,>) and C* core subset candidates not covering C. Assuming Cheokup is the backup subset of candidates for O", If [Chackupl 2 and the order of voters with respect to C* distinguishes least two voters, we can determine the order Chackup-
Proof. Based on Lemma 38 if Cbackup = fc,, c. then each of them is on one end the line. Let Vi and V, be the set of leftmost and rightmost candidates with respect C As C* distinguishes at least two voters, V/2 * V,. The goal here is find on E Vi and u, E V, such that iz prefers one of {c, eÿ} while er prefers the other. In this case, we can conclude which of e and c, is on the left side of the other. Let
Ciackup = {cr E 1 E Vi V, such that --10-111-css
Now, it suffices to show that I Caackupl 2, that Chackupl 1. Without loss of generality, let Chackup = {(s)- Then, there exists voter Um Vi V, such that mm, Cj. By Lemma 38 know that c and ej are different sides of V and V,.. Additionally, um is positioned between Vi and Vr, which leads to contradiction since both and V, prefer cj Figure II illustrates this.
easily choose in and u,- Suppose instead
V1
Uma
X
Figure 11: This figure illustrates that when V,, prefers e; and ej on right side of V,, voter Um cannot prefer ej over G,
Next, we focus on the order of voters in the case |C*|=
Lemma 41. For an election = [V,C,>] and a core subset of candidates C*, if Chackup contains only one candidate c₁ then for any subset A S C that does not include G,, the ordering of voters with respect to A is the same as the ordering of voters with respect to AU {cs).
Proof. Recalling the definition of "with respect to" (Definition 22 voters compared based on the preference profile the given subset in lexicographic order. Assume the order with respect to A U {cz). We know that c; has fixed position in all voters' preference orders. Additionally, the set of candidates before this position is disjoint from the set of candidates after it.
Thus, comparing voters involves two steps:
22

---

Published as a conference paper at ICLR 2026
First, compare the portion of the preference order before ç; lexicographically.
If they identical, then compare the portion after c; lexicographically.
Due to this disjointness, the order with respect to A follows the same structure. Consequently, the order of voters in both cases is identical.
Finally, we provide the proof of Theorem
Proof of Theorem 34
We are showing that Algorithm 7 provides the exact order of voters. First, da e LesAnneoteerrrreeeee and according to Theorem 23 determines the order of
it runs candidates for a core subset and retrieves the order of voters with respect to this order.
In each iteration of Line one or two candidates.
by Lemma 38
the next position in the preference profile contains either
If it contains candidate:
We can include this candidate C*, resulting a larger core.
Additionally, by Lemma 41 the position this candidate does not affect the order of voters, we can skip it in the order of this core subset.
On the other hand, if it contains two candidates:
We determine their order using Lemma 40
Then, excluding C*, Corollary 39 ensures that these two candidates consecutive, allow- ing us to identify additional candidates using SplitLine.
Next, we sort them based on the order of the first voter, as Lemma 36 and Lemma 38
indicate that the first voter positioned between these two candidates.
Furthermore, by concatenating the left and right parts of this newly ordered candidate set, we obtain a larger core with its sorted version.
Lastly, sort the voters based on the expanded ordering of candidates.
By the end the algorithm, since core extended each step, all effective candidates are considered in the voter ordering. Therefore, the exact order of voters is identified.
B PROOFS OF UPPER BOUNDS ON DISTORTION FACTOR
B. UPPER BOUNDS FOR SUM-COST
Lemma 6
When considering the sum of distances objective and the candidates and voters are located on the real line, of the candidates directly the right left of the median voter will be an optimal candidate.
Proof. Denote the median voter as v. Assume the chosen candidate is not immediately to the left or right of v. Without loss of generality, let consider that the chosen candidate lies to the left of v. and denote the first candidate to the left as er. now formally show that replacing e with e results in solution that is at least as effective in minimizing voter distances.
The change in the total distance is given by:
A (dl(u, d(u,c))
Σ (d(u,a) d(u.c)) Σ (d(u,a)-d(uuc)) NER.
HEL.
where L, = {u E u < 2} represents voters to the left of v, and R, = (u E V 1uz1 v} represents voters to the right of (including itself).
23

---

Published as a conference paper at ICLR 2026
For each voter Rg, since both and et are to the left of these voters, we have:
Vu E Res d(u, d(u, d(e,
For each voter Lu, observe that: Substituting these relations, the change in total distance can be bounded as:
Yu E Lu, d(u,a) S d(u, d(e,
A Σ d(c,c)) - Σ
d(c,c) |o d(c, et) - -Rell -.ll
NER.
Since v is the median voter and belongs to Ry it follows that Lel S [Re.. Thus:
A 0.
Therefore, replacing e with ey does not increase the total distance, ensuring that choosing ot is at least as good as choosing c.
Since is the median voter, there are least as many voters to the right of e (including e) as there to its left (excluding v). Therefore, the total cost cannot increase when moving from to e, implying that the cost of ç at most the cost exists, any candidate farther to the right will have a distance that is at least as great. Hence, either or or will be an optimal candidate that minimizes the total cost.
Similarly, if a candidate o, directly to the right of
Lemma 7, There exists voting rule for the 3-committee election the line metric such that the resulting committee includes an optimal candidate.
Proof. First, algorithms in Section A (see Theorem 23 Additionally, by Lemma 31 any candidate &f C* cannot be optimal candidate, since will be farther from all voters than any candidate in C Thus, we can ignore the candidates outside C* and proceed with the remaining candidates.
determine the order of a subset of candidates C* and all voters based on the
Now, consider the median voter in the ordering of voters. We note that there might be tie between multiple voters for this position, but we will only utilize the voter's closest candidate, which will be the same for all tied voters.
After identifying the median voter, we consider u's closest candidate c. This candidate will be either the one immediately the left or the right of the median voter v. Next, we use the ordering of the candidates to find the candidates set {c, ct c, guaranteed to include an optimal candidate: if e to the left of the median voter, then will be the first candidate to the right of the median, and one of candidate by Lemma Similarly, if is to the right of the median, one of e or a will be an optimal candidate. Therefore, the set {c, Ct2 3 will contain an optimal candidate (Figure 12
to the left of с and to the right of c. We claim that the
c, will be an optimal
Figure 12: This figure illustrates that the set of three candidates-ccoprrisin comprising the closest candidate to the median voter, as well as the candidates positioned to the left and right this candidate always includes the optimal candidate. Here, v represents the median candidate, is the closest candidate to v. and o and e, are the candidates on either side. The figure considers two cases based on the position of relative to
Finally, we note that candidates e and c, might not exist. such cases, the candidates to the left and right of are still selected if they exist.
24

---

Published as a conference paper at ICLR 2026
2/2
V3
Vi
V/2
V/3
Figure 13: A figure illustrating three candidates C1 cg2 and 03 along with the possible locations of voters closest to each candidate, V1, V22 and V3. Voters U1. and Dy show examples of voters in each set.
Theorem There exists voting rule for the 2-committee election for the sum-cost objective, on the line metric, such that the resulting committee includes an optimal candidate. Consequently, the 1-distortion of the voting rule is 1.
Proof. By Lemma 7 we can select three candidates that include an optimal candidate. Let C1, C2. and ca denote these candidates from left right. We then define the sets Vi, V2, and V3 the sets of voters who prefer the corresponding candidate to the other two, as illustrated in Figure [3 We note that the Vi, 12, V/3 can be determined using ordinal preferences.
Thus, we can state that
costs
Σ d(v,02)
eEV
Σ 02) + Σ d(1,02)
Σ d(v,c2)
VEV/
VeV/3
d d(c, 02)
Σ
Ed(u,
d(u, 02)
Σ
(d(u, cz) d(c2,cs)
(Triangle Inequality)
'
"EV/
v
Σ
d(u, 02)
Σ
d(t,
Σ
(d(v, 0z) d(c2,
VEV
V
(Vievs d(v, I d(v, ez))
Σ (d(v,c)) d(c3, + Σ d(u,cz)
Σ
(d(u, (3u, d(c2, c3))
VEV2
rEVs
(YoEv, d(u, (2) = d(e, c3) - d C2, c3))
cost, |1 d(c2, (3) + V/s d(c2,cs) 03) (cs), + (1Vg [il) C3).
Similarly, we can show that cost,(c2) (c2) S cost, + (1//- (Vl)) d()2),1). Now, depending on whether [V] VVsl not, can that either cost,(c2) cost,(c)) or cost,
cc)) So we can disregard one of cj and C3 based on this and still find the optimum, as C2 is guaranteed be better candidate than the discarded one.
Theorem There exists voting rule choosing 1 out of candidates achieving a 1-distortion of for the sum-cost objective.
Proof. For each voter v, let first, be their closest candidate. Then, we claim that the voting rule that chooses the candidates appearing most frequently in first achieves the desired distortion. For a given instance, let C be the set of candidates selected by this algorithm and Copt be an (arbitrary) optimal single candidate. If Copt C, then get 1-distortion of 1, and are done. Otherwise, includes every candidate except for Cyn-- Now, we can bound the optimal cost OPT this instance
25

---

Published as a conference paper at ICLR 2026
OPT
Σ iE(N]
d(Copt: v)
d(Copt, 1) +
E
d(Cope, v)
weV first Cups
VEV
Brit,
d(Copts 2)
d(C,o).
first, Cog
first Hecu
where the last inequality follows since for any voter o E V, Virst, C if first, # copt. Let v' be the voter closest to Copt such that first, o Cupt- Then, we can use this to state that
OPT Σ
d(Cogt v))
VEV first, #Cap
Σ VEV first, Frae
CCoop, o')
(n m
d((oopt v²)
dlcc
(first, = Copt for at most n voters based on choice of C?)
and therefore
n Copt: o') S 111 - OPT.
(2)
m
Now, we can bound the cost of C follows:
costm(C) = Σ d(C,o)
VEV
Σ
d(C,u)+ Σ v)
VEV first Fag
NEV
first,
(d(Copps v) + d(C Σ d(C,v)
NEV firu, Cog
NEV first, Paye
(Triangle inequality)
(d(Cope, + cl(Copt v²) + dl dl(ooee v'))
d(C,v)
VEV first Eog
DEV firit (first,r + Copt and first, E C')
S OPT
Σ
2d( v')
(By Equation T
VEV fam cm
OPT 2 d(Copt, v')
(first, Copt for most voters)
m
2
1+
OPT
(By Equation 2
m
B.2 UPPER BOUNDS FOR MAX-COST
LemmaD 9.
If the distance between and u, is D (i.e., D = d(vi, V,)), then the cost for the optimal single candidate OPT satisfies OPT 2 D
Proof. Let Copt be an optimal candidate. The distance between in and Cope is d(vi, Copt), and the distance between u, and Cope is d(vr, Copt). By the triangle inequality:
d(v,, Cape) d(vr, Capt) 2 D.
26

---

Published as a conference paper at ICLR 2026
Thus,
D max(d(vr Cop); d(urr Copa)) 2 2
Therefore, OPT 2 2'
Lemma 10 If there candidates placed between By and Uy, voting rule that selects et and Cr. achieves a
distortion
Proof. In this case, the voters are next to each other in block, with et being the first candidate immediately to the left of all voters and being the first candidate immediately to the right of all voters. So, by selecting e and Gr, we ensure that the closest candidate to each voter included. Therefore, the cost of this set is, at most, that of the single optimal candidate, and thus we conclude that 1 distortion is 1.
Lemma 11 If d(vi, U,) D, then for every voter u, either d(u, v1) S OPT d(u, v,) S OPT.
Proof. Since is a voter between and (recall or is the left-most and or is the right-most voter), we have:
d(v, v) + d(v, D.
Thus, either d(v, v) s 2 or d(e, S
D 2
By Lemma
9
D 2 < OPT. Therefore, we conclude:
D d(vi, v) - OPT, d(v, S OPT.
D
Theorem 12 For any election on the line metric, let o and o, be the leftmost and rightmost voters, and and be the closest candidates to and or, respectively. Then, voting rule f that outputs the set c, satisfies 1-distortion(f) < 2 with respect the max-cost objective.
Proof. Since e is closest to i and we know d(v,, Copt) I OPT, it follows that:
d(11,c)) I d(v,, Cop)) I OPT.
Similarly, d(u,, cx) OPT.
For any voter v, by Lemma 11 either d(u, m) < OPT or d(u, v,) S OPT. Without loss of generality, assume that d(u, v)) S OPT. Then:
d(v, c)) S d(v, d(v q.) S OPT OPT 2 OPT.
Similarly, in the other case:
d(v, c,) < OPT.
Thus, for every voter, the distance to the closest candidate in {q, c, most OPT. Hence, this selection achieves distortion of 2.
Theorem 13 For any election E on the line metric, there exists a voting rule to select three candi- dates, which achieves 1-distortion of 3/2 with respect to the max-cost objective.
Proof. Let and u, be the lefimost and rightmost voters, and and their closest candidates. Using the ordering of the candidates, let &f be the candidate immediately to the left of cr. We claim that the set C = {ct, cr, c achieves distortion of 3/2.
First, we note that any voter the left of e or the right of cf has their closest candidate included in this set. Specifically, for any voter that is either left of c right of c,, the closest candidates are Ci and c,, respectively. For candidates between e, and Gr, the closest candidate either e, or cy.
Now, one of d, Cr must be the rightmost candidate between and ey- Let this be candidate of E c.). We already know that any voter outside the interval between a and et has their closest candidate included. In addition, we have
d(ci, ct) d(cr, vx) d(v), Cupt) + d(Copt: c,) < 3OPT.
27

---

Published as a conference paper at ICLR 2026
Therefore, for any voter u in this interval,
min (d(u, (() & OPT.
So. the maximum distance of any voter to the candidate set C' is at most 30PT/2, /2, and we achieve a distortion 3/2.
Theorem 14 For any election on the line metric, there exists voting rule select four candi- dates, which achieves a 1-distortion of with respect to the max-cost objective.
Proof. Again, we consider the leftmost and rightmost voters by and v,, and their closest candidates a and cy. In addition, choose candidate to the right of e and c, to the left of G, based on the ordering of candidates. Now, one of Ct and of will be the first candidate to the right of by: If ct is to the right of ut, must be the first such candidate. Otherwise, it is the first candidate the left of us so ef is to the right of iz. Let this candidate be of and define c, similarly. Now, any voter o to the left either between q and c/ one of these
of ci has their closest candidate included in the set, two is v's closest candidate or is to the left of ct, in which case must be v's closest candidate. Similarly, the closest candidate each voter to the right of e, is selected (Figure
cj
0r
this figure, the set at e, Gr e has a 1-distortion of 1. Here, v and v, represent the leftmost and rightmost voters, respectively. For u. the closest candidate is et, which is positioned to its left; therefore, oj is the closest candidate to its right. Conversely, for ür, the closest candidate is Cr, which is also the closest candidate to its left, while d, is the next leftward candidate. However, in this case, & is not necessary to achieve a 1-distortion of
Figure 14:
Next, since both of and ct are between en and v, and d(v,, U,) S 20PT, we have d(c), S 20PT. Therefore, any voter between of and c,. has a distance of at most OPT to the closer candidate in {ct c). As every voter is either between of and c, or outside the interval d, c, the distance of each voter to the closest candidate in our selected set is at most OPT, and we get distortion of 1.
C PROOFS OF LOWER BOUND ON DISTORTION FACTOR
C.1 LOWER BOUND FOR SUM-COST
For k 2 3, there exists an instance for the k-committee election (with respect to the sum-cost) where no voting rule choosing & candidates can achieve a bounded distortion even when compared to optimal choice of [log, (k: 1)1 candidates.
Theorem 15.
Proof. Without loss of generality, we assume that & is of the form 2 - 1, and [log, + 1)] +1= + Now, we consider an instance with 2 candidates and voters on a line. We further assume that voters and candidates are numbered from 0 to 2 - 1 and use by to denote the l digit binary representation of for 0 < i 2'. For each 6,, we assume the bits are numbered left to right from to l with the j-th bit shown by bigj.
For any two values 0 i < 2 let LCP:,, be the length of the longest common prefix between by and by. Now, for each voter vt, the preference of v; is determined as follows: For any two candidates c, and c.. if LCP, ir * LCP,,. i,s, U; prefers the candidate with the longer common prefix. Otherwise, let bit, be the first bit in b; that differs from b, and b,. Similarly, let bitz be the first bit b, that differs from b,. Then, if bit; bitz, i/ will prefer candidate c, to candidate c,j otherwise, c, cy-
Now, any voting rule choosing 2 candidates will not choose one of the candidates. Let Ca- be the candidate left unselected. We show that we can arrange the voters and candidates the line such that this selection will have unbounded distortion compared to a committee containing only l + candidates.
28

---

Published as a conference paper at ICLR 2026
In construction, will place each candidate c; and voter 82 the same point and describe the position for each candidate. For each candidate ç₁. let len, = LCP,,- -- be the length of the longest common prefix between b; and b;-. For any candidate and index 0 S j S l 1, let Aa,j equal b j S len,; and eb,,3 otherwise, where 0 < < 1 is a small arbitrary constant (to be set appropriately). Then, we will place candidate C; at
8-1 Ps
leng
h 1=
3
ab, 3
j=len;+1
Now, show that this placement follows the voters' preference orders. First, note that can- didates (and voters) are positioned on the line in increasing order of their indices. To show this, consider candidates o₁ and ej with i < j. Consider the index ind LCP,, where by and by first differ. Since i < J, we must have bi,ind = 0 and bj,ind = 1. Now, hat hyj for t < ind, so we have
ind 1
Pj
hge + hg.ind
1=0
while
ind
Pi
higt +
Σ
hig
t=0
t=ind+1
So, suffices to show that hndind" 2 Et=ine41 hi,e. while
(-1
inidd= S leny, we would have hy.ind 3 3-ind ind
1-1
3-nnd
Σ h S
Σ t=ind+1
3
2
t=ind+
so the inequality holds. Otherwise, if leny S ind, we will also have len; S ind, as b; and by match in the first ind indices. Therefore, we will have hj.ind 2 =3 ind while
3-ind
Σ
h S
3 S
1=ind+1
t=ind+1
In either case, we have shown that S Pj-
Now, take i and candidates 6, and 6, such that is prefers c, Cs- First, consider the where LCP,,- * LCP,,. Since v, prefers c, to C.. we must have LCP,, > LCP,, if they are not equal. Then, have
8-1 Σ t=
8-1
d(v,,c)) = lp, - prl
(he
hrtel
Σ L=PCP
hhe - hr.e
while
8-1 Σ No,e)l 1=0
8-1
d(v, 6o) = pp, Pel =
=
Σ t=L.P...
(bi, - ho,1) 2 IIs.LCP.. - -.,.CCP...
har
len; 2 LCP.,.v then we will also have len, 2 LCP. and since and by differ at index LCP,,s. one of ha,.PP.. and he,.PP, is 0 while the other 3 LLCP.... so
d(vi, hu,cer,, he.LCP...
Σ
hat 3 --I,, -3 31CCP, 3ICCP,
t.
Additionally, we have
d(u, c)) S Σ
hhe Nnd < <3-ICP,, 12//,t11/200 -CCP; < d(v,,
LCP.
29

---

Published as a conference paper at ICLR 2026
LCP,, i,r L.P.,
On the other hand, if len, & LCP,,s, we will have leng S LCP,,s and len, 2 LCP,,e. Therefore, get
d(u, 2 | Ns.LCPe.dl
Σ
-E3 E33-LCs, ha, - -
LCP.
and
d(vi,c)) S
Σ
hist - hral < E3 e3-LCP.,tt 5 LL-L /2 d(vi,
(=LCP.
Finally, if L.P.,, = I.C.,.. both e, and Cg will fall on the same side of u. b.L.P.... = 0, then both G and C, will be to the right of U;, and since c, >; Cs. we must have D,,LCP,.. 0 while De,LCPr. = I. Therefore, r < 5 and G, will be to the left of C and closer to V/- Similarly, Dr, = 1, will have each voter U/ are respected by this positioning.
and G, will again be closer Us than C.. So, the preferences of
Next, show that the ratio of the cost of the selection excluding c+. to the cost of the optimal committee with ++1 candidates unbounded, Consider any candidate ej other than cr. Then, we have
8-1 d(ur, = Σ (hrr. - h1gt)l =1 Σ t=
- -13,))
tlen,
2-1 Σ
hi Jeny
higteny
h33 2 3 g-ns len, c3 c3-1en; 1/2 12336 3-3/222
t=leny +1
So the cost of the selection excluding C:- is at least 3-t/2, a constant independent of e. On the other hand, consider the following selection of most e + candidates. For each 0 E, consider the candidate G; such that bi.t be at for / < j. bi. show that the cost of the selection {c;; S f) (c=] } is multiple of
for all > j. We bi and big
First, it is clear that U;- has cost 0 given this selection, as c-- is included. Next, take any other voter ey and consider the candidate c; our selection for j len, Then, we have
E-1 d(us, c12) = 1 (hr (haa-hij hig
8-1
8-1
h4. h S
Σ I=len:+1
E3 =
< E3 Ien, /2.
1=
I=len:1
Now, since 0 is value choose, we can arbitrarily decrease the cost of this selection while the cost of the selection excluding G₁. remains a constant value at least 3-f/2. Therefore, the distortion of any voting rule choosing 2 candidates is unbounded compared to the optimal selection of l + candidates.
For any number of candidates m and any > O, there exist instances of the (m 1)- committee election problem in the 2D Euclidean metric for which no voting rule can guarantee I-distortion factor less than + m-
Theorem 16
Proof. We consider a family of m + instances Lo, -1,........ Im with m voters {vi, U2, vm} and m candidates {c1, {c,, Cm.) J on two-dimensional plane. In terms of voters' and candidates' locations on the plane, each of these instances is distinct. However, in terms of voters' preference orders on candidates (i.e., ordinal information). Ig. I.. II are the same. To be more specific, let us describe these instances.
Let 3/8
We first describe the instance To. For each E [m], the candidate e; is located at the point (-E, 2:-1-/1122 122". For each E [m]) the voter us is located the point (0, 22-1/22m) (See
Figure 15 It is straightforward to observe that, for each E [mm], the preference order of the voter
2 is
G>1 C--1 > G441 > G42 by > Cm-
30

---

Published as a conference paper at ICLR 2026
C4
104 X
Ca
103 X
C2
172
(a) The instance
C3 2 03
C2
X 01 X
(b) 1z: Instance with voter by and candidate cy moved
Figure 15: Figures of the lower bound instances. In (a), all candidates are located on the line = -l, with voters with matching y-coordinates on the line = O. In (b), voter Vy and candidate C3 are moved to the line E, while keeping the same y-coordinate.
Next, for each [m]] we define the instance I; follows: For each * [m], the locations of the candidate c; and the voter U; are the same as that in the instance To- Both the candidate oj and the voter are located at the point (e, 22m (See Figure 15 It easy to observe that for any voter nt (where + j). the distance any candidate ej remains the same (as in Io). Since the locations of other candidates remain the same, the preference order for any voter Uy (where * j) remains the same in fo. Let us now consider the voter Vj. Note that its closest candidate is cj. and the distance to any other candidate o; remains the same as in lo. Thus, the preference order of the voter U is
> es > Cjtl b > ... > Cm
which is the same as that in In-
Let us now consider any arbitrary deterministic algorithm ALG that selects at most m candidates. Now, suppose given the preference orders of voters as in To (the same as in I..... Im). ALC selects a of candidates where |C| < m Suppose C & C, for some k [m]. Now, consider the instance Tg. Note, since voters' preference orders, i.e., ordinal information, are the same as in Jo- ALG also selects the set C' for the instance Ig. Then
costa(C,I1) = Σ d(vr, C)
Σ
e 28 (m + 1)e.
On the other hand, selecting only the candidate es for the instance /5 would lead the cost of
cost, (Ck: IR)
I|0 - cxl12 - (m 1m- Σ
xE(m)
and thus the optimal cost (PT(T)) < (m 1) (e + 1).
31

---

Published as a conference paper at ICLR 2026
Hence, the distortion factor of ALG on the instance Ig is
1 1-distortionnAAG] cO,t,(C,1k))
OPT(IK)
(m + 1)
()(e+
- m-1]
2
(
1+
{+1
1 + 2
1
1 2 21)
1
&+1 1
2
1 +
8
(since ( =3// 1//5- 1)).
m
Theorem 17
For any number of candidates m and any > O, there exist instances of the (m 1)- committee election problem with metrics for which no voting rule can guarantee 1-distortion factor less than +
Proof. Consider a star with a central vertex and leaves, such that the edge to leaf i has cost 1 where e S 83 S 2e are m distinct values. Then, we construct m instances on this tree, such that any voting rule has 1-distortion of 1 + _ e' on at least one instance. In every instance, there are m candidates, with candidate located at leaf i. In addition, there are voters with voter i; located on the edge going toward leaf the i-th instance, every voter except voter v; is located distance E; from the center of the star, while voter coincides with candidate on the leaf. This is illustrated Figure T6
In every instance, for any voter Vj. the distance to Cj is at most - < 2e, while the distance to any other candidate сę is at least 1 - E + E, 2 1-E. Therefore, the closest candidate to each voter 0j is candidate cj. For other candidates, the distances are determined by 1 Ek. and each voter Uy 's preference order for candidates except its most preferred choice of Cj will be in descending order of EK-
Therefore, the voters' preference orders are identical across the m instances, and it is not possible to distinguish between the instances given the voters' ordinal preferences. Now, any deterministic voting rule choosing m 1 candidates must exclude one of the candidates. Let this candidate be Cz-. Then, in instance i", the cost achieved by this voting rule is least
-1- e:) + E3- +1
max Ej m + 2 (2m)(2e) + 1 4ms jØ3
while the cost of choosing only candidate i" is
Σ1- +c++) ==)))==0) =m
3
Therefore, the I-distortion of any voting rule can be lower bounded by
m 4ms
2
+
85.
(m - 1)
m
This completes the proof with e 8e.
C.2 LOWER BOUNDS FOR THE MAX-COST
Theorem 18
Any deterministic algorithm for the k-committee election (with respect to the max-
cost) that selects at most k < m candidates out m candidates must have a I-distortion of least 3 for any 0.
32

---

Published as a conference paper at ICLR 2026
55
54
25
E1
Em
1
Ei
E2
-
1
Cy
U2
Figure 16: An illustration of the i-th instance on the star graph, where the i-th voter is located at the same spot as the i-th candidate. For each voter vj. the closest candidate is cj. followed by other candidates in descending order of Eg. This ensures that all instances result in the same preference ordering for voters.
Proof. We proceed similarly Theorem [6 using family of instances Io, [1 ........ Im on the dimensional plane, such that the voters' ordinal preferences are the same in all of these instances, but the locations and distances of candidates and voters vary. In each instance, we have m voters {V1, U2 J and m candidates {c1, C2 Cm
Let L = 3/e 1. We use the same instance Lg as in Theorem 16 where for each E [m], candidate is located at (-E, (0-1/2mm and voter v; is located at (0, 2' """". Then, for each i E [m], voter 2/ will have the ordinal preference
C > C-1 > > C1 > c++1 > C+2 > ... > Cm-
in instance To-
Next, we define instance Iy for each E [m]. For each E [m]] \ {j), is and c will remain in the same location in To- Meanwhile, candidate ej is moved to (f, (e,2/-1/2m) and voter ey to (2f, / It can be seen that for any i # J. the distance of voter e; to candidate сy will be unchanged compared to In. and therefore the voter's ordinal preference will remain the same. For voter j. its closest candidate will remain Cg. In addition, its preference for the other candidates will remain unchanged. Therefore, voter 's ordinal preference will remain the same as in To. too, and all voters' ordinal preferences are identical in lo and Iz. An example of these instances illustrated in Figure 17
Now, consider an arbitrary deterministic algorithm ALG that selects k m candidates. Since k m, when running ALG on Iu. there exists candidate e, that is not in the set of selected candidates C. Now, consider the algorithm's 's performance on Ij. Since the voter's ordinal preferences are the same in to and I,. and ALG operates using only this information, its output on I₁ must be the same as in To and therefore, it does not select Cj. Now, we can lower bound the cost of ALG with respect to the max objective as
cost (C,10) d(vj, 2 34,
(Since ej & C)
On the other hand, if we only select ej, get
costmle,,1 10)
max |0u C; 1
iE ml
l + 1.
33

---

Published as a conference paper at ICLR 2026
C4
1/4 X
03
03
02
U2 %
U1
(a) The instance lo
04
0/4 X
C3
C2
0/2
(b) 13: Instance with voter and candidate moved
Figure 17: Figures of the lower bound instances for the max objective. (a), all candidates are located the line x -t, with voters with matching y-coordinates on the line 0. In (b), candidate C3 is moved to the line x = l, and voter 03 is moved to the line x 26 while keeping the same y- coordinnatss.
This shows that the optimal cost OPT (1₁) < l + 1. Finally, combining these two, we get that the distortion of ALG on instance 1; at least
cost (C,Is)
1 1-distortion(ALG)
>
OPT (Ik)
38
2 [+1
3 1+1
= 3 -
(e= 36=3/8 1)
Theorem 19 Any deterministic algorithm for the 2-committee election (with respect to the max- cost) when voters and candidates are located line must have 1-distortion of at least E for any 0.
Proof. We consider the following instance with three voters {vi, v3) and three candidates {ci, C2, ca). Let the preferences of voters be as follows:
> >
U/ 02 > c > Cs
U3
Next, we consider three possible placements for the voters and candidates that respect the above (desired) preference order of voters, as shown Figure 18 In all instances, Vi is located point -1, and V3 at point 1. In the first instance, U2 is located at 0.5. Candidates C1, C2, C3 are located at points 0, 1 - s and 1 + e/2 respectively. It is easy to see that the voters' preferences in this instance match desired orders. Now, every voter, while both 02 and Cy have a distance at least E from U1. Therefore, not choosing e, will lead to distortion of least 2
that in this instance, C₁ has distance of at most 1 to
In the second instance, we place U/2 and C2 at point 0, c at point -2 + E, and C3 at point 2 - =/22. that the voters' preferences will follow the desired orders. In this instance, ea
Again,
34

---

Published as a conference paper at ICLR 2026
03
02
(a) First instance: Choosing ei achieves a cost of 1, while the other two candidates have a distances of at least to
(b) Second instance: Choosing e2 achieves a cost of 1, while other two candidates have distance of at least - to 02.
6102
(c) Third instance: Choosing Os achieves a cost of 1, while the other two candidates have a distances of at least to us.
Figure 18: Possible locations of the voters and candidates in the lower bound instance for 2.
has a distance of at most 1 from voters, while v2 a distance of at least & from the other candidates. Therefore, not choosing 02 will lead to distortion of least 2
Finally, the third instance, we place 0j at point -1, C2 and U/ at point -1 + e and c3 at point 0. This placement will also respect the desired preference orders for each voter. Additionally, since C3 has a distance at most 1 from all voters and vy has a distance at least e from the other candidates, not choosing C3 leads distortion of least 2
Now, since these instances cannot be distinguished based on the voters' ordinal preferences, and not choosing any of the candidates leads to a distortion of at least 2 E, any deterministic algorithm selecting two candidates cannot achieve a distortion better than 2 -
Theorem 20 Any deterministic algorithm for the 3-committee election (with respect to the max- cost) when voters and candidates are located on line must have I-distortion at least 3/2 for any > 0.
Proof. We consider instances {4, 12, 13, Ja), each with four voters {u), U2 U3. v4) and four candi- dates (c1, 022 C32 c such that the preferences of voters are follows in every instance:
C4 01 02 > Ci > Cg
:1:01 02
8 C3 C4 22 C1
U4 :4:04 C4 C3
C2
x C1-
For the instance J, we choose the location of voters and candidates so that candidate c; has distance of at most 2 to each voter, while voter has a distance of at least 3 2c to every candidate except This leads to distortion at least 3/2 e for any deterministic algorithm ALG, as these instances cannot be distinguished based ordinal preferences, and at least one candidate e; is not chosen in
instance 4 by ALG. These instances are shown in Figure 19
In instance 41 have voters U1, U2, U3 Ug located at points -2, - c, 2, and candidates C1, C22 C3 Ca located at points 0, 1,2 2 s, respectively. can be seen that the ordinal preference of each voter, in this instance, matches the desired ordering. Now, c₁ has distance of at most 2 to every voter in this instance, while 0y is at distance at least 3 from every candidate except C1. So, if is not chosen, get distortion of at least 3/2.
In instance I2, we have voters U1, U2 Dg U4 located at points 22 - - E,2 - E,2 and candidates that the ordering
C C2 Ca located at points -4+6, 0, -, respectively. Once again,
35

---

Published as a conference paper at ICLR 2026
1/2
02
(a) Ji: Choosing ej achieves a cost of 2, while the other candidates have a distances of at least 3 to on.
U2
(b) I2: Choosing o2 achieves a cost of 2, while the other candidates have a distances of least 3 to tt..
Figure 19: Possible locations the voters and candidates in the lower bound instance for
for voters' preferences is respected:
(1) = 2 < (2) = 2 ---
d(u2, 22) = 1
= d(v2, = 2 =)
= +
d(v3, Ca) = 0 < d(r3, (4) = < d(rs, (2) = - < () =6 2 d(v4, 02) < (1) 6
d(v4,ca 04) 0 d(va, 03)
In addition, since 02 is at distance of at most 2 from every voter and every candidate except c2 has a distance at least 3 25 from D2 not choosing 02 leads to a distortion of at least 3/2 - E.
Based on the symmetry in voters' preferences between C₁, and C4, C3, we create mirror versions of I and I as I and I3 respectively, so that not choosing 01 or Cy would lead to distortion of at least 3/2 cannot achieve a distortion of better than 3/2 & in this case.
Therefore, since any deterministic algorithm must omit one of the candidates,
36


Reviews:
[{"review_id": "ZginiGiXkE", "reviewer": "Reviewer_VGd9", "summary": "The paper studies the question of whether it is possible to achieve the cost of an optimal candidate in the metric distortion framework when selecting only a fixed number of candidates instead of a single one. For the line metric, it provides a positive answer both for the utilitarian objective (with just 2 candidates) and the egalitarian objective (with just 4 candidates). It also provides matching lower bounds. In contrast, even in the 2D Euclidean metric, guaranteeing optimality requires selecting all candidates.", "questions": "- Is there some general property of the metric space that could be used to parameterize the number of candidates needed to reach optimality? I am trying to understand whether it is really only the 1D metric that has this nice property. Could you prove that, in some sense, any metric that is not isomorphic to the 1D will always fail to reach optimality with all but one candidates?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies a very natural question: how many additional candidates are needed to guarantee optimal distortion. This to some extend related with k-committee selection, but the main question posed here is different. The paper obtains strong and non-trivial results both both the utilitarian and egalitarian objectives, and both the 1D case and more general metrics. The results on the line are particularly surprising: a constant number of candidates (and in fact a small constant at that) always suffices to guarantee optimality. I find this result very interesting and informative in practice. In cases where one can potentially select more than one candidate, the results of this paper explain how one can navigate the tradeoff between picking a small number of candidates and guaranteeing small distortion. The paper also provides an interesting impossibility result, showing that a similar guarantee cannot be attained in general metrics. In fact, selecting all but one candidates will always fail to guarantee optimality. This provides an interesting separation between 1D and more general metrics, something which hasn't been investigated a lot in this line of work, with some exceptions. Overall, the paper makes a concrete contribution to a natural problem. It provides a comprehensive understanding under different objectives and metric spaces, together with matching lower bounds. \n\nFurthermore, the writing of the paper is very good. It accurately places its contributions in the context of the existing work; all relevant references have been discussed. The technical component is also non-trivial and explained well in the main body.", "weaknesses": "The main weakness is that, a priori, selecting more than one winning candidate could trivialize the problem when comparing against the optimal omniscient solution that picks a single candidate. Still, the lower bounds of the paper show that this is far from trivial in general, and accomplishing it in 1D turns out to be highly non-trivial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yZz1u2GWf0", "reviewer": "Reviewer_xGkU", "summary": "The paper investigates whether selecting multiple representatives (a committee) instead of a single candidate can reduce the efficiency loss that arises when elections rely only on ordinal preferences rather than full cardinal information. This problem is studied within the metric distortion framework, where voters and candidates are points in a metric space and the cost of selecting a candidate for a voter is their distance. \n\nThe authors introduce a bi-criteria approximation perspective, asking whether selecting a small committee of size k≥1 can yield a total or maximum voter cost close to that of an optimal single candidate. They show that in the line metric, it is indeed possible to achieve the optimal cost with only a constant number of candidates. \n\nHowever, this improvement is shown to be unique to one-dimensional settings. In two-dimensional Euclidean and tree metrics, achieving optimal cost is impossible unless all candidates are selected.", "questions": "No questions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper introduces a bi-criteria approximation framework to analyze how selecting multiple candidates can reduce efficiency loss in metric distortion, extending classical single-winner results to multi-candidate settings for both utilitarian and egalitarian objectives. It establishes precise trade-offs between committee size and approximation quality, proving that on the line metric two candidates can achieve optimal cost, while in higher-dimensional and tree metrics such improvement is impossible without selecting all candidates.", "weaknesses": "The main weakness of the paper is in the presentation, given that the introduction is too long and most proofs of correctness are relegated to the appendix, which is pretty long. On the other hand, the results are presented well and given that the paper is technically demanding, this choice is justified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YkMTvyHAZZ", "reviewer": "Reviewer_rpfj", "summary": "For reasons of convenience and practicality, when soliciting preferences we often see ordinal preferences. These preferences mask the true intensity of certain opinions and the gap between them - a small gap between A and B and a large gap between B and C are represented simply as A,B,C. And so the optimal solution can be ambiguous.\n\nThe authors propose an approach of committees' to address this well-established problem, in a bi-criteria sense: select a small k-committee but compare its cost against the best single candidate. They establish bounds on the maximum level of distortion this approach can have. While fairly simple intuitively, the authors prove their methods bounds and claims rigorously.", "questions": "I think this paper is solid content-wise when the supplementary material is considered. I think the writing and presentation are not. I know much of the content is in the appendices, but as is, the writing in Sections 3 and 4 is not yet there in my opinion. That is my primary critique, and revision there could easily raise my score.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "* I think the content of the paper is good, and I feel that between the appendices and the main body a strong paper can be found (more in weaknesses/suggestions)\n\n* The content is well motivated, I believe it is a novel contribution, and well-justified.", "weaknesses": "* I thought the visuals in the paper were quite weak and to the detriment of the clarity of the paper. There are only 2 figures. The first is quite large but has conveys relatively little information. The next (2/3) one doesn't convey much beyond the writing. I felt that understandability could be easily enhanced with more visuals that convey more meaning (there are several in the appendix that seem to be much better/efficient at conveying information)\n\n* Perhaps the above could be overcome, but the writing in section 3/4 was not, in my opinion, up to par. The lemmas are given in succession, the connections are weakly explained, and it's not presented in an easy way to follow. I recognize that there are proofs in the appendix and the space provided is limited, but the main text is not up to par. Between lemma 9-11 and then theorem 12 for instance, we cover 2 different cases in the span of a few sentences, with choppy flow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uM431YP6Hl", "reviewer": "Reviewer_HLZ6", "summary": "This paper investigates the following problem in social choice theory under the metric distortion framework: if, instead of selecting a single winner, a deterministic mechanism is allowed to select multiple candidates (where the cost to a voter is their distance to the nearest selected candidate), then can this lead to smaller distortion relative to the optimal single candidate?\n\nThe authors obtained the following results:\n\n1. Line metric (1D Euclidean): At most 4 candidates suffice to achieve optimal cost in both the utilitarian  and egalitarian cost setting.\n2. 2-D Euclidean and tree metric: Even when selecting $m−1$ of $m$ candidates, the distortion cannot be smaller than $1+2/(m−1)$ for utilitarian and $3$ for egalitarian. As a corollary, it is impossible to achieve the optimal cost unless all candidates are selected.", "questions": "See \"weakness\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is a theoretical paper addressing a natural and interesting question in metric distortion. The results are logically sound and well contextualized within the existing literature. The writing is clear and well-organized.", "weaknesses": "1. The contribution is limited to deterministic algorithms and highly restricted metric classes (line, 2-D Euclidean, and tree metrics). It would be interesting to see whether similar results extend to randomized mechanisms or more general metrics.\n\n2. The paper focuses on existence results without explicitly discussing the computational complexity or implementability of the proposed mechanisms.  Clarifying whether these mechanisms can be computed efficiently would strengthen the practical relevance of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)