Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting
Authors: Mohammad Abam
Davoud Kareshki
Marzie Nilipour
MohammadHossein Paydar
Masoud Seddighin
Venue: NeurIPS 2025 poster ()
Keywords: Distributed voting
Distortion
Metric
Randomization
Primary area: theory

Abstract: We study metric distortion in distributed voting, where $n$ voters are partitioned into $k$ groups, each selecting a local representative, and a final winner is chosen from these representatives (or from the entire set of candidates). This setting models systems like U.S. presidential elections, where state-level decisions determine the national outcome. We focus on four cost objectives from Anshelevich \et~\cite{anshelevich2022distortion}: $\avgavg$, $\avgmax$, $\maxavg$, and $\maxmax$. We present improved distortion bounds for both deterministic and randomized mechanisms, offering a near-complete characterization of distortion in this model.

For deterministic mechanisms, we reduce the upper bound for $\avgmax$ from $11$ to $7$, establish a tight lower bound of $5$ for $\maxavg$ (improving on $2+\sqrt{5}$), and tighten the upper bound for $\maxmax$ from $5$ to $3$.
For randomized mechanisms, we consider two settings: (i) only the second stage is randomized, and (ii) both stages may be randomized. In case (i), we prove tight bounds: $5\!-\!2/k$ for $\avgavg$, $3$ for $\avgmax$ and $\maxmax$, and $5$ for $\maxavg$. In case (ii), we show tight bounds of $3$ for $\maxavg$ and $\maxmax$, and nearly tight bounds for $\avgavg$ and $\avgmax$ within $[3\!-\!2/n,\ 3\!-\!2/(kn^*)]$ and $[3\!-\!2/n,\ 3]$, respectively, where $n^*$ denotes the largest group size.

Tight Bounds On The Distortion of Randomized and Deterministic Distributed Voting
MohammadAli Abam" abam@sharif edu
Davoud Kareshki" davood. kareshki wwwssaiii1@shhr....oo edu
Marzich Nilipour" marzie. marzie.nilipone milzieenilipour@hharii edu
MohammadHossein Paydar' mohammad, payssharif......oooa edu
Masoud Seddighin seddiiginn@eeiss institute
Abstract
We study metric distortion in distributed voting, where voters partitioned into k groups, each selecting a local representative, and a final winner is chosen from these representatives (or from the entire set of candidates). This setting models systems like U.S. presidential elections, where state-level decisions determine the national outcome. We focus four cost objectives from Anshelevich al. (I]: avg-avg, avg-max, max-avg, and max-max. We present improved distortion bounds for both deterministic and randomized mechanisms, offering a near-complete characterization of distortion in this model.
For deterministic mechanisms, to 7, establish tight lower bound of 5 for max-avg (improving on 2 + v5), and tighten the upper bound for max-max from to 3. For randomized mechanisms, we consider two settings: (i) only the second stage is randomized, and (ii) both stages may be randomized. case (i), we prove tight bounds: 5-2/k for avg-avg, 3 for avg-max and max-max, and for max-avg. In case (ii), show tight bounds for max-avg and max-max, and nearly tight bounds for avg-avg and avg-max within [3 2/n, 3-2/ (knn") ) and 2/n, 3). respectively, where n" denotes the largest group size.
reduce the upper bound for avg-max from 11
Introduction
In social choice theory, voting rule is function that takes agents' preferences over alternatives and selects one as the final outcome. Preferences are usually represented as ranked lists, and the goal is to design voting rule that best reflects these preferences.
How can we evaluate whether a voting rule is appropriate? There are both axiomatic and guantitative benchmarks for assessing outcomes 2 3 4. In this paper, we focus one of the most prominent quantitative measures: distortion. The idea is simple: each agent hidden numerical values-either costs utilities-fi the alternatives, and their ordinal rankings reflect these values. Suppose ultimate goal is to optimize an objective function ø, such as social cost, maximum cost, or total utility, based on these hidden values. However, since the voting rule only has access to the agents' ordinal preferences-now not numerical values-it may select a suboptimal outcome with respect to Φ. The
'Computer Engineering Department, Sharif University of Technology, Tehran, Iran 'Computer Science Department, Tchran Institute for Advanced Studies (TelAS), Tehran, Iran
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Cost objective
General metric
Line metric
avg-avg
[7, 7,,11 [
1
avg-max
[2 V5, 11] 1
2 v5 (25
max-avg
[2 + 55 [
2 v5 [25]
max-max
[3,5]
|
3 [
Table 1: Known results for deterministic distributed mechanisms under various cost objectives.
distortion of a voting rule captures how far its chosen outcome can be from the optimal one in the worst case. is defined as the ratio between the value of Φ for the selected outcome and the value of for the optimal alternative in the worst case.
Since its introduction by Procaccia and Rosenschein 4 distortion has been a consistent focus of investigation not only in voting, but also in related social choice problems such as facility location 6 8 and matching 7 [T. Still, the core of the literature lies in voting, with particularly
rich results when costs of agents form metric space [TO] [2 [3] 14
[5] 16, 17 18 19
20 21]. For
a comprehensive overview of distortion in voting, we refer to the survey by Anshelevich el [22
In this paper, we study the distortion in the metric setting when the voting process is distributed. Unlike centralized voting, in many large-scale scenarios, outcomes emerge via two-stage manner: decisions are made locally within separate groups of agents, the local outcomes are then aggregated into a final outcome. A notable example is the U.S. presidential election, where each state selects winner, and the national outcome is determined by weighted aggregation of the state-level results. More formally, distributed voting mechanism is pair (fin foe), where
1. fan an in-group voting rule that selects local winner for each group based solely on the preferences of agents within that group.
2. Assuming R is the set of local winners, fou is over-group voting rule that selects the final winner based on the preferences of R over all alternatives [ or local winners 23
The study of distortion in distributed voting was pioneered by Filos-Ratsikas et al. who extended the notion of distortion the utility-based distributed scenario. Later, Anshelevich et al. investigated distributed voting in the metric cost setting. In the context of distributed voting, since decisions occur in two stages, is natural to define separate cost objectives for each level. Building on this, Anshelevich el al. I introduced four standard objectives combining average and maximum costs within and across the groups: avg-avg. max-avg, avg-max, and max-max. the deterministic setting, they proved constant upper and lower bounds for all objectives in both general and line metric spaces, summarized Table Later, Voudouris (25) focused on the line metric and proposed two simple mechanisms for the avg-max and max-avg objectives. These mechanisms achieve an upper bound of 2 + v5, closing the corresponding gap derived by M.
As shown in Table I. distributed voting the line metric is well-understood with tight distortion bounds already achieved. We therefore turn to general metric spaces and explore whether random- ization also improve distortion in the distributed setting. This work presents the first formal investigation into randomized distributed mechanisms within the metric setting.
In this paper, we make significant progress on the distortion of distributed voting mechanisms in two main directions. First, we improve the existing distortion bounds of deterministic mechanisms with respect to the avg-max, max-avg, and max-max objectives. Second, explore rules that incorporate randomized techanisms-eithee in the second stage only, or both
to as rand-det and rand-ramd respectively. The output of randomized mechanism is probability distribution over the alternatives, rather than a single winner. For both the rand-det and rand-rand mechanisms, prove tight bounds for almost all of the objectives.
1.1 Further Related Work
The most relevant studies to our work 1 25 are discussed in Section Here, we briefly review other related studies. Since Procaccia and Rosenschein's 's seminal work 4 research distortion in

---

social choice problems has expanded, covering utilitarian settings [26 12
27
28 29
30
metric settings
14
32
16
33 20], and combined approaches 34
In deterministic case, Anshelevich et al. 12] pioneered the study of distortion for the metric frame- work. Using simple example, they show that the distortion of any deterministic voting rule is at least 3. Gkatzelis et al. [14] proposed an elegant and intricate voting rule, Plurality Matching, which achieves tight distortion of 3. Next, Kizilkaya and Kempe [32] attained the same upper bound with a simpler voting rule, Piurality Veto. Filos-Ratsikas et al. 244 pioneered distortion analysis in distributed voting under the utilitarian framework. Their work extended to other social choice problems, including facility location [35], aiming to select a single location from set of alternatives. More recently. Voudouris [36] investigated the distributed distortion in obnoxious voting. where alternatives are undesirable.
Unlike deterministic voting rules, randomized rules can achieve distortion below 3. Anshelevich
and Postl [15] proved that the metric distortion of Random Dictatorship is at most - 2/n, with n
agents, and establish lower bound of for any randomized voting rule. Kempe (37] improved the upper bound for Random Dictatorship to 3 - 2/m, where m is the number of candidates. Charikar and Ramakrishnan [6] further raised the lower bound for any randomized rule 2.112. Recently, Charikar et al. [33 reduced the upper bound to 2.753. In the context of distributed voting, Filos- Ratsikas and Voudouris [23 investigated randomized mechanisms under the utilitarian framework, establishing distortion bounds in various cases.
1.2 Our Contributions
Our results provide improved upper and lower bounds the distortion of distributed mechanisms across various combinations of deterministic and randomized voting rules and cost objectives, As summarized in Table most of our bounds are dighttd the fact that our proposed mechanisms are simple. In addition to general metric spaces, we also analyze the Euclidean setting and derive corresponding bounds under this restriction
Randomized Mechanisms. Previous work on metric distortion in the distributed setting has focused exclusively on deterministic voting rules 11 25 38 (6). In this paper, we take significant step toward understanding randomized mechanisms in distributed voting. We study two natural classes of randomized mechanisms rand-det and rand-rand withhh general metrie spaces, and analyze their performance with respect to the four objectives. See Table for an overview of our results.
rand-det mechanisms, defined as pairs (fin: fow), where fün is deterministic voting rule and for is randomized one. We derive tight distortion bounds with respect to the all objectives in Section 3
max-max, avg-max: For both objectives, we derive tight distortion bound of 3. The lower bound is established through a basic example within single group on line metric, simplifying the max-max and avg-max objectives to max. The upper bound is proven by distributed mechanism that first selects a representative for each group with the Plurality Matching rule and then chooses the final winner uniformly at random.
max-avg: We establish tight distortion bound of 5. The lower bound is proven using a line metric and novel tool we introduce, called the Bias Tournament, which may be of independent interest. For the upper bound, we show that applying a deterministic in-group rule with distortion at most 2 3, followed by the Random Dictatorship rule, achieves an overall distortion of at most a + 2. Since the best achievable value a is (via the Plurality Matching rule), this yields matching upper bound of 5.
avg-avg: We prove a tight distortion bound of 5 - 2/2. Obtaining this bound for the avg-avg objective is the most challenging aspect of the rand-det mechanisms. The lower bound construction, though similar to that of the max-avg objective, requires a more delicate analysis to extract the 2/x improvement. Once again, we employ the Bias Tournament and model the metric space via shortest-patt distances a graph.
we analyze rand-rand mechanisms, defined as pairs (frnfor) comprising of two randomized voting rules, and derive tight or near-tight distortion bounds. All the upper bounds obtained via distributed mechanism that initially applies the Random Dictatorship rule within
In Section 4
3

---

Objective
Distortion
lower bound
upper bound
rand-rand rand-det det-det
avg-avg
avg-max
2 2+
5
7 (Comolarry 5.3
max-avg
5 (Theorem
5.4
5 [
max-max
(Theorem
5.1
avg-avg
22
k (Theorem
3.8
5 2. (Corollary)
3.4
avg-max
3 (Theorem
3.6
3 (Theorem 3.5
max-avg
(Theorem
3.7
5 (Corolarry 3.2
max-max
3 (Thenrem
3.6
3 (Theorem
3.5
avg-avg
3 2
(Thearem 4.9
3
knn (Theorem 4.4
2
3 1/
avg-max
(Theorem 4.7
3 (Thoorem 4.2
max-avg
3 (Theorem
3 (Theorem 4.3
max-max 3 (Theorem 4.6
3 (Theorem 4.1
Table 2: overview of our results for various cost objectives in general metric spaces, with gray-text results indicating those derived from prior work. n" denotes the size of the largest group. Thus, the bound of 2/n for the avg-avg objective rand-rand tight when group sizes are equal.
each group and then randomly selects the final winner from the chosen representatives with uniform probability.
max-max, max-avg: For both objectives, we establish tight distortion bound of We construct a shared example consisting of single-voter groups to establish the lower bound, even when the metric space is line. In this scenario, the max-max and max-avg objectives both simplify to the max objective.
avg-max: We establish a lower bound of 3 2, which nearly matches our upper bound of The lower bound is proven with an instance where the number of candidates and voters are equal (n = m) and there only single group (A: = 1). Additionally, we conclude lower bound for the max objective in the centralized setting: we show that any randomized rule must have a distortion of at least 3 - for any constant & > This is particularly interesting since even deterministic rules are known to have upper bound of 3 for max (14)
x²*
avg-avg: We establish a nearly tight distortion bound slightly below 3. For an instance with i single-voter groups
graph, we prove lower bound of 3 n We further derive an upper bound of 2_. where n" denotes the largest group size. When all groups are of equal size, it yields matching upper and lower bounds. Notably, deriving these bounds is the most challenging aspect of analyzing rand-rand, mechanisms.
kn
Deterministic Mechanisms. We consider det-det mechanisms, defined as pairs for) compris- ing of two independently deterministic voting rules, in Section We resolve the previously known gaps for the max-avg and max-max objectives and provide an enhanced upper bound for the avg-max objective. In this section, we adopt a setting akin to [I], where for selects winner from the set of all candidates, not solely those chosen in the first stage.
avg-max. We improve the upper bound from 11 to 7. Anshelevich al. 1 show that combining the in-group and over-group voting rules with distortions a and 3, respectively, yields overall distortion of this gives 11. We prove that the in-group rule, f.. merely satisfies the property of Pareto efficiency, then the overall distortion is most 233 results in a tighter upper bound of 7, and shows the dominant role of the over-group rule.
a. With their best known values (a 3, 3 2),
which is independent of a. This
max-avg. We improve the lower bound from 2 + 55 to 5. Interestingly, our lower-bound instance based on metric constructed via shortest-patte Euclidean. This confirms that the upper bound from [1] is indeed tight.
graph, rather than line or
max-max. We improve the upper bound on distortion from 5 to for general metric spaces. Although bound of 3 was previously known for the line metric, the general case remained open. We show that distributed mechanism same as the Arbitrary Dictator, proposed by [. actually achieves distortion 3 for any metric space.

---

Bias Tournament. The Bias Tournament is directed graph with one node per candidate. For any pair of candidates ej and C22 we add directed edge from ej to ca if. in a group containing only two voters with preferences (c1, (2....) and (C2, C1 ........ - the remaining candidates are ordered identically according to fixed permutation a over all candidates the in-group rule fün deterninistically selects e₁ as the winner. This construction captures the bias in f.n 's tie-breaking behavior across candidate pairs. To analyze the implications of these biases, we use a well-know property of tournaments: any tournament This fact allows us to identify a losing candidate-onf pairwise comparisons and use it as the basis for constructing an instance with high distortion, which helps us to establish the lower bounds for the rand-det and det-det mechanisms.
nodes contains at least one node with in-degree
at least
frequently defeated in
Centralized Setting. Interestingly, one of our lower bound constructions, originally developed for distributed mechanisms also applies to randomized centralized setting. In particular, we analyze the max cost objective in this setting. Previously, Gkatzelis et al. [14] established an upper bound of 3 for max using Plurality Matching, as defined in Section In our work, we revisit the avg-max objective for the rand-rand mechanisms and prove a distortion lower bound. We then reuse the same construction to show that the distortion of max under centralized voting is at least 3 for any constant & > 0, thus matching the known upper bound up to an arbitrarily small gap.
Euclidean Space. Our lower-bound constructions for the avg-avg objective rely on general metric spaces that do not reduce simpler structures such as the line Fuelidean space. This raises the natural question of whether similarly strong bounds can be achieved in more structured settings. In Section [ we address this by constructing novel instances within a Euclidean hyper-simplex, obtaining lower bounds of v5- for the rand-rand mechanisms and 2 + v5 for the rand-det ones, where & is arbitrarily small. Specifically, for rand-rand, we fix an integer and construct an instance with 1 + 2 candidates and k: = 1 + 1 single-voter groups embedded in R Similarly, for rand-det, we construct an instance with 2m candidates and m groups of two voters each, embedded in I m (where m is fixed).
2 Basic Notations
An instance of the distributed voting problem is a tuple (V, C, G, n, d). Here, V is a set of n voters, and C is set of m candidates. We use v; to denote the i-th voter and symbols a, c, O, and w to refer to candidates. In particular, W typically denotes the winner and o refers to the optimal candidate. is a partition of voters into & groups, such that each voter belongs to exactly one group. For each group E G, n.g is the number of voters in g. We denote the optimal candidate for group g by og. We say an instance is symmetric, if all groups have equal sizes. Each voter v; has a strict ranking m. over the set of candidates, representing their ordinal preferences. A preference profile is the collection of preferences from all voters, denoted by π = (M1,-.. ).)) These preferences arise from cost function based on the underlying metric space d. For each voter and candidate c, d(v, e) denotes the cost of candidate e for voter v. The voters rank all candidates in increasing order of cost, which means they prefer those who are closer. The distance function d satisfies the standard metric properties of non-negativiry, symmetry, and the triangle inequality.
We denote the top-ranked candidate of each voter v as top(e). For candidate c and group g E G. (c g) = arg max,ey d(e, c) denotes the farthest voter from e within group g. Similarly, v**(c) (c) arg m d(v, c) represents the farthest voter from across all voters. We also use costy(c) to de- note the cost of candidate e restricted to group g, and define g" (c) = arg maxges(1/n)) Eveg d(u c) that is, the group in which candidate e incurs the highest average cost.
Given an instance I, various cost objectives can be considered to evaluate the final winner. In the distributed voting, we can be even more flexible by applying different objectives at each stage. Following 11, we consider four cost objectives:
Average of averages (avg-avg): Average the costs within each group, then average across all groups; avg-avg(c I) k: ΣgES ng Eve, d(u, c) ; Eyec cost,
Average of maxima (avg-max): Find the most dissatisfied voter in each group, then average their costs; avg-max(c [T) -/2 Eneo maxvey d(r, c) Eneg ((v"(c,
5

---

Maximum of averages (max-avg): Compute the average cost in each group; return the
worst among them; max-avg(c I) maxgec (,. Eeeg d(u. c)) (o)
Maximum of maxima (max-max): Return the cost of the most dissatisfied voter overall; max-max(e| T)= = maxgeg maXvey d(, c) = =(vx" (c),
For simplicity, when the objective is clear from context, we simply write cost(c Z). When the instance is also clear, omit it entirely.
voting rule maps a preference profile a to a winning candidate w. This rule may deterministic or involve rundomization. Next, we define distributed voting mechanism V (fén: fou), which consists of two stages:
Stage I: Each group g independently selects representative candidate wy by applying the in-group rule fi to the preferences of its members. Let R = (w, E g)-
Stage 2:
The final outcome chosen by applying the over-grous rule for to the (centralized)
instance (R, R, x" d), where R acts both the set of candidates and the set of voters, and x denotes the preferences of representatives over one another.
For each group g, the rule fi has access only local information: the group size (ng) and the preference profile of its voters (T over all candidates. In contrast, foe receives the preferences of the selected representatives together with the sizes of all groups
Distortion. Given a distributed mechanism y = (fins fav). which takes an instance I T (I), the expected cost of w defined as Elcost(w) 2) = Eg gggg Pr(w = Wg) E costsw, (y Z)], and the expected cost of W, is defined as E|cost(w, []] Leec Pr(w,- c) cost(c I), where cost(-) denotes one of the four objectives
(V,C.g, æ, d) as input and outputs a winner
defined earlier. Now, we define the distortion of V as
D(V) sup Fl I)
min.ec cost(c I]
Definition 2.1 (Pareto Efficiency). A voting rule is Pareto efficient for any pair of candidates and if all voters prefer x to then the rule does not select as the winner.
We now present several voting rules (for centralized settings) and mechanisms (for distributed settings) frequently used in this work:
Plurality Matching rule (fpm) Introduced by [14,, Plurality Matching is a deterministic voting rule that guarantees distortion 3, the best possible among all deterministic rules in the metric setting. Given an instance I with voters V, candidates C, and preference profile a, fpm considers each candidate e and constructs a bipartite domination graph G(c) with voters both sides and an edge (v,, 02) if and only if voter prefers to top-ranked candidate of voter by (i.c., c Zu. top(v;)). The rule then selects any candidate for which its corresponding graph G(c) admits perfect matching (which is guaranteed exist).
Pareto-efficient Plurality Matching rule (fym-par): We now introduce variant of fpm that ensures Pareto efficiency while preserving the optimal distortion of 3. fpm-par operates follows: it starts with candidate e₁ chosen by fpm (one whose corresponding domination graph G(c,) admits a perfect matching M) ) and iteratively refines this choice;
If ej is Pareto efficient-no other candidate C2 preferred by all voters over Ci chet C₁ is returned as the final winner.
Otheewisee there must exist candidate co that Pareto dominates e₁ (i.e., every voter prefers C2 to c1). A key insight is that if o2 Pareto dominates C1, then G(c2) is also admits the same perfect matching M as G(c)).
The voting rule replaces e₁ with 02 and iterates until a candidate satisfying Pareto efficiency is found.
Random Dictatorship rule (fra): A randomized voting rule in which voter is selected uniformly at random, and the outcome is that voter's top-ranked candidate [15] 37]. In the first stage of the rand-rand mechanism used to establish upper bounds, apply this rule.

---

Uniform selection rule (fur): A randomized voting rule that selects the winner uniformly at random from the set of candidates. This rule used in the second stage of both the rand-det and rand-rand mechanisms that establish upper bounds.
Arbitrary Dictator mechanism (mad): Introduced by [. this mechanism operates two stages. First, each group selects representative by arbitrarily choosing a voter and taking her top-ranked candidate. Second, the final winner is determined by arbitrarily selecting one of the representatives. This mechanism is employed to analyze the upper bound of the max-max objective in det-det.
o-in-8-over mechanism (mas): Proposed by [T. the a-in-B-over mechanism operates in two deterministic stages, first applying an in-group voting rule with distortion at most o, followed by selecting a final winner using an over-group rule with distortion at most B.
Definition 2.2 (Promotion). Given an order a over a set of candidates and a candidate E a, the operation are returns a new preference in which e moved the top, and the relative order of all other candidates remains unchanged. When multiple 1 operations are applied in sequence, they are evaluated from left to right. atba a first moves b to the top of 0, then moves to the top of obb..
Using the promote operation, we define the Bias Tournament- special complete directed graph (tournament) over the aandidates-wiig is erucial for establishing lower bounds of the rand-det and det-det mechanisms.
Definition 2.3 (Bias Tournament). Let f be deterministic voting rule, C a set of candidates. and an ordering of C. The Bias Tournament T(f.C. F, o) is a complete directed graph where each vertex candidate in C. For every pair of distinct candidates and there is a directed edge from u. to w if and only if selects u as the winner in a two-voter election with preferences Ti uu and T2 atutw.
corresponds
Example 1. Let = {cz, C22 c3} and a deterministic rule f that selects the candidate with the smallest index among those ranked first by at least one voter. Suppose: (i) between e1 and cz2 the winner is ci: (i) between e and C32 the winner is C1: (iii) between c2 and ca2 the winner cz. Then O) contains edges e₁ - C2. C1 - C3, and C2 + C3-
Basic Observations. We present several preliminary observations that lay the groundwork for proving our main theorems. For clarity and consistency, we fix instance I = (V,C, 9, T, throughout this section. The proof of Observation [26]is deferred to the appendix.
Observation 2.1. In distributed voting with single-voter groups, ler V = (fin: faw) be distributed mechanism with finite distortion. Within each group, f. must select the top-ranked candidate of each voter as the group representative.
Observation 2.2. For any deterministic voting rule f and an ordering a over C, there exists candidate with in-degree at least m= in T(,,
Observation 2.3, Since Og is the optimal candidate in group g. we have cost, (0₂) S cost, (c) for any candidate including O. This holds for all objectives considered.
Observation 2.4. Since cost(.) defined as the maximum over cost,(.) under the max-avg and max-max objectives, it follows that cost, (0) I cost 0), for each group g. Observation 2.5. For rand-det mechanism mechanism is given by E|cost( w)] = EGEG COST( (g))
(fen: fur) with output w, the expected cost of the
Observation 2.6. For rand-rand mechanism V = (fra: fur) with oulput w, the expected cost of the mechanism is given by Elcost( w)) = Eyes ny Eveg cost(top(u))
Observation 2.7. For the max-avg objective and any group 9. we have cost, (o) I cost( as implied directly by the definition of max-avg.
Observation 2.8. Since top(v) denotes the candidate closest to voter v, it follows that d(v, top(u)) <
du, for any candidate
Observation 2.9. For every voter u and every candidate c, we have d(u, c) S (c)')
Observation 2.10. For every group 9. every voter v E 9. and every candidate c, we have diu c) s d(u" d(v"(c,g):o (). Observation 2.11. Consider distributed mechanism vp = =fin (fin;foo) fov), where fin is deterministic rule with distortion at most a. By the definition of centralized distortion, for any group g E G, we obtain cost, (W,) S cost,(O..
7

---

Observation 2.12. Consider det-det mechanism v = foe), where for has distortion at most with respect to the avg objective. By the definition of centralized distortion, for any group g E G. we have 1 3. Zgeg d w. Wg) S 3 ge d(o, Wg).
3 Distortion Bounds for rand-det
This section examines rand-det mechanisms, defined as pairs (fin; foo), where fin is a deterministic voting rule and foo is randomized one. We establish distortion bounds under all considered objectives. For brevity, all proofs are deferred to the appendix.
3.1 Upper Bounds
Let fa be deterministic voting rule with distortion most o, and let fpor be any deterministic voting rule that satisfies Pareto efficiency. We analyze the mechanisms (fa, fur) and (fpar: (frar:fur) fur).
For the max-avg and avg-avg objectives, we show that the mechanism (fa- fur) achieves distortion at most a + and a + 2 2/k, respectively. Since fpm-par achieves the best-known distortion of and also satisfies Pareto efficiency, we instantiate our theorems with the mechanism (fpm-pary fur) to obtain the tightest bounds.
Finally, for the avg-max and max-max objectives, we prove that the mechanism (fpar: fur) achieves distortion at most 3, a consequence of Pareto efficiency.
Theorem For the max-avg objective general metric spaces, we have D((fa, fur)) S
By using fpm instead of f, as the in-group voting rule (with a = and applying Theorem 3.1 we conclude that V = (fpm fur) is rand-det mechanism that satisfies the bound stated in Corollary 3.2
Corollary 3.2 (of theorem B.I.. For the max-avg objective general metric spaces, there exists rand-det mechanism with distortion at most 5.
Theorem 3.3
For the avg-avg objective in general metric spaces, we have D((fa, fur)) S a
Once again, by using fpm instead of fa as the in-group voting rule (with and applying Theorem 3.3 we conclude that V = (fpm: fur) is rand-det mechanism that satisfies the bound stated in Corollary 3.4
Corollary 3.4 (of theorem 3.3). For the avg objective in general metric spaces, there exists a rand-det mechanism with distortion at most 5 163-2/1 -/kk.
For the avg-max and max-max objectives, we derive upper bound of 5 following argument analogous to the proof of Theorem 3.1 Now, we improve the upper bound of 5 to 3 by applying the property of Pareto efficiency. Theorem
3.5 For the avg-max and max-max objectives in general metric spaces, we have D((fpar: fur) S 3.
3.2 Lower Bounds
Now, we establish lower bounds on the distortion of rand-det mechanisms. Specifically, Theorem 3.6 provides lower bounds for the max- max and avg-max objectives. Theorem 3.7 covers the max-avg objective, and Theorem 3.8 addresses the avg-avg objective. It is worth noting that all the lower bounds in this section are derived from symmetric instances and apply in that setting as well.
Theorem 3.6, For the avg-max and max-max objectives, the distortion of any rand-det mechanism is at least 3, even when the metric space is line.
For the max-avo avg, and avg avg, objectives, use the Bias Tournament establish the lower bounds stated in Theorems 3.7 and 3.8
Theorem 3.7. For the max-avg objective, the distortion of any rand-det mechanism is at least 5, even when the metric space line.
We now establish the lower bound for the avg-avg objective in general metric spaces. Theorem 3.8 For general metric spaces and the avg-avg objective, the distortion of any rand-det mechanism is at least 5 k.
8

---

Distortion Bounds for rand-rand
This section examines the rand-rand mechanisms, which are pairs (fr:: composed of two randomized voting rules füx and fou. We establish distortion bounds under all considered objectives.
4.1 Upper Bounds
Throughout this section, analyze the mechanism (fra fur) and show that despite its simplicity, achieves tight (or nearly tight) distortion bounds for various cost objectives. In particular, for the max-max objective (indeed the objective), establish that choosing the top candidate of any voter yields a distortion of at most We begin with the simplest case, max-max, and move towards the most intricate avg-avg.
Theorem
4.1
For the max-max objective in general metric spaces, we have D((frd: fur)) S 3.
Theorem 4.2
For the avg-max objective in general metric spaces, we have D((frd: fur)) I 3.
For the max-avg objective, the key insight is to show that for any voter costy* ()) (top(v)) < 2d(v, o) + cost(o). This crucial inequality is the foundation for proving the desired upper bound.
Theorem
For the max-avg objective in general metric spaces, we have D((frd: fur)) I 3.
Theorem For the avg-avg objective in general metric spaces, we have D((fra, fur)) 2/km"
where n represents the maximum value of Bi over all groups.
As corollary of Theorem 4.4 we conclude that =(fra; fur) is rand-rand mechanism that satisfies the bound stated in Corollary particularly in the symmetric case (kn* =n).
Corollary 4.5 (of theorem 4.4). For the avg-avg objective in general metric spaces, there exists rand-rand mechanism with distortion at most 3 2, provided that the groups are symmetric.
4.2 Lower Bounds
In this section, all results derived from the symmetric instances and apply to that setting well.
Theorem 4.6 For the max-avg and max-max objectives, the distortion of any rand-rand mechanism least 3, even when the metric space is line.
Theorem 4.7 For the avg-max objective, the distortion of any rand-rand mechanism is at least 3 (equivalently. 3 _)), even when the metric space is line.
In the centralized setting. where all voters belong single group (k 1), the avg-max objective simplifies to the max objective. Thus, the instance and analysis from the proof of Theorem [4.7] which already considers the single-group case, apply directly. As the number of voters increases, the distortion approaches 3. Therefore, for any constant & > 0, an instance can be constructed with a sufficiently large number of voters (n ?) such that the distortion of any randomized voting rule exceeds 3 - e. This yields the following corollary.
Corollary 4.8 (of Theorem 4.7.. For the max objective in the centralized setting, the distortion of any randomized voting rule is at least 3 E, for any constant > O, even when the metric is a line.
Theorem 4.9 For general metric spaces and the avg-avg objective, the distortion of any rand-rand mechanism is at least 3 (equivalently 3 7
5 Resolving the Distortion Bounds for det-det
In this section, we study the distortion of deterministic distributed mechanisms, providing both lower and upper bounds in general metric spaces. Anshelevich al. (1) proposed the a-in-B-over mechanism (Mas), ), which allows any candidate- not just representatives to be selected as the final winner. We adopt their approach here.
5.1 Upper Bounds
We establish improved upper bounds for deterministic mechanisms with respect to the avg-max and max-max objectives. Let fa be deterministic voting rule with distortion at most 3, and let fpor

---

be a deterministic voting rule that satisfies the property of Pareto efficiency. We improve the best known upper bound for the avg-max objective from 11, as proved by [. to 7 by applying mechanism (par; fg)). For the max-max objective, we improve the previous upper bound of 5 to 3 using Med- We begin with the simplest case, max-max, and move towards the slightly more intricate avg-max.
Theorem 5.1
For the max-max objective in general metric spaces, we have (mma)) ) S 3.
Theorem 5.2
For the avg-max objective in general metric spaces, have (((ppars fß)) - 2,3 + 3.
We can apply fpm-par as both the in-group and over-group voting rules. Assuming each voter is at distance of 0 from her top choice, this yiclds a distortion of = 2, as shown in [[4]. Combined with Theorem 5.2 conclude that V/ (fpm-par, fpm-par) is a det-det mechanism that satisfies the bound Corollary 5.3
Corollary 5.3 (of Theorem 5.2p. For the avg-max objective in general metric spaces, there exists
det-det mechanism with distortion at most
5.2 Lower Bounds
In this section, we present a lower bound of on the distortion of any det-det mechanisms under the max-avg objective, improving upon the previous bound of + v5, which achieved by [. Following the framework in that paper, our analysis applies the over-group voting rule across the set of candidates (C), rather than the group representatives (R).
Theorem 5.4, For general metric spaces and the max-avg objective, the distortion of any det-det mechanism is at least 5.
6 An Extension of Lower Bounds for rand-rand and rand-det
In this section, we focus on the Euclidean metric and establish lower bounds on the avg-avg distortion for both the rand-rand and rand-det mechanisms, as presented in Theorems 6.1 and 6.2 respectively.
Theorem 6.1. For the avg-avg objective in Euclidean space, the distortion of any rand-rand mechanism is at least /5 E, for every constant e O.
Theorem 6.2 For the avg-avg objective in Euclidean space, the distortion of any rand-det mecha- nism least + v5- E, for every constant E >> 0.
7 Discussion and Open Problems
In this paper, we have initiated the study of metric distortion in single-winner distributed voting under randomized mechanisms (rand-rand and rand-det) for many different objectives. We also have improved upon previous results for deterministic mechanisms (det-det). Although our work presents an almost complete picture in the distortion of distributed voting problem, it reveals several promising directions for future research. A significant challenge about our work leaves open lies in analyzing the det-rand mechanisms, where random decisions in the first stage are followed by deterministic ones in the second. Our primary tool, the Bias Tournament technique, is incompatible with the randomized first stage of det-rand. Currently, our understanding is confined to basic results inherited from rand-rand (for the lower bounds) and det-det (for the upper bounds). To obtain tighter results, need more refined arguments, a promising direction for future work.
Within the scope of our work, another possible direction could be to close the remaining narrow gaps between the lower and upper bounds presented in Table 2 particularly for the avg-avg and avg-max objectives in det-det, as well as the avg-avg and avg-max objective in rand-rand. Another direction is to examine the distortion of the avg-avg objective for all proposed mechanisms, in more structured Euclidean and line metrics--herr results may differ from those in general metric spaces. Another natural extension is to investigate distributed mechanisms in cardinal setting, where agents have access to exact distances, instead of solely the ordinal rankings induced by those distances.
Going beyond the single-winner voting, one could study the distortion of distributed mechanisms that select committees comprising a specified number of alternatives. Another intriguing direction for future research is to investigate how agents' strategic behavior impacts distributed distortion. The goal could be understand whether possible to design distributed mechanisms that are both strategyproof and capable of achieving low distortion.
10

---

References
[1] Elliot Anshelevich, Aris Filos-Ratsikas, and Alexandros A Voudouris. The distortion of distributed metric social choice. Artificial Intelligence, 308:103713, 2022.
[2] Kenneth J Arrow, Amartya Sen, and Kotaro Suzumura. Handbook of social choice and welfare. 2010.
[3] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jéröme Lang, and Ariel D Procaccia. Handbook of computa- tional social choice. 2016.
[4] Ariel D Procaccia and Jeffrey S Rosenschein. The distortion of cardinal preferences in voting. In Proceedings of International Workshop on Cooperative Information Agents (CIA), pages 317-331, 2006.
[5] Michal Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. In Proceedings of ACM Conference on Economics and Computation (EC), pages 269-286, 2016.
[6] Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: survey. In Proceedings of International Joint Conference on Artificial Intelligence (ICCI). pages 4356-4365, 2021.
[7] Elliot Anshelevich and Wennan Zhu. Ordinal approximation for social choice, matching, and facility location problems given candidate positions. ACM Transactions on Economics and Computation, 9():: 2021.
Panagiotis Kancllopoulos, Alexandros A Voudouris, and Rongsen Zhang. Truthful two-facility location with candidate locations. In Proceedings of International Symposium on Algorithmic Game Theary (SAGT). pages 365-382, 2023.
[9] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikss, and Alexandros Voudouris. few queries go long way: Information-distorie tradeoffs in matching. Journal of Artificial Intelligence Research, 74:227-261, 2022.
[10] Nima Anari, Moses Charikar, and Prasanna Ramakrishnan. Distortion in metric matching with ordinal preferences. Proceedings of ACM Conference on Economics and Computation (EC), pages 90-110, 2023.
[11] Mohamad Latifian and Alexandros A Voudouris. The distortion of threshold approval matching. In Proceedings of International Joint Conference on Artificial Intelligence (ICCAI), pages 2851-2859, 2024.
[12] Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264:27-51, 2018.
[13] Kamesh Munagala Kangning Wang. Improved metric distortion deterministic social choice rules. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC), pages 245 262,2,2222 2019.
[14] Vasilis Gkatzelis, Daniel Halpemn and Nisarg Shah. Resolving the optimal metric distortion conjecture. In P Proceedings of Symposium on Foundations of Computer Science (FOCS), pages 1427-1438, 2020.
[15] Elliot Anshelevich and John Postl. Randomized social choice functions under metric preferences. Journal of Artificial Intelligence Research, 58:797-827, 2017.
[16] Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for randomized social choice. In Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2986-3004, 2022.
[17] loannis Caragiannis, Nisarg Shah, and Alexandros A Voudouris. The metric distortion of multiwinner voting. Artificial Intelligence, 313:00 2022.
[18] Ioannis Anagnostides, Dimitris Fotakis, and Panagiotis Patsilinakos. dettic-distortion bounds under limited information. Journal of Artificial Intelligence Research, 74: 14:1449-1488, 2022.
[19] Fatih Erdem Kizilkaya and David Kempe. Generalized veto and practical voting rule with optimal metric distortion. In Proceedings of ACM Conference on Economics and Computation (EC), pages 913-936, 113-936,727 2023.
[20] Amirreza Bagheridelouee, Marzie Nilipour, Masoud Seddighin, and Maziar Shamsipour. Metric distortion under public-spirited voting. In Proceedings of International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2144-2146, 2024.

---

[21] Mohammad Ghodsi, Mohamad Latifian, and Masoud Seddighin. On the distortion value of the elections with abstention. Proceedings the AAAI Conference on Artificial Intelligence (AAAI). volume 33, pages 1981-1988. 2019.
[22] Elliot Anshelevich, Aris Filos- Ratsikas, Nisarg Shah, and Alexandros A Voudouris. Distortion in social choice problems: The first 15 years and beyond. In Proceedings of International Joint Conference on Artificial Intelligence (ICCAI). pages
2021.
[23] Aris Filos-Ratsikar and Alexandros A Voudouris. Revisiting the distortion of distributed voting. Theory of Computing Systems, 1138 1159, 2024.
[24] Aris Filos-Ratsikas, Evi Micha, and Alexandros Voudouris, The distortion of distributed voting, Artificial Intelligence, 18331,,34,, 2020.
[25] Alexandros Voudouris. Tight distortion bounds for distributed metric voting on a line. Operations Research Letters, (113))666-2000 2023.
[26] Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227:190-213, 2015.
[27] Ioannis Caragiannis and Ariel D Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(0-10::1555-177,,2 2011.
[28] Soroush Ehadian, Aris Filos-Ratsikas, Mohamad Latifian, and Nisarg Shah. Explainable and efficient randomized voting rules. In Proceedings of Conference on Neural Information Processing Systems (NeurIPS), volume 36, pages 20034-23046, 2023.
[29] Soroush Ebadian, Anson Kahng. Dominik Peters, and Nisarg Shah. Optimized distortion and proportional fairness in voting. ACM Transactions Economics and Computation, 12(1):1-39 2024.
[30] Mark Bedaywi, Bailey Flanigan, Mohamad Latifian, and Nisarg Shah. The distortion of public-spirited par- ticipatory budgeting. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 39, pages 33605-13613. 2025.
[31] Michal Jaworski and Piotr Skowron. Evaluating committees for representative democracies: the distortion and beyond. In Proceedings of International Joint Conference on Artificial Intelligence (ICCAI), pages 196 202, 2020.
[32] Fatih Erdem Kizilkaya and David Kempe. Plurality veto: A simple voting rule achieving optimal metric distortion. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pages 349-355, 2022.
[33] Moses Charikar, Prasanna Ramakrishnan. Kangning Wang, and Hongxun Wu. Breaking metric voting distortion barrier. Journal of the ACM, (1(6):1-33, 2024.
[34] Vasilis Gkatzelis, Mohamad Latifian, and Nisarg Shah. Best both distortion worlds. In Proceedings of ACM Conference on Economics and Computation (EC), pages 738-758, 2023.
[35] Aris Ratsskaa Panagiotis Kanellopoulos, Alexandros A Voudouris, Rongsen Zhang. The distortion of distributed facility location. Artificial Intelligence, 328:104066, 2024.
[36] Alexandros Voudouris. Metric distortion obnoxious distributed voting. Information Processing Letters, 189:106559, 2025.
[37] David Kempe. Communication, distortion, and randomness metric voting, In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 2087-2094, 2020.
[38] Georgios Amanatidis, Elliot Anshelevich, Christopher Jerrett, and Alexandros Voudouris. Metric distortion under group-fair objectives. In Proceedings of International Symposium on Algorithmic Game Theory (SAGT), pages 465-482, 2025.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide proof sketch for all our claims in the main paper, with the full proof' detailed in the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
The gap between our upper and lower bounds for various settings is detailed in Table
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
[TODO]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu Sotp:///ggiddeeeeCouuuuubbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
19

---

A Proofs for Section 2 (Basic Notations)
Observation 2.6, For rand-rand mechanism (frd: fur) with oupuu w, the expected cost of the mechanism is given by El w)] = 2geg 1 Eveg cost(top(u)).
Proof. By the definitions of the Random Dictatorship rule (fyd) and the uniform selection rule (fur), we have
El Elcost(w))
Pr(w W.)) .E(cost(w,))
DEG
E(cost(w,,)
k gEg
Pr (w, top(e)) cost(top(1))
h
JEG c5
cost(top(u)).
k
n2 wEg
JEG
B
Proofs for Section 3 (Distortion Bounds for rand-det)
Theorem 3.1 For the max-avg objective in general metric spaces, have D((fa: fur))
Proof. Consider an instance = (V,C,9, x. and rand-det mechanism V = (fas fur). We have
F[cost(w))] = Σ
co,)(
(Observation 2.5
9E9
Σ
Σ
d(v, Wy)
(Definition of max-avg)
nn (wo) vEg' (W,)
gEg
Σ
d(v,,)) + d(),w))
(Triangle Inequality)
ng (Wa)
959
VEg vEg"(W,) (W₂)
Σ BEG
Σ
d(v,o)
k
Ng' (Wa)
"Eg (w,)
1
d(o, wg))
k
Nig (w,)
gEg
VER" (Wa)
<
cost(o)= +
Σ
d(o,
(Observation 2.4
k
gg (Wa) "En" (w,)
9Eg
9Eg
Σ cost(o) +
Σ
d(o, wg)
T
9Eg
93g
cost(o)
+
d(v,,) + d(),
(Triangle Incquality)
ng
SEG
VEg
cO +
Σ d(e, o)
1o
ng DEg
#Eg
d(v. d(v,wy)
k
fg vEg
gEg
< cost(o) +
cost(o)
Σ
1
cost,(w,)
T
gEg
gEg
20

---

2cost(o) +
Σ
(Wg)
k
NEg
20) +
(O,)
(Observation 2.11
k
gEg
2c +
(O)
(Observation 2.3
k
gcg
2c +
cost(o)
(Observation 2.4
k
9EG
= (a + 2))
Theorem 3.3.
For the avg-avg objective in general metric spaces, we have D((fa, fur)) S a - 2
Proof. Consider an instance I= (V,C,9, and rand-det mechanism V = (fax fur). We have
Fl[cos(ww)]
cost(w,)
(Observation 2.5
9Eg
k
k
gEg
g'Eg
d(e, wy)
(Definition of avg avg-avg)
1:
'l'g
9Eg
l'eg
vEN
d(u, ((u,0)+
9E6
g'E9.94g'
vEg'
Σ
Σ
(W)
(Triangle Inequality)
k
ng'
DEG
of g'EG.gmm
NEg'
Σ
Σ
d(u. () +(),
Tl'
9E9
8'E9.
vEg'
+
cost, (Wg)
#69
Σ
d(u,o) dd
Og' veg'
9EG
g'E0.9t''
+
(Og)
(Observation 2.11
DEG
Σ
Σ
Σ
d(v,, () +do,
959
g'E9.g#g'
Nl' vEg'
cost,
(Observation 2.3
Σ
d(u.,) + +d(,
k
Ng wEg'
GEg
9'E9.9t0'
+ cost(o)
(cost(o) = Σ cost,(o))
9EG
L
d(
Rg veg'
gEg
g'EG.gty'
21

---

+ 1 k
Σ
Σ
c( Wg) + cost(o)
ngg
DEG d'Eaiartu
NES
Σ
Σ
d(e,,o
k 9EG
k
k
+
d(o,
(g)
cost(o)
h
DEG
Σ MEG
Σ
d( o)
k
g' 9'E ng nEg'
1
(d(r,o) + d wg)) + k
cost(o)
(Triangle Inequality)
k
Bg
DEG
vEg
Σ
d(e,o)
ng'
DEG
g'EG.97''
wEg'
+
(costy + cost, (Wg)) (W
cost(o)
(Definition of cost, (.))
9EG
Σ
Σ
d(
ng'
9Eg
g' g'E0.9#g'
wEg'
+
Σ
(costy a cost,(0,)) + a -ost(o)
(Observation 2.11
k
9EG
Σ
Σ
d(c,o)
Vl'g vEg'
gE9
g'E9.gfg'
k
+
(costy (0) a (os + cost(o)
(Observation 2.3
DEG
Σ
o(
g'E". Tl'' vEg'
9E9
(k 1) + 1)
+
cost(o) + k
cost(o)
(Definition of avg-avy wv-a
cost, (0) + ak + k cost(o)
k:
k
k
9CG
g'E
Σ
cost (0)
ΣΣ
cost. (0)
k
k
k k
gEG
g'Eg
gEG d'E5.g=o'
ak + k -
+
cost(o)
b
cost, (0) ak + - cost(o)
cost(o) T gEg
cost(o) cos + ak k-1 cost(o)
(a co)
Theorem
3.5 For the avg-max and max-max objectives in general metric spaces, we have (((ppar:fur) < 3.
Proof. We present a proof for the avg-max result for the max-max objective as well.
max objective. A similar argument can be used to prove the
22

---

1/2
C2
position
0.5
0.5
Figure I: An example used in the proof of Theorem 3.6
Consider an instance I = (V, G, d) and rand-det mechanism v (fpars fur). By the property of Pareto efficiency, for each group g, there exists a voter Un E who prefers Wg to o. Therefore, we have
B[cost(w)] = Σ
(Observation 2.5
9E9
Σ
d(o" (Wg. W))
(Definition of avg wyg-
J'EG
Σ
Σ
((w g. 0) + w()
(Triangle Inequality)
k
k
9-9
d0Eg
Σ
Σ
d(v ("..''))))) -
(Observation 2.10
9Eg
g'Eg
cost(o)
+ Σ
d(o, Wg)
DEG
cost(o) +
d(o, (ig) + d( wg)
(Triangle Inequality)
k 9Eg
2
cost(o) + d(
(d(eg. wg) d(tig. o))
k
cost(o)
2
Σ
ddv
(Observation 2.10
k:
9EG
3cost(o).
Theorem 3.6 For the avg-max and max-max objectives, the distortion of any rand-det mechanism is at least 3, even when the metric space is line.
Proof. Consider rand-det mechanism V = (fin foo). We construct an instance with candidates (2),02) and voters (V1, 122 single group. Ci and C2 are located positions 0 and 1, respectively, U1 and with preference profiles
(C1, C2) and πΣ (e2, 01), are also positioned 00.5 and 0.5, respectively. Refer to Figure [ a visual illustration. Without loss of generality, assume that V selects C2 as the representative of the group, and thus the final winner is C2. Since there is only one group, the avg-max and max-max objectives both simplify to max. Thus, we have cost(c1) & and cost(c2) = Clearly, ei is the optimal candidate. The distortion of V is
cost(c2) cost(c1)
D(V)
3.
Theorem 3.7
For the max-avg objective, the distortion of any rand-det mechanism is at least 5, even when the metric space is a line.
Proof. Consider rand-det mechanism Vi (fin: for). We construct an instance with candidates C = {cr. C2, C3, (4), and voters V = (1), 02, V3. ). all located along line metric. The voters are partitioned into two groups, 91 (w), 02) and g2 (wa, v4)- Let a an arbitrary ordering of the candidates. Without loss of generality, assume that e₁ candidate with in-degree at least
23

---

1/3
V/
O2
0/
C3
C4
position
-1
0.5
0
0.5
10
An example used in case of Theorem 3.7 distinct colors.
Figure 2:
Different voter groups are distinguished by
1/
01
C1
04
position
0.5
0.5
Figure 3: An example used in case 2 of Theorem 3.7 distinct colors.
Different voter groups are distinguished by
2 tournament ((ssn C, o), such a candidate is guaranteed to exist by Observation 2.2 Suppose and are two candidates with directed edges toward eı, meaning that is the "losing candidate while both 02 and 63 "defeat" it in the tournament. We may further assume that 02 >o C3- Now, consider the following construction on the line metric:
Voters and Vy are located at positions 0, while voters and are located at -0.5 and 0.5, respectively.
Candidates c2, C1, and C3 are located at positions 1,, and respectively. The position of candidate Ca depends on the ordering a, ensuring the input to [(fin. C, remains valid. We analyze three cases based on the relative ordering of c22 C3. Ca:
Case If C2 >a C3 >a c4. candidate C4 located at position 10. Refer to Figure for an illustration.
Case 2: If C2 >a C4 >a Cg. candidate C4 is located at position -1. This case is illustrated Figure 3
-Case 3: If ca To > a C3 candidate is located at 1. A visual representation of this case can be found Figure
Note that when a voter equidistant from two candidates, multiple preference profiles may be consistent with the underlying metric space. According to T(fin, C, d), we can determine the group representatives:
A directed edge from to C1 implies that co is selected as the representative for group 91-
Similarly, a directed edge from C3 to C1, means is the representative for group g2-
By the definition of the max-avg objective, we have cost(c2) cost(c3) and cost(c1) 1 Thus, C₁ is the optimal candidate in all cases. The mechanism must select the final winner from the group representatives, C2 C3. Finally, we derive the distortion of mechanism V/ as:
D(V) > min cost(c2)
cost(ca)
cost(o) cost(o)
cost(c.)
Theorem 3.8
general metric spaces and the avg-avg objective, the distortion of any rand-det
mechanism is at least 5
k.
24

---

U2
C2
C1
04
Ca
position
0.5
0.5
Figure 4: An example used in case 3 of Theorem distinct colors.
3.7
Different voter groups are distinguished by
C1
C2
Ck
Ug
245
W2k++1
U2
14
U2k
U2
u4
U22
02k
U2k+2
U2k+3
U1 03 ..... U2h-1
Ck+11
C2k-1
Figure 5: Tree graph used in the proof of Theorem 3.8 distinct colors.
Different voter groups are distinguished by
Proof. Consider a rand-det mechanism v (fan for). We construct an instance with a set of C2 and l groups 9s = { [2) for S S k. Let a be an arbitrary ordering of the candidates. Without loss of generality, assume that C22 candidate with in-degree at least m==1
m = 2k candidates, C = C2. Cm=2k }, set of n. 2k voters, V = {V1, .2,.... Un=2k }.
in the
tournament (ffin C, .), such candidate is guaranteed to exist by Observation 2.2 Further, suppose
C1, C2,-.... C* are k candidates that have directed edges toward C2k in the tournament, meaning that C2k: the "losing" candidate.
We construct a connected graph G with 2k + 3 vertices, denoted U1 U2, U22433 where the shortest-path distances in G' define the underlying metric space d. Each voter and candidate is placed on one of the vertices (a single vertex may host multiple entities). The graph constructed as follows (see Figure 5 for illustration):
Place candidate C2k vertex W1.
For each 1 < i S k + 1, add an edge between #1 and tigs and another edge between U2i and U2;-1- This forms & + branches extending from the central vertex
For each i < k. place voter U2:1 vertex U1, voter Uai at vertex ugi and candidate ca at vertex U2:+1
For each & + < i < 2k 1, place candidate at vertex W2k+3-
Pairwise distances between the candidates and voters are presented in Tables and 4 Moreover, the preference profiles Table by the shortest-path distances in graph G, are consistent with the metric space d. Note that multiple preference profiles may be consistent with d.
According (ffin C, .). the representative of group gi candidate e, for any Si k. Thus. the mechanism must select one of these representatives as the final winner. By the definition of the
avg-avg objective, we have cost(c2)) = 1 and cost(c;) = 5-ž, for all S i < k. Thus, 62k the optimal candidate. It follows that the distortion of mechanism v:
25

---

d(
Cj
U2i-1
2
1/2
22 1-
2
22
3
Table 3: For any 1 S i,j S Is with + j. the shortest-path distances in graph G between candidates
C1, -2..... C and the voters used in the proof of Theorem 3.8
dl...)
C2
C2k 0
22
U2j
3
Table 4: For any & + Si and S S k, the shortest-patt distances graph G between
candidates C++1; Ck+2. .... C2k-1: C2k and the voters used in the proof of theorem 3.8
(cos((c)
ginigise
D(V)
cost(o)
cost(
2
5 k
C Proofs for Section (Distortion Bounds for rand-rand)
Theorem 4.1
For the max-max objective in general metric spaces, we have D((frd; fur)) S 3.
Proof. Consider an instance I = (V,C, d) and rand-rand mechanism v (frd far). For any
voter V, we have
cost(top(w)) = d(u (top(u)),top(w)
(Definition of max-max)
d(u"" (top(t)))))
(Triangle Inequality)
+ d(e, top(u))
(Triangle Inequality)
I ((((),)) d(r,
(Observation 2.9
I =d) d(v.o)
(Observation 2.8
22(()) < 3d(x"*(o),
(Observation 2.9 (cost(o) d(v (o),
3cost(o)
Combining this with Observation 2.6 we have
E| c(cost(w)] = Σ Σ
cost(top(v))
9EG fy
vEg
< 3cost(o).
Theorem 4.2
For the avg-max objective in general metric spaces, have D((frd, fur)) S 3.
26

---

Voter 2/2
Preference Profile
o Tozk
1/i
a t0
Table 5: The preference profiles of the voters within each group gi S k), used in the proof of theorem 3.8
Proof. Consider instance I (V, C, 9, d) and rand-rand mechanism V (frrd fur). By definition of the avg-max objective for any voter v E V. we have
cost(top(w)) = Σ (top(())
gEG
Now, for any groups 9. E G and any voter v E g', we have
cost, (top(u)) = (t(=) top(()
(Definition of cost,
s (top"(too())))))) d top.to
(Triangle Inequality)
< (top()) d(v.
(Observation 2.8
d(="(top(vv)g) d(v. + d(r,o)
(Triangle Inequality)
S d(v"(o.g). ())((vo)))))((()))))))
(Observation 2. 2010
+ cost,(o)+2d(cr 2d(r,
(Definition of cost, (-))
< cost, + 2d(r"
(Observation 2.10
cost, (0) + 2cost, (0)
(Definition cost, (.)).
Combining this with Observation 2.6
we obtain
[[cost(w)]
cost, (t)p(r))
k
Fig
gEg
VEg
5'Eg
1
(2cost, (0) + cost,.(o))
k
ng
k
0EG
eEg
3'EG
2cost, (o) + cost, (o)
h 9Eg
d'E9
1
2cost, + cost(o)
(Definition of cost(-))
k 9EG
3cost(o)
(Definition of cost(.))
Theorem 4.3
For the max-avg objective in general metric spaces, we have D((frd: fur)) I 3.
Proof. Consider an instance I = (V,C, G. π, d) and rand-rand mechanism v (frd, fur). By the definition of the max-avg objective for any voter E V, we have
cost(top(v)) = max coop,(toprrr))
gEğ
costy (top()) (top()))
Σ
top())
(Definition of cost, (.))-
ng (top(v)) v'En" d'En""lop(on (lop(v))
Thus, have
cost.- . (top( (top(e))
=
Σ
((v'.top(v))
ngg (top())) o'En" (top(r))
Σ
(((w)) + d(v,
(Triangle Inequality)
Ng' (lop(n)) e'En" (top(u))
27

---

(((.,)) + +
(Observation 2.8
Ng" (top(:)) e'Eg" (top(v))
Σ
d(u,o) d( d(),
(Triangle Inequality)
(gg((()())) o'Eg" (top(w))
2d(w, o) + T (top((())
Σ
d(o,
E'Eg (top(v))
2d( v. o) (lop()((
< 2d(e, 0) cost(o)
(Observation 2.7
Combining this with Observation 2.6 we obtain
E[cost(w)]
cost(top(())
k:
fg
9E9
cost (top(o)) (top(())))pp
(Definition of cost(.))
7:
fg
9Eg
vEg
(2d 1. 0) + cost(o))
k gEG
fgg
vEg
cos +
2d or o)
Fgg
y6g
#Eg
cost(o) + (ost,
(Definition of cost, (.))
k
SEG
< cost(o) +
cost(o)
(Observation 2.7
#Eg
3cost(o).
Theorem 4.4
For the avg-avg objective in general metric spaces, we have D((frá, fur)) 2/kmn where n* represents the maximum value of ngg over all groups.
Proof. Consider an instance I (V, C, ,, d) and rand-rand mechanism v/ (frdd fur). By the definition of the avg-avg objective for any voter v E V. we have
cost(top(v)) k
Σ 8'EG
costy (top(u)).
For any voter E V and group g', we have 1
costy (top(u)) = Σ
topp()
(Definition of cost, (-))
ngg v'Eg'
<
1
Σ
d(c,,to(v)) + d(o',
(Triangle Inequality)
Ylg''
v'Eg'
1
<
(((,,)) + d(d(
(Observation 2.8
'h'g
v'Eg'
d(r, +
Σ d(vl,u).
Ng' v'eg'
Combining this with Observation 2.6
obtain
B[cost(w)]
Σ
cost, (top()))
(Definition of cost(.))
Tg
gEg
VEg
g'eg
28

---

d(v o)+ +
d(v',
ng
k
ng
DEG
vEn
D'EG
r'Eg'
d 0)
Σ
d(v',u)
ng
ng
k
9E9
gEg
vEn
g'Eg
V'Ey'
cost(o)
d(u'.u) ..)
(Definition of avg-avg)
Rg
Ng
JEG
eEg
g'Eg
E'Eg'
cost(o)
E
((v.,)+ + d(o,
(Triangle Inequality)
Fg
Nig'
DEG
vEy
d'Eg
v'
cost(o) +
Σ
Σ
Σ
Σ
d(e,o) + d(o,
k
Ri
k
Ngs
geg
vEg
g'Eg
d'Eg'
Σ
E
d(u.o) + d(o,
Fg
Rig
DEG
vEg
o G'EG.g'
mg
o'Eg' oo'mp
1
cost(o)
d(u,o) d(o,
k
Rg
k
9Eg
eEg
60Eg
v'Eg'
1
2d(v,o) o)
Thg
Thg
wEg
cost(o) 2c0st(o)
Σ
(d 0)
(Definition of avg avg-avg avg)
ng
k T2g
8Eg
1
3cost(o)
2d
(v, o)
gEg
vEg
2
3cost(o)
(o)
(Definition of cost, (.))
2
ng
gEg
< 3c
2
Σ
(o)
k2
n
gEg
2
(3 kn
cost(()
(Definition of avg-avg),
Theorem 4.6
For the max-avg and max-max objectives, the distortion of any rand-rand mechanism least even when the metric space is line.
Proof. Consider any rand-rand mechanism v = (fin, foo). We construct an instance with candidates [e1, 02 03) and voters V = (11, where each voter belongs to a distinct group: d1 E 91 and U2 92. The instance is constructed the line metric as follows (refer to Figure
Candidates C1, C2, and C3 are located at positions -1, 0, and 1, respectively.
Voters ej and 02 are located at positions -0.5 and 0.5, respectively.
The preference profile of each voter is mi (c1, C22 C3) for 01 and गे (c3, C2 01) for Us.
Trivially, the preference profiles are consistent with the distances in Figure 6 According to Observation 2.I] candidates 61 and c3 are chosen as the representatives of groups 91 and ga. respectively, and then mechanism y must select one of them as the final winner. We have cost(c1) cost(ca) o and cost(c2) $.. Clearly, e2 is the optimal candidate. The distor- tion of V is:
min (ino(ts(())) cost(o)
D(V)=
29

---

position
0.5
Figure 6: An example used in the proof of Theorem 4.6
for)
C\ {ca
position
-0.5
0.5
Figure 7: Configuration of the candidates and voters in instance I used in the proof of Theorem 4.7
cost(c2 (c2)
3.
Theorem 4.7 For the avg-max objective, the distortion of any rand-rand mechanism is at least 3 3-2 (equivalently, 3 - 1.), even when the metric space is line.
Proof. We construct instance with set of m candidates, C= fc, (2......... Cm ) and set of
n = m voters, V = (Ui ....., vn
). all belonging to single group. Each voter n has a preference profile T. that ranks candidates cyclically, starting with a their top choice:
R (c,, C++1. Cra C1 C2:
G-11)
Now, we construct m instances, denoted I1 I2....... Im. on the line metric. Across all instances, the voter set V, candidate set C, and the preference profile are identical; they differ only in the arrangement of voters and candidates within the underlying metric space.
For any instance I, where 1 < S m, configuration of the line metric is as follows (see Figure 7
Candidate o is located at position 0, while all other candidates are located at 1.
Voter 0ú is located at position -0.5, and all other voters are located at 0.5.
is straightforward verify that each constructed instance is consistent with the specified preference profile. Since there is single group, the avg avg-max max objective simplifies to max. For each instance I, we have cost(c;) (c;) 2' and cost(c,) 2 for S m (where + j). Clearly, G, the optimal candidate in Z,
Now, consider any rand-rand mechanism V. Let ps denote the probability that V selects ez the winner, where Σ/ -i= Ps 1. For instance I,, the mechanism' 's expected cost is
Flcost( V (II))) =
cost(c,) = Σ 1
+ Pi
1
(1
pb)
P: +
pi-
2
2
2
2
It follows that
E E|cost( (Z)))
P:
3 2p:-
cost(o)
Since the total probability must sum up to I, there exists some index such that p; S n Finally, obtain the following lower bound on the distortion of T
D( V
2
=
m
n
Theorem 4.9
For general metric spaces and the avg-avg objective, the distortion of any rand-rand mechanism is at least 3 (equivalently 3 2
30

---

C1
C2
Gm-1
U3
Ug
m2m-1
U1
U2
vm-1
U2
U4
U2m 2
Cm
Figure 8: Tree graph used in the proof of Theorem 4.9 distinct colors.
Different voter groups are distinguished by
d
C4
Cm
Table For any 1 S i,j & with + j. the shortest-path distances between candidates and voters, derived from tree graph G in the proof of Theorem 4.9
Proof. Consider rand-rand mechanism V. We construct an instance with a set of m k + candidates, C = {ci, ....... Cm-k+11 set of n = k voters V = ffr, 02,.... Un and l single- voter groups, 9: = { for 1 S i S k. Each voter e; has preference profile mis with 6, as top choice, immediately followed by Cm. denoted candidates.
otcnte, where a is ordering of the
We now construct a connected graph G with + m vertices, denoted u1, U2...... Un+ where the shortest-path distances in define the underlying metric space d. Each voter and candidate is placed on one of the vertices. The construction of G is as follows (see Figure [ for an illustration):
Place candidate cm at vertex
For each 1 < i < k, place voter v, at vertex U2a and candidate at vertex U2i+1
For each 1 < i < k, add an edge between in and u2c, and another edge between ua and U21+1- This forms & branches extending from the central vertex
See for the corresponding distances. For all 1 sis k. we have top(v;) Therefore, the representative of group 9i is candidate e; (by Observation 2.1). Consequently cm is not the representative of any group, and thus cannot be the winner of mechanism V. According to the definition of the avg-avg objective,
have cost(c:) 3(m-1)+1 3- for < m, and cost(cm) = 1. Clearly, 6n is the optimal candidate. We obtain the lower bound on the distortion of as follows:
cost(c;)
D(V) 2 min 1mcm
cost (o)
3
cost(cm.)
3 71
31

---

D Proofs for Section (Resolving the Distortion Bounds for det-det)
Theorem For the max-max objective in general metric spaces, we have D(mad) S 3.
Proof. Consider an instance I = CV, and the Arbitrary Dictator mechanism (Vi = mad), which selects the top-ranked candidate an arbitrary voter e as the final winner; that w top(v). We follow a strategy roughly analogous to that in Theorem 4.1
cost(top(e))
d(u (top(t)).
(Definition of max-max)
< d(e""(top(v))) ((v, d(u,
(Triangle Inequality)
d(u (top(t)). d(v,
(Observation 2.8
S d(u" (top(u)).o) + d(o, u) + +d(,.o)
(Triangle Inequality)
d(u" +
d( (top(u)).o) + 2d(r 2d(r"
(Observation 2.9
3d (o).
(Observation 2.9
3c)
(Definition of max-max).
Theorem 5.2
For the avg-max objective in general metric spaces, have D((ppar. fß)) S 2,8 + 3.
Proof. Consider instance I (V, CV, d) and det-det mechanism V (fpar: fa). By the property of Pareto efficiency. for each group there exists a voter Vi E who prefers the representative W the optimal candidate o. We have
cost(w)=
Σ d(v"(w:g)... (W,g).w)
(Definition of avg-max)
DEg
d(v (W, g), + d(o,w)
(Triangle Inequality)
9Eg
d(r (0. 9), 0) - d(o, w)
(Observation 2.10
gEg
= cost(o) +
d(o, w)
(Definition of avg-max)
SEG
< cost(o) d(o, W + d(w,w,)
(Triangle Inequality)
gEg
cost(o) (3 1)
d(o, wg)
(Observation 2.12
k
DEG
< cost(o) (B+11) 1)
1
Σ
d(o, v/))
+ d(ug.
(Triangle Inequality)
h
DEG
< cost(o) + 2(3 + 1)
Σ
d Un))
(d(u,. w,y) S d(Ugs o))
T
gEg
< cost(o)+ + 2(8 1)
d(o, ((.g))
(Observation 2.10
gE
= (25 + 3)oos(()
(Definition of avg-max).
Theorem 5.4
For general metric spaces and the max-avg objective, the distortion of any det-det mechanism is at least 5.
32

---

C1 01, 03
24
u1
V/2
116
U2
C3
U5
u3
C2
u4
u/
ug
U77
C4
Figure 9: An illustration of the graph G used in the proof of Theorem distinguished by distinct colors.
5.4
Different voter groups
d
C1
C2
C3
C4
01
0
2
2
2
1/2
1
1
3
3
03
0
2
2
2
17
3
3
Table 7: The shortest-path distances between candidates and voters, as derived from the graph G in the proof of theorem 5.4
Proof. Consider det-det mechanism T -fin: foo)- We construct instance with set of candidates = {c1: C2 Cy. c1), a set of voters V ff1, U2 U3 va), and 2 groups 91 = {ur, by and 92 {va, 14 J. Let be arbitrary ordering of the candidates. Without loss of generality, assume that has in-degree of at least m=-1" 2 in the tournament T (f C, such candidate is guaranteed to exist by Observation
2.2 Further, let 0o and c3 be the two candidates with directed
edges toward in the tournament.
We now construct a connected graph G with vertices, denoted U1. U2. Ug, where the shortest- path distances in G define the underlying metric space d. Each voter and candidate is placed at one of the vertices single vertex may host multiple entities). The graph configuration is as shown in Figure
Pairwise distances between the candidates and voters are presented in Table 7 Now, we define the preference profiles in Table & which consistent with both the thortest-path distances in graph G and the input of tournament (ffmn C, ar. Note that multiple profiles may be consistent.
Since candidates 02 and c3 defeat in T(fin: C, o), they must serve the representative of groups Si and G2. respectively. Thus, the set of representatives is R 0a).
At the second stage of the distributed voting process, we consider two instances:
Zi: The preference profiles of 02 and are (c2, C12 ca) and (c3, C4, 62), respectively.
Zz: The preference profiles of and cy are (c2, ca, C1, ca) and (cy, C1 62), respectively.
is straightforward to verify that both I₁ and Iz are consistent with the metric space defined earlier. In both cases, the preference profiles of 02 and ca follow the pattern
(C2, Cas Cb. C3) and (ca, Cas Cb 02):
where (ca, cb) is some ordering of c4).
the rule selects the first-ranked or fourth-ranked candidate, then er not chosen. If the rule selects the second-ranken candidate (c,), then in In again exclude c1. If the rule selects the third-ranked
33

---

Voter
Preference Profile
U1
t/2
oter
03
tes
1/
oter te3
Table 8: The voter preference profiles used in the proof of theorem 5.4
candidate (ct), then in In exclude et. Therefore, in every case, there exists instance in which the mechanism selects the winner from the set (02, C3, ca).
By the definition of the max-avg objective, we have cost(c)) = å/ and cost(c2) cost(c3) cost(ca) 3. Thus, e₁ is the optimal candidate. The distortion of mechanism y is obtained as follows:
D(V) min cost(s
cost(o)
cost(c1)
5.
Proofs for Section (An Extension of Lower Bounds for rand-rand and rand-det)
Theorem 6.1
the avg-avg objective Euclidean space, the distortion of any rand-rand mechanism at least v5- E, for every constant 0.
Proof. Consider any rand-rand mechanism V. Let be positive integer. Consider an instance in (I + 1) dimensional Euclidean space, IR/+1, with + candidates, denoted 6 ..,.... Ct+2, and k = ++1 groups, each with single voter e for 1 s S 1 1. We construct the instance follows:
Let qi be the point in R++1 whose i-th coordinate is and all other coordinates are for s iisl+1
Place candidate o at point q for each
The final candidate, 442- is placed at the centroid of the other candidates; [ - 1 -
In the i-th group, the single voter u, is positioned the midpoint between their corresponding candidate, and the centroid candidate, C1+2- Indeed, each voter U; is located at a point
where the i-th coordinate is 2(T+1) and other coordinates are 2(1-1j Note that each voter's preference profile is structured so that the top-ranked candidate of voter e is e. consistent with the underlying Euclidean space.
I+2
particular, 3D space (I = 2), the instance lies within an equilateral triangle with vertices (1,0,0). (0, 1, 0). and (0, 0, 1), illustrated in Figure 10
For all
< ( 1, we have
d(c, v/) = d(c(42 vz)
1
2
2
1
2(1 + +1)
2(1+1)
I
4(1 11
34

---

C3
(0, 1))
6..0 6.
3 82
02
(0,1,0)
6 (1,0,0)
Figure 10: A dimensional Euclidean model (l 2) illustrating the geometric lower bound construction for the rand-rand mechanisms under the avg-avg objective. Candidates Cı C22 and cs are located at the unit basis vectors, with 4 = (3: 1 3: at the centroid of the triangle they form. Voters U1, U2, and Uy positioned at the midpoints between the centroid and their top-ranked candidate G. Different group voters are indicated via distinct colors.
Moreover, for all 1 1 i,j < 1 + 1 (where i * f), we have
1+2
+ 1
d(c, uy)
V
(1 (1-1)+
1)+
+
2(T
2(1 2(1+1)
21 +
55 +
41 +
By the definition of the avg-avg objective, the cost of each candidate is the average distance to all ++ voters. Thus, we conclude that
cost(c142) =
2
1+1
1/
51+4 al+4
2 41
cost(c:)
(15151+1).
1+1
Clearly, the optimal candidate is Ct+2- According to Observation 2.1 the representative of the i-th group is candidate e. Finally, the mechanism selects winner from among the candidates
C2,02....5 (2,...,,44,,, A lower bound on the distortion of the mechanism V is obtained as follows
<L
cost(c;)
D D
cost
(44)
54+4
41+4
2(+11
2 V
35

---

As I + oo, the ratio approaches v5 = 2.236. Therefore, for any E >> 0, we can construct an instance with distortion greater than v5 s.
Theorem 6.2 For the avg-avg objective in Euclidean space, the distortion of any rand-det mecha- nism least + V5 E, for every constant E >
Proof. Consider rand-det mechanism Vp (fin: fou), set of 2m candidates C {ci, 02,..., (2m). and an arbitrary ordering a over them. By Observation 2.2 the tournament T(fan: C, must have candidate with in-degree least 2m-1 m. Without loss of general- ity. let Cm+11 be such candidate and let ......, Cm be m candidates that have directed edges toward Cm+1 in the tournament. We now construct the following instance with m groups in (m + 1) dimensional Euclidean space:
Let q, be the point in m=+1 whose i-th coordinate is 1 and all other coordinates for S i m + 1.
Place candidate o at point q, for each 1 & < m and candidate Cm+1 at the centroid
m+1 m+1
m+1
Place candidate e; point gm+1 for each m S S 2m.
In the i-th group (1 < m). there are voters:
1. Voter U2--1 is located at the centroid, which is the same position candidate Cm++1 2. Voter 2/2 is located exactly at the midpoint between candidates Cm+11 and C₁ with coordinates equal to 2[m=1]
m++2 in the i-th dimension and 2m++1 in all other dimensions.
The ordinal preferences of the 12;-1 and U2i are defined T2:-1 om and T2.
a These preferences are consistent with the underlying Euclidean space:
1. The distance from 1 to all candidates except Gm+2 is equal.
2. The distance from 12 to Cm++ is zero.
3. Voter is closer to candidates Cm+11 and C; than to any other candidates, and is equidistant from all remaining ones.
The distance from U2 to candidates 6m+1 and e is equal.
When m = 2 the instance lies within an equilateral triangle with vertices at (1, 0, 0), (0, 1,0), and (0, 1), shown in Figure 11 For all 1 S i, m, we have
d(c,, 1m++1 = d(c;, U2--1)
m +
m 1
+
m
m +
for all 1 5 1 (where + j), we have
2mm + 1) )
+
2
2m + 1
2
d(c,, U2j)
(m (m-1)= 1)+
+
2(m
2m + 2
5mm 4
V
4m
and for all 1 < we have
1
m
d(c,, U21)
+
2(m 1)
2m +
4(m + 1)"
36

---

C4
10,
C3
21
3133)
11
12.2
31
33
C2
(0, 1,,1,0
61 (1,0,0)
Figure 11: An illustration the constructed instance when m = 2. The candidates are positioned at the corners and centroid of the 3D simplex (i.e., the equilateral triangle embedded in TR$). Candidate C3 is placed at the centroid, representing the candidate with high in-degree in T(fin. C, σ). Each group contains voters: 1 located at the centroid, while 12 placed at the midpoint between c3 and o; for = 1, Different group voters are indicated via distinct colors.
By the definition of the avg-avg objective, conclude that
0+
4m++1)
m
cost (cm+())
77
4 m 1
(m 1)
4(m44)
cost(c;)
(1sis m).
m
Clearly, the optimal candidate is Cm+1- By the definition of (f C, the representative of group i < < m) is o₁. Therefore, the mechanism selects the final winner from among the candidates C1, C2..., Cm A lower bound on the distortion of the mechanism V is obtained as follows S i m):
cost(c:)
(
cost( Cm++1)
m 55m +
2 + m
+
(1 m),
As m - xc, the ratio approaches 2 + v5 R 4.236. Therefore, for any & > 0, we can construct an instance with distortion greater than + V5- - 6.
37


Reviews:
[{"review_id": "vFrN3s9DYo", "reviewer": "Reviewer_LVHh", "summary": "The paper studies metric distortion in distributed voting, where (1) voters are divided into groups, (2) each group selects a local winner, and (3) the group winners then select a final winner. The authors consider four social cost objectives and present improved upper and lower bounds on the distortion of both deterministic and randomized voting rules.", "questions": "The authors are encouraged but not required to answer the questions mentioned in “Strengths & Weaknesses” above.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper studies voting rules quantitatively through the lens of metric distortion, which complements the traditional axiomatic approach. There have been many theoretical advances in this area recently.\n- It is natural to study the distortion of voting rules in the distributed setting, which could be of practical relevance in the long run. The presentation of the paper is clear.\n- The paper presents solid technical results. The authors close the gap in worst-case distortion for the max-avg and max-max social objective for deterministic rules (and reduce the gap for avg-max), establish tight bounds in 6 out of 8 randomized settings they consider (and give nearly tight bounds in the 2 remaining cases).\n\nWeaknesses\n- The paper has a wide range of results but can read like a Cartesian product of different settings: 4 objectives, 3 randomness models (where is det-rand? I am not advocating for adding it), and various metric spaces. This can seem tedious to readers unfamiliar with the area. The paper could be strengthened by emphasizing which results are most novel or challenging to prove, and what ideas the authors propose (e.g., Bias Tournament) that are missing from prior work. How much are the authors' proofs inspired by that in Kizilkaya-Kempe? \n- The authors could consider splitting Table 1 into two tables (one for deterministic and one for randomized) and/or adding the avg-avg row in det-det to provide a complete overview. (Are the upper and lower bounds of the avg-avg deterministic case still $7$ and $11$?). The paper should define $n^*$ in Table 1 (in addition to Theorem 4.4). The phrase \"tight bounds\" in the title may be a bit of an overstatement as some bounds are not tight, perhaps \"tighter bounds\"?\n\nTypos\n- Line 78: $\\alpha$ is not defined yet, and should it be $\\alpha+2$ instead of $5$?\n- Line 330 and 955: \"an unanimous\"\n- Line 347: \"can not\"\n- Line 951: \"these information\"\n- Line 960: \"Observation A.11\" missing brackets in the long equation", "was_revised": true, "final_justification": "Most (if not all) of my comments are constructive suggestions. The authors responded that they would revise the paper accordingly. A few short and clear points that justify my rating were provided under \"Strengths and Weaknesses.\"", "rebuttal": "Thank you for taking the time to review our paper and provide thoughtful comments. Below, we address the technical comments.\n***\n > **The paper has a wide range of results but can read like a Cartesian product of different settings: 4 objectives, 3 randomness models (where is det-rand? I am not advocating for adding it), and various metric spaces. This can seem tedious to readers unfamiliar with the area.** \n\nWe acknowledge that some parts of the paper may feel dense to readers less familiar with the field. Our goal was to provide a comprehensive view of the problem, which, due to space constraints, may have led to a quicker transition into technical material than ideal. In the final version, we will ensure smoother transitions, clearer emphasis on the main ideas, and an overall more accessible presentation.\n\n>**Where is det-rand? I am not advocating for adding it.**\n\n The randomized nature of in-group selection limits the direct applicability of techniques such as the Bias Tournament. Due to time and space constraints, we focused on the det-det, rand-rand, and rand-det models in this work. For det-rand, we currently only have trivial bounds: the lower bound from rand-rand and the upper bound from det-det. Analyzing the det-rand model is indeed a promising direction for future work.\n\n>**The paper could be strengthened by emphasizing which results are most novel or challenging to prove, and what ideas the authors propose (e.g., Bias Tournament) that are missing from prior work.** \n\nThank you for the helpful points. In the final version, we will place more emphasis on which results are the most novel and technically challenging, as well as the new ideas introduced in the paper.\nFor the upper bounds, the mechanisms in the same class are structurally simple but require different and nontrivial analyses for different cost functions. Among these, the upper bounds for the avg-avg objective in the rand-det and rand-rand settings are the most challenging  to obtain.\nFor the lower bounds, we introduce several new ideas that we believe will be useful for future work. One is the Bias Tournament technique, which offers a flexible tool for analyzing distortion. Another is modeling the metric space via shortest paths in a graph. Additionally, our Euclidean lower bounds rely on a new construction that places voters and candidates on a hyper-simplex, which may offer further insight into geometric aspects of distortion.\nWe will make sure to highlight these aspects more clearly in the final version to better convey the novelty and significance of our contributions.\n\n>**How much are the authors' proofs inspired by that in Kizilkaya-Kempe?** \n\nIn most of the deterministic parts of our mechanisms, we can employ either the plurality-veto or plurality-matching rule, which achieves the distortion of 3 in the metric setting. While there may arise similarities with prior work due to the problem's nature, our paper was developed independently of Kizilkaya–Kempe [2,3].\n\n>**The authors could consider splitting Table 1 into two tables (one for deterministic and one for randomized) and/or adding the avg-avg row in det-det to provide a complete overview. (Are the upper and lower bounds of the avg-avg deterministic case still 7 and 11?) The paper should be defined n\\* in Table 1 (in addition to Theorem 4.4).**\n\nDue to page limitations, we consolidated all of our results into a single table. We will do our best to address this concern in the final version. For the avg-avg objective under the det-det model, to the best of our knowledge, the best-known bounds are 7 and 11, as established in [1], and we will include these in the final version of the table to provide a more complete overview. We also apologize for missing the definition of n* in the tables and will address this by clearly defining it.\n\n>**The phrase \"tight bounds\" in the title may be a bit of an overstatement as some bounds are not tight, perhaps \"tighter bounds\"?** \n\nSince the majority of our results—6 out of 8 in the randomized setting (rand-rand and rand-det) and 2 out of 3 in the deterministic case (det-det)—are indeed tight, we felt the current title was justified. However, we are open to revising it to something like “Bounds on the Distortion” to more accurately reflect the scope of the results.\n\n>**Line 78: ɑ is not defined yet, and should it be ɑ+2 instead of 5?** \n\nHere, we mean that “any deterministic in-group rule with distortion at most \\alpha (for \\alpha>= 3), followed by Random Dictatorship, achieves an overall distortion of \\alpha+2. Since the best possible value for α is 3, this yields an upper bound of 5”. In the final version, we'll write this part more carefully.\n\n**Typos:**\nThanks; in the final version, we’ll address the other typos you pointed out.\n\n**References:** \n\n[1]   Anshelevich, Filos-Ratsikas, and Voudouris, “The distortion of distributed metric social choice,” Artificial intelligence, 2022.\n\n[2]   Kizilkaya and Kempe, “Plurality veto: A simple voting rule achieving optimal metric distortion,” IJCAI 2022.\n\n[3]   Kizilkaya and Kempe, “Generalized veto core and a practical voting rule with optimal metric distortion,” EC 2023."}, {"review_id": "foa0e8HKet", "reviewer": "Reviewer_6jcC", "summary": "This paper studies metric distortion in distributed voting systems, where voters are split into groups, each choosing a representative. The final winner is determined from these representatives. It focuses on four common cost objectives: avg-avg, avg-max, max-avg, and max-max, and provides tight upper and lower bounds for distortion with respect to deterministic and randomized mechanisms in general and line metric spaces. Some applications for this problem include certain elections, such as the US presidential election.\n\nThe authors use methods such as bias tournament constructions and shortest path distances in order to derive these bounds. Some of the existing bounds are improved, and most of the developed bounds are tight.", "questions": "1. This is mostly a well-written paper; however, it would be better to explain how distortion can be used in the real world.\n2. Distortion seems to be a worst-case measure of sorts. It might help to include experiments to show how much distortion occurs in practice.", "limitations": "Since this is a theoretical paper, it is not expected to consider the societal impact. However, is there a potential use case where the knowledge of distortion can be used to manipulate elections?", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is well written and includes the necessary details, while leaving the details to the appendix.\n2. The problem in question regarding studying distortion bounds is an important one, and the paper provides tight upper and lower bounds for an extensive number of deterministic and randomized mechanisms.\n3. The methods used, such as bias tournament and shortest path distances, in the proofs are interesting.\n\nWeakness:\n1. There is a lack of empirical results, and real-world applications could be better explained.", "was_revised": true, "final_justification": "I am satisfied with the response and have no further questions.", "rebuttal": "Thank you for taking the time to review our paper and provide helpful suggestions. Below, we address the technical comments.\n\n\n>**Weakness: There is a lack of empirical results, and real-world applications could be better explained.** \n\nWe acknowledge the importance of bridging theory and practice. The current version of the paper includes a wide range of results, and the conference page limit prevented us from including additional material. In the final version, we will clarify connections to real-world applications, such as federated elections (e.g., U.S. Electoral College, Indian Presidential Elections, and European Union Council Voting). \n\n>**Question1: It would be better to explain how distortion can be used in the real world.** \n\nThanks for the suggestion; we will place more emphasis on real-world applications in the final version. Distortion is a well-established efficiency measure, meaningful in any decision-making context with limited information—such as voting and other real-world applications including matching, participatory budgeting, facility location, and so on. \n\n>**Question2: Distortion seems to be a worst-case measure of sorts. It might help to include experiments to show how much distortion occurs in practice.**\n\nYes, distortion is commonly used as a worst-case benchmark, which can be overly pessimistic, as such extremes may not occur in real-world scenarios. It is therefore reasonable to consider less pessimistic settings, such as average-case analyses, which have been explored in prior work [1,2]. Adding an experimental component is a valuable suggestion. While it may be difficult to include in the current version due to space constraints, we will consider it for a more complete version, such as a future journal article. Thank you.\n\n>**Limitation: Since this is a theoretical paper, it is not expected to consider the societal impact. However, is there a potential use case where the knowledge of distortion can be used to manipulate elections?** \n\nIndeed, distortion depends on the voting rule itself, so it is not possible to determine the distortion before the rule is specified. Furthermore, since distortion is defined based on worst-case scenarios, it does not necessarily provide voters with useful information to strategically manipulate the election.\n\n\nReferences: \n\n[1]   Caragiannis, Fehrs. Beyond the worst case: Distortion in impartial culture electorates, 2023.\n\n[2]   Boutilier, Caragiannis, Haber, Lu, Procaccia, and Sheffet. Optimal social choice functions: A utilitarian view, 2012."}, {"review_id": "FuMHkPBsJn", "reviewer": "Reviewer_YmDb", "summary": "The paper studies distributed voting systems, where n voters are partitioned into k groups. Each group selects a local representative, and a final winner is chosen from the set of representatives (or all candidates). The key measure of interest is \"distortion,\" which quantifies how much worse the outcome chosen by a voting rule (using only ordinal preferences) can be compared to the optimal outcome (knowing all voters' actual numerical costs or utilities) in a metric space. Distributed voting was first considered by Anshelevich et al. '22, and since then, only deterministic voting rules have been explored. This paper is the first to explore randomized voting rules in the distributed setup, though it is worth noting that randomized voting mechanisms in the distortion framework (standard non-distributed setting) have already been explored and are known to provide a better distortion bound compared to deterministic ones.\n\nThe current paper mostly focuses on the randomized-deterministic and randomized-randomized mechanisms. For rand-det, the authors provide matching (upper and lower) bounds for all four (avg-avg, avg-max, max-avg, and max-max) cases, while on rand-rand, they provide matching 3-distortion bounds for max-avg and max-max, and near-matching bounds for the other two cases. Further, the authors also manage to strengthen the lower bound of det-det mechanisms in the max-avg case, provide a tight 5-distortion lower bound, and improve the upper bounds of avg-max (10 to 7) and max-max case (5 to 3). In the end, the authors focus on the Euclidean metric and provide a lower bound on distortion for both rand-rand and rand-det mechanisms in the avg-avg case.", "questions": "Nothing specific", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This paper shows a host of new results on distributed voting mechanisms and shows many interesting tight bounds. One can say that a small weakness is that this paper does not introduce any new interesting techniques. Upper bound results, though interesting (some improve the known bounds, such as how to merge distortion bounds of outer and inner mechanisms to get a better final bound), are pretty simple. However, the lower bound constructions are clever, albeit with their simplicity.", "was_revised": true, "final_justification": "I did not have any major concern; on the other hand, I do not find the results or techniques super exciting (rebuttal does not give any additional information), and thus I am keeping the score as it is.", "rebuttal": "Thank you for taking the time to review our paper and provide sincere comments. Below, we address the technical comments.\n\n>**This paper shows a host of new results on distributed voting mechanisms and shows many interesting tight bounds. One can say that a small weakness is that this paper does not introduce any new interesting techniques. Upper bound results, though interesting (some improve the known bounds, such as how to merge distortion bounds of outer and inner mechanisms to get a better final bound), are pretty simple. However, the lower bound constructions are clever, albeit with their simplicity.**\n\nWe agree that most the mechanisms we propose are simple mechanisms; however, analyzing certain settings, such as the average-average objective are very challenging. Additionally, the fact that such simple rules achieve tight distortion bounds is both intriguing and noteworthy. We also believe that the concepts of bias tournament and shortest-path metrics introduce valuable new tools for establishing lower bounds in various scenarios, which could be explored further in future work."}, {"review_id": "ApjGr7lohG", "reviewer": "Reviewer_buyo", "summary": "This paper presents a comprehensive study of metric distortion in distributed voting systems, where voters are grouped, and local winners are selected before a final aggregation. The authors consider both deterministic and randomized voting rules and analyze their performance across four natural cost objectives: avg-avg, avg-max, max-avg, and max-max. Significant theoretical advances are made, including tight or nearly tight bounds for all objectives in both rand-det and rand-rand settings. For example, the paper improves the deterministic upper bound for avg-max from 11 to 7, establishes a tight lower bound of 5 for max-avg, and proves distortion bounds of 3 for several randomized objectives. The analysis introduces novel tools, such as the Bias Tournament, and explores both general metric and Euclidean spaces. The results offer a near-complete characterization of distortion in this setting and highlight the benefits and limitations of randomization in distributed social choice. The paper is well-structured and clearly written, with detailed proofs and illustrative examples that support its contributions, making it a valuable reference for future research in metric voting theory and distributed decision-making.", "questions": "Why didn't you consider the det-rand mechanism?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\nThe paper makes substantial progress in understanding the distortion of distributed voting mechanisms, closing gaps in existing bounds and introducing novel techniques like the Bias Tournament for lower bounds.\n\nWeaknesses:\n1.Authors may refine their descriptions, such as some proof sketches, in order to include a conclusion section.\n2.Authors do not propose new mechanisms.", "was_revised": true, "final_justification": "The paper makes substantial progress in understanding the distortion of distributed voting mechanisms.", "rebuttal": "Thank you for taking the time to review our paper. We noticed that the 'Strengths' section of the review did not align with the content of our submission and might have been included by mistake. Below, we address the technical comments.\n\n>**However, the paper’s technical exposition could be improved. While the core algorithmic ideas and analysis are sound, several important definitions and procedural steps are presented in a terse or abstract way, making the work less accessible to readers unfamiliar with the topic. For example, the intuition behind the penalty functions and dual constructions could be elaborated with more concrete examples or illustrations. Strengthening the clarity and pedagogical structure of the technical sections—particularly the algorithm descriptions and analytical proofs—would make the paper more readable and broaden its impact beyond the expert audience.**\n\nDue to space limitations, some of the definitions and algorithms were presented more tersely than we would have preferred. In the final version, we will do our best to improve the exposition, and ensure the presentation is clearer and easier to follow. We would greatly appreciate any specific feedback on definitions that may require further clarification, so we can enhance them accordingly.\n\n>**Why didn't you consider the det-rand mechanism?** \n\nAnalyzing the det-rand model is indeed a promising direction for future work. The randomized nature of in-group selection limits the direct applicability of techniques such as the Bias Tournament. Due to time and space constraints, we focused on the det-det, rand-rand, and rand-det models in this work. For det-rand, we currently only have trivial bounds: the lower bound from rand-rand and the upper bound from det-det."}]

Author rebuttal:

Meta-review: The paper studies distributed voting systems, where voters are partitioned into groups. A representative is chosen by each group, and the final winner is selected from these representatives (or all candidates). The key measure of interest is "distortion." 

The reviewers were unanimous in praise of the strength of the results and of the writing quality. The proofs of the lower bounds introduce new techniques which may be useful in the future. 

There were a number of minor issues which were pointed out by the reviewers, and we would request the authors to address them in the final draft.
Decision: Accept (poster)