Paper deep dive
Metric Distortion of Social Welfare Functions
Fatih Erdem Kizilkaya, Aaryaman Aggarwal, Evi Micha
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/25/2026, 6:11:15 AM
Summary
This paper extends the metric distortion framework from single-winner social choice functions to social welfare functions that output a complete ranking of candidates. It introduces a model where voters have monotone weight vectors indicating the importance of each ranking position. The study analyzes three information regimes: known weights, identical unknown weights, and normalized heterogeneous weights. Key findings include that recursively applying FractionalVeto achieves an optimal distortion of 3 under known weights, distortion is bounded by 1+(β-1)range(w) under identical weights, and optimal distortion is Θ(m) under normalized heterogeneous weights.
Entities (10)
Relation Signals (9)
Metric Distortion of Social Welfare Functions → hasauthor → Fatih Erdem Kizilkaya
confidence 99% · Title and author list in the paper header.
Metric Distortion of Social Welfare Functions → hasauthor → Aaryaman Aggarwal
confidence 99% · Title and author list in the paper header.
Metric Distortion of Social Welfare Functions → hasauthor → Evi Micha
confidence 99% · Title and author list in the paper header.
FractionalVeto → achievesdistortion → 3
confidence 96% · We show that its recursive extension achieves the optimal distortion of 3.
Metric Distortion of Social Welfare Functions → fundedby → Ministry of National Education of the Republic of Türkiye
confidence 95% · Thanks section: 'This work was supported in part by the Ministry of National Education of the Republic of Türkiye.'
Social Welfare Functions → generalizes → Single-winner voting
confidence 95% · This model generalizes both single-winner voting and committee selection.
Social Welfare Functions → generalizes → Committee selection
confidence 95% · This model generalizes both single-winner voting and committee selection.
FractionalVeto → generalizes → PluralityVeto
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output a ranking of $m$ candidates. We associate each voter $v$ with a monotone weight vector $\mathbf{w}_v = (w_{v1},\ldots,w_{vm})$, specifying the importance of the $i$-th position for voter $v$, and define the cost of a ranking as the position-weighted sum of their distances to the ranked candidates. This model generalizes both single-winner voting and committee selection. We consider three information regimes. First, we study the setting where the positional weight vectors are known. A natural approach recursively applies a single-winner rule with distortion $\beta$ to construct the ranking one position at a time. We show that this yields distortion at most $3\beta$ in general. This gap is not merely an artifact of the analysis: we show that no analysis based solely on per-round guarantees can certify a bound better than $2\beta$. By exploiting structural properties specific to Fractional Veto of Kizilkaya and Kempe, we show that its recursive extension achieves the optimal distortion of 3. Second, when all voters share the same unknown weight vector, recursively applying any social choice function with distortion $\beta$ achieves distortion at most $1+(\beta-1)\text{range}(\mathbf{w})$, where $\text{range}(\mathbf{w})=(w_1-w_m)/w_1$ denotes the normalized range of the common weight vector $\mathbf{w}$. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is $\Theta(m)$.
Tags
Links
- Source: https://arxiv.org/abs/2608.21790v1
- Canonical: https://arxiv.org/abs/2608.21790v1
Trouble viewing inline? Open PDF directly →
Full Text
128,433 characters extracted from source content.
Expand or collapse full text
\__cmd_normalize_type_g:w\__cmd_normalize_type_g:w Metric Distortion of Social Welfare Functions Fatih Erdem Kizilkaya Thanks: Corresponding author (fatih.erdem.kizilkaya@gmail.com). Thanks: This work was supported in part by the Ministry of National Education of the Republic of Türkiye. Aaryaman Aggarwal & Evi Micha Abstract Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output an entire ranking over a set of m candidates. We associate each voter v with a monotone weight vector v=(wv1,…,wvm)w_v=(w_v1,…,w_vm) that specifies the relative importance of the ithi^th position for voter v, and define the cost of a ranking as the position-weighted sum of the voter’s distances to the ranked candidates. This model generalizes both single-winner voting and committee selection while allowing different positions to carry different weights. We consider three information regimes within this model. First, we study the setting in which the positional weight vectors are known to the rule. A natural approach recursively applies a single-winner rule with distortion β to construct the ranking one position at a time. We show that this yields distortion at most 3β3β in general. This gap is not merely an artifact of the analysis: we exhibit instances where making a locally β-approximate choice at every position drives the overall distortion up to 2β2β, showing that no analysis based solely on per-round guarantees can certify a bound better than 2β2β. By exploiting structural properties specific to FractionalVeto of 25, we show that its recursive extension achieves the optimal distortion of 33. Second, when all voters share the same (unknown) weight vector, recursively applying any social choice function with distortion β achieves distortion at most 1+(β−1)range()1+(β-1)range(w), where range()=(w1−wm)/w1range(w)=(w_1-w_m)/w_1 denotes the normalized range of the common weight vector w. Thus, the guarantee interpolates between distortion 11 for uniform weights and β for single-winner weights. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is Θ(m) (m). 1 Introduction Computational social choice (11) studies how to aggregate the preferences of multiple agents into a collective decision. While the classical axiomatic approach compares voting rules through the normative properties they satisfy (7), a complementary quantitative approach assumes that voters have underlying cardinal utilities for the candidates, but that only the ordinal rankings that these utilities induce can be elicited. The distortion of a voting rule measures the worst-case loss in social welfare resulting from this limited information (28). In the most general setting, voters may have arbitrary underlying utilities consistent with their ordinal rankings. Without further assumptions on these utilities, obtaining meaningful approximation guarantees is not possible, motivating the study of more structured preference models. One such approach is the normalized distortion framework, which assumes arbitrary nonnegative cardinal utilities, normalized so that each voter’s utilities sum to one (10; 14; 17; 15). A more structured model that has received significant attention in recent years is the metric distortion framework (4). In this model, voters and candidates are embedded in a latent metric space, and each voter ranks the candidates according to their distance from them. This notion has led to a rich line of work on the distortion of voting rules (5; 6; 23; 24). The case of single-winner voting is now well understood: deterministic social choice functions achieving the optimal distortion of 33 have been developed (19; 25; 26). More recently, this line of research has been extended to multiwinner elections, leading to a growing understanding of the metric distortion of committee-selection rules under a variety of voter cost functions (20; 13; 22; 12). Many applications, however, require not a single winner or an unordered committee, but a complete ranking of the candidates. Recommendation systems aggregate rankings induced by different criteria, hiring committees rank candidates so that additional offers can be made if earlier candidates decline, funding agencies prioritize proposals for sequential funding, and universities maintain ranked waitlists for admissions. In these settings, different positions of the ranking may carry different importance. For example, users of a product ranking typically care only about the top few positions (21). The metric distortion of social welfare functions, rules that return a complete ranking rather than a single winner, has, to the best of our knowledge, not been studied before. Addressing this question first requires specifying how voters evaluate an entire ranking. In particular, different positions of the ranking may carry different importance, which may vary across voters. For example, in a recommendation system, some users may be willing to browse several recommendations before finding a suitable item, whereas others may rely almost exclusively on the first recommendation. We capture this by associating each voter v with a monotone, non-increasing weight vector wv1≥⋯≥wvm≥0w_v1≥·s≥ w_vm≥ 0, where wviw_vi specifies the importance of position i to voter v. The cost of a ranking is then the sum, over all voters v and positions i, of v’s distance to the candidate in position i, weighted by wviw_vi. This position-weighted model was introduced by 8 in the utilitarian distortion framework and subsumes both single-winner elections, in which every voter values only the top-ranked candidate, and committee selection, in which every voter assigns equal value to the first k positions and zero value to the remaining positions. In this paper, we study the metric distortion of ordinal social welfare functions under this general model. Contributions. Without any assumptions on the weights, or without revealing them to the social welfare function, bounded metric distortion is impossible. This motivates the study of three natural information regimes, distinguished by what is known or assumed about the positional weights. Our results are summarized in Table 1. 1) Known Weights. First, we consider the setting in which the positional weight vectors are given as input to the social welfare function. In this case, a natural approach is to construct the ranking recursively, filling the positions one by one by repeatedly applying a single-winner rule to the remaining candidates. However, the distortion guarantee of the underlying single-winner rule does not automatically carry over to its recursive extension. In particular, the best generic guarantee that we obtain for recursively applying an arbitrary distortion-β rule is a distortion of 3β3β, while we exhibit instances in which a local distortion of β at every recursive step results in an overall distortion of 2β2β. Surprisingly, our main result shows that this apparent loss is not inherent. We prove that recursively applying FractionalVeto, a generalization of the optimal deterministic single-winner rule PluralityVeto (26), yields a social welfare function with the optimal distortion of 33 for every monotone weight profile. Thus, constructing an entire ranking incurs no additional distortion over the classical single-winner setting. Our proof exploits structural properties specific to FractionalVeto, beyond its single-winner distortion guarantee. We also study Weighted Recursive Copeland. Although Copeland achieves distortion 55 in the single-winner setting, here we obtain a bound of 77, leaving open whether the optimal bound of 55 can be achieved. 2) Identical Weights. Second, we study the identical weights setting, in which the positional weights are unknown but all voters share the same weight vector. We show that recursively applying any single-winner rule with distortion β achieves distortion at most 1+(β−1)range()1+(β-1)range(w), where range()=(w1−wm)/w1range(w)=(w_1-w_m)/w_1 denotes the normalized range of the common weight vector w. Thus, the distortion interpolates continuously between 11, when all positions are valued equally, and β, when only the first position matters. This strictly generalizes previous recursive guarantees for committee selection and is nearly matched by our lower-bound construction. 3) Normalized Weights. Finally, we consider the normalized weights setting, in which voters may have different weight vectors but these vectors satisfy a natural normalization. We study two such normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. We show that, under both models, the optimal distortion is Θ(m) (m): Recursive PluralityVeto achieves a linear upper bound, and we establish matching asymptotic lower bounds. Weight Regime Recursive rule Distortion Known Weighted f ≤3β≤ 3β Known FractionalVeto 33 (optimal) Known Weighted Copeland 5≤Dist.≤75 .≤ 7 Identical f ≤1+(β−1)range()≤ 1+(β-1)range(w) Normalized (unit-sum) PluralityVeto Θ(m) (m): [m2, 8m+3] [ m2,\,8m+3 ] Normalized (unit-top) PluralityVeto Θ(m) (m): [m4, 4m+1] [ m4,\,4m+1 ] Table 1: The summary of our results. Here, β denotes the distortion of the underlying social choice function f, and range()=(w1−wm)/w1range(w)=(w_1-w_m)/w_1 is the normalized range of the common weight vector w. Related Work. Distortion has been studied extensively under both utility-based and metric preference models, as well as under richer (18; 27; 24) or more limited preference information (9; 16; 2), and in other settings such as matching (3; 1). A work particularly relevant to ours is that of 25, who introduced FractionalVeto, a fractional generalization of PluralityVeto. Since this rule plays a central role in our algorithms and analysis, we review it in detail in the Preliminaries. Our work is also closely related to the metric committee-selection setting of 20. Their objective corresponds to the special case of our identical-weights model in which every voter assigns equal value to the first k positions and zero value thereafter. They show that recursively applying any single-winner rule with distortion β preserves distortion β in this setting. Our result strictly generalizes theirs to arbitrary monotone shared weight vectors. Another conceptually relevant work is that of 8, who introduced the position-weighted objective for extending distortion from social choice to social welfare functions in the utilitarian setting. They show that randomized social welfare functions can asymptotically match the distortion of the corresponding social choice problem, even when the positional weights are unknown. We study the same objective in the metric distortion framework, obtaining a fundamentally different picture: knowledge of the positional weights becomes crucial for achieving bounded distortion. 2 Preliminaries We write vectors and matrices with bold letters. We denote the ithi^th entry of a vector x by xix_i, and we extend this notation to sets via addition, i.e., xT=∑i∈Txix_T= _i∈ Tx_i. Given a matrix M, we denote the ithi^th row vector by iM_i, the jthj^th column vector by jM T_j, and the entry in the ithi^th row and jthj^th column by MijM_ij. Given a set X, let ΔX _X denote the set of non-negative weight vectors over X that add to 1. A ranking σ=(σ1,…,σk)σ=( _1,…, _k) of a set X is a permutation of its elements where σi _i occupies position i, and XS_X denotes the set of all such rankings. Elections. An election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ) consists of a set of n voters V, a set of m candidates C and the rankings # �≻=(≻v)v∈V # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ =( _v)_v∈ V where ≻v∈C _v _C expresses the ordinal preferences of voter v over candidates. We write a≻vba _vb to express that voter v prefers candidate a to candidate b; we write a≽vba _vb if a=ba=b or a≻vba _vb, and say that v weakly prefers a to b. We write top(v)top(v) for the candidate ranked highest by voter v. The plurality score of a candidate c, denoted by plu(c)plu(c), is the number of voters v such that top(v)=ctop(v)=c. A social choice function f maps each election ℰE to a winning candidate f(ℰ)∈Cf(E)∈ C. A social welfare function F maps each election ℰE to a consensus ranking F(ℰ)∈CF(E) _C. Given a social choice function f, Recursive f is the social welfare function that constructs a ranking σ=(c1,…,cm)σ=(c_1,…,c_m) successively, from left to right, as follows: At position j, let Aj:=C∖c1,…,cj−1A_j:=C \c_1,…,c_j-1\ denote the remaining candidates, and, with a slight abuse of notation, let topj(v)top_j(v) denote the candidate ranked highest in AjA_j by voter v. The rule applies f to the election restricted to AjA_j, places the resulting winner cjc_j in position j, and continues. We use this notation for every recursive construction below. Metric Distortion. A metric over a set X is a function d:X×X→ℝ≥0d:X× X _≥ 0 with the following three properties for all x,y,z∈Xx,y,z∈ X: (1) Identity: d(x,y)=0d(x,y)=0 if and only if x=yx=y,11 1 We allow voters and candidates to be co-located, so that their distance may be zero, i.e., we technically consider a pseudometric. (2) Symmetry: d(x,y)=d(y,x)d(x,y)=d(y,x), (3) Triangle Inequality: d(x,y)+d(y,z)≥d(x,z)d(x,y)+d(y,z)≥ d(x,z). The key assumption in the notion of metric distortion is that preferences are induced by some metric d over V∪CV∪ C, not available to the social choice (or welfare) function. Given an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), we say that a metric d is consistent with # � 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu ≻ , and write d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , if d(v,c)≤d(v,c′)d(v,c)≤ d(v,c ) for all v∈Vv∈ V and c,c′∈Cc,c ∈ C such that c≽vc′c _vc . The social cost of candidate c∈Cc∈ C under metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ is SC(c|d):=∑v∈Vd(v,c)SC(c\,|\,d):= _v∈ Vd(v,c). Let cd∗∈argminc∈CSC(c|d)c^*_d∈ _c∈ CSC(c\,|\,d) denote an optimal candidate under d. Definition 1. The distortion of candidate c∈Cc∈ C in election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), denoted by Distℰ(c)Dist_E(c), is the largest possible ratio between the cost of c and that of an optimal candidate over all metrics: Distℰ(c):=supd∼# �≻SC(c|d)SC(cd∗|d).Dist_E(c):= _d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ SC(c\,|\,d)SC(c_d^*\,|\,d). The distortion of social choice function f is its worst-case distortion over all elections: Dist(f):=supℰDistℰ(f(ℰ))Dist(f):= _EDist_E (f(E) ). Our Model. To extend metric distortion to social welfare functions, we associate each voter v with a monotonically decreasing, non-negative weight vector v∈ℝmw_v∈ ^m, where wviw_vi specifies the relative importance of the ithi^th position for voter v in the consensus ranking. A weight profile bundles the voters’ weight vectors into an n×mn× m matrix =(v)v∈Vw=(w_v)_v∈ V. Let n×m:=∈ℝ≥0n×m∣wv1≥⋯≥wvm for all vW^n× m:=\w _≥ 0^n× m w_v1≥·s≥ w_vm for all v\ denote the domain of all such weight profiles. We then define the social cost of ranking σ∈Cσ _C under metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ and weight profile ∈n×mw ^n× m as SC(σ|d,):=∑v∈V∑j=1mwvjd(v,σj).SC (σ\,|\,d,w ):= _v∈ V _j=1^mw_vjd(v, _j). We drop d and w from the notation whenever they are clear from context, and write SC(σ)SC(σ) for SC(σ|d,)SC(σ\,|\,d,w). With a slight abuse of notation, we write SCj(c):=SC(c|d,j)=∑v∈Vwvjd(v,c)SC_j(c):=SC(c\,|\,d,w T_j)= _v∈ Vw_vjd(v,c) to denote the marginal social cost of assigning candidate c to position j. Note that the social cost of a ranking σ∈Cσ _C decomposes as SC(σ)=∑j=1mSCj(σj).SC(σ)= _j=1^mSC_j( _j). Also, let σd,∗∈argminσ∈CSC(σ|d,)σ^*_d,w∈ _σ _CSC(σ\,|\,d,w) denote an optimal ranking under d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ and ∈n×mw ^n× m. Definition 2. The distortion of ranking σ∈Cσ _C in election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), denoted by Distℰ(σ)Dist_E(σ), is the largest possible ratio between the cost of σ and that of an optimal ranking over all consistent metrics and weight profiles: Distℰ(σ):=supd∼# �≻∈n×mSC(σ|d,)SC(σd,∗|d,).Dist_E(σ):= _ subarraycd # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ \\ 8.19447pt\>\>\>w ^n× m subarray\; SC(σ\,|\,d,w)SC(σ^*_d,w\,|\,d,w). The distortion of social welfare function F is its worst-case distortion over all elections: Dist(F):=supℰDistℰ(F(ℰ))Dist(F):= _EDist_E (F(E) ). Without further assumptions on the weight profile, every social welfare function F that does not observe the weight profile has unbounded distortion. Consider an election with two candidates a,ba,b and two voters 1,21,2 embedded on the real line. Candidate a is co-located with voter 1 at position 0, while candidate b is co-located with voter 2 at position 1. The induced preferences are therefore a≻1ba _1b and b≻2ab _2a. By symmetry, suppose that F returns σ=(a,b)σ=(a,b). Under the weight profile with 1=(1,0)w_1=(1,0) and 2=(x,0)w_2=(x,0), the cost of σ is x, whereas the optimal ranking (b,a)(b,a) has cost 1. Hence, the distortion equals x and is unbounded as x→∞x→∞. Information Regimes. Obtaining bounded distortion requires either giving the weight profile to the social welfare function or restricting the admissible weight profiles. Thus, we consider three regimes below: 1) Known Weights. The weight profile w is given to the social welfare function F, whose output may thus depend on both inputs, and is denoted by F(ℰ,)F(E,w). Then, its distortion is defined accordingly as Dist(F):=supℰ,∈n×mDistℰ,(F(ℰ,))Dist(F):= _E,w ^n× mDist_E,w (F(E,w) ) where Distℰ,(σ):=supd∼# �≻SC(σ|d,)SC(σd,∗|d,).Dist_E,w(σ):= _d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ SC(σ\,|\,d,w)SC(σ^*_d,w\,|\,d,w). 2) Identical Weights. The weight profile is not given but all voters share the same weight vector. For this regime, let idn×m:=∈n×m∣u=v for all u,vW^n× m_id:=\w ^n× m w_u=w_v for all u,v\ denote the domain of admissible weight profiles, and define distortion as Distid(F):=supℰ,∈idn×mDistℰ,(F(ℰ))Dist_id(F):= _E,w ^n× m_idDist_E,w (F(E) ). 3) Normalized Weights. The weight profile is not given but weight vectors are normalized. We consider two types of normalizations: unit-sum and unit-top, for which the domain of admissible weight profiles and distortion, is defined as follows, respectively: – Let sumn×m:=∈n×m∣v∈Δm for all vW^n× m_sum:=\w ^n× m _v∈ _m for all v\ and Distsum(F):=supℰ,∈sumn×mDistℰ,(F(ℰ))Dist_sum(F):= _E,w ^n× m_sumDist_E,w (F(E) ) – Let topn×m:=∈n×m∣wv1=1 for all vW^n× m_top:=\w ^n× m w_v1=1 for all v\ and Disttop(F):=supℰ,∈topn×mDistℰ,(F(ℰ))Dist_top(F):= _E,w ^n× m_topDist_E,w (F(E) ). Lastly, we review concepts from the single-winner setting that will be useful also in our rank aggregation setting. Single-Winner Review. Given an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), the domination graph of a candidate a is the bipartite graph Ga=(V,C,Ea)G_a=(V,C,E_a) in which (v,c)∈Ea(v,c)∈ E_a if and only if a≽vca _vc. Given normalized weight vectors ∈ΔVp∈ _V and ∈ΔCq∈ _C, a non-negative matrix ∈ℝ≥0V×CM∈ _≥ 0^V× C is a (,)(p,q)-matching if ∑c∈CMvc=pv _c∈ CM_vc=p_v for all voters v∈Vv∈ V and ∑v∈VMvc=qc _v∈ VM_vc=q_c for all candidates c∈Cc∈ C We say that candidate a admits the (,)(p,q)-matching M if Mvc>0M_vc>0 only if (v,c)∈Ea(v,c)∈ E_a. Lemma 3 (25, Theorem 2). Given an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ) along with ∈ΔVp∈ _V and ∈ΔCq∈ _C, FractionalVeto of 25 returns a candidate admitting a (,)(p,q)-matching. FractionalVeto initializes the residual vote of each voter v to pvp_v and the residual score of each candidate c to qcq_c. While some voter has positive residual vote, it chooses any such voter, finds that voter’s least-preferred candidate among those with positive residual score, and decreases both residuals by their minimum. It returns the last candidate whose residual score reaches zero. A (uni,plu)(p^uni,q^plu)-matching is called a plurality matching, where pvuni=1/np_v^uni=1/n for all v∈Vv∈ V, and qcplu=plu(c)/nq_c^plu=plu(c)/n for all c∈Cc∈ C. Equivalently, candidate a admits a plurality matching if there is a bijection M:V→VM:V→ V such that a≽vtop(M(v))a _vtop(M(v)) for every v∈Vv∈ V. With these weights, FractionalVeto specializes to PluralityVeto, and achieves distortion 3, the lowest possible distortion that any social choice function can have (4). 3 Known Weights In this section, we consider the first information regime, where the weight profile w is given as input to the social welfare function. At position j, the entries of jw T_j can be therefore viewed as voter masses in a weighted single-winner election over the remaining candidates. This suggests constructing the ranking by recursively applying a weighted extension of a social choice function. The difficulty lies in composing these single-winner calls. If σ∗=(c1∗,…,cm∗)σ^*=(c_1^*,…,c_m^*) is a globally optimal ranking, then cj∗c_j^* may already have been selected when position j is reached. Thus, a guarantee relative to the best available candidate is only local and need not be preserved by recursion. We first study this problem in a black-box manner. If f has distortion at most β, we consider its natural clone-weighted recursive extension and show that it achieves distortion at most 3β3β. We also show the limitation of using only the per-round guarantee: choosing a β-approximate candidate at every position can produce a ranking whose cost is 2β2β times optimal. This naturally raises the question whether producing an entire ranking requires distortion higher than 33 which is the optimal single-winner bound.22 2 This bound remains a lower bound in our setting, since setting v=(1,0,…,0)w_v=(1,0,…,0) for every voter v reduces the objective to the single-winner problem. It does not: exploiting the matching certificates underlying FractionalVeto, we show that Recursive FractionalVeto achieves the optimal distortion of 33. Moreover, by operating directly on normalized masses, the rule runs in polynomial time, whereas the black-box extension may require exponential time because its explicit clone population can be exponential in the bit length of the weights. Finally, we study the analogous question for Copeland. While its single-winner distortion is 55, Weighted Recursive Copeland requires a substantially different analysis, for which we obtain a distortion bound of 7. However, whether a bound of 55 is actually achievable, remains an open question. 3.1 General Weighted Recursion We first formalize the clone-weighted extension of a social choice function. For a rational voter-mass vector ∈ΔVp∈ _V, let f(ℰ)f_p(E) be the outcome of f after replacing every voter v by LpvLp_v identical copies, where L is the smallest positive integer for which all multiplicities are integral. Given a known weight profile w, Weighted Recursive f constructs a ranking σf=(c1,…,cm) _f=(c_1,…,c_m) from left to right. At position j, let Wj:=∑v∈VwvjW_j:= _v∈ Vw_vj. If Wj>0W_j>0, define pv(j):=wvjWjfor all v∈V.p_v^(j):= w_vjW_j all v∈ V. The rule then applies f(j)f_p^(j) to the election restricted to AjA_j, places the resulting winner cjc_j in position j, and continues with the remaining candidates. If Wj=0W_j=0, monotonicity implies that all remaining positions have zero weight, so the remaining candidates are appended arbitrarily. We use this same convention for every recursive rule in this section. For the remainder of this section, fix an arbitrary election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), a metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , and a monotone weight profile ∈n×mw ^n× m. The following rule-independent lemma will be used throughout this section. Lemma 4. For every ranking σ∗=(c1∗,…,cm∗)∈Cσ^*=(c_1^*,…,c_m^*) _C, ∑j=1m∑v∈Vwvjd(v,topj(v))≤SC(σ∗) _j=1^m _v∈ Vw_vjd(v,top_j(v)) (σ^*) Proof. Fix a voter v, and let dv(1)≤⋯≤dv(m)d_v^(1)≤·s≤ d_v^(m) denote the distances from v to the candidates in increasing order. Before position j, only j−1j-1 candidates have been removed, so at least one of the j closest candidates to v is available. Therefore, d(v,topj(v))≤dv(j)d(v,top_j(v))≤ d_v^(j). Moreover, since c1∗,…,ck∗c_1^*,…,c_k^* are distinct candidates, for every k∈1,…,mk∈\1,…,m\, ∑i=1kd(v,topi(v))≤∑i=1kdv(i)≤∑i=1kd(v,ci∗). _i=1^kd(v,top_i(v))≤ _i=1^kd_v^(i)≤ _i=1^kd(v,c_i^*). Set wvm+1:=0w_vm+1:=0 and define δvℓ:=wvℓ−wvℓ+1≥0 _v :=w_v -w_v +1≥ 0. Using the above bound and summation by parts, we obtain ∑j=1mwvjd(v,topj(v)) _j=1^mw_vjd(v,top_j(v)) =∑ℓ=1mδvℓ∑j=1ℓd(v,topj(v)) = _ =1^m _v _j=1 d(v,top_j(v)) ≤∑ℓ=1mδvℓ∑j=1ℓd(v,cj∗) ≤ _ =1^m _v _j=1 d(v,c_j^*) =∑j=1mwvjd(v,cj∗). = _j=1^mw_vjd(v,c_j^*). Summing this inequality over all voters and exchanging the order of summation completes the proof. ∎ Theorem 5. If social choice function f has distortion at most β, then Weighted Recursive f has distortion at most 3β3β. Proof. Let σf=(c1,…,cm) _f=(c_1,…,c_m) be the ranking returned by Weighted Recursive f, and let σ∗=(c1∗,…,cm∗)σ^*=(c_1^*,…,c_m^*) be an optimal ranking under d and w. When Wj>0W_j>0, the cloned election has candidate costs proportional to SCj(⋅)SC_j(·). Therefore, the distortion guarantee of f gives SCj(cj)≤βminc∈AjSCj(c).SC_j(c_j)≤β _c∈ A_jSC_j(c). (1) Since topj(u)∈Ajtop_j(u)∈ A_j for every voter u, minc∈AjSCj(c)≤1Wj∑u∈VwujSCj(topj(u)). _c∈ A_jSC_j(c)≤ 1W_j _u∈ Vw_ujSC_j(top_j(u)). (2) For u,v∈Vu,v∈ V, the triangle inequality gives d(u,topj(v))≤d(u,cj∗)+d(cj∗,v)+d(v,topj(v)).d(u,top_j(v))≤ d(u,c_j^*)+d(c_j^*,v)+d(v,top_j(v)). Thus, fixing v, multiplying by wujw_uj, and summing over all voters u∈Vu∈ V, we obtain SCj(topj(v))≤SCj(cj∗)+Wjd(cj∗,v)+Wjd(v,topj(v)).SC_j(top_j(v)) _j(c_j^*)+W_jd(c_j^*,v)+W_jd(v,top_j(v)). Averaging this inequality over v yields 1Wj∑v∈VwvjSCj(topj(v)) 1W_j _v∈ Vw_vjSC_j(top_j(v)) ≤2SCj(cj∗) ≤ 2SC_j(c_j^*) +∑v∈Vwvjd(v,topj(v)). + _v∈ Vw_vjd(v,top_j(v)). (3) Consequently, SCj(cj) _j(c_j) ≤βminc∈AjSCj(c) ≤β _c∈ A_jSC_j(c) (by Eq. 1) ≤βWj∑v∈VwvjSCj(topj(v)) ≤ βW_j _v∈ Vw_vjSC_j(top_j(v)) (by Eq. 2) ≤2βSCj(cj∗) ≤ 2β\,SC_j(c_j^*) +β∑v∈Vwvjd(v,topj(v)). +β _v∈ Vw_vjd(v,top_j(v)). (by Eq. 3) When Wj=0W_j=0, the weight column jw T_j is identically zero, so both sides vanish and the same inequality holds trivially. Summing over all positions, and then applying Lemma 4, we obtain SC(σf) ( _f) ≤2βSC(σ∗)+β∑j=1m∑v∈Vwvjd(v,topj(v)) ≤ 2 (σ^*)+β _j=1^m _v∈ Vw_vjd(v,top_j(v)) ≤3βSC(σ∗), ≤ 3 (σ^*), which completes the proof. ∎ Call a recursive construction locally β-approximate if SCj(cj)≤βminc∈AjSCj(c)SC_j(c_j)≤β _c∈ A_jSC_j(c) at every position with Wj>0W_j>0. Proposition 6. For every β≥1β≥ 1, locally β-approximate recursion can incur a cost ratio of 2β2β. Proof. Consider two voters u,vu,v and three candidates a,b,ca,b,c on the real line, placed at u=a=0u=a=0, v=b=1v=b=1, and c=β+1c=β+1. Thus, u ranks a≻b≻ca b c, while v ranks b≻a≻cb a c. Give the voters monotone weight vectors u=(β,0,0)andv=(1,1,0).w_u=(β,0,0) _v=(1,1,0). At the first position, SC1(a)=1SC_1(a)=1 and SC1(b)=βSC_1(b)=β, so selecting b is locally β-approximate. Once b is removed, SC2(a)=1SC_2(a)=1 and SC2(c)=βSC_2(c)=β, so selecting c is locally β-approximate. The resulting ranking (b,c,a)(b,c,a) has cost 2β2β, whereas (a,b,c)(a,b,c) is optimal with cost 11. ∎ Proposition 6 does not imply that Weighted Recursive f has distortion at least 2β2β for every function f of distortion β: in the construction above, f may select a rather than b and still have distortion β. Rather, it shows that the per-round cost comparison alone cannot yield a guarantee below 2β2β. This means that any upper bound better than 2β2β requires additional structural properties of the underlying rule. The clone construction is likewise conceptual rather than computationally efficient. After clearing denominators, a voter of integer weight K is represented by K clones. Since K requires only O(logK)O( K) bits to encode, explicitly constructing the cloned election can take time exponential in the input size. For PluralityVeto, we avoid this blowup using the direct fractional extension FractionalVeto, which results in a social welfare function with polynomial running time and optimal distortion 33. 3.2 Recursive FractionalVeto For every position j with Wj>0W_j>0, we define pv(j) p_v^(j) :=wvjWjfor all v∈V := w_vjW_j all v∈ V qc(j) q_c^(j) :=∑v∈V:topj(v)=cpv(j)for all c∈Aj. := _ subarraycv∈ V:\\ top_j(v)=c subarrayp_v^(j) all c∈ A_j. Instead of cloning the voters, we run FractionalVeto with normalized weights (j)∈ΔVp^(j)∈ _V and (j)∈ΔAjq^(j)∈ _A_j on the election restricted to AjA_j, place the winning candidate cjc_j in position j, and continue with remaining candidates. This implements Weighted Recursive PluralityVeto without cloning the voters and thus runs in polynomial time. We now analyze the rule. Fix an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), a metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , and a monotone weight profile ∈n×mw ^n× m, and let σ=(c1,…,cm)σ=(c_1,…,c_m) be the returned ranking. The first lemma uses the (,)(p,q)-matching guarantee of FractionalVeto to compare the selected candidate with any metric point, by which we mean a point that can be adjoined to the metric space (V∪Aj,d)(V∪ A_j,d) without violating the triangle inequality. In particular, this includes candidates removed in earlier iterations. Lemma 7. For every position j and every metric point x, SCj(cj) _j(c_j) ≤2SCj(x)+∑v∈Vwvjd(v,topj(v)). ≤ 2\,SC_j(x)+ _v∈ Vw_vjd(v,top_j(v)). Proof. The claim is immediate when Wj=0W_j=0, so suppose that Wj>0W_j>0. By Lemma 3, the candidate placed at position j admits a ((j),(j))(p^(j),q^(j))-matching. Scaling this matching by WjW_j gives a matrix M satisfying ∑c∈AjMvc _c∈ A_jM_vc =wvj =w_vj for every v∈V, every v∈ V, ∑v∈VMvc _v∈ VM_vc =∑v∈V:topj(v)=cwvj = _ subarraycv∈ V:\\ top_j(v)=c subarrayw_vj for every c∈Aj. every c∈ A_j. As cjc_j admits M, the condition Mvc>0M_vc>0 implies cj≽vcc_j _vc, and therefore d(v,cj)≤d(v,c)d(v,c_j)≤ d(v,c). Hence, using the row and column sums of M, and the triangle inequality twice, we obtain SCj(cj) _j(c_j) =∑v∈Vwvjd(v,cj) = _v∈ Vw_vj\,d(v,c_j) =∑v∈V∑c∈AjMvcd(v,cj) = _v∈ V _c∈ A_jM_vc\,d(v,c_j) ≤∑v∈V∑c∈AjMvcd(v,c) ≤ _v∈ V _c∈ A_jM_vc\,d(v,c) ≤SCj(x)+∑v∈V∑c∈AjMvcd(x,c) _j(x)+ _v∈ V _c∈ A_jM_vc\,d(x,c) =SCj(x)+∑v∈Vwvjd(x,topj(v)) =SC_j(x)+ _v∈ Vw_vjd(x,top_j(v)) ≤2SCj(x)+∑v∈Vwvjd(v,topj(v)). ≤ 2\,SC_j(x)+ _v∈ Vw_vjd(v,top_j(v)). Since x is an arbitrary metric point, this completes the proof. ∎ Theorem 8. For every monotone weight profile, Recursive FractionalVeto has distortion at most 33. This bound is optimal among weight-aware social welfare functions. Proof. Suppose that σ∗=(c1∗,…,cm∗)∈Cσ^*=(c_1^*,…,c_m^*) _C is an optimal ranking under d and w. For every position j, candidate cj∗c_j^* is a metric point, even if it is no longer available when cjc_j is selected. We may therefore apply Lemma 7 with x=cj∗x=c_j^*. Summing the resulting inequalities over all positions and applying Lemma 4, we obtain SC(σ) (σ) =∑j=1mSCj(cj) = _j=1^mSC_j(c_j) ≤2SC(σ∗)+∑j=1m∑v∈Vwvjd(v,topj(v)) ≤ 2\,SC(σ^*)+ _j=1^m _v∈ Vw_vjd(v,top_j(v)) ≤3SC(σ∗). ≤ 3\,SC(σ^*). Since the election, metric, and weight profile fixed above were arbitrary, this completes the proof. Tightness follows by setting v=(1,0,…,0)w_v=(1,0,…,0) for each voter v∈Vv∈ V, which reduces the objective to the single-winner case. ∎ 3.3 Weighted Recursive Copeland Copeland selects a candidate of maximum out-degree in the majority tournament, the directed graph whose vertices are the candidates with an edge from candidate a to candidate b whenever a strict majority of voters prefer a to b. For every position j with Wj>0W_j>0, Weighted Recursive Copeland constructs the weighted majority tournament Tj=(Aj,Ej)T_j=(A_j,E_j) as follows. For each pair of distinct candidates a,b∈Aja,b∈ A_j, orient the edge from a to b whenever ∑v:a≻vbwvj>Wj2. _v:a _vbw_vj> W_j2. The masses on the two sides sum to WjW_j. Thus, exactly one orientation satisfies the strict inequality unless both masses equal Wj/2W_j/2, in which case we orient the edge arbitrarily. Consequently, TjT_j is a tournament. Weighted Recursive Copeland places a candidate cjc_j of maximum out-degree in TjT_j in position j and continues. Fix an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), a metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , and a monotone weight profile ∈n×mw ^n× m, and let σ=(c1,…,cm)σ=(c_1,…,c_m) be the returned ranking. We first bound the increase in social cost along a single edge of a weighted majority tournament. As in Lemma 7, the reference point need not correspond to an available candidate, or even to a candidate at all. Lemma 9. For every position j with Wj>0W_j>0, every edge (a,b)∈Ej(a,b)∈ E_j, and every metric point x, SCj(a)≤SCj(b)+2SCj(x).SC_j(a) _j(b)+2\,SC_j(x). Proof. Let δ(v):=d(v,a)−d(v,b)δ(v):=d(v,a)-d(v,b), and partition the voters into V+:=v∈V∣δ(v)>0V^+:=\v∈ V δ(v)>0\ and V−:=V∖V+V^-:=V V^+. Every voter in V+V^+ ranks b above a, while every voter who ranks a above b belongs to V−V^-. Set s:=∑v∈V+wvjs:= _v∈ V^+w_vj and t:=∑v∈V−wvj.t:= _v∈ V^-w_vj. Since (a,b)∈Ej(a,b)∈ E_j, the total mass of voters ranking a above b is at least the total mass of those ranking b above a, and thus, s≤ts≤ t. If s=0s=0, then ∑v∈Vwvjδ(v)≤0 _v∈ Vw_vjδ(v)≤ 0, and the claim follows. Hence, suppose that s>0s>0, which also implies that t>0t>0. For every v∈V+v∈ V^+ and u∈V−u∈ V^-, we have δ(v) δ(v) ≤δ(v)−δ(u) ≤δ(v)-δ(u) =(d(v,a)−d(u,a))+(d(u,b)−d(v,b)) = (d(v,a)-d(u,a) )+ (d(u,b)-d(v,b) ) ≤2d(v,u) ≤ 2d(v,u) ≤2d(v,x)+2d(u,x). ≤ 2d(v,x)+2d(u,x). Averaging this inequality over u∈V−u∈ V^- with weights wuj/tw_uj/t, multiplying by wvjw_vj, and summing over v∈V+v∈ V^+ gives SCj(a)−SCj(b) _j(a)-SC_j(b) =∑v∈Vwvjδ(v) = _v∈ Vw_vjδ(v) ≤∑v∈V+wvjδ(v) ≤ _v∈ V^+w_vjδ(v) ≤2∑v∈V+wvjd(v,x) ≤ 2 _v∈ V^+w_vjd(v,x) +2st∑u∈V−wujd(u,x) +2 st _u∈ V^-w_ujd(u,x) ≤2SCj(x), ≤ 2\,SC_j(x), where the last inequality follows from s≤ts≤ t. ∎ A candidate belongs to the uncovered set if, for every other candidate b, it either defeats b directly or defeats some candidate that defeats b. It is well known that every Copeland winner belongs to the uncovered set (see, for example, (4)). Combining this property with Lemma 9 gives the following corollary. Corollary 10. For every position j with Wj>0W_j>0, every candidate b∈Ajb∈ A_j, and every metric point x, SCj(cj)≤SCj(b)+4SCj(x).SC_j(c_j) _j(b)+4\,SC_j(x). Taking x=bx=b in Corollary 10 recovers the usual factor-55 comparison for a single Copeland winner. At position j of the recursive rule, however, the candidate occupying that position in an optimal ranking may no longer be available. We therefore use it as the metric point x and average the available comparison candidate b over voters’ top choices. Theorem 11. For every monotone weight profile, Weighted Recursive Copeland has distortion at most 77. Proof. Let σ∗=(c1∗,…,cm∗)∈Cσ^*=(c_1^*,…,c_m^*) _C be an optimal ranking under d and w. Fix a position j with Wj>0W_j>0 and a voter u∈Vu∈ V. Since topj(u)∈Ajtop_j(u)∈ A_j, we may apply Corollary 10 with b=topj(u)b=top_j(u) and x=cj∗x=c_j^*. Notice that cj∗c_j^* is a valid metric point even if it was removed in an earlier iteration. Thus, SCj(cj)≤4SCj(cj∗)+SCj(topj(u)).SC_j(c_j)≤ 4\,SC_j(c_j^*)+SC_j(top_j(u)). Averaging this inequality over voters u with probabilities wuj/Wjw_uj/W_j, and writing Bj:=1Wj∑u∈VwujSCj(topj(u)),B_j:= 1W_j _u∈ Vw_ujSC_j(top_j(u)), gives SCj(cj)≤4SCj(cj∗)+Bj.SC_j(c_j)≤ 4\,SC_j(c_j^*)+B_j. (∗*) For every pair of voters u,v∈Vu,v∈ V, the triangle inequality gives d(v,topj(u))≤d(v,cj∗)+d(u,cj∗)+d(u,topj(u)).d(v,top_j(u))≤ d(v,c_j^*)+d(u,c_j^*)+d(u,top_j(u)). Consequently, Bj B_j =1Wj∑u,v∈Vwujwvjd(v,topj(u)) = 1W_j _u,v∈ Vw_ujw_vjd(v,top_j(u)) ≤2SCj(cj∗)+∑u∈Vwujd(u,topj(u)). ≤ 2\,SC_j(c_j^*)+ _u∈ Vw_ujd(u,top_j(u)). Here, the first two terms produced by the triangle inequality each equal SCj(cj∗)SC_j(c_j^*), while the third gives the final sum. Substituting this bound into Eq. ∗ , we obtain SCj(cj) _j(c_j) ≤6SCj(cj∗)+∑v∈Vwvjd(v,topj(v)). ≤ 6\,SC_j(c_j^*)+ _v∈ Vw_vjd(v,top_j(v)). The same inequality is immediate when Wj=0W_j=0. Since Lemma 4 is independent of the rule used to select the candidates, summing over all positions yields SC(σ) (σ) ≤6SC(σ∗)+∑j=1m∑v∈Vwvjd(v,topj(v)) ≤ 6\,SC(σ^*)+ _j=1^m _v∈ Vw_vjd(v,top_j(v)) ≤7SC(σ∗). ≤ 7\,SC(σ^*). Since the election, metric, and weight profile fixed above were arbitrary, this completes the proof. ∎ When v=(1,0,…,0)w_v=(1,0,…,0) for every voter v∈Vv∈ V, only the first position contributes to the objective and Weighted Recursive Copeland reduces to ordinary Copeland. The single-winner lower bound of 55 (4) therefore continues to apply. Thus, we currently only know that the distortion of Weighted Recursive Copeland lies between 55 and 77. 4 Identical Weights We now consider the second information regime, in which the weight profile is unknown, but all voters share the same monotone weight vector. Despite not observing this vector, we show that the optimal distortion of 33 can still be achieved. While the previous section required properties specific to FractionalVeto and Copeland, here the distortion guarantee of every social choice function will transfer to its recursive extension. This regime subsumes both single-winner voting and committee selection. The shared vector =(1,0,…,0)w=(1,0,…,0) recovers the single-winner objective, whereas (k):=(1,…,1⏟k entries,0,…,0)w^(k):=( 1,…,1_k entries,0,…,0) recovers the sum-of-costs objective for a committee of size k. 20 show that recursively applying a social choice function preserves its distortion for these cutoff vectors. Our result generalizes theirs to every monotone shared weight vector and gives a sharper guarantee as its range decreases. Write v==(w1,…,wm)w_v=w=(w_1,…,w_m) for every v∈Vv∈ V, where w1≥⋯≥wm≥0w_1≥·s≥ w_m≥ 0 and w1>0w_1>0. Let range():=1−wm/w1∈[0,1]range(w):=1-w_m/w_1∈[0,1] denote the normalized range of w, which is invariant under scaling. Theorem 12. If f has distortion at most β≥1β≥ 1, then under every shared weight vector w, Recursive f has distortion at most 1+(β−1)⋅range()1+(β-1)·range(w). Proof. Fix an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), a metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , and a shared weight vector ∈idn×mw ^n× m_id. Let σ=(c1,…,cm)σ=(c_1,…,c_m) be the ranking returned by Recursive f. Index the candidates so that SC(c1∗)≤⋯≤SC(cm∗).SC(c_1^*)≤·s (c_m^*). Since w1≥⋯≥wmw_1≥·s≥ w_m, the ranking σ∗:=(c1∗,…,cm∗)σ^*:=(c_1^*,…,c_m^*) is optimal under w. When position j is filled, at least one of c1∗,…,cj∗c_1^*,…,c_j^* remains available. Hence, the guarantee of f on the restricted election gives SC(cj)≤βminc∈AjSC(c)≤βSC(cj∗).SC(c_j)≤β _c∈ A_jSC(c)≤β\,SC(c_j^*). Define X X :=∑c∈CSC(c), := _c∈ CSC(c), Y Y :=∑j=1m(wj−wm)SC(cj∗). := _j=1^m (w_j-w_m )SC(c_j^*). For every position j, write wj=wm+(wj−wm)w_j=w_m+(w_j-w_m). The first term assigns the same weight wmw_m to every position. Since every ranking contains each candidate exactly once, ∑j=1mwmSC(σj)=wm∑c∈CSC(c)=wmX. _j=1^mw_mSC( _j)=w_m _c∈ CSC(c)=w_mX. Therefore, SC(σ) (σ) ≤wmX+βY, ≤ w_mX+β Y, SC(σ∗) (σ^*) =wmX+Y. =w_mX+Y. Moreover, monotonicity gives 0≤wj−wm≤w1−wm0≤ w_j-w_m≤ w_1-w_m for every position j. Since σ∗σ^* is a complete ranking, c1∗,…,cm∗c_1^*,…,c_m^* contain every candidate exactly once. Therefore, we obtain 0≤Y 0≤ Y =∑j=1m(wj−wm)SC(cj∗) = _j=1^m (w_j-w_m )SC(c_j^*) ≤(w1−wm)∑j=1mSC(cj∗) ≤ (w_1-w_m ) _j=1^mSC(c_j^*) =(w1−wm)∑c∈CSC(c) = (w_1-w_m ) _c∈ CSC(c) =(w1−wm)X=w1range()X. = (w_1-w_m )X=w_1range(w)X. If the optimal cost is zero, then wmX+Y=0w_mX+Y=0, and the preceding bound SC(σ)≤wmX+βYSC(σ)≤ w_mX+β Y shows that the cost of σ is also zero. Otherwise, wmX+Y>0w_mX+Y>0. Since the function x↦x/(wmX+x)x x/(w_mX+x) is nondecreasing for x≥0x≥ 0, the bound on Y gives YwmX+Y Yw_mX+Y ≤(w1−wm)XwmX+(w1−wm)X ≤ (w_1-w_m)Xw_mX+(w_1-w_m)X =w1−wmw1=range(). = w_1-w_mw_1=range(w). Consequently, Distid(Recursive f) _id(Recursive f) =SC(σ)SC(σ∗) = SC(σ)SC(σ^*) ≤wmX+βYwmX+Y ≤ w_mX+β Yw_mX+Y =1+(β−1)YwmX+Y =1+(β-1) Yw_mX+Y ≤1+(β−1)range(), ≤ 1+(β-1)range(w), which completes the proof. ∎ The single-winner vector witnesses the hardest case: its normalized range is 11, and Recursive f has the same distortion as f. As the vector becomes flatter, the guarantee improves, reaching 11 for a uniform vector. We next give a range-dependent lower bound that applies to every social welfare function. Theorem 13. For every social welfare function F and every r∈[0,1]r∈[0,1], there exists an election ℰE and an identical weight profile ∈idn×mw ^n× m_id with range()=rrange(w)=r, under which the distortion is at least Distℰ,(F(ℰ))≥4−r4−3r=1+2r4−3rDist_E,w(F(E))≥ 4-r4-3r=1+ 2r4-3r. Proof. Consider two voters u,vu,v and two candidates a,ba,b, with a≻uba _ub and b≻vab _va, and take the shared vector =(1,1−r)w=(1,1-r). Suppose that F returns (a,b)(a,b); the other case is symmetric. Place a at 00, voter u at 11, and voter v and candidate b at 22 on the real line. This metric is consistent and gives SC(a|d)=3SC(a\,|\,d)=3 and SC(b|d)=1SC(b\,|\,d)=1. Hence, the returned ranking costs 4−r4-r, whereas the optimal ranking (b,a)(b,a) costs 4−3r4-3r. Their ratio is (4−r)/(4−3r)(4-r)/(4-3r), as claimed. ∎ The lower bound applies to every social welfare function, whereas Theorem 12 with β=3β=3 gives the upper bound 1+2r1+2r for Recursive PluralityVeto. The two bounds coincide at 11 when r=0r=0 and at 33 when r=1r=1; and for intermediate ranges, their additive gap is (1+2r)−4−r4−3r=6r(1−r)4−3r≤23, (1+2r )- 4-r4-3r= 6r(1-r)4-3r≤ 23, with equality at r=2/3r=2/3. Thus, the upper bound is exact at both extremes and is no more than 2/32/3 above the universal lower bound in Theorem 13. Corollary 14. Recursive PluralityVeto has optimal distortion 33 under identical weight profiles. More precisely, for every election ℰE and identical weight profile ∈idn×mw ^n× m_id, F=F= Recursive PluralityVeto has distortion at most Distℰ,(F(ℰ))≤1+2range()Dist_E,w (F(E) )≤ 1+2range(w). 5 Normalized Weights We now consider the third information regime, in which the weight profile remains hidden and may vary across voters, but every voter’s weight vector is normalized. We consider the unit-sum and unit-top domains defined in the preliminaries. In contrast to identical weights, hidden heterogeneity makes constant distortion impossible under either normalization. Theorem 15. Distsum(F)≥m2Dist_sum(F)≥ m2 and Disttop(F)≥m4Dist_top(F)≥ m4 for every social welfare function F. Proof. Let h:=m/2h:=m/2, and partition the candidates into sets X and Y of size h. Consider two voters u and v, where u ranks every candidate in X above every candidate in Y, while v has the reverse preference. Place u and all candidates in X at one point, and v and all candidates in Y at another point at distance 11. This metric is consistent with the rankings. Let σ:=F(ℰ)σ:=F(E). We first consider unit-sum weights. Suppose that σ1∈Y _1∈ Y. Give u the top-only vector and give v weight 1/h1/h on each of the first h positions and 0 thereafter. The cost of σ is at least 11, whereas a ranking that places one candidate from X first and h−1h-1 candidates from Y next has cost 1/h1/h. Thus, the distortion is at least h=m/2h=m/2. If σ1∈X _1∈ X, the same argument holds after exchanging u and v. For unit-top weights, consider the first h positions of σ. Suppose that at least h/2h/2 of these positions contain candidates from Y. Give u weight 11 on the first h positions and zero thereafter, and give v the top-only vector. The returned ranking costs at least h/2h/2, whereas a ranking that places all candidates in X first costs 11. The ratio is therefore at least h/2=m/4h/2=m/4. If fewer than h/2h/2 candidates are from Y, the symmetric argument applies with the roles of X and Y exchanged. ∎ We now turn to upper bounds, and show that Recursive PluralityVeto achieves distortion O(m)O(m) under both normalizations. Theorem 16. Recursive PluralityVeto has distortion at most 8m+38m+3 under unit-sum weight profiles and at most 4m+14m+1 under unit-top weight profiles. Proof. We first consider the unit-sum domain. Fix an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), a metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , and a profile ∈sumn×mw ^n× m_sum. Let σ be the ranking returned by Recursive PluralityVeto, let σ∗=(c1∗,…,cm∗)σ^*=(c_1^*,…,c_m^*) be an optimal ranking. Define w¯j:=1n∑v∈Vwvj w_j:= 1n _v∈ Vw_vj and SC¯(π):=∑j=1mw¯jSC(πj) SC(π):= _j=1^m w_jSC( _j), and let Π:=1n∑u,v∈Vd(u,v) := 1n _u,v∈ Vd(u,v). For every ranking π∈Cπ _C, the triangle inequality gives, for every pair of voters u,v∈Vu,v∈ V and every position j, d(v,πj)≤d(v,u)+d(u,πj).d(v, _j)≤ d(v,u)+d(u, _j). Since this inequality holds for every u, averaging over all u∈Vu∈ V yields d(v,πj)≤1n∑u∈Vd(v,u)+1n∑u∈Vd(u,πj).d(v, _j)≤ 1n _u∈ Vd(v,u)+ 1n _u∈ Vd(u, _j). Multiplying both sides by wvjw_vj and summing over all voters v and positions j, we obtain SC(π) (π) =∑j=1m∑v∈Vwvjd(v,πj) = _j=1^m _v∈ Vw_vjd(v, _j) ≤1n∑j=1m∑u,v∈Vwvjd(v,u)+1n∑j=1m∑u,v∈Vwvjd(u,πj). ≤ 1n _j=1^m _u,v∈ Vw_vjd(v,u)+ 1n _j=1^m _u,v∈ Vw_vjd(u, _j). For the first term, exchanging the order of summation and using the unit-sum normalization, ∑j=1mwvj=1for every v∈V, _j=1^mw_vj=1 every v∈ V, gives 1n∑u,v∈Vd(u,v)∑j=1mwvj=1n∑u,v∈Vd(u,v)=Π. 1n _u,v∈ Vd(u,v) _j=1^mw_vj= 1n _u,v∈ Vd(u,v)= . For the second term, exchanging the order of summation gives 1n∑j=1m∑u,v∈Vwvjd(u,πj) 1n _j=1^m _u,v∈ Vw_vjd(u, _j) =∑j=1m(1n∑v∈Vwvj)∑u∈Vd(u,πj) = _j=1^m ( 1n _v∈ Vw_vj ) _u∈ Vd(u, _j) =∑j=1mw¯j∑u∈Vd(u,πj)=SC¯(π). = _j=1^m w_j _u∈ Vd(u, _j)= SC(π). Therefore, SC(π)≤Π+SC¯(π).SC(π)≤ + SC(π). Averaging the reverse inequality d(u,πj)≤d(u,v)+d(v,πj)d(u, _j)≤ d(u,v)+d(v, _j) similarly gives SC¯(π)≤SC(π)+Π SC(π) (π)+ . Due to monotonicity and unit-sum normalization, we have wv1≥1/mw_v1≥ 1/m. Consequently, SC(σ∗)≥1mSC(c1∗)SC(σ^*)≥ 1mSC(c_1^*). The triangle inequality therefore gives Π ≤1n∑u,v∈V(d(u,c1∗)+d(v,c1∗)) ≤ 1n _u,v∈ V (d(u,c_1^*)+d(v,c_1^*) ) =2SC(c1∗) =2SC(c_1^*) ≤2mSC(σ∗). ≤ 2mSC(σ^*). Since the average vector (w¯1,…,w¯m)( w_1,…, w_m) is also monotone, Theorem 12 gives SC¯(σ)≤3minπ∈CSC¯(π) SC(σ)≤ 3 _π _C SC(π). Thus, SC(σ)≤3SC¯(σ∗)+Π≤3SC(σ∗)+4Π≤(8m+3)SC(σ∗).SC(σ)≤ 3 SC(σ^*)+ ≤ 3SC(σ^*)+4 ≤(8m+3)SC(σ^*). We next consider the unit-top domain. Fix an election ℰ=(V,C,# �≻)E=(V,C, # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ ), a metric d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , and a profile ∈topn×mw ^n× m_top. Let σ=(c1,…,cm)σ=(c_1,…,c_m) be the returned ranking and let σ∗=(c1∗,…,cm∗)σ^*=(c_1^*,…,c_m^*) be an optimal ranking. By definition, there exists a bijection Mj:V→VM_j:V→ V, for every position j, such that cj≽vtopj(Mj(v))c_j _vtop_j(M_j(v)) for all v∈Vv∈ V. Fix v∈Vv∈ V and set u:=Mj−1(v)u:=M_j^-1(v). Since d∼# �≻d # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ # -0.7pt $ 2.0mu $ $ $ $ $ $ $ $ -1.5mu $ 0.0mu $ $ $ $ $ $ $ $ 0.0mu$ -1.5mu $ -0.3pt $ $ , we obtain d(v,cj) d(v,c_j) ≤d(v,u)+d(u,cj) ≤ d(v,u)+d(u,c_j) ≤d(v,u)+d(u,topj(v)) ≤ d(v,u)+d(u,top_j(v)) ≤2d(v,u)+d(v,topj(v)). ≤ 2d(v,u)+d(v,top_j(v)). Let D:=∑j=1m∑v∈Vwvjd(v,Mj−1(v))D:= _j=1^m _v∈ Vw_vjd (v,M_j^-1(v) ). Multiplying the above inequality by wvjw_vj and summing over all voters and positions, we obtain SC(σ) (σ) ≤2D+∑j=1m∑v∈Vwvjd(v,topj(v)) ≤ 2D+ _j=1^m _v∈ Vw_vjd(v,top_j(v)) ≤2D+SC(σ∗), ≤ 2D+SC(σ^*), where the second inequality follows from Lemma 4. It remains to bound D. Unit-top normalization implies wvj≤1w_vj≤ 1 and ∑jwvj≤m _jw_vj≤ m. Therefore, D D ≤∑v∈V(∑j=1mwvj)d(v,c1∗) ≤ _v∈ V ( _j=1^mw_vj )d(v,c_1^*) +∑j=1m∑v∈Vwvjd(c1∗,Mj−1(v)) + _j=1^m _v∈ Vw_vjd (c_1^*,M_j^-1(v) ) ≤mSC(c1∗)+∑j=1m∑v∈Vd(c1∗,Mj−1(v)) ≤ mSC(c_1^*)+ _j=1^m _v∈ Vd (c_1^*,M_j^-1(v) ) =2mSC(c1∗), =2mSC(c_1^*), where the last equality follows because Mj−1M_j^-1 is a permutation of V for every j. Finally, since wv1=1w_v1=1 for every voter v, we have SC(σ∗)≥SC(c1∗).SC(σ^*) (c_1^*). Hence, D≤2mSC(σ∗)D≤ 2mSC(σ^*), and consequently SC(σ)≤(4m+1)SC(σ∗),SC(σ)≤(4m+1)SC(σ^*), completing the proof. ∎ Together with Theorem 15, these bounds determine the optimal distortion up to constant factors: it is Θ(m) (m) under either normalization. 6 Conclusion We initiated the study of metric distortion for social welfare functions, extending the metric distortion framework from selecting a single winner to constructing complete rankings under position-weighted objectives. Our results show that the amount of information available about the positional weights fundamentally determines the achievable distortion: knowing the weights allows optimal constant distortion, identical hidden weights still admit strong guarantees, while heterogeneous hidden weights inevitably lead to linear distortion, even under natural normalizations. These results leave several interesting directions for future work. In particular, can the distortion of Recursive Copeland be improved from the current upper bound of 77 to the conjectured bound of 55? More generally, it would be interesting to understand which single-winner distortion guarantees extend to recursive ranking rules, and to study metric distortion for social welfare functions under richer preference models, such as limited cardinal information or randomized social welfare functions. Acknowledgments This work was supported in part by the Ministry of National Education of the Republic of Türkiye. OpenAI’s GPT-5.5 and GPT-5.6 Sol were used to assist in developing some of the results presented in this paper. The authors reviewed and verified the resulting arguments and proofs and take full responsibility for the paper’s content. References Amanatidis et al. (2022) G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris A few queries go a long way: information-distortion tradeoffs in matching. Journal of Artificial Intelligence Research 74, p. 227–261. Cited by: §1. Anagnostides et al. (2026) I. Anagnostides, D. Fotakis, and P. Patsilinakos Sampling and optimal preference elicitation in simple mechanisms. Theory of Computing Systems 70 (2), p. 17. Cited by: §1. Anari et al. (2023) N. Anari, M. Charikar, and P. Ramakrishnan Distortion in metric matching with ordinal preferences. In Proceedings of the 24th ACM Conference on Economics and Computation, p. 90–110. Cited by: §1. Anshelevich et al. (2018) E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron Approximating optimal social choice under metric preferences. Artificial Intelligence 264, p. 27–51. Cited by: §1, §2, §3.3, §3.3. Anshelevich et al. (2015) E. Anshelevich, O. Bhardwaj, and J. Postl Approximating optimal social choice under metric preferences. In aaai15, p. 777–783. Cited by: §1. Anshelevich and Postl (2016) E. Anshelevich and J. Postl Randomized social choice functions under metric preferences. In ijcai16, p. 46–59. Cited by: §1. Arrow (1990) K. Arrow Advances in the spatial theory of voting. Cambridge University Press. Cited by: §1. Benade et al. (2019) G. Benade, A. D. Procaccia, and M. Qiao Low-distortion social welfare functions. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, p. 1788–1795. Cited by: §1, §1. Borodin et al. (2022) A. Borodin, D. Halpern, M. Latifian, and N. Shah Distortion in voting with top-t preferences.. In IJCAI, p. 116–122. Cited by: §1. Boutilier et al. (2015) C. Boutilier, I. Caragiannis, S. Haber, T. Lu, A. D. Procaccia, and O. Sheffet Optimal social choice functions: a utilitarian view. Artificial Intelligence 227, p. 190–213. Cited by: §1. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.) (2016) F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.) Handbook of computational social choice. cambridge. Cited by: §1. Burkhardt et al. (2024) J. Burkhardt, I. Caragiannis, K. Fehrs, M. Russo, C. Schwiegelshohn, and S. Shyam Low-distortion clustering with ordinal and limited cardinal information. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, Vol. 38, p. 9555–9563. Cited by: §1. Caragiannis et al. (2022) I. Caragiannis, N. Shah, and A. A. Voudouris The metric distortion of multiwinner voting. Artificial Intelligence 313, p. 103802. Cited by: §1. Caragiannis and Procaccia (2011) I. Caragiannis and A. D. Procaccia Voting almost maximizes social welfare despite limited communication. Artificial Intelligence 175 (9), p. 1655–1671. Cited by: §1. Couvreur and Bressler (2000) C. Couvreur and Y. Bressler On the optimality of the backward greedy algorithm for the subset selection problem. SIAM Journal on Matrix Analysis and Applications 21 (3), p. 797–808. Cited by: §1. Ebadian et al. (2024) S. Ebadian, D. Halpern, and E. Micha Metric distortion with elicited pairwise comparisons.. In IJCAI, p. 2791–2798. Cited by: §1. Ebadian et al. (2022) S. Ebadian, A. Kahng, D. Peters, and N. Shah Optimized distortion and proportional fairness in voting. In ecom22, p. 563–600. Cited by: §1. Ebadian and Shah (2025) S. Ebadian and N. Shah Every bit helps: achieving the optimal distortion with a few queries. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 13788–13795. Cited by: §1. Gkatzelis et al. (2020) V. Gkatzelis, D. Halpern, and N. Shah Resolving the optimal metric distortion conjecture. In focs20, p. 1427–1438. Cited by: §1. Goel et al. (2018) A. Goel, R. Hulett, and A. K. Krishnaswamy Relating metric distortion and fairness of social choice rules. In Proceedings of the 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon), Note: arXiv:1810.01092 Cited by: §1, §1, §4. Joachims et al. (2017) T. Joachims, A. Swaminathan, and T. Schnabel Unbiased learning-to-rank with biased feedback. In Proceedings of the tenth ACM international conference on web search and data mining, p. 781–789. Cited by: §1. Kalayci et al. (2024) Y. H. Kalayci, D. Kempe, and V. Kher Proportional representation in metric spaces and low-distortion committee selection. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, p. 9815–9823. Cited by: §1. Kempe (2020a) D. Kempe An analysis framework for metric voting based on LP duality. In aaai20, p. 2079–2086. Cited by: §1. Kempe (2020b) D. Kempe Communication, distortion, and randomness in metric voting. In aaai20, p. 2087–2094. Cited by: §1, §1. Kizilkaya and Kempe (2022) F. E. Kizilkaya and D. Kempe PluralityVeto: a simple voting rule with optimal metric distortion. In ijcai22, p. 349–355. Cited by: §1, §1, Lemma 3, Lemma 3, Abstract. Kizilkaya and Kempe (2023) F. E. Kizilkaya and D. Kempe Generalized veto core and a practical voting rule with optimal metric distortion. In ecom23, p. 913–936. Cited by: §1, §1. Mandal et al. (2019) D. Mandal, A. D. Procaccia, N. Shah, and D. Woodruff Efficient and thrifty voting by any means necessary. Advances in Neural Information Processing Systems 32. Cited by: §1. Procaccia and Rosenschein (2006) A. D. Procaccia and J. S. Rosenschein The distortion of cardinal preferences in voting. In Proc. 10th Intl. Workshop on Cooperative Inform. Agents X, p. 317–331. Cited by: §1.