{'fraction_non_alphanumeric': 0.04492878722485973, 'fraction_numerical': 0.008113940440224428, 'mean_word_length': 4.283434044008665, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation

We present a unifying framework encompassing many social choice settings. Viewing each social choice setting as voting in a suitable metric space, we consider a general model of social choice over metric spaces, in which---similarly to the spatial model of elections---each voter specifies an ideal element of the metric space. The ideal element functions as a vote, where each voter prefers elements that are closer to her ideal element. But it also functions as a proposal, thus making all participants equal not only as voters but also as proposers. We consider Condorcet aggregation and a continuum of solution concepts, ranging from minimizing the sum of distances to minimizing the maximum distance. We study applications of the abstract model to various social choice settings, including single-winner elections, committee elections, participatory budgeting, and participatory legislation. For each setting, we compare each solution concept to known voting rules and study various properties of the resulting voting rules. Our framework provides expressive aggregation for a broad range of social choice settings while remaining simple for voters, and may enable a unified and integrated implementation for all these settings, as well as unified extensions such as sybil-resiliency, proxy voting, and deliberative decision making.


Introduction
A thriving e-democracy [59] will have to address the choice of officers, committees, parameters (e.g., interest rate), budgets, and legislation. Today, social choice theory addresses each of these settings separately, offering different elicitation and aggregation methods for each, thus making the practical realization of an e-democracy untenable. In addition, current theory focuses on the act of voting, practically ignoring the need for an egalitarian process for determining which alternatives to vote upon. Here, we present a unifying framework for all these social choice settings with a uniform elicitation and aggregation method, which is egalitarian in that voters cast both proposals and votes.
Indeed, different models of social choice are concerned with aggregation of different objects. For example, the most basic social choice setting is singlewinner elections (see, e.g., [5,55,24]), in which voter preferences over a given set of alternatives are aggregated to decide upon a single winning alternative. More complex social choice settings include multiwinner elections [31], in which voter preferences are aggregated to select a winning committee, and participatory budgeting (see, e.g., [39,8,32]), in which voter preferences are aggregated to select a bundle of items respecting a given budget limit. Further social choice settings include graph aggregation [26] and aggregation of combinatorial domains [21].
Usually, mathematical foundations and theories in the social choice literature are tailored for a specific setting. Here, however, motivated by the application of a holistic e-democracy, we study a general framework of social choice that can be applied to many settings at once. Observing the plethora of social choice settings, one merit of our approach is that it incorporates many such settings uniformly, which allows an investigation of complex settings and may enable a unified and integrated implementation to many settings at once.
Another motivation for this work comes from Reality-Aware Social Choice [58], which requires the status quo (Reality) to always be present as a distinguished alternative when electing among several alternatives. According to Reality-Aware Social Choice, if the majority perceives the status quo as negative and prefers a particular alternative to the status quo, then that alternative will be chosen. If the majority prefers the status quo over every proposed alternative, then it will be chosen. But if the majority prefers other alternatives to the status quo, but no specific alternative among those proposed has majority support, then the status quo reigns. This situation is clearly distressing, as the will of the people to change the status quo cannot be accommodated, perhaps due to the incompetence or interests of those who select the alternatives to vote upon, or the lack of an adequate mechanism to identify alternatives that may have majority support over the status quo. This paper proposes a model that may identify such alternatives.
A key merit of our approach is being egalitarian, in the sense that participants are not just equal as voters on proposals predetermined by others, but are also equal as proposers. This is manifest especially in our approach to budgeting and legislation, where the domains of budgets and laws are open-ended and potentially infinite. This is in contrast to the classical social choice setting, in which an external authority is assumed to fix a finite number of alternatives prior to the vote. Thus, our model may enable a deliberative process in which participants transition between making proposals, negotiating changes to competing proposals to achieve common ground, building coalitions in support of a particular proposal, and supporting proposals different from their original ones as a result of negotiation, deliberation, and coalition building. The result could be a deliberative framework in which participants are equal as proposers, deliberators, coalition builders, and voters.
Furthermore, by letting voters only specify their ideal points, and relying on the metric space to infer more complex preferences, our model can incorpo-rate very complex aggregation scenarios (such as participatory legislation) while remaining relatively simple for voters (wrt. the general trade-off between expressiveness and cost). On the other hand, this simplicity means that certain voter preferences cannot be expressed, such as a dependency among budget items or the inconsistency of an intermediate point between two legislative texts; we elaborate on this point in Section 9 and discuss possible remedies. Finally, we find efficient aggregation algorithms to many of the scenarios we consider. Coping with the NP-hardness of the remaining scenarios is left for future study.
Our model, described in Section 2, consists of elements connected via a metric. The elements of the metric space may serve in three roles: proposals, votes, and outcomes of the vote aggregation process. We associate each voter with a single element of the space, referred to as the voter ideal element, understood as her most-preferred element of the space. Then, we assume that each voter prefers closer elements to elements which are farther away from her ideal element. Given a metric space, we are interested in aggregating several voter ideal elements in it into an aggregated element, which is the election winner (we discuss other options in Section 9). We study several solution concepts: Condorcet aggregation, in which a Condorcet-winning aggregated element is selected (if it exists); and a continuum of solution concepts, containing on one end minimizing the sum of distances to the ideal elements and, at the other end, minimizing the maximum distance to the ideal elements.
We study applications of this model to various settings of social choice. For each setting we identify a metric space suitable for the application, and investigate each solution concept by comparing it to known aggregation methods and studying its axiomatic properties. While our model can be applied to many social choice settings, here we concentrate on the following, prominent ones: 1. Plurality elections (Section 3); 2. Social welfare functions (Section 6); 3. Single-winner elections over a 1-dimensional Euclidean issue space (Section 4); 4. Committee elections (Section 7); 5. Continuous participatory budgeting (Section 5); and 6. 2 Participatory legislation (Section 8), in which the task is to aggregate text drafts. The study of further settings is left to future work. A key initial motivation for our work was participatory legislation, which is perhaps the most complex setting we study here. To the best of our knowledge, here we propose the first aggregation method for this important social choice setting.

Related Work
The spatial model of elections [27] considers voter ideal elements and infers voter preferences using an underlying Euclidean metric. This model was later extended to Hilbert spaces [38], normed spaces [49], and semi-inner product spaces [37]. Here, we consider general metric spaces, including discrete and not limited to complete and well-structured ones. This approach allows us to apply this model to a broad range of social choice settings, including elections, budgeting, committee elections and legislation.
Metric preferences are quite prominent in the social choice literature. Much of this research is similar to ours in considering ideal elements of voters and alternatives. Contrary to our model, however, extant literature is usually concerned with aggregating derived rankings rather than with directly aggregating the ideal elements themselves. Specifically, the notion of distortion [52] is prominent (e.g., [40,60,3]). Here, in contrast, we aim to aggregate the ideal elements and argue this to be a productive approach. Indeed, the idea of using distances in social choice is prominent; e.g., distance-based completion principles used in combinatorial voting [42] which relate to set extensions [9] and are used in committee elections. We do not aim to reinvent the wheel in the applications we consider, but rather to propose a unified model and incorporate many social choice settings at once; thus, we discuss such relations in the respective sections.
We do mention the general concept of distance rationalizability (DR) [25], in which voting rules are defined via consensus classes and distances. Here, we do not consider consensus classes per se, but aggregation methods of ideal elements. Specifically, DR is concerned with summing voter distances to reach consensus in the ordinal model of single-winner elections. This relates to our social choice maximization (specifically, the unanimous consensus [25]). But, notions such as Condorcet aggregation do not easily fit to DR and, furthermore, our focus is on a general metric-based model as it applies to a variety of social choice settings.
Finally, we mention the work of Feldman et al. [34]; specifically, their location model is very similar to our metric-based model, but their study is focused on other aspects, such as on randomized mechanisms. We also mention the work of Fain et al. [29] and Garg et al. [36], which also consider aggregation in continuous metric spaces. Additional works that tackle facility location mostly focus on strategic voting over simple metric spaces as the line or the circle [53,44,4].

Metric Spaces
Our model consists of a metric space (X, d), where X is a set of elements and d : X × X → R is a metric function. Namely, d is: (1) symmetric, with d(x, y) = d(y, x) for every pair x, y ∈ X, (2) non-negative, with d(x, y) ≥ 0 and d(x, y) = 0 if and only if x = y, and (3) satisfies the triangle inequality d(x, z) ≤ d(x, y) + d(y, z) holds for all x, y, z ∈ X.

Voters, Ideal Elements, and Inferred Weak Orders
We assume n voters, where voter i corresponds to an element v i ∈ X. We refer to v i as the ideal element of voter i, interpreted as her most-preferred element of the metric space. Based on the ideal element v i , and the metric itself, we infer a ranking over the whole metric space, where, for each two elements x, y ∈ X, voter i prefers x to y (i.e., ranks x higher than y) if and only if d(v i , x) < d(v i , y). A voter is indifferent to elements x and y for which d(v i , x) = d(v i , y). Slightly overloading the notation, we use v i to denote both the ideal element and this inferred weak ranking of voter i (the two cases will always be clear from the context).

Aggregation Methods
An aggregation method is a function R : X n → X that, given a metric space (X, d) and n ideal points V = {v 1 , . . . , v n } of the voters, returns an aggregated point, denoted by R(V ), which is the winner according to R of the election corresponding to V over the metric space (X, d). 4 Condorcet Aggregation. We adapt the Condorcet principle to our model. Definition 1 (Condorcet winner). Let (X, d) be a metric space and consider n voters with their ideal elements and corresponding weak rankings over X, denoted by V = {v 1 , . . . , v n }. An element x ∈ X is a Condorcet winner wrt. V if for any other element y ∈ X, it holds that |{v i ∈ V : x i y}| > |{v i ∈ V : y i x}|.
That is, a Condorcet-winning element is such that, if chosen, then there is no voter majority for changing it. For simplicity, we shall use the notation for every y ∈ X. An aggregation method R is Condorcet-consistent if it elects a Condorcet winner whenever such exists; that is, R(V ) = c where c is a Condorcet winner. 5 L p Aggregation. Besides Condorcet aggregation, we consider L p aggregation, a continuum of solution concepts, parameterized by a parameter 1 ≤ p ≤ ∞. Specifically, for a given p, we look for an element which minimizes the sum of p-factored distances to the voter ideal elements.
Similarly, we define The L p aggregation method returns these elements x as the co-winners.
Note that L p (V ) is not necessarily unique, thus we treat this term as a subset of X. (Furthermore, L p (V ) might be empty.) To tackle the issue of uniqueness, we sometimes consider reduced L p aggregation: 4 Indeed, due to ties, there might be co-winners. We usually do not consider these, but assume a standard arbitrary tie-breaking mechanism. 5 Weak Condorcet winners are defined similarly, by replacing > with ≥ in the definition above. As the distinction between Strong/Weak Condorcet winners is in essence an issue of tie breaking, we will not focus on it.
which satisfies L p (V ) ⊆ L p (V ) due to the continuity of These notions would mainly be applied to resolve uniqueness issues for p = 1, ∞.
L p norm estimators have been widely studied in the statistical literature [62], and are usually applied when estimating the parameters in linear regression models. The choice of the parameter p in this context critically depends on the underlying distribution, and reflects a tradeoff between the number of samples needed (the efficiency of the estimator) and its sensitivity to departures from normality in the residual distribution (the estimator's robustness) [47].
To better understand the notion of L p estimation, observe that L 1 (V ) minimizes the sum of absolute errors, L 2 (V ) minimizes the mean squared error, and L ∞ (V ) minimizes the maximal distance from all the ideal points. 7 L p norms have been also studied within the social choice literature (e.g., [30]). Intuitively, in the context of vote aggregation, the choice of the parameter p reflects the relative influence of an individual in a joint decision making. For example, applying L ∞ as a voting rule, intuitively, protects minority rights, in the sense that it does not disregard outliers (in this context we mention the work of Aziz et al. [7] which use the maximum operator to achieve the same protection for minorities). Further intuition regarding the role of the parameter p in the aggregation appears in Section 4.

Axiomatic Properties
In subsequent sections we consider applications of our general model. To better understand how different solution concepts behave in each application, we consider several axiomatic properties.
Definition 3. An aggregation method R is majoritarian if, whenever a voter majority selects the same ideal element w, then w is selected by the aggregation method; formally, and as there could be co-winners, R is majoritarian if |{v i ∈ V : v i = w}| ≥ |V |/2 implies that w ∈ R(V ).
That is, majoritarity holds if the aggregated point equals the majority ideal point, while monotonicity holds if moving an ideal point to the aggregation point does not change the aggregation point.

Overview of our Results
Throughout, we study properties of Condorcet-aggregation and L p aggregation for certain applications of our general model. We note that distance metrics may not be sufficiently expressive in general, as they cannot express dependencies (among candidates or budget items) or semantic relations (among sentences in a legislation). Overcoming this limitation is further discussed in Section 9. Table 1 lists our main results.

Proposition 1.
In the application to Plurality elections, Plurality is both Condorcetconsistent and satisfies L p (V ), for any p ≥ 1.
Then, for any x ∈ X, it follows that: Item 1. above completes the proof for Condorcet aggregation, while Item 2. above completes it for L p aggregation for 1 ≤ p = ∞ For p = ∞, notice that z ∈ L ∞ (V ) for unanimous elections (in which all voters vote the same); however, as soon as there are at least two different ideal points, we have max i {d(x, v i )} = 1 for every x ∈ X, hence L ∞ (V ) = X, thus all alternatives tie as co-winners.
We note that, while L ∞ (V ) does not contain much information here, its reduced form L ∞ (V ) := lim p→∞ L p (V ) is restricted to the plurality elements in X. The following corollary is immediate.
In the application to Plurality elections, both Condorcet aggregation and L p (V ) exist for any p ≥ 1, but are not always unique. Furthermore, they are monotonic, majoritarian, and may be computed in linear time.
Proof. Uniqueness is not guaranteed in situations where more than one alternative gets the highest number of votes. Monotonicity holds as a Plurality winner remains so whenever ballots are changed to it. Majoritarity holds as a majority of ideal elements on one alternative would make it the Plurality winner. Plurality can be computed in linear time by summing the tally of each alternative.

1-Dimensional Single-Winner Elections
Next we consider a different model of single-winner elections, corresponding to choosing a parameter in a 1-dimensional space (say, a price for a commodity, a tax rate) or political elections over a single political axis. We assume that some subset X ⊆ R is given as the set of alternatives. As is the case with Plurality elections (Section 3), the task here is to select a single alternative as a winner.
Formal model. We consider a metric space (X, d), where X ⊆ R is a set of real numbers, and d corresponds to the absolute distance; i.e., for each x, y ∈ X, d(x, y) = |x − y| (recall that each x ∈ X corresponds to a real number). For the ease of notation, we shall order the ideal elements in V by their magnitude, i.e., v 1 ≤ v 2 ≤ ... ≤ v n . We begin with a simple characterization of Condorcet winners and L p aggregation for p = 1, 2, ∞ in this setting.
Observation 1 For the application to 1-dimensional single-winner elections, the Condorcet aggregation and the L 1 aggregation are the median of V . 8 Proof. For Condorcet aggregation, the result follows Black's celebrated Median Theorem [12]. The results for L p (V ) are folklore and appear, e.g., in [47].
When X ⊆ R is compact, the existence of L p aggregation for other values of p follows since i∈[n] |v i − x| p is continuous, and thus must obtain a minimum in A. Furthermore, if X ⊆ R is convex and 1 < p ≤ ∞, this function is strictly convex and thus obtains a unique minimum. It follows that the aggregation point for convex domains may be efficiently computed via gradient descent methods. Otherwise, if X is not convex, then an efficient algorithm can be realized by first computing L conv p (V ), the aggregated element wrt. the convex hull conv(X) : We thus conclude the following.
Observation 2 For the application to 1-dimensional single-winner elections, Condorcet aggregation and L p aggregation exist wrt. any compact set of alternatives X ⊆ R. These aggregation rules can be efficiently computed via gradient descent schemes (L 1 aggregation and Condorcet aggregation can also be computed in linear time, as they are equivalent to the median). If X ⊆ R is convex While the median, L 1 (V ), is not necessarily unique when |V | = n is even, its reduced form, L 1 (V ) := lim p→1 L p (V ), is unique on convex domains (in a similar manner to the case of p = ∞ presented in Section 3). L ∞ (V ) always exists, but it is not always unique. To get some more intuition for the behavior of L p aggregation, consider the extreme cases depicted in Figure 1.

Corollary 2.
For the application to 1-dimensional single-winner elections, Condorcet aggregation and L p aggregation are not always unique. The reduced form L 1 (V ) is unique on convex domains.
Next we consider monotonicity and majoritarity. make it be the median. For odd number of voters, the median is indeed a point, thus monotonicity holds as moving elements to the median would not change the median. For even number of voters, there is not only a single median, thus monotonicity (as defined), due to tie breaking, is not satisfied. For L p aggregation for p > 1, the distribution V in Figure 1 provides a counterexample to majoritarity. Monotonicity does not hold for similar reasons (e.g., moving one voter from 0 to the aggregation point of V would result in changing the aggregation point).

Continuous Participatory Budgeting
Here we apply our general model to a continuous model of budgeting. Several budgeting methods exist in the literature [32,8,14]; we also mention related work on probabilistic social choice [15]. Here we concentrate on a model, termed continuous participatory budgeting, in which fractional funds shall be allocated to several divisible items (in contrast to the non-divisible model of participatory budgeting [18], in which items come with cost, and an item cannot be partially funded): 9 Specifically, individual financial statement items are grouped by cost centers or departments, and there is a given, fixed budget limit. In contrast to related models [36,28], we do not assume a fixed set of alternatives provided to the agents to choose from. Rather, every agent may propose a set of alternatives, (represented, e.g., by a string) and an allocation of funds between them.
Formal model. We assume that each agent i proposes a finite set of alternatives A i and a distribution of the funds between these alternatives. For normalization, let the given amount be 1, and thus the distribution corresponds to a probability vector v i ∈ R |Ai| . Let A = i A i denote the (finite) set of alternatives proposed by the agents. We shall decide how to distribute a given amount of available funds between |A| = m alternatives. Thus, the set of possible ideal points consists of the (m − 1)-dimensional simplex where each vector in ∆ m−1 corresponds to a distribution of the budget among the m alternatives. In order to define distances in this context, it is natural 10 to consider the metric induced by the Euclidean norm Utilizing Plott's theorem [50], that provides a full characterization of Condorcet winners in euclidean spaces, we conclude the following: In fact, as follows from the literature on spatial models [27], a Condorcet winner exists with probability zero, and the Condorcet cycle usually spans over almost the entire domain.
In contrast, with regards to L p aggregators, since f (x) = i∈ [n] x − v i p is continuous over the compact domain ∆ m−1 , it follows that there always exists an element in X = (∆ m−1 , · p ) that minimizes f . Furthermore, when the ideal points v 1 , ..., v n are not collinear (i.e., they do not lie on the same line), it holds that f is positive and strictly convex in ∆ m−1 , hence obtains a unique minimum (we refer the reader to [63] for elaborate discussion for the case of p = 1).
Corollary 4. L p aggregation always exists, and it is unique (except for the case of p = 1 with respect to an even number of ideal points that are collinear). In contrast, Condorcet aggregation usually does not exist and is not necessarily unique. Remark 1. We note that the L 1 -estimator in this setting is the geometric median of v 1 , ..., v n (sometimes called the Fermat or the Torricelli point), and the L 2estimator is the center of mass of the given ideal points, which corresponds to the average in every coordinate.
The situation here generalizes the situation of 1-dimensional Euclidean elections described in Section 4, as a 1-simplex is a 1-dimensional Euclidean space. From similar reasons as discussed in Section 4 (specifically, the convexity and compactness of ∆ m−1 ), efficient computation for L p aggregation follows by using gradient descent.
Corollary 5. L p aggregation can be computed efficiently using gradient descent.
Majoritarity holds for Condorcet aggregation and for L 1 aggregation.
Proposition 3. For the application to continuous budgeting, majoritarity holds for L 1 but not for L p for p > 1. No p ≥ 1 satisfies monotonicity. Condorcet aggregation satisfies both monotonicity and majoritarity.
Proof. For p > 1 majoritarity fails due to Proposition 2. For p = 1, majoritarity holds as any deviation from the majority ideal point would increase the distance from the majority voters, while, following the triangle inequality, the decrease from other voters would not suffice to account for the increase. Monotonicity is not satisfied even for p = 1 (e.g., consider a triangle).

Social Welfare Functions
We consider social welfare functions, where the input for an aggregation method is a set of n linear orders and the output of an aggregation method is another linear order. A relevant metric space in this setting is the set of all permutations X = S z over a set of z underlying alternatives, equipped with the metric d induced by swaps of consecutive alternatives (other options are natural for future study).
Observation 3 For the application to social welfare functions L p aggregation for any 1 ≤ p ≤ ∞ always exists but are not always unique. Condorcet aggregation does not always exist.
Proof. Being the minimum of a continuous function over a compact domain, the existence of L p aggregation in this setting is guaranteed. To see why they are not unique, consider a finite set of alternatives A and |A|! voters, each of which corresponds to a different permutation over A. By symmetry considerations, Observation 4 In the application to social welfare functions, the L 1 aggregation point is the Kemeny ranking and thus L 1 aggregation is NP-hard.
Proof. Given n ordinal ballots (i.e., n linear orders) over an underlying set A of alternatives, a Kemeny ranking is a linear order which minimizes the sum of distances to the n linear orders, where the distance is defined via swap distance, thus equivalent to minimizing the sum of absolute distances.
As for L ∞ , it is equivalent to the NP-hard Adjacent Element Swap Centre Permutation problem [51, Corollary 1]. Thus L ∞ is NP-hard here as well. This fact also follows from Biedl et al. [11].
Corollary 6. For this setting, L ∞ aggregation is NP-hard.
The following result shows that, for this setting, L p is NP-hard for any p ≥ 1.
Theorem 1. For this setting, L p aggregation is NP-hard for any 1 < p < ∞.
Proof. We reduce the problem of finding the aggregation point for L 1 to the problem of finding the aggregation point for L p , for 1 < p < ∞. The proof then follows as L 1 aggregation is NP-hard (Observation 4).
For simplicity of presentation, we describe the proof for the case of 3 voters; but the proof generalizes in a straightforward way to more voters. Let A be a set of alternative, and let V = {a, b, c} be the voters; i.e., each of a, b, and c, is a permutation over A. Let x * be the L 1 aggregation point of V . We reduce the problem of finding x * to the problem of finding the L p aggregation point of the election we describe next.
The reduced election has a set A ∪ D ∪ D of alternatives (where the sets D and D are sets of dummy alternatives of sufficient size; details below). Let d be an arbitrary (but fixed) permutation over D and d an arbitrary (but fixed) permutation over D . The reduced instance has a set V = {A, B, C} of voters, such that: Recall that x * is the L 1 aggregation point of V . Consider the permutation Below we show that X * minimizes the L p distance, and that only strings of this form (i.e. more generally, using any three optimal L 1 aggregation points of V instead of three copies of x * ). To show this, consider an arbitrary permutation X (in the metric space of the reduced election). First, observe that, if D and D are large enough, then if X is not of the form X = y 1 d y 2 d y 3 (where y i is a permutation over A), then it would incur a higher distance than X * , due to the dummy alternatives (note that the dummy alternatives are disjoint from the alternatives in A).
So, assume that X is of the form Furthermore, we assume that X does not only use L 1 aggregation points of V , i.e. that L 1 (y 1 , V ) + L 1 (y 2 , V ) + L 1 (y 3 , V ) > 3 · L 1 (x * , V ).
Next we compute the L p distance between X and the electorate V ; denote this as L p (X, V ): where the first equality is by definition; the second equality follows whenever D and D are large enough; and the third is simply by defining u, v, and w (as notation). Now we have the following: where the first equality is by definition of u, v, and w; the second equality is by rearranging terms; the third equality is by definition of V and of L 1 ; and the (last) inequality is from the fact that one of y 1 , y 2 , y 3 is not optimal. Next we mention a folkore algebraic inequality on generalized means (see, e.g., [17]), stating that for positive integers n 1 , . . . , n k and p > 1, In other words, for any m, we have that Using this algebraic inequality, we have that, We conclude that X * is the L p aggregation point. Thus, to find the L p aggregation point, one cannot avoid finding the L 1 aggregation point.
We conjecture that also Condorcet aggregation is NP-hard for this setting, however proving it seems to be quite tricky. Conjecture 1. Condorcet aggregation for this setting is NP-hard.
The next example demonstrates that L p aggregation is not monotone for any p > 1.
Proof. The proof follows from the one-dimensional case, in particular, from Proposition 2 as we can devise instances of social welfare functions that would correspond to one-dimensional lines.
Consider, for example, two ideal points, v 1 = a b c d e and v 2 = e a b c d. Then, observe that the ranking w = a b e c d satisfies w ∈ L ∞ (V ); however, changing v 2 to vote as w would result in a new aggregation point a b c e d. Notice that the instance described above indeed simulates a one dimensional line (containing five points, where v 1 corresponds to the right-most point, while v 2 corresponds to the left-most point).
Next we consider majoritarity.
Proposition 5. Condorcet aggregation and L 1 aggregation are majoritarian for the application to social welfare functions, while L p aggregation for p > 1 are not.
Proof. For Condorcet aggregation, majoritarity always holds. For L 1 aggregation, consider linear order corresponding to the voter majority's choice and, intuitively, observe that deviating from this linear order would increase the sum of absolute errors. More formally, consider a situation with voter majority on one ideal point x and consider some other ideal element y, of distance d(x, y) from x. Then, each voter voting on x would cause an increase to the sum of distances for y, which would be at least the sum of distances of all voters from x; thus, x would minimize L 1 .
For L p aggregation for p > 1, consider the set {a, b, c} of underlying alternatives and three voters with linear orders a b c, a b c, and c a b. Then, we have that the sum of L p distances from a b c (which is the majority choice) is 2 p , which is at least 4 for p ≥ 2, while the sum of L p distances from a c b is 1 p + 1 p + 1 p = 3, which is smaller.

Committee Elections
Here we consider selecting a committee from a given set of candidates.
Formal model. Let A be the underlying set of alternatives and notice that the set of possible committees is 2 A (that is, the set of all possible subsets of A). Thus, we consider the metric space (X, d) where X ⊆ 2 A ; specifically, each x ∈ X is a subset of A, x ⊆ A. As two specific cases, note that X = 2 A corresponds to the setting where the size of the committee is not given a priori but is decided by the aggregation method itself. This scenario was considered by Kilgour [41], Duddy et al. [23], and Faliszewski et al. [33]. However, denoting by 2 A k the set of all ksize subsets over A, note that X = 2 A k corresponds to the setting of k-committee selection, in which k committee members shall be elected. This setting is studied quite extensively [31]. As we assume no structure or dependencies between the alternatives, we do not impose any particular structure on X and define d to be the symmetric distance: For each x, y ∈ X, d(x, y) = |x y| (indeed, d(x, y) is the Hamming distance between the corresponding binary vectors of x and y).
First, recall the definition of the median element [43]: Consider an election E based on n ideal elements V = {v 1 , . . . , v n }, v i ∈ X. Then, the median element is the element x ∈ X which contains exactly those alternatives a ∈ A for which |{v ∈ V : a ∈ v}| ≥ n/2. That is, the median element is the unique element containing exactly those alternatives with weak voter majority support.
Proposition 6. For the application to committee elections, if X = 2 A then L 1 (V ) chooses the median element, while if X = 2 A k , then L 1 aggregation is approval voting.
Proof. For X = 2 A , for a set of voters V , the aggregated point x = L 1 (V ) minimizes the expression vi∈V |x v i |, which equals to vi∈V a∈A 1 a∈x vi , which equals to a∈A vi∈V 1 a∈x vi . Thus, any element y different from the median element x would give a higher sum, as for each a ∈ x y, vi∈V 1 a∈y vi ≥ vi∈V 1 a∈x vi holds. The case where X = 2 A k follows similarly.
Remark 2. The MW rule, described recently by Faliszewski et al. [33], which elects a committee containing all candidates with strong majority approval, is the L 1 aggregation where X = 2 A . Notice that L 1 (V ) is not unique for even number of voters (e.g., consider V = {v 1 , v 2 } with v 1 : {a} and v 2 = {b}; then, both {a} and {b} are winners). For odd number of voters L 1 (V ) is unique.
For X = 2 A , finding L ∞ (V ) is equivalent to the NP-hard Closest String problem [35]. We also mention that it is equivalent to the variable number of winners counterpart of minimax approval voting [13].
Corollary 7. For the application to committee elections with variable number of winners, computing L ∞ (V ) is NP-hard.
Chen et al. [20], using a slightly different jargon, prove that L p aggregation in NP-hard for all values of p > 1.

Corollary 8.
For the application to committee elections with variable number of winners, L p aggregation is NP-hard for any p > 1.
While L p aggregation always exist for this setting, the next example demonstrates that Condorcet winners do not always exist for this application. Condorcet aggregation for this application can be phrased also as a Condorcetconsistent aggregation method for a binary combinatorial domain with top-based input, where the completion principle is based on the Hamming distance (see, e.g., [21]). Condorcet aggregation was studied by Darmann [22] which demonstrated the computational intractability of a related problem [22,Theorem 3.7].
We note that for committee election, only one committee may be a Condorcet winner: namely the one obtained by the majority voting rule, i.e. taking each alternative selected in a majority of preferences. Indeed, for any other committee, there is no strict majority against adding or removing an "unpopular" alternative. However, this is a necessary condition only, and it remains to decide if such committee actually is a Condorcet winner.
Theorem 2. For the application to committee elections with variable number of winners, Condorcet aggregation is NP-hard (more precisely, it is coNP-hard to decide whether the committee obtained by majority voting is a Condorcet winner).
Proof. We provide a reduction from the NP-hard Vertex Cover problem. Consider a graph G with vertex set denoted A (with n := |A|) and edge set E (with |E|); and an even integer k. We first duplicate every edge in E (E becomes a multi-set), and write m for the (new) size of E. Note that this operation is safe, in the sense that a subset of vertices is a vertex cover in the original graph if, and only if, it is a vertex cover in the new one. We further assume that G has no isolated vertices, is not a star, and that n ≥ k + 4.
Let the set of alternatives be A := A ∪ B, where B is a set of k − 1 dummy alternatives. Build a set of 2m + 1 voters V := E ∪ F ∪ {g} as follows: -E is the set of edges, i.e. it is a set of m voters with preference {u, v} ⊂ A -F is a set of m voters, all preferring set B g is a voter with preference A = A ∪ B The majority voting winner for this election (denoted w) is the set B of alternatives. Indeed, each element of B appears in the preference set of m + 1 voters, and no element in A appears in m + 1 preference sets (otherwise such an element would be a vertex incident to all edges, i.e. G would be a star). We prove the following equivalence: w is not a Condorcet winner ⇔ G has a vertex cover of size k.
We first compute the distances between w and the different voters. For e ∈ E, d(w, e) = |B| + |e| = k + 1 (since e and B are disjoint). For f ∈ F , d(w, f ) = 0. Finally, for voter g, d(w, g) = |A| = n. Now for any other committee h ∈ 2 A , h = w, we have d(h, e) = |h| − 2 if h contains e, d(h, e) = |h| if h contains one endpoint of e, and d(h, e) = |h| + 2 otherwise. Also, d(h, f ) > d(w, f ) for all f ∈ F , and d(h, g) < d(w, g) ⇔ |h| ≥ k.
⇐. Let h ⊂ A be a vertex cover of G of size k (then h ⊂ A is also a candidate committee). For any voter e ∈ E, since h ∩ e = ∅, we have d(h, e) ≤ |h| = k < d(w, e); and for voter g, d(h, g) < d(w, g). So all m + 1 voters in E ∩ {g} strictly prefer h over w: w is not a Condorcet winner.
⇒. Assume that w is not a Condorcet winner. Let h ⊆ A ∪ B, h = w be a committee beating w, i.e. a (not necessarily strict) majority of voters prefer h over w. Since voters in F strictly prefer w over h, then all voters in E ∪ {g} must strictly prefer h over w (except at most one voter, in case of a tie, which is at the same distance from both). Thus, |h| > k − 1, and d(h, e) < k + 1 for all e ∈ E (except for at most one strict inequality which may be an equality). In particular, using d(h, e) ≥ |h| − 2, the latter implies |h| < k + 3.
First if |h| = k − 1 (the unique equality is for voter g), then d(h, e) < k + 1 implies that h intersects every edge e: h is a size-(k − 1) vertex cover. Now if |h| = k, and e ∩ h = ∅ for all (or all but one) edge e. Then h covers at least m − 1 edges, which is sufficient to be a vertex cover (since every edge has been duplicated).
Next we consider majoritarity.
Observation 5 For the application to committee elections with variable number of winners, Condorcet and L 1 aggregation are both majoritarian, while L p aggregation for p > 1 are not majoritarian.
Proof. For Condorcet aggregation majoritarity holds for any metric space, thus, in particular, also here. For L 1 aggregation, the claim follows as the median element would be the choice of the voter majority, and, in case of voter majority on one ideal element, it would be the median element.
For L p aggregation with p > 1, choose sufficiently large odd n such that In contrast, It follows that, even though the majority choice is {a}, the L p aggregation of this instance must be some x = a in X.
The following example shows that monotonicity is not satisfied for p > 1. Condorcet aggregation does satisfy monotonicity, as it does for all applications we consider in this paper. L 1 aggregation is monotone here as the median element would stay when moving a voter ideal point to it.

Participatory Legislation
We consider participatory legislation (see, e.g., [2]). Clearly, plurality elections can be applied to approve a proposed legislation, or to choose among a given set of proposed legislation. Even if such a proposal is made by an elected legislation committee, such a process falls short of the egalitarian vision of the 1789 Declaration of the Rights of Man and Citizen [6, Article VI], which states that all citizens have the right of contributing to the formation of the law personally, not only via their representatives. Hence, we focus here on aggregating text drafts, e.g., to jointly write a constitution. In fact, our main motivation for this work comes from the apparent lack of literature on a participatory approach to this key social choice setting in the computational social choice community.
Formal model. Here we have a certain alphabet Σ. The possible outcomes, as well as the possible votes, are all strings over Σ; thus, we consider a metric space (X, d) where X = Σ * , such that each x ∈ X is a string over the alphabet Σ.
Various possibilities exist for defining the metric d. The first thing that comes to mind is to consider the Levenstein edit distance: For two ideal element x, y ∈ X, the Levenstein distance d(x, y) is the minimum number of edit operations of the form insert (which adds a character at a certain position), delete (which deletes a character at a certain position), and swap (which swaps two consecutive characters) that shall be performed to convert x into y. Assume that strings are documents consisting of a sequences of sentences, namely that characters are sentences. We feel that in this setting, this metric is not appropriate as it gives the same importance to the identity of the sentences as to their order. However, when writing, e.g., a constitution, the contents of the sentences in it are more important than their order. For this reason, we consider a different distance metric, namely a weighted-Levenstein distance d(x, y), which equals the minimum weight of operations that transform x to y, with the following weighted operations: an insert operation costs 1, a delete operation costs 1, and a swap operation costs 1/ 2 , where is the length of the longest ideal point proposed by any voter. The situation now boils down to a two-phase election: First, one shall find the set of sentences to be included in the constitution; second, one shall find the best ordering of these sentences. We consider these two phases in turn.
Phase 1: Selecting the set of sentences. Here, only considering the set of sentences in each ideal point, the task is to aggregate those n sets of sentences into one set of sentences. We assume that the resulting aggregated has at most one copy of each sentence. Thus, this setting is formally equivalent to multiwinner elections with variable number of winners, studied in Section 7.
Phase 2: Selecting the order of the selected sentences. Following phase 1, we shall order the elected sentences. This setting is formally equivalent to social welfare functions, studied in Section 6.
Combining the two phases. Naturally, we get the combined hardness of the two phases: Existence is guaranteed only for L p aggregation; uniqueness is not guaranteed for any aggregation method; Condorcet and L 1 aggregation are majoritarian, while L p aggregation for p > 1 are not majoritarian; and computational hardness follows.
Remark 3. For L 1 aggregation, one can use the polynomial time algorithm for L 1 aggregation for multiwinner elections with variable number of winners discussed in Section 7, followed by solving Phase 2 heuristically, e.g., using one of the methods for Kemeny ranking studied by Ali and Meilȃ [1]).

Discussion
We proposed a general metric-based model and applied it to a broad range of social choice settings, demonstrating its applicability as providing a unifying elicitation and aggregation framework for the social choice situations needed for an e-democracy. Below we discuss some avenues for future research.

Further Settings
Further social choice settings shall be realized in our general model. In particular, further distance measures, such as, e.g., those described by Schiavinotoo and Stützle [54] can be applied. Related, our aggregation methods for participatory legislation only take into account syntactic distance, but not semantic distance. An intriguing avenue for future research would be to apply NLP methods which take into account the semantics of the aggregated text drafts.

Extensions
A major advantage of utilizing a unified framework, capturing many social choice settings at once, is that extensions and generalizations can be designed in a unified way, making them applicable to all such settings at once. One natural extension would be to incorporate proxy voting [45] and liquid democracy [10,16] to the model. Another natural extension would be to incorporate sybil resilience [56] to the model, making it applicable in situations in which not all agents participating in the process can be assumed to be genuine.

Voting and Deliberation
A major caveat of our model is that we infer voter preferences over the metric elements based only on their ideal points, while it might be the case that, e.g., voters with identical ideal points have different preferences over other elements of the metric space. This is especially problematic, e.g., when dependencies exist between committee members in multiwinner elections; where interdependent items are to be funded in participatory budgeting; or where different sentence ordering alter the meaning of the resulting text.
One remedy for this might be to incorporate Reality (the status quo) in a process that interleaves voting with deliberation; for instance, similarly in spirit to Reality-aware action plans [58] and to other works [61], we envision an iterative process where the deliberation phase of each iteration is based on the aggregated point identifying based on the voting phase of the last iteration, following which participants may change their votes; the result of such an iterative process could be an aggregated point that has majority support over the status quo, or else a recognition that the status quo is presently preferred over any aggregated alternative.