key: cord-0585045-8s6v1c9z
authors: Meir, Reshef; Sandomirskiy, Fedor; Tennenholtz, Moshe
title: Representative Committees of Peers
date: 2020-06-14
journal: nan
DOI: nan
sha: aa9244cc8e319c1d2268725b7cd72c6c4d3d0d6d
doc_id: 585045
cord_uid: 8s6v1c9z

A population of voters must elect representatives among themselves to decide on a sequence of possibly unforeseen binary issues. Voters care only about the final decision, not the elected representatives. The disutility of a voter is proportional to the fraction of issues, where his preferences disagree with the decision. While an issue-by-issue vote by all voters would maximize social welfare, we are interested in how well the preferences of the population can be approximated by a small committee. We show that a k-sortition (a random committee of k voters with the majority vote within the committee) leads to an outcome within the factor 1+O(1/k) of the optimal social cost for any number of voters n, any number of issues $m$, and any preference profile. For a small number of issues m, the social cost can be made even closer to optimal by delegation procedures that weigh committee members according to their number of followers. However, for large m, we demonstrate that the k-sortition is the worst-case optimal rule within a broad family of committee-based rules that take into account metric information about the preference profile of the whole population.

How well do committees represent preferences of the underlying population? How to select committees optimally? This paper aims to answer both questions taking the design perspective on committeeselection procedure and the choice of inter-committee voting rule.

The mainstream social-choice literature considers preferences on the set of candidates to be the primitive of the model. In contrast, we assume that voters have preferences on decisions of the committee. This richer structure provides a natural way to assess how well the committee represents electorate's preferences.

We consider a population that is going to face a sequence of binary issues to decide on (e.g., academics select a committee to decide whether to run a new journal, where to organize the next workshop, whether to conduct it online because of the pandemic of . Once a new issue emerges, each voter can possibly form his preference about the best alternative. This allows us to consider a "socially optimal" alternative that would be selected at the whole-population referendum, had such a referendum been conducted. 1 However, engaging in a frequent referenda may be a heavy burden for the population. This is part of the reason why historically, most of the world has moved from direct democracy to some form of representative democracy (by committees or parliaments), whereas more recently there is much interest in increased public participation via technological means [Dalton et al., 2001 , Brill, 2019 , Allen et al., 2019 .

We follow the representative democracy approach in this paper, assuming there is a strict limit on the number of representatives that can actively vote on all issues. We then ask if and how a representative committee can be selected from the general population.

We evaluate how well the committee aggregates preferences of a given population by its social cost, where the cost of a voter is proportional to the number of issues on which he disagrees with the final decision. Following the standard worst-case approach in approximate mechanism design, the approximation ratio is defined as the worst-case ratio between the (expected) social cost of the elected committee and the optimal social cost. The latter is obtained by an issue-by-issue majority vote of the entire population. We impose no restriction on preference profiles of the population.

The simplest way to select a committee is to select k individuals uniformly at random from the population. This way is known as "sortition" and it has been discussed-although not frequently usedsince ancient times Dowlen [2017] .

Note that we did not say explicitly how the selected committee is supposed to make a decision. Indeed, a natural approach is to use a majority vote inside the committee but we may also consider other alternatives.

Our main goal in this paper is to understand the best approximation ratio that can be obtained by a committee, and what selection rules and/or internal voting rules are optimal.

Our main result is a characterization of the approximation ratio of k-sortition: For a committee of size k = 3 the ratio is equal to 1.316 (Example 4) and behaves as 1 + Θ 1 √ k , when k increases (Theorem 2). As a corollary of this result, we infer that the optimal committee size k for a population of size n is of the order of n 2 3 given fixed preference-elicitation costs (Corollary 1). Can we do better than k-sortition? It turns out that for a small number of issues m, the approximation ratio can be made exponentially close to 1 in k by weighing each committee member according to the fraction of the electorate it best represents (Proposition 3). However, this improvement disappears in a realistic scenario of large number of issues m, moreover, the suggested average-proximity weighing becomes harmful (Proposition 4).

We complete the results above by showing that without further restrictions, k-sortition is the best rule among a broad family of committee-selection and inter-committee voting rules (Theorem 5).

To summarize, in unstructured environments, k-sortition is a compelling choice for representing preferences of the electorate.

Structure of the paper The model is introduced in Section 2. We analyze the benchmark rule, k-sortition in Section 3. Section 4 is devoted to improving the outcome of k-sortition for small number of issues by using additional information about the proximity of committee members and voters. In Section 5, we show that k-sortition is worst-case optimal within a broad family of rules. Limitations of the model and remaining questions are discussed in Section 6. Most of the proofs are only sketched in the main body of the paper; all the details can be found in Appendices A, B, and C.

Finding good voting rules for committee-selection and even formalizing what is "good" is still a big challenge for the social-choice literature, see a recent survey [Faliszewski et al., 2017] ; this literature takes a normative approach and aims to characterize voting rules by the combination of desired properties known as axioms. Preferences over candidates are considered to be the primitive of the model despite that, as argued by political scientists, preferences on candidates originate from the electorate's preferences on future decisions that a candidate would take if elected [Austen-Smith and Banks, 1988] . This limitation does not allow to capture the objective of selecting committees that optimally represent electorate's preferences on future policies.

The idea of selecting representatives as a small random sample from the electorate has its roots in Athenian democracy (see e.g. [Hansen, 1999] ). Recently this idea gained popularity [Dowlen, 2017 , Cheng et al., 2017 , Guerrero, 2014 for its fairness, representativness, and high barriers to various manipulations including vote-buying [Parkes et al., 2017 , Jamroga et al., 2019 , Gersbach et al., 2017 . It was also deployed by at least one startup [Chaum, 2016, https://rsvoting.org/] . Preliminary experimental data suggests that random-sample voting is suitable for political elections, see [Fishkin et al., 2018] and [Blanchard, 2019, Chapter 7] . Trustworthy and secure large-scale implementation of these ideas leads to cryptographic challenges [Lenstra and Wesolowski, 2015, Basin et al., 2018] . We emphasize that in this work fairness (in the sense of representation for minorities) is not one of our goals, as the selected committee is only an intermediate step for a final decision that applies to the entire population.

One stream of the literature on multiple referenda deals with the dependency among issues in voters' preferences (see e.g. Lang and Xia [2016] ); or with restrictions on the valid outcomes, as in judgement aggregation Pauly and Van Hees [2006] . We follow a different stream of the literature, making the simplifying assumption of that the full preferences of each voter are fully captured by her position in some metric space (in our case, the binary cube with the Hamming distance) Border and Jordan [1983] , Procaccia and Tennenholtz [2009] , Meir et al. [2012] , Goel et al. [2017] , Anshelevich et al. [2018] .

Measuring the performance of a voting rule by its approximation ratio (or distortion, which is an analogue of the approximation ratio for a given set of candidates) was suggested in [Procaccia and Rosenschein, 2006] . It was later applied by Procaccia and Tennenholtz [2009] for facility-location in metric spaces and became a gold standard in economic-design literature. In this line of papers, the optimal outcome is compared to the best possible outcome subject to some constraint on the voting rule (e.g. that it is strategyproof, or uses only ordinal information). Indeed, in the special case of a singleton (k = 1), k-sortition boils down to the familiar random dictator voting rule, whose approximation ratio for large populations is 2. Cheng et al. [2018] also consider voting on a metric space, where candidates are uniformly sampled from the set of voters, and characterize the class of scoring rules having bounded distortion. Our paper is different in many aspects: it analyzes the decisions of the elected committee, allows for fairly general committee-selection procedure, e.g., the sampling procedure may depend on preferences of the electorate, and achieves the approximation-ratio close to 1.

The fact that the approximation ratio of k-sortition goes to 1 for large committee size, can be regarded as an extension of the famous Condorcet Jury theorem, which claims that if each voter receives a noisy signal about the "right" alternative, the majority vote of a large population reveals the ground truth. In this interpretation, preferences of a random committee member are seen as a noisy estimate of preference of the majority. An important difference is that the jury theorem requires the population to be far enough from a tie [Paroush, 1998] , while our bounds are applicable to all preference profiles.

Delegation A compromise between the direct and representative democracies is provided by proxy voting [Alger, 2006 , Green-Armytage, 2015 , Cohensius et al., 2017 and liquid democracy , Goelz et al., 2018 : each voter has an opportunity to engage in the decision-making directly but, since he may be non-motivated enough or unavailable, there is an option to specify a representative thus delegating the vote to the proxy. The idea of weighing the committee members, used in Section 4, is inspired by this line of research. Below we provide a detailed overview of several papers on proxy voting with multi-issue setting sharing some similarity with ours. Pivato and Soh [2020] consider a fixed committee with delegation to the closest representative and evaluate its performance on a sequence of i.i.d. issues. They demonstrate that in the limit of large electorate, the decision of the committee always matches the alternative preferred by the majority. This conclusion holds even for committees of size 1 because authors impose additional strong assumptions on the alignment of electorate's and committee members' preferences. Our approach significantly differs: we are interested in the worst-case guarantees, work with a fixed population of voters, allow them to have arbitrary preferences, and the only randomness in our model comes from the randomization performed by voting rules.

The setting in [Skowron, 2015] is similar to [Pivato and Soh, 2020] : implicitly assumed i.i.d. issues and strong restrictions on the alignment of preferences of the committee and the electorate. The paper discusses how the inter-committee voting rule affects the optimal selection of the committee. We are interested in the optimal selection of the pair (a committee and an inter-committee voting rule), make no assumptions on the preference profile, and rely on the worst-case analysis giving the robust guarantees.

In contrast to the two aforementioned papers, Abramowitz and Mattei [2018] impose no restrictions on preferences and propose an interesting continuous way to mix direct and proxy voting by allowing voters to readjust the weights of committee members for each issue. In Section 5, we consider a family of rules containing the proposal of Abramowitz and Mattei [2018] and demonstrate the worst-case optimality of k-sortition within this family.

There is a population [n] = {1, 2, . . . , n} of n voters who are going to face a sequence of m binary issues [m] = {1, 2, . . . , m} to decide on. Preferences of each voter i ∈ [n] are represented by a vector x i ∈ {0, 1} m , where x i,j = 1 if i prefers the alternative 1 for issue j and x i,j = 0 if the alternative 0 is preferred. The preference profile of the population is thus given by an n × m-matrix X = (x i,j ) i∈[n],j∈ [m] of zeros and ones.

For a pair of vectors z, z ′ ∈ {0, 1} m , we define the distance d(z, z ′ ) between them to be the number of issues where they disagree, i.e., the Hamming distance: d(z, z ′ ) = j∈[m] |z j − z ′ j |. For a pair of voters i, k ∈ [n], the distance between their preferences d(x i , x j ) captures the overall alignment of their tastes.

Definition 1 (voting rules). A voting rule f specifies the outcome vector z ∈ {0, 1} m for each preference profile profile X.

We allow for randomization and so a voting rule maps X to a probability distribution f (X) ∈ ∆ {0, 1} m according to which z ∈ {0, 1} m is then chosen.

Here and below ∆(A) denotes the set of all probability measures on A.

Classes of committee voting rules. We are interested in voting rules that can be represented as a two-stage procedure: first voters select a certain committee of peers C ⊂ [n] and then the committee members vote to determine the outcome for each of the issues. The restriction of a preference profile X to committee members C ⊂ [n] is denoted by X| C ; for definiteness, we assume that the order of rows in X| C is the same as in X, i.e., the row corresponding to a committee member with lower index comes first.

Definition 2 (committee voting rules). A committee voting rule is given by a function g that maps preference profile X to a probability distribution over pairs (C, h), where a committee C is a subset of [n] and h : {0, 1} |C|×m → {0, 1} m is a voting rule. The outcome of g is computed as follows: first the pair (C, h) is chosen with probability g(X) and then the outcome-vector z is obtained by applying h(X| C ).

We say that g is a k-committee rule if |C| = k with probability 1.

Any committee rule is a voting rule, and any voting rule can be seen as a k-committee rule with k = n, i.e., the whole population plays a role of the committee. We are interested in the opposite scenario, when the committee size k is small compared to the total number of voters, the total number of voters n.

Without further restrictions, every voting rule r (even randomized) can be represented as a 1committee rule, where C contains a single arbitrary voter and h is the fixed rule h(X| C ) ≡ r(X).

We therefore consider two natural restrictions on committee rules: the selection phase can only be based on pairwise distances; and in the voting phase, the committee decides on each issue separately (formal definitions below).

Indeed, the idea behind committee rules is that they avoid elicitation of detailed preferences of large population and rely on a small number of committee-members instead; 2 and the decision making process of the committee itself should be simple and transparent to maintain a clear connection between representatives and the voters they represent, and to enable voting on arbitrary issues as they come along.

For a preference profile X, we denote by D(X) the matrix of pairwise distances D(

. We focus on those committee rules that base the choice of the committee and of the inter-committee rule on information encoded in D(X) only.

Definition 3 (distance-based committee rules). A committee voting rule g is distance-based if the probability distribution g(X) over pairs (C, f ) of a committee and an inter-committee voting rule depends only on matrix of pairwise distances D(X). In other words, g(X) = g(X ′ ) whenever D(X) = D(X ′ ).

Example 1 (a distance-based k-committee rule.). Consider the following k-committee rule. It picks a committee C that minimizes the total distance to all the voters i∈[n] min i ′ ∈C d(x i , x i ′ ) (if there are several such committees, it randomizes over them uniformly) and the inter-committee rule h is the weighted majority vote on every issue, where the weight of a member c is given by

So for issue j, the outcome z j = 1 whenever c∈C: xc,j =1 w c > 1 2 c∈C w c ; in case of opposite strict inequality, z j = 0 and z j ∈ {0, 1} is picked at random in case of a tie.

Definition 4 (issue-wise voting rule). A voting rule f is issue-wise if it treats all issues separately i.e., for any pair of preference profiles X, X ′ that coincide on issue j and the corresponding outcome vectors z ∼ f (X) and z ′ ∼ f (X ′ ), we have P(z j = 1) = P(z ′ j = 1). The latter property is also known as independence of irrelevant alternatives (IIA) (see e.g. [Pauly and Van Hees, 2006] ).

Definition 5. A committee rule g is has issue-wise inter-committee vote if for any preference profile X the probability distribution g(X) is supported on pairs (C, h) such that the inter-committee voting rule h is issue-wise.

All the committee rules we consider will be distance-based with issue-wise inter-committee vote. Note issue-wise inter-committee vote does not imply that the rule itself is issue-wise since the distribution of the pair (C, h) depends on preferences of the whole population over all issues through D(X). E.g., the rule from Example 1 is not issue-wise but has issue-wise inter-committee vote. An example of a committee voting rule that violates the definition, is when h approves the three issues with the largest support in X| C and rejects all others.

Inefficiency of voting rules. Informational parsimony of distance-based committee rules may lead to selecting suboptimal outcomes. To quantify this inefficiency, we employ the utilitarian approach. We define the disutility of a voter i for an outcome-vector z ∈ {0, 1} m as the total number of issues, where i's preferences and z disagree, i.e., this disutility equals to the distance d(x i , z).

The utilitarian social cost of an outcome vector z is given by the sum of disutilities, and the social cost of a voting rule f on a preference profile X is defined as the expected social cost of its outcome:

Denote by z opt = z opt (X) the socially-optimal outcome, i.e., the one with the minimal cost

Definition 6. The approximation ratio of a voting rule f is the worst-case ratio of the expected social cost of its outcome z and the optimal social cost

The maximum is over all preference profiles X with fixed numbers n, m of voters and issues. If the denominator is zero (this happens for unanimous preference profiles), the following agreement is used: 0 0 = 1 and C 0 = +∞ for C > 0. When we drop some of the subscripts n and/or m, this means considering their worst-case values, i.e., AR n = sup m∈N AR n,m , AR m = sup n∈N AR n,m , and AR = sup n,m∈N AR n,m , Example 2 (The simple majority rule MAJ). The outcome z j for each issue j is determined on the wholepopulation referendum: z j = 0 if i∈ [n] x i,j < n 2 ; for the opposite strict inequality, z j equals 1; and z j is 0 or 1 equally likely in case of a tie. The resulting majority rule denoted by MAJ has the approximation ratio AR n,m (MAJ) = 1, i.e., it always select the socially-optimal outcome. Indeed, minimization of the social cost of SC(z) splits into a family of issue-wise minimization problems min zj i∈[n] |x i,j − z j | for each j ∈ [m] and the minimum is achieved if z j matches the majority of (x i,j ) i∈ [n] . Optimality of MAJ comes at the cost of huge burden imposed on the population: to compute the outcome we may need the preferences of the whole population on all the issues. Example 3 (The random dictatorship RD). The random dictator rule RD is a benchmark example in the voting theory. In our setting it works as follows: a voter i ∈ [n] is selected uniformly at random and i's preference dictates the outcome of each referendum, i.e., z = x i . Note that RD is an example of a 1-committee rule.

It is known that RD has the approximation ratio AR n (RD) ≤ 2 − 2 n for voting in general metric spaces [Meir et al., 2012, Anshelevich and Postl, 2017] . Our setting can be regarded as a particular metric space {0, 1} m with the Hamming distance d. However this does not improve the approximation ratio.

Let us compute the approximation ratio for the one-issue case. Without loss of generality, we can restrict our attention to profiles X such that the majority prefers the alternative 0 but not unanimously (for unanimity SC(z opt ) = SC(RD(X)) = 1). Denote the number of supporters of the alternative 1 by n 1 = i∈ [n] x i,1 . By the assumption, 1 ≤ n 1 ≤ n 2 . The social costs are SC(0) = n 1 and SC(1) = n − n 1 . With probability n1 n the random dictator supports 1 and with the complement probability he supports 0. Therefore, SC(RD(X)) SC(z opt ) = n1 n · (n − n 1 ) + 1 − n1 n · n 1 n 1 = 2 − 2n 1 n .

The maximal value AR n,1 (RD) = 2 − 2 n is achieved at n 1 = 1. A simple argument (Lemma 1 below) implies that AR n,m (RD) does not depend on m and thus AR n,m (RD) = 2 − 2 n for any number of issues.

At the end of the last section, we considered the two examples. At one extreme, we have the simple majority rule MAJ, which achieves a socially-optimal outcome but may require the information on preferences of the whole population of voters. The random dictatorship RD is on the other extreme: it is enough to know preferences of one voter only, but RD can almost double the social cost in the worst-case. Our goal in this section is to find the middle ground between these two extremes. We construct simple rules that have the approximation ratio close to 1 and require to learn preferences of a negligible fraction of the population. The following family of k-committee rules is a natural extension of both MAJ and RD.

Definition 7 (k-SORT: k-sortition). A committee C ⊂ [n] of size |C| = k is selected uniformly at random. The preferences of the committee members are aggregated using the simple majority rule h = MAJ (see Example 2).

Note that for a population of n voters, n-SORT coincides with the simple majority rule MAJ, while 1-SORT coincides with RD.

Example 4 (The approximation ratio for 3-SORT and one issue). Let's compute the approximation ratio for a random committee of size 3 and one issue. Similarly to Example 3, we can assume that the profile X has the following structure: the majority of n ≥ 3 voters supports the alternative 0, and there are 1 ≤ n 1 ≤ n 2 supporters of the alternative 1. We denote by p = n1 n ∈ 0, 1 2 the probability that a random voter supports 1.

Let A be the event that the committee with 3 members selects the suboptimal alternative 1; A occurs if and only if two or three members support 1. The probability of this event equals to

The probability P(A) tends to p 2 (3 − 2p) for fixed p and large n. For p ≤ 1 2 and any n, this limiting value provides an upper bound: P(A) ≤ p 2 (3 − 2p).

Taking into account that SC(0) = n 1 and SC(1) = n − n 1 , we obtain

Taking supremum over p ∈ 0, 1 2 results in an upper bound on the approximation ratio AR n,1 3-SORT ≤ 1 + sup

The maximum is attained at p * = 4− √ 7 6 ≈ 0.226. It is easy to see that if we define n 1 = p * · n and let n go to infinity, the ratio of the social costs converges to the upper bound in (2). Thus AR m=1 3-SORT = 1 + 7 √ 7 − 10 27 ≈ 1.316.

The next simple lemma implies that the approximation ratios computed for RD and 3-SORT in the one-issue case remain the same for any number of issues.

Lemma 1. For any number of voters n and any committee size k ≤ n, the approximation ratio of k-SORT does not depend on the number of issues m: AR n,m k-SORT = AR n,1 k-SORT

The lemma is proved in Appendix A; here we present a sketch.

Proof sketch of Lemma 1. The left-hand side of (3) is bounded by the right-hand side since any worstcase profile with one issue can be cloned m times. To prove the opposite inequality, we observe that the worst-case profile with m issues cannot be worse than its restriction to the worst issue.

Corollary 1. For a random committee of size k = 3, the approximation ratio AR m 3-SORT ≈ 1.316 for any number of issues m.

We see that passing from a random dictator to a random 3-committee significantly improves the approximation ratio. The following theorem covers the case of committees of arbitrary size k and demonstrates that the approximation ratio converges to 1 fast with the growth of k.

Theorem 2. For any number of voters n, committee size k ≤ n, and number of issues m, the approximation ratio of k-SORT enjoys the following upper bound

This upper bound has the right order of magnitude as a function of k. The lower bound is

dy is the standard Gaussian cumulative distribution function.

The proof is rather long because of technicalities and is postponed to Appendix A; here we sketch the main ideas.

Proof sketch of Theorem 2. Lemma 1 allows to focus on one-issue case. Similarly to Example 4, we aim to find the worst-case profile by maximizing over the fraction p ∈ 0, 1 2 of voters supporting the alternative 1. Given n, p, and k, the number of supporters of the alternative 1 in a random committee has the hypergeometric distribution with parameters (n, p · n, k). Despite hyper-geometric random variable is not a sum of i.i.d. contributions, it satisfies the Hoeffding tail-bound, familiar by the i.i.d. case. This bound and optimization over p leads to upper bound (4). Note that the worst-case p = 1 2 − Θ 1 √ k ; however, it takes additional work to exclude small p because the denominator in the approximation ratio (1) vanishes as p → 0.

For the lower bound, we approximate the hypergeometric distribution by the sum of i.i.d. Bernoulli random variables and apply the Central Limit Theorem to this sum (we use the so-called Berry-Esseen version of the CLT, which provides an upper bound on the error term). As a result, we get a statement even stronger than the lower bound (5): this lower bound holds for AR n,m k-SORT if that n is big enough compared to k, namely, 2(k + 1) 2 ≤ n.

Corollary 2 (Asymptotic behavior). Combining upper and lower bound we see that AR m k-SORT = 1 + Θ 1 √ k . Proof of the theorem demonstrates that worst-case preference profiles for large k are those, where both alternatives have approximately equal support with the imbalance created by Θ 1 √ k -fraction of voters.

Corollary 3 (Deterministic committees). By the probabilistic-method argument, the theorem implies the existence of a deterministic committee of size k such that the majority vote of its members has the approximation ratio at most 1 +

Remark 1 (Optimal size of the committee). Assume that eliciting preference of one voter on one issue has some fixed cost c measured in the same units as social costs of a voting outcome. Let's determine the optimal committee size that minimizes the worst-case regret for large number of voters n. Regret is defined as the difference between the total cost of k-SORT (including the elicitation cost) and the social cost of the optimal outcome

Regret(X) = SC k-SORT(X) + c · k · m − SC(z opt (X)).

By Corollary 2,

Minimizing the worst-case regret over k is, therefore, equivalent to minimizing Θ 1 √ k + c n · k. 3

Corollary 4. The optimal committee size is k = Θ n c 2 3

.

In the previous section, we saw that the k-sortition achieves an approximation ratio close to 1. A natural question to ask is whether we can push the approximation ratio even closer to 1 by using slightly more information about preferences of the population. We first show that the approximation ratios from the previous section can be significantly improved if the number of issues m is small. For this purpose, we use weighted majority voting to aggregate preferences of the committee members, where the weight of a member is determined by the fraction of voters to which this member is the "closest" representative Alger [2006] , Cohensius et al. [2017] .

Similar approach to weighing representatives is studied in the field of proxy voting (see Section 1). The common wisdom suggested by that strain of literature is that usually the quality of opinion-aggregation can be significantly improved by finding a clever way of transforming proximity to weights. It turns out, that in case of large number of issues, this is not the case.

While for small number of issues, weighing makes the approximation ratio exponentially close to 1 in the committee size k (compare with 1 + O(1/ √ k) from Theorem 2), we show that for large number m of issues, delegation is harmful and the approximation ratio is bounded from below by 9 8 for any size of the committee k.

For a committee C ⊂ [n] and a voter i ∈ [n], denote by C i the subset of committee members closest to i, his best representatives. We assume that each voter distributes one unit of "weight" over his closest representatives. So the weight w c of a committee member c ∈ C is given by w c = i∈[n]: c∈Ci 1 |Ci| .

Definition 8 (k-wSORT: weighted k-sortition). A committee C ⊂ [n] of size |C| = k is selected uniformly at random.

The committee decides on each issue j ∈ [m] using weighted majority vote with weights w c : if c∈C x c,j · w c > 1 2 c∈C w c , then the outcome is z j = 1; in case of the the opposite strict inequality, z j = 0; in case of a tie, z j ∈ {0, 1} is taken equally likely.

The following simple example shows that the approximation ratio is exponentially close to 1 in the one-issue case.

Example 5 (k-wSORT for 1 issue). Assume that n 1 among n voters support the alternative 0 and denote n1 n by p. Without loss of generality, 0 < p < 1 2 , i.e., the majority of voters prefers the alternative 0 that has the social cost of p · n.

If the preferences of all the committee members coincide with those of majority (x c,1 = 0, ∀c ∈ C), then, the committee selects the optimal alternative 0. Similarly, if x c,1 = 1 for all c ∈ C, the sub-optimal alternative 1 with the social cost (1 − p) · n is selected.

Consider the remaining case: both views 0 and 1 are presented in C. We check that, in this case, the decision is socially optimal for any proportion of supporters of each of the alternatives (compare with at least k+1 2 members needed without weighing!). Indeed, the total weight received by the supporters of zero alternative is (1 − p) · n and is bigger than the weight of the supporters of one, p · n.

Thus the committee makes the sub-optimal decision if and only if it contains no supporters of zero alternative, which happens with probability n 1 k / n k ≤ p k . Therefore, the approximation ratio admits the following upper bound

To find the worst-case, we take the logarithmic derivative and get k−1 p = 1 1 2 −p ; hence, p * = 1 2 k−1 k = 1 2 − 1 2k . We get AR n,1 k-wSORT ≤ 1 + 1 k · 2 k−1 1 − 1 k k−1 . 3 A fine issue here is that the optimal social cost in the worst case increases linearly in n and m. This follows from Lemma 1 (for m) and from the fact that the worst instances are those where the minority fraction p is far from 0.

By taking a sequence of preference profiles with growing number n of voters and ⌊p · n⌋ supporters of the alternative 1, we see that the upper bound is achieved in the limit. Thus

We see that weighing drastically improves the approximation ratio:

If there are several issues, weights of the committee members depend on all of them. Therefore we don't have an analog of Lemma 1, which allowed us to analyze the rule k-SORT in the one-issue case and then extend the results in a straightforward way. In particular, for k-wSORT, the approximation ratio depends on the number of issues. Now we demonstrate that for small number of issues, delegation leads to exponential improvement as in Example 5. To simplify the analysis we focus on preference-profiles with i.i.d. issues.

We say that the profile X = (x i,j ) i∈[n],j∈ [m] has i.i.d. issues if, when we sample a voter i ∈ [n] uniformly at random, the random variables (x i,j ) j∈m are independent and identically distributed. Informally this property means that issues are similar but unrelated: there are no logical dependencies between them or other correlations in preferences.

We define approximation ratio for i.i.d. issues by restricting the maximization in (1) to profiles with i.i.d. condition

Note that AR i.i.d. n,m is always below AR n,m .

Proposition 3. The approximation ratio of k-wSORT satisfies the following upper bound for profiles with m i.i.d. issues

We see that for small number m of issues the approximation ratio converges to 1 exponentially fast in the size of the committee. Thus, as in Example 5, the delegation improves the asymptotic behavior compared to k-SORT (note that AR i.i.d.

n,m and AR n,m coincide for k-SORT; the argument is similar to Lemma 1 and is omitted). However, the rate of exponential convergence drops drastically with the growth of the number of issues m. Below we will see that this is not a coincidence.

Proposition 3 is proved in Appendix B and the proof is sketched here.

Proof sketch of Proposition 3. It is enough to look at i.i.d. profiles X, where the majority prefers 0 for each issue; we denote by p ≤ 1 2 the fraction of supporters of the alternative 1. If p is very small (p < 1 2m ), then by the union bound, more than half of the population prefers 0 for all issues. Therefore, if at least one "all 0" voter enters the committee, they get more than half of the total weight and the committee selects the socially optimal outcome. Since such voters are likely to be among the committee members (the probability is at least 1 − (pm) k ), the social cost of k-wSORT at X is exponentially close to optimal.

For p ≥ 1 2m , the argument for the low social cost is different. Using the union bound we show that, with high probability, for each sequence z ∈ {0, 1} m there is a committee member with such preferences. Note that given this event, each voter delegates his voting right to a member with exactly the same preferences as his own, and hence, the outcome of the committee vote coincides with the majority vote of the whole population. Details of the computation can be found in Appendix B.

The next result complements Proposition 3 and shows that for unbounded number of issues, delegation is harmful and the approximation ratio is separated from 1 even for big committees.

Proposition 4. For unbounded number of issues, the approximation ratio of k-wSORT admits the following lower bound AR k-wSORT ≥ 9 8 for any committee size k.

Corollary 5. Comparing this result with Theorem 2, we see that 1000-SORT outperforms k-wSORT for any committee size k. Note that ancient Athenian democracy had 1100 magistrates, 1000 of whom were selected by lot [Hansen, 1999] . Committees of size 1000 are also recommended by Mueller et al. [1972] .

The fact that delegation in multi-issue setting may lead to inferior outcomes compared to majority vote is mentioned in [Cohensius et al., 2017, Section 5 ] for a similar model but without the worst-case analysis. Their insight is that for some preference profiles delegation leads to the most extreme voters attracting almost all weight, thus wasting the information about others' preferences. We build upon this insight.

Proof sketch (for details, see Appendix B). The idea is to construct a preference profile X with two groups of voters P and Q. All voters from Q have identical preferences and all voters from P are equidistant and the distance between any two distinct voters from P is bigger than the distance between a voter from P and a voter from Q.

Given such a metric structure, if any voters from Q enter the committee, they receive the weight both from Q and P and thus the committee decision becomes dictatorial and coincides with preferences of a voter from Q. In particular, the social cost of the outcome coincides with the social cost of the unanimous preferences of Q.

In the appendix, we show existence of such a preference profile X, where the social cost of Q's preferences is 9 8 of the optimum. The profile X is constructed via the probabilistic argument: (x i,j ) i∈P,j∈[m] are i.i.d. Bernoulli random variables with success probability p < 1 2 ; and for i ∈ Q and j ∈ [m] we put x i,j = ξ j , where (ξ j ) j∈[m] are i.i.d. Bernoulli random variables with success probability q < p. Therefore, for large number of issues m, the distance between any two voters from P is approximately 2p(1 − p)m · (1 + o(1)), while the distance between a voter from P and a voter from Q is (p(1 − q) + q(1 − p))m · (1 + o(1)). Optimization over p, q, and sizes of P and Q leads to the desired lower bound.

In Section 4, we considered weighing of the committee members, where a voter delegates one unit of weight to the closest representative. This method proved to be much better than the simple majority rule for a few i.i.d. issues, however it gives no advantage and may even harm if the number of issues is big.

One may think that poor guarantees for large number of issues is a feature of this particular delegation method. Indeed, it is easy to come up with alternative proposals that seem to be better: a voter may "smoothly" distribute the weight among the committee members in a way that members that are closer to him get more weight. Also, instead of selecting the committee uniformly, a higher chance can be given to voters with smallest average distance to the rest of the population.

In this section we show that none of such natural modifications can improve the approximation ratio with many issues: k-SORT, a uniformly random committee with the simple majority rule, is worst-case optimal among a large family of rules that may use the whole metric information about the preference profile.

Theorem 5. For any distance-based k-committee rule g with issue-wise inter-committee vote and any number of voters n, we have sup m∈N AR n,m g ≥ AR n,1 k-SORT .

In other words, a uniformly-random committee with the simple majority rule is worst-case optimal within this family of committee rules.

We prove a stronger result: instead of supremum over m on the left-hand side, one can take m = n! issues.

The proof is based on two lemmas. The first one shows that it is enough to prove the theorem for anonymous committee rules, i.e., symmetric with respect to permutation of voters.

For a preference profile X with n voters and a permutation π of [n], we denote by π(X) the preference profile with permuted voters: π(X) i,j = X π(i),j .

Definition 9 (anonymous voting rules). A voting rule h is anonymous if h(X) = h π(X) for any preference profile X and permutation π.

Note that even if committee members receive different weights as in Section 4 (and thus intercommittee rule is not anonymous), the committee rule may still be anonymous if the selection of the committee and the inter-committee rule depends on preferences of the population in an anonymous way. For example, k-wSORT rule is anonymous.

For a rule h, denote by h anym its anonymization: for any preference profile X

where n is the number of voters and S n is the set of all permutations of [n].

Lemma 6. For any numbers of voters and issues and any voting rule h AR n,m h anym ≤ AR n,m h .

The proof is elementary and can be found in Appendix C. The combination of anonymity and the distant-based property becomes very restrictive if distances between pairs of voters are all the same. The following lemma demonstrates that the set of such preference profiles is rich enough.

Lemma 7. For any number of voters n and n 1 ≤ n, there exists a preference profile with n voters and m = n! issues such that for each issue j ∈ [m] exactly n 1 voters support the alternative 1 and for each pair of distinct voters

Sketch of the proof (see Appendix C for the formal argument): The idea is similar to the one used in Proposition 4: if preferences of each voter are given by a vector of i.i.d. Bernoulli random variables with success probability p = n1 n , then, in expectation, n 1 voters prefer alternative 1 for each j ∈ [m], and the distance between any pair of voters concentrates around 2p(1 − p)m for large m by the law of large numbers.

To prove Lemma 7 we use a derandomization of this construction. This allows to have exactly n 1 supporters of 1 for each issue and exact equality of distances. Details can be found in Appendix C. Now we are ready to prove the theorem.

Sketch of the proof of Theorem 5 (see Appendix C for details). By Lemma 6, we can assume that g is anonymous without loss of generality.

Using Lemma 7, we pick a profile X such that all the voters are equidistant. On such a profile, the metric information encoded in the distance matrix becomes useless and the only anonymous way to select a committee is uniformly at random. The next step is to show that among the family of all committee rules with uniformly random committee and ble inter-committee vote, no rule can outperform k-SORT both on the profile X and on the complement profileX, where preference of all the voters are flipped. This boils down to solving an explicit optimization problem; the details can be found in Appendix C.

Lemma 7 provides enough flexibility to make X (and, hence,X), the worst-case profile for k-SORT. Since g is worse off on one of these profiles, it has higher approximation ratio.

The main takeaway message from our work is that at least when the preferences of the individuals in the society are separable, the simple and well known k-sortition rule is a reasonable choice that guarantees low approximation ratio.

While for a low number of issues we saw that there are more representative rules than the k-sortition rule, the latter also has other benefits. First, the selection of the committee C (and its internal voting rule h) is completely oblivious to voters' positions. As such, it can be used to select a committee even before we know some or all of the issues on the agenda.

Second, while we did not focus on incentive analysis in this work, it is easy to see that k-sortition is strategyproof for the the entire population: no voter can affect the selection of the committee, and representatives are always weakly better of by voting their true position on every issue. In contrast, under the proxy-weighted variant, voters may have an incentive to lie in order to affect the weights of committee members.

The main direction we are currently investigating is a better understanding of the effects of delegation, in particular when there are few issues and/or our restrictions on the structure of preferences.

In the long run, we are interested in how sortition and/or delegation-based voting rule can guarantee low distortion and good approximation in other domains, including ranked preferences and interdependent issues.

Proof of Lemma 1. In order to show that AR n,m k-SORT ≤ AR n,1 k-SORT , consider a worst-case profile X * ∈ {0, 1} n×1 for one issue. Define a new profile X with m issues by cloning X * : x i,j = x * i . Since different issues contribute to the Hamming distance in an additive way and k-SORT operates on each issue separately,

To prove the opposite inequality, pick a worst-case profile Y * ∈ {0, 1} n×m with m issues and denote by Y j a one-issue profile obtained by the restriction of Y to issue j, i.e., y j i = y * i,j . The following computation shows that the worst-case profile with m issues is not worse than its restriction to the worst issue

Combining inequalities (6) and (7), we obtain the desired equality of approximation ratios.

Proof of Theorem 2. By Lemma 1, it is enough to consider a one-issue profile X. Without loss of generality, we assume that the majority supports the alternative 0: 1 ≤ n 1 ≤ n 2 voters prefer the alternative 1, and the rest prefer 0. Denote p = n1 n ∈ 0, 1 2 . Let ξ be the number of committee members supporting the alternative 1. The random variable ξ has the hypergeometric distribution with parameters (n, n 1 = pn, k). Recall that the hypergeometric distribution describes the number of red balls among k draws without replacement from an urn with n 1 red and n − n 1 white balls. If we represent supporters of 0 as white balls and supporters of 1 as red and take into account that sampling without replacement is equivalent to picking a uniformly random subset, it becomes obvious that ξ is hypergeometric.

If ξ < k 2 , then the committee selects the socially-optimal alternative 0 with the social cost p · n; for ξ = k 2 (can happen only if k is even), there is a tie and the committee picks any of the two alternatives equally likely; for ξ > k 2 , the committee selects the sub-optimal alternative 1 with the social cost (1−p)·n. Therefore, the ratio of social costs in (1) can be represented as SC k-SORT(X) SC z opt = P ξ < k 2 · p · n + P ξ = k 2 · n 2 + P ξ > k 2 (1 − p) · n p · n ≤ (8)

We will consider the two cases of p close to zero and p close to 1 2 separately. As we will see, the worst-case instances correspond to the latter scenario, however, p in the denominator of (8) does not allow to cover both cases at once.

The case p ≤ 1 6 . For small p, we use a rough bound on P(ξ ≥ k 2 ) based on the Chebyshev inequality. The expectation and the variance of a hypergeometric random variable are given by

see e.g. [Feller, 2008, §2.6 ]. By the Chebyshev inequality,

Thus by (8),

Since 1 2m ≤ p, the right-hand side does not exceed

where in the last inequality we used that (1 − t) 1 t ≤ 1 e for any t ∈ (0, 1). Note that for any m, k ≥ 1, this upper bound exceeds the one obtained for p < 1 2m and thus

Proof of Proposition 4. Consider a random preference profile X with n voters and m issues. There are two groups of voters P and Q with sizes α · n and (1 − α) · n, respectively. All the voters i ∈ Q are unanimous: their preferences x i coincide with a vector ξ = (ξ j ) j∈[m] with components given by i.i.d. Bernoulli random variables with success probability q < 1 2 . In contrast, preferences of voters in P are not aligned: (x i,j ) i∈P,j∈[m] is a matrix with i.i.d. Bernoulli entries with success probability p ∈ q, 1 2 . The expected distance between two distinct voters i

] is equal to pm for i ∈ P and qm for i ∈ Q.

By the law of large numbers, for any ε > 0 we can find m = m(ε, n, p, q) such that all the distances are within a factor 1 ± ε from their expected values with positive probability:

Abusing the notation, we denote by X the realization of the random profile satisfying these inequalities.

Assuming that ε is small, we see that the distance between any two voters from P exceeds the distance between voters from P and voters from Q (it is enough to assume that

Consider a random committee C of size k. If C contains some voters from Q, all voters from [n] \ C delegate their weight to them. Therefore, if n − k > k 2 (i.e., n is large enough compared to k), voters from C ∩ Q get more than half of the total weight and, therefore, their unanimous preferences ξ coincide with the outcome of the committee vote.

The chance that C ∩ Q is nonempty equals 1 − αn k n k ≥ 1 − α k . Putting all the pieces together, we obtain the following lower bound on the approximation ratio

Taking into account that SC(z opt ) ≤ SC(0) and using the lower bound on the minimal distance, we get

Letting ε → +0 and q → p − 0, we get rid of ε and simplify the expression

Now, letting p go to 0, we see that

For k = 1, the maximum of the right-hand side is achieved at α = 3 4 . Substituting this value for any k, we obtain AR k-wSORT ≥ 3 2 − 1 2 3 4 k ≥ 9 8 .

Proof for Lemma 6. Pick a profile X with n voters and m issues and denote by X * the profile of the form π(X) maximizing SC h(π(X)) over all permutations π ∈ S n . Note that the socially-optimal cost is the same for X and X * . Therefore,

By maximizing the left-hand side over X, we obtain the desired inequality.

Proof of Lemma 7. Identify the set of issues with the set S n of all permutations π of [n]. So there are m = n! issues. Fix a set A ⊂ [n] of cardinality n 1 . The set of voters preferring alternative 1 for issue π is defined to be the preimage π −1 (A) of the set A under permutation π. In other words, preference of a voter i on an issue π is given by x i,π = 1, π(i) ∈ A 0, π(i) / ∈ A.

By the construction, exactly n 1 voter prefers 1 for each issue. Consider the distance d(x i , x i ′ ) = π∈Sn |x i,π − x i ′ ,π | between two distinct voters i, i ′ ∈ [n]. Let τ be the permutation such that τ (i) = 1 and τ (i ′ ) = 2. Taking into account that π → π • τ defines an automorphism of S n and that x i,π•τ = x τ (i),π , we get

Therefore, all the distances between distinct voters are equal to common constant d = d(x 1 , x 2 ). To find d, note that if we take a pair of voters uniformly at random (not necessary distinct), the chance they have different opinion on a certain issue π is n1(n−n1)+(n−n1)n1 n 2 , while the chance that they are distinct is n 2 −n n 2 . Thus n 2 − n n 2 · d = n 1 (n − n 1 ) + (n − n 1 )n 1 n 2 =⇒ d = 2p (1 − p) 1 − 1 n .

Proof of Theorem 5. Consider the anonymized rule g anym and check that for m = n! we have AR n,m g anym ≥ AR n,m k-SORT .

By Lemma 6, this implies the same lower bound for g. Pick n 1 ≤ n 2 such that the preference profile with one issue and n 1 supporters of the alternative 1 is the worst profile for k-SORT.

With this n 1 , construct the profile X from Lemma 7 and denote by X ′ the profile, where all the voters flipped their preferences on all the issues, i.e., x ′ i,j = 1 − x i,j . Both X and X ′ are worst profiles for k-SORT (see Lemma 1) and have the same socially-optimal cost SC(z opt (X)) = SC(z opt (X ′ )). Therefore, AR n,m k-SORT = 1 2 SC k-SORT(X) + SC k-SORT(X ′ ) SC(z opt (X)) .

Our goal is to show that SC k-SORT(X) + SC k-SORT(X ′ ) ≤ SC g anym (X) + SC g anym (X ′ ) .

Together with (14) this inequality would imply (13) since AR n,m g anym ≥ SC g anym (Y ) SC z opt (Y )

for any profile Y .

Consider the distributions g anym (X) and g anym (X ′ ) on pairs (C, h) of a committee with k members and the inter-committee rule. The two distributions coincide because g anym is distance-based and matrices of distances for X andX are the same; for definiteness, let's focus on X.

Since all pairs of voters in X are equidistant, the only anonymous way to select a committee C of size k is to take it uniformly at random among subsets C ⊂ [n] with |C| = k. Indeed if two such subsets C and C ′ differ in probability, this contradicts anonymity because C = π(C ′ ) for some permutation π of [n] and no permutation changes the matrix of distances.

Consider the probability P(z j = 1 | C) that the outcome of g anym (X) for issue j is 1 conditional on the selected committee C. This probability can only depend on (x i,j ) i∈C because h is issue-wise. Since g anym is distance-based and anonymous, and any permutation of voters (in particular, those in C) leaves the matrix of distances unchanged, we see that the probability can only depend on q = i∈C x i,j , i.e., the total number of supporters of the alternative 1 for issue j. Hence, P(z j = 1 | C) = h q,j = h q,j (C).

For any alternative j, the chance that the uniformly random committee C contains exactly q supporters of the alternative 1 is equal to n 1 q · n − n 1 k − q n k for the profile X and n − n 1 q · n k − q n k for X ′ . Selection of the alternative supported by majority contributes n 1 to the social cost for both profiles, while the sub-optimal costs n − n 1 . This allows to rewrite the right-hand side of (15):

SC g anym (X) + SC g anym (X ′ ) = = j∈[m] k q=0 n 1 q · n − n 1 k − q n k (n − n 1 )h q,j + n 1 (1 − h q,j ) + + n − n 1 q · n 1 k − q n k n 1 h q,j + (n − n 1 )(1 − h q,j ) .

To minimize this expression over h q,j ∈ [0, 1], one should minimize the contribution of the first summand whenever n 1 q · n − n 1 k − q n k > n − n 1 q · n k − q n k which leads to h q,j = 0; similarly, for the opposite strict inequality, it is optimal to minimize the second summand, which gives h q,j = 1. Therefore, the optimal h q,j equals 0 if q < k 2 and 1 if q > k 2 . Such h corresponds to the simple majority rule with arbitrary tie-breaking in case of a tie. Therefore, SC g anym (X) + SC g anym (X ′ ) ≥ SC k-SORT(X) + SC k-SORT(X ′ ) , which completes the proof.

Flexible representative democracy: an introduction with binary issues

Voting by proxy

Cryptodemocracy: How Blockchain Can Radically Expand Democratic Choice

Randomized social choice functions under metric preferences

Approximating optimal social choice under metric preferences

Elections, coalitions, and legislative outcomes

Alethea: A provably secure random sample voting protocol

Usability: low tech, high security

Straightforward elections, unanimity and phantom voters

Interactive democracy: New challenges for social choice theory

Random-sample voting

Of the people: voting is more effective with representative candidates

On the distortion of voting with multiple representative candidates

Proxy voting for better outcomes

Public opinion and direct democracy

The political potential of sortition: A study of the random selection of citizens for public office

Multiwinner voting: A new challenge for social choice theory

An introduction to probability theory and its applications

Deliberative polling for multistakeholder internet governance: considered judgments on access for the next billion

Sophisticated attacks on decoy ballots: The devil's menu and the market for lemons

Metric distortion of social choice rules: Lower bounds and fairness properties

The fluid dynamic of liquid democracy

Direct voting and proxy voting

Against elections: The lottocratic alternative

The Athenian democracy in the age of Demosthenes: structure, principles, and ideology

Probability inequalities for sums of bounded random variables

Risk-limiting tallies

Liquid democracy: An algorithmic perspective

Voting in combinatorial domains

A random zoo: sloth, unicorn, and trx

Algorithms for strategyproof classification

Representative democracy via random selection

Thwarting vote buying through decoy ballots

Stay away from fair coins: A condorcet jury theorem. Social Choice and Welfare

Logical constraints on judgement aggregation

Weighted representative democracy

The distortion of cardinal preferences in voting

Approximate mechanism design without money

On the absolute constants in the berry-esseen type inequalities for identically distributed summands

What do we elect committees for? a voting committee model for multi-winner rules

The case 1 6 ≤ p ≤ 1 2 . To estimate the probability of ξ ≥ k 2 , we use the tail bounds for hypergeometric random variables. They enjoy the usual Hoeffding inequalityas if ξ was the sum of k Bernoulli random variables with success probability p. The inequality for hypergeometric distribution is proved in the same paper of Hoeffding [1994] , see Section 5 there. From (10), we get P ξ ≥ k 2 ≤ exp − 1 2 (1 − 2p) 2 · k . Substituting this bound in (8), replacing p in denominator by its lower-bound 1 6 , and denoting 1 − 2p by t, we obtainGluing the two cases. For k ≥ 2, the upper bound (11) proved for 1 6 ≤ p ≤ 1 2 exceeds (9) derived for p ≤ 1 6 . Indeed,Therefore, (11) bounds the ratio of the social costs for any p and k ≥ 2. For k = 1, the right-hand side of (11) is equal to 1 + 6 exp − 1 2 ≈ 4.6, while the worst-case approximation ratio for 1-SORT (a random dictator) is below 2 by Example 3. Thus the approximation ratio satisfiesfor all n and k.Asymptotic tightness. We will consider the scenario where 2(k + 1) 2 ≤ n, i.e., the number of voters n is large compared to the committee size k. From (8), we deduce the lower bound:Let's estimate P ξ > k 2 from below for the hypergeometric distribution with parameters (n, n 1 = pn, k). If k ′ ≤ k balls are already taken and n ′ 1 ≤ k ′ of them are red, the chance to pick the next red ball isbe approximated by the normal law using the Berry-Esseen theorem (a version of the central limit theorem with a bound on approximation error [Shevtsova, 2011] )where we wrote 1 4 instead of Vη 1 ≤ 1 4 .Let the number of supporters for the suboptimal alternative beand hence 1 2 − 1 2 √ k + k n ≤ p < 1 2 − 1 2 √ k + k n + 1 n . Note that p ∈ 0, 1 2 by the assumption on n and k. We getSubstituting this into (12), we obtainInequalities Φ(−1) ≤ 1 2 and 2(k+1) n ≤ 1 k lead to the lower bound on the approximation ratiovalid for 2(k + 1) 2 ≤ n.

Proof of Proposition 3. Consider a preference profile X with i.i.d. issues. Without loss of generality, for every issue j ∈ [m], the majority of voters prefers the alternative 0 but not unanimously. We denote by p the fraction of supporters of the alternative 1, so 0 < p ≤ 1 2 . Consider first the case of small p < 1 2m , which will not require the independence assumption. By the union bound, at least 1 − pm > 1 2 fraction of all voters prefer the alternative 0 on every issue. Therefore, if the committee C contains a "zero" member that prefers 0 for every issue, he receives more than 1/2 of the total weight and the alternative 0 wins for all issues thus providing the socially optimal outcome.The probability that a random committee contains a zero member is at least 1 − (pm) k , therefore, the ratio of social costs satisfiesNow consider the case of 1 2m ≤ p ≤ 1 2 . Let's estimate that probability of the event A that for every sequence z ∈ {0, 1} m there is a committee member c ∈ C with x c = z. Given A, every voter delegates his vote to a committee member with exactly the same preferences as his own and thus the outcome of the committee vote coincides with the outcome of the majority vote of the whole population. Thus, if A occurs, the committee selects the socially-optimal outcome.We estimate the probability of A using the union bound. For any z ∈ {0, 1} m with q ones, the probability that there is no committee member with such preferences is is at most (1 − p q (1 − p) m−q ) k .Since there are Therefore SC k-wSORT (X) SC(z opt ) ≤ P(A) · p + (1 − P(A)) · (1 − p) p ≤ 1 + 2 m p (1 − p m ) k .