Distortion in Voting with Top-t Preferences

1 Introduction

A common task in multi-agent systems is to make collective decisions that serve multiple agents well in a measurable sense, and voting is a frequently-used tool for this purpose [Shoham and Leyton-Brown, 2008; Pitt et al., 2006], in applications such as human computation [Procaccia et al., 2012], distributed sensor networks [Lesser et al., 2003], meeting scheduling [Haynes et al., 1997], planning [Ephrati and Rosenschein, 1997], and rank aggregation for the web [Dwork et al., 2001].

Voting has been studied for centuries in social choice theory, dating back to the early work by Condorcet [1785], in which voters rank candidates, and the goal is to select one or more candidates. But the prominent approach for evaluating the efficacy of voting rules has been the axiomatic approach, which is more qualitative in nature and has resulted in celebrated impossibility results [Arrow, 1951]. Arguably, this has led to a lack of consensus, even among social choice theorists, on which voting rules are the "best."

∗Contact Author

A recent wave of interest in voting from computer science has provided a fundamentally new perspective for quantitatively evaluating voting rules. Procaccia and Rosenschein [2006] propose to view the ranked preferences submitted by voters over candidates as proxies for their underlying numerical utility functions. This assumption allows one to focus on a canonical quantitative goal: maximizing the (utilitarian) social welfare [Bentham, 1780]. They propose to judge voting rules by their distortion, the worst-case approximation ratio between the maximum possible social welfare given complete utility functions and the (expected) social welfare achieved by the voting rule given only the partial preference information. Hence, distortion is the "price" of missing information and acts as a yardstick for answering the age-old question: Which voting rules are the best?

Boutilier et al. [2015] identify a near-optimal randomized voting rule for selecting a single candidate given ranked preferences of voters. Caragiannis et al. [2017] extend their analysis to deterministic and randomized rules for selecting a committee of candidates of a given size k. Since then, the distortion literature has proliferated, and the idea has been applied to settings even beyond voting; we refer the reader to the recent survey by Anshelevich et al. [2021] for a detailed overview of the results.

Of particular interest to us is the observation that once we surmise the existence of underlying utility functions, we do not need to stick with asking voters to rank candidates. As Benade et al. [2021] observe, distortion can be used to evaluate and compare different elicitation formats (i.e., ballot designs). Mandal et al. [2019] and Mandal et al. [2020] stretch this to the extreme, allowing arbitrary elicitation formats and studying the tradeoff between the number of bits they extract from each voter and the distortion they enable. However, this can lead to unintuitive elicitation formats, which may be difficult for humans to answer.

Another line of work focuses on intuitive elicitation formats that are either more expressive than ranked preferences [Amanatidis et al., 2021] or less expressive [Gross et al., 2017; Kempe, 2020b; Halpern and Shah, 2021]. A common less-expressive format is top-t preferences, where each voter ranks only her t most favorite candidates instead of ranking all candidates. This is particularly well-suited in applications where we have far too many candidates to choose from [Procaccia et al., 2012]. Kempe [2020b] studies the distortion under this type of preferences in the metric framework, where voters have costs rather than utilities. In this paper, our main goal is to study distortion with top-t preferences under the original utilitarian framework.

1.1 Our Results

We consider selecting a committee of a given size k given top-t preferences of the voters over the candidates, under the model in which a voter's utility for a committee is her maximum utility for any candidate in the committee. We consider approximating the social welfare, and also generalize our results to approximating the p-th power of the social welfare for p ⩾ 1, as advocated by Fain et al. [2020]. As described in Section 2, the results of Caragiannis et al. [2017] can be used to immediately settle this question for deterministic voting rules; hence, we focus exclusively on randomized rules.

Considering the standard first-moment distortion (p = 1) and single-winner selection (k = 1), we identify a tight bound of Θ(max(√m,m/t)) using a recently-introduced technique [Ebadian et al., 2022]. Strikingly, the optimal distortion is already achieved asymptotically with t = √m. In practical terms, this is encouraging, as it may be much more feasible for voters to rank √m rather than m alternatives.

Furthermore, for committee selection (k ⩾ 1), we are able to extend this to an upper bound of O(min (m/k,max (√m,m/t))). For the case of full rankings (t = m), this matches the lower bound of Caragiannis et al. [2017], closing a m1/6 gap they left open. This resolves the optimal distortion for committee selection as Θ(min(m/k, √m)). The lower bound of Caragiannis et al. [2017] continues to match our upper bound when k ⩾ √m (with arbitrary t) or k ⩽ √m ⩽ t. However, when k, t ⩽ √m, our lower bound of Ω(max(√m,m/kt)) is weaker than our upper bound of O(m/max(k,t)). A visualization of our results is show in Table 1.

Finally, as a theoretical curiosity, we extend our bounds to higher moments (p > 1), where for single winner selection our bound is tight up to the log t factor, but in the case of committee selection, we leave open substantial gaps.

1.2 RelatedWork

To the best of our knowledge, the only work that comes close to studying distortion under top-t preferences in the utilitarian framework is that of Mandal et al. [2019]. They propose a voting rule, PREFTHRESHOLD, which asks voters to report the set of their t most preferred candidates along with their approximate utilities for these candidates, by partitioning the utility space into discrete buckets and asking the voters to identify the appropriate buckets. Their distortion bound is only comparable to ours when their rule uses a single bucket, for which their bound is infinite.

In the metric framework, distortion under top-t preferences is better understood. For single winner selection (k = 1) with the first moment (p = 1), Kempe; Kempe [2020b; 2020a] proves a lower bound of (2m- t)/t and an asymptotically matching upper bound of 12m/t. Recently, Anagnostides et al. [2021] improve the upper bound to 6m/t and show that this can be further improved to (4m-t)/t if a generalization of a combinatorial lemma due to Gkatzelis et al. [2020] holds.

While top-t preferences are relatively less explored in the distortion setting, they are very well studied more broadly in voting [Oren et al., 2013; Lee et al., 2014; Lu and Boutilier, 2011; Filmus and Oren, 2014] and in settings beyond voting [Drummond and Boutilier, 2013; Hosseini et al., 2021].

Finally, following Caragiannis et al. [2017], we use the model where the utility of a voter for a committee is her maximum utility for any candidate in the committee. This is in the style of common voting rules such as the Chamberlin-Courant rule and the Monroe rule (see [Lang and Xia, 2016] for definitions), which aim to select committees in which every voter has a candidate representing her. An alternative model would be to model the utility of a voter for a committee as the sum of her utilities for the candidates in the committee, which has also been considered in the literature [Benade et al., 2021].

2 Preliminaries

For t ∈ N, define [t] = {1, . . . , t}. Let V = [n] be a set of n voters and C be a set of m candidates. We use indices i, j to denote voters and letters a, b, c to denote candidates. A committee is a subset of candidates. In this work, we consider selecting a committee of a given size k ∈ [m]. Let Pk(C) denote the set of all committees of size k. When k = 1, we refer to it as single winner selection.

Voter utilities. Each voter i has a utility ui(c) ∈ R⩾0 for every candidate c; we assume the standard normalization that ∑c∈C ui(c) = 1 for every i [Aziz, 2020]. We refer to u = (u1, . . . , un) as the utility profile. For a committee X ∈ Pk(C), we define, with slight abuse of notation, the utility of voter i for X as ui(X) = maxc∈X ui(c). This is a standard extension studied in the literature [Caragiannis et al., 2017], whereby a voter cares about having some representative in the committee that they like. The (utilitarian) social welfare of X is then given by sw(X, u) = ∑ni=1 ui(X); for X = {c}, we simply write sw(c, u). When the utilities are clear from context, we may drop them from the notation and simply write sw(X) or sw(c).

Preference profile. We do not directly observe voters' underlying utility functions. Instead, we ask each voter i to submit a ranking of her t most preferred candidates, denoted by a one-to-one function σi : [t] → C satisfying ui(σi(1)) ⩾ . . . ⩾ ui(σi(t)) ⩾ ui(c) for all c ∈ C \ σi([t]). We allow the voter to break any ties arbitrarily. We refer to

σ = (σ1, . . . , σn) as the preference profile. We use u ▷ σ to denote that preference profile σ is induced from the underlying utility profile u.

Voting rule. A (randomized) voting rule f takes as input a preference profile σ and outputs a distribution f(σ) over committees of size k. We say that the voting rule is deterministic if it always returns a distribution with singleton support, in which case we use f(σ) to denote the unique committee of size k in the support.

Distortion. Roughly speaking, the distortion captures how far the candidate elected by f can be from the optimal alternative. More formally, let I be an instance in this model which is given by the tuple (V,C, u). When evaluating distortion, we fix the number of candidates m. Let I denote the set of all instances with m candidates. Fix p ∈ N>0. Following Fain et al. [2017] and Fain et al. [2020], the p-th moment distortion of voting rule f on an instance I = (V, C, u) is given by

The p-th moment distortion of f is obtained by taking the worst case over all instances: distp (f) = supI∈I distp (f, I).

Note that for deterministic rules, since there is no expectation in the denominator, the choice of p does not affect the distortion as it cancels out; hence, analyzing p = 1 is sufficient. For p = 1, Caragiannis et al. [2017] prove that a deterministic rule achieves distortion 1 + m(m - k)/k even with t = 1, and no deterministic rule can be asymptotically better even when t = m. Hence, this provides asymptotically optimal distortion bounds for all values of t, k, and p. Consequently, in this work, we focus exclusively on randomized voting rules.

3 SingleWinner Selection

Let us begin by analyzing the distortion for single winner selection given top-t preferences. Given only plurality votes (t = 1), it is known that the best possible distortion is m, which can be achieved by selecting a uniformly random candidate (see, e.g. [Mandal et al., 2019, Proposition 1]). On the other hand, given ranked preferences (t = m), Boutilier et al. [2015] pinpoint the optimal distortion to be between O(√m· log∗ m) and Ω(√m), and Ebadian et al. [2022] close this gap to establish a Θ(√m) bound.

In this section, we fill the gap between these two extremes. We show that the optimal distortion for top-t preferences is Θ(max(m/t, √m)). Hence, it first decreases from m to Θ(√m) as t increases from 1 to Θ(√m), but then remains Θ(√m) as t increases further. In a sense, this shows that after eliciting the top-Θ(√m) preferences of the voters, eliciting the rest of their preference ranking does not significantly help. Our analysis extends to the p-th moment with a logarithmic gap when p > 1.

3.1 Upper Bound

For ranked preferences, Boutilier et al. [2015] show that a simple rule achieves O(√mlogm) distortion, which is only logarithmically worse than the optimal distortion. They define the harmonic score of candidate a as hsc(a) = ∑i 1/σ-1 i (a); that is, candidate a gets 1/r points whenever it appears in the r-th position in a voter's preference ranking. Then, their rule chooses each candidate a with probability 12 hsc(a) ∑b hsc(b) + 12 1m .

We show that a natural extension of this rule to top-t preferences achieves near-optimal distortion simultaneously for all p. We define the truncated harmonic score of candidate a, whereby the candidate still gets 1/r points whenever it appears in the r-th position for r ⩽ t, but gets zero points if it does not appear in the top t positions; that is, hsct(a) = ∑i:a∈σi([t]) 1/σ-1 i (a). Then, our rule, f h , chooses hsct (a)

Theorem 1. For all p ⩾ 1 and t ∈ [m], we have that

Here, Ht = ∑tr=1 1r is the t-th harmonic number and W(p) = Θ(log p) is the solution of W(p)eW(p) = p. 1 Asymptotically, Ht ∈ Θ(log t) and W(p) ∈ Θ log(p).

Proof. Fix an arbitrary instance I = (V,C, u) with top-t preference profile σ = (σ1, . . . , σn) induced by u. Fix an optimal candidate a ∈ arg maxc∈C sw(c). Let qc be the probability by which f h chooses candidate c on this profile.

We will show two separate upper bounds on the welfare approximation ratio sw(a)p ∑c∈C qc·sw(c)p ; then, taking the minimum of the two ratios yields the bound stated in the theorem.

First, an upper bound of 2m follows directly from the fact that qa ⩾ 1/(2m). Hence,

For the second upper bound, we consider two cases depending on the truncated harmonic score hsct(a) of the optimal candidate a. Fix τ = W(p) p · ( Ht mp )1/(p+1) . We consider hsct(a) ⩾ nτ and hsct(a) < nτ, and show that the desired upper bound holds in both cases.

Case 1: First, suppose hsct(a) ⩾ nτ . We have that

Hence, by the same argument as above, the welfare approximation ratio is at most

Case 2: Next, suppose hsct(a) < nτ. Note that the utility of voter i for a is at most 1/r if the voter ranks a in the r-th position, for some r ⩽ t, and at most 1/t otherwise. Hence,

1 This is known as the Lambert W function.

The expected social welfare when picking a uniformly random candidate is n/m, which implies that, by Jensen's inequality, the expected p-th moment of social welfare is at least (n/m)p . Since our rule f h implements this with probability 1/2, we have ∑c∈C qc · sw(c)p ⩾ (1/2) · (n/m)p . Together, these imply that

Combining this with Case 1 yields the desired bound.

For p = 1, this bound is O(max(√mlog t,m/t)). In this special case, we can eliminate the √log t factor by extending a recent technique due to Ebadian et al. [2022]. This follows directly from Theorem 4 presented in Section 4.

Proposition 1. For t ∈ [m] and p = 1, there exists a randomized rule whose distortion is O(max(√m, m/t)).

3.2 Lower Bound

Next, we show that the bound achieved in the previous subsection is tight up to the (log t)p/(p+1) factor. For p = 1, the following lower bound is Ω(max(√m,m/t)), precisely matching the upper bound from Proposition 1. The proof of the following result, along with the other missing proofs, can be found in the full version. 2

Theorem 2. Fix constant p ⩾ 1. Every randomized rule f for selecting a single winner given top-t preferences has

4 Committee Selection for the First Moment

We now turn our attention to selecting a committee of size k ⩾ 1 given top-t preferences. In this section, we focus on the first moment, for which we are able to derive tight distortion bounds. The next section focuses on committee selection with higher moments , for which our bounds are not tight.

4.1 Upper Bound

In order to derive the upper bound, we extend a recent approach introduced by Ebadian et al. [2022]. They use it to derive an optimal Θ(√m) bound for single winner selection (k = 1) given full rankings. We extend this to all k, t ∈ [m].

The approach relies on another recent result due to Cheng et al. [2020]. They consider randomized committee selection that satisfies a compelling stability/fairness property. For a pair of committees S, S′ ⊆ C, we say that S′ ≻i S if voter i ranks her most preferred candidate in S′ above her most preferred candidate in S. Let V (S, S′ ) = {i ∈ V : S′ ≻i S}.

2 https://www.cs.toronto.edu/∼nisarg/papers/distortion-top-t.pdf

Definition 1 (Stable Lotteries). Fix t ∈ [m]. A distribution S over committees of size t is said to be stable if, for every committee S′ with |S′ | ⩽ t, we have ES∼S[|V (S, S′ )|] ⩽ n · |S′ |/t.

Note that when a committee S is sampled from a stable lottery S, the fraction of voters preferring any other fixed committee S′ over S is bounded, in expectation, by the ratio of the sizes of S′ and S. In other words, a small committee cannot be preferred by many voters. It is worth noting that if the property is satisfied for all S′ with |S′ | = 1, then it is satisfied for all S′ with |S′ | ⩽ t (see [Cheng et al., 2020]).

Theorem 3 (Cheng et al. [2020]). Given ranked preferences and t ∈ [m], a stable lottery over committees of size t always exists.

We note that Cheng et al. [2020] also provide a poly(mt , 1/ϵ) time algorithm to compute an ϵ-approximately stable lottery. Using that in our analysis only affects the distortion bound by a factor of 1 + ϵ. For simplicity, we work with exactly stable lotteries.

Given ranked preferences, Ebadian et al. [2022] show that if S is a stable lottery over committees of size t = √m, then picking a candidate uniformly at random from a committee S ∼ S with probability 1/2 and picking a uniformly random candidate from C with probability 1/2 yields distortion O(√m) for single winner selection with p = 1.

We want to extend this to select a committee of size k given only top-t preferences. Our rule, f mix , is a combination of two rules.

• f unif picks a uniformly random committee U of size k.
• f stable arbitrarily completes the partial preference profile into a ranked preference profile, finds a stable lottery S over committees of size k√m, samples S ∼ S, and then picks a uniformly random subset S′ ⊆ S of size k.

If k > √m, f mix applies f unif . Otherwise, it applies f stable with probability 1/2 and f unif with probability 1/2.

Note that while Ebadian et al. [2022] use a stable lottery over committees of size √m to pick a single candidate, f stable uses a stable lottery over committees of size k√m to pick a committee of size k. While this approach does not work when k > √m (since then k√m > m), that case turns out to be rather easy to address. Finally, note that we are able to handle the partial top-t preferences by simply extending them arbitrarily to complete ranked preferences!

Theorem 4. For all k, t ∈ [m], we have that

Proof. We prove two separate upper bounds of 2m/k and 4max(m/t, √m) on dist(f mix ). Fix an arbitrary instance (V,C, u) with top-t preference profile σ induced by u. Let D = f mix (σ) be the distribution return by our rule, and qa = PrS∼D[a ∈ S] be the marginal probability of candidate a being included in the chosen committee. Fix an optimal committee S∗ ∈ argmaxS∈Pk(C) sw(S).

First bound: Since f mix executes f unif with probability at least 1/2, we have that qa ⩾ k/(2m) for all a ∈ C. Hence, we have ES∼D[sw(S, u)] ⩾ (k/(2m)) · sw(S∗ ). Rearranging yields the desired distortion bound.

Second bound: Our desired bound is 4max(m/t, √m). We assume k ⩽ √m, otherwise 2m/k is already a stronger bound. Let ˆσ denote the arbitrarily completed ranked preference profile, and let S be the stable lottery computed in f stable for ˆσ. Fix a committee S in the support of S. Let us partition the set of voters V into three:

• V (S, S∗ ) includes every voter i for whom S∗ ≻i S under ˆσ. From Definition 1, ES∼S[|V (S, S∗ )|] ⩽ n/√m.
• G(S∗ , S) includes every voter i for whom S ≻i S∗ and she ranks her favorite candidate from S in the first t positions. This guarantees ui(S) ⩾ ui(S∗ ).
• N(S∗ , S) includes every voter i for whom S ≻i S∗ but she ranks her favorite candidate from S after the first t positions. In this case, ui(S∗ ) ⩽ 1/t.

Now, we have

Next, we take the expectation over S ∼ S.

Let W1 be the expected social welfare under f unif and W2 be the expected social welfare under f stable . The expected social welfare under f mix is (W1 +W2)/2. We express the RHS in Equation (1) in terms of W1 and W2.

First, Caragiannis et al. [2017] argue that W1 is at least n/m. Next, consider S′ ⊆ S of size |S′ | = k chosen uniformly at random. For each voter i, her most favorite candidate in S is included in S′ with probability |S′ |/|S| = 1/√m. Hence, ES′ [ui(S′ )] ⩾ ui(S)/√m. Summing over all voters and taking the expectation over S ∼ S, W2 = ES,S′ [sw(S′ , u)] ⩾ ES[sw(S, u)]/√m. Hence, ES [sw(S, u)] ⩽ √m · W2.

Plugging these into Equation (1), we get

which yields the desired distortion bound of 4max(√m,m/t) upon rearranging.

4.2 Lower Bound

We now turn our attention to lower bounds. Caragiannis et al. [2017] already prove a lower bound of

Ω(min(m/k, √m)) that holds even with fully ranked preferences (t = m), which obviously holds for all t ⩽ m. This matches the upper bound from Theorem 4 when k ⩾ √m or when k ⩽ √m ⩽ t. In the remaining region of k, t ⩽ √m, the upper bound from Theorem 4 is O(min(m/k,m/t)); for this case, we are able to establish a weaker lower bound of Ω(m/(kt)). We do not provide a separate proof of the Ω(m/(kt)) lower bound because it is implied by Theorem 6 in the next section.

Proposition 2. Every randomized rule f for selecting a committee of size k given top-t preferences has

Crucially, note that there is no gap between our upper and lower bounds when k = O(1), t = O(1), k ⩾ √m, or k ⩽ √m ⩽ t. Particularly, for ranked preferences (t = m), we derive a tight distortion bound of Θ(min(m/k, √m)), which was posed as an open question by Caragiannis et al. [2017]. Their upper bound was loose by a factor of O(m1/6 ). While our upper bound in Theorem 4 eliminates this completely using a technique very different from theirs, our upper bound in the next section would show that even their technique can be modified to eliminate this factor up to a logarithmic term.

5 Committee Selection for Higher Moments

Finally, we consider the p-th moment distortion, with p > 1, for selecting a committee of size k given top-t preferences. Unfortunately, the ingenious approach of Ebadian et al. [2022] to utilize stable lotteries to bound distortion seems to break down for higher moments. If we want a committee sampled from such a lottery to well-approximate the optimal p-th moment of the social welfare, it forces us to use a lottery over committees larger than kt; however, this reduces the performance of subsampling of a size-k committee, resulting in unappealing distortion bounds.

In contrast, we prove that the approach of Caragiannis et al. [2017], which extends the harmonic score based approach of Boutilier et al. [2015], continues to work reasonably well for higher moments. In doing so, we identify and improve upon a suboptimal step in their approach. For p = 1 and t = m, this is what reduces their m1/6 gap to a logarithmic gap, as mentioned above.

5.1 Upper Bound

Let us define our harmonic score based rule f hc for committee selection. The rule is independent of p. Given a top-t preference profile σ, the rule works as follows. With probability 1/2, it picks a uniformly random committee of size k. With the remaining probability 1/2, it does the following. First, it computes the truncated harmonic score hsct(c) of every candidate c, as defined in Section 3. At this point, Caragiannis et al. [2017], whose rule is only defined for complete rankings with t = m, hence using hsc instead of hsct, define a marginal probability qa = α·(k/m)+(1-α)·k· hsc(a) ∑c∈C hsc(c) , find α such that qa ⩽ 1 for all a, and compute a distribution over committees matching these marginal probabilities (which can be done efficiently using an extension of the Birkhoff-von Neumann theorem due to Budish et al. [2013]). Instead, we compute a distribution over committees such that the marginal probability of each candidate a being included is at least qa =min(k· hsct(a) ∑c∈C hsct(c) , 1). It can be shown that this is always feasible (indeed, ∑a∈C qa ⩽ k and qa ∈ [0, 1] for all a) and efficiently computable. This change in the marginal probabilities allows us to improve upon their bounds.

Theorem 5. For all p ⩾ 1 and k, t ∈ [m], we have that

5.2 Lower Bounds

Next, we establish two lower bounds via different proof methodologies. The first bound is achieved using a more straightforward analysis.

Theorem 6. Fix constant p ⩾ 1. Every randomized rule f for selecting a committee of size k given top-t preferences has

The next bound requires a more intricate analysis; a proof sketch is presented below.

Theorem 7. Fix constant p ⩾ 1. Every randomzied rule f for selecting a committee of size k given top-t preferences has

Proof sketch. At a high level, the proof works as follows. We construct a simple profile with n = m voters, each ranking a different candidate first; the rest of the profile is arbitrary. Further, the utilities are always such that there is a unique optimal committee S∗ . All voters that rank a candidate a ∈ S∗ first have utility 1 for a and 0 for the other candidates; all other voters have utility 1/m for all candidates. Note that under these utilities, S∗ uniquely has the highest p-th moment social welfare of (k + m-k m )p . We then use an averaging argument to claim that regardless of the distribution picked by the rule on this profile, we can find some S∗ and its corresponding utility profile so that the rule only achieves expected p-th moment social welfare of at most 1 (kh) · (m-k k-h ) · (h + m-k m )p . The remainder of the

proof is dedicated to bounding the ratio of these two values. Namely, we use the Chernoff bounds on binomial random variables to upper bound the binomial sum. This allows us to make the following claim: for all c ⩾ 2 · k2 m-k , the distortion

(mk) · ∑kh=0 is at least

The final part of the proof is optimizing the value of c to get the tightest bound.

6 Discussion

Our work identifies exciting technical open questions. While we identify tight distortion bounds for single winner selection (k = 1), for committee selection (k > 1) with the first moment (p = 1), there is a gap between our upper bound of O(m/kt) and our lower bound of O(m/max(k,t)) in the case where k, t ⩽ √m. We remark that in practice, it is common for k and t to be very small, for which the gap between our upper and lower bounds is also small. However, it would be interesting to close these gaps.

In the full version, we also prove encouraging preliminary results for the metric distortion framework. We identify tight distortion bounds for single winner selection (k = 1) with an arbitrary moment p, but our bounds for committee selection are off by a polynomial factor. Closing this gap would also be of immediate interest.

More broadly, an interesting direction for future work is to study distortion under other realistic settings and thrifty elicitation methods. For example, what is the best possible distortion if we have access to the ranked (or top-t) preferences of only a subset of randomly sampled voters? What if these voters are not sampled randomly? What if the preferences of the voters are not worst case, but instead stochastic (and possibly correlated)?

Casting an even broader net, the distortion framework is highly versatile and can shed a new light on quantitatively evaluating the effectiveness of more complex collective decision-making paradigms such as distributed elections [Filos-Ratsikas et al., 2019], participatory budgeting [Benade et al., 2021], and primaries [Borodin et al., 2019]. An exciting direction for the future is to use this framework to analyze real-world decision-making paradigms such as sortition [Flanigan et al., 2021] and liquid democracy [Brill, 2019].