# distortion_in_voting_with_topt_preferences__f9ebae80.pdf

Distortion in Voting with Top-t Preferences

Allan Borodin1 , Daniel Halpern2 , Mohamad Latiﬁan1 , and Nisarg Shah1

1University of Toronto 2Harvard University bor@cs.toronto.edu, dhalpern@g.harvard.edu, {latiﬁan, nisarg}@cs.toronto.edu

A fundamental question in social choice and multiagent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identiﬁes near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.

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 efﬁcacy 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

Contact Author

led to a lack of consensus, even among social choice theorists, on which voting rules are the best. 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 difﬁcult 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 ap-

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Setting Upper and Lower Bounds

k = 1 Θ max m, m

t = m Θ min m

Lower Bound: Ω min m

Upper Bound: O min m

Table 1: A summary of our bounds for the ﬁrst moment distortion. Although there is a gap in the general case, bounds are tight in two interesting special cases.

plications 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 ﬁrst-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 Related Work 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 inﬁnite. In the metric framework, distortion under top-t preferences is better understood. For single winner selection (k = 1) with the ﬁrst 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 deﬁnitions), 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, deﬁne [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 P c C ui(c) = 1 for every i [Aziz, 2020]. We refer to u = (u1, . . . , un) as the utility proﬁle. For a committee X Pk(C), we deﬁne, 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) = Pn i=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 proﬁle. 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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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

Voting rule. A (randomized) voting rule f takes as input a preference proﬁle σ 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 ﬁx 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

distp(f, I) = sup σ:u σ

max Y Pk(C)[sw(Y, u)]p

EX f(σ)[(sw(X, u))p] .

The p-th moment distortion of f is obtained by taking the worst case over all instances: distp(f) = sup I 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 sufﬁcient. 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 Single Winner 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 ﬁll the gap between these two extremes. We show that the optimal distortion for top-t preferences is Θ(max(m/t, m)). Hence, it ﬁrst 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 signiﬁcantly 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( m log m) distortion, which is only logarithmically worse than the optimal distortion. They

deﬁne the harmonic score of candidate a as hsc(a) = P 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 1 2 hsc(a) P

b hsc(b) + 1

2 1 m. We show that a natural extension of this rule to top-t preferences achieves near-optimal distortion simultaneously for all p. We deﬁne 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) = P i:a σi([t]) 1/σ 1 i (a). Then, our rule, f h, chooses

every candidate a with probability 1

2 hsct(a) P

b hsct(b) + 1

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

distp(f h) 2 min m, p W(p) max (Ht m)

Here, Ht = Pt r=1 1 r is the t-th harmonic number and W(p) = Θ(log p) is the solution of W(p)e W (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 proﬁle σ = (σ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 proﬁle. We will show two separate upper bounds on the welfare approximation ratio sw(a)p 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,

sw(a)p P c C qc sw(c)p sw(a)p

qa sw(a)p = 1

For the second upper bound, we consider two cases depending on the truncated harmonic score hsct(a) of the opti-

mal candidate a. Fix τ = W (p)

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

2 hsct(a) P c C hsct(c) = 1

n Ht τ 2Ht .

Hence, by the same argument as above, the welfare approximation ratio is at most 1 qa 2Ht

τ = 2p W(p) (Ht m)

2p W(p) max (Ht m)

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,

sw(a) hsct(a) + n/t n (τ + 1/t).

1This is known as the Lambert W function.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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 P c C qc sw(c)p (1/2) (n/m)p. Together, these imply that

c C qc sw(c)p np (τ + 1/t)p

(1/2) (n/m)p

= 2 (mτ + m/t)p

= 2 (W (p)/p) (Ht m) 1 p+1 + m

2 (1 + W (p)/p)p max (Ht m) 1 p+1 , m

2 e W (p) max((Ht m) p p+1 , (m/t)p)

= 2p W(p) max((Ht m) p p+1 , (m/t)p).

Combining this with Case 1 yields the desired bound.

For p = 1, this bound is O(max( m log 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

distp(f) = Ω min m, max m

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 ﬁrst 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 satisﬁes 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}.

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

Deﬁnition 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 ﬁxed 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 satisﬁed for all S with |S | = 1, then it is satisﬁed 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 proﬁle into a ranked preference proﬁle, ﬁnds 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

dist(f mix) min 2m

k , 4 max m

Proof. We prove two separate upper bounds of 2m/k and 4 max(m/t, m) on dist(f mix). Fix an arbitrary instance (V, C, u) with top-t preference proﬁle σ induced by u. Let D = f mix(σ) be the distribution return by our rule, and qa = Pr S D[a S] be the marginal probability of candidate a being included in the chosen committee. Fix an optimal committee S arg max S 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,

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

we have ES D[sw(S, u)] (k/(2m)) sw(S ). Rearranging yields the desired distortion bound.

Second bound: Our desired bound is 4 max(m/t, m). We assume k m, otherwise 2m/k is already a stronger bound. Let ˆσ denote the arbitrarily completed ranked preference proﬁle, 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 Deﬁnition 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 ﬁrst 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 ﬁrst t positions. In this case, ui(S ) 1/t.

Now, we have

i V (S,S ) ui(S ) + X

i N(S,S ) ui(S ) + X

i G(S,S ) ui(S )

|V (S, S )| 1 + n (1/t) + X

i G(S,S ) ui(S)

|V (S, S )| + n/t + sw(S, u).

Next, we take the expectation over S S.

sw(S , u) n m + n

t + ES S[sw(S, u)]

2n min( m, t) + ES S[sw(S, u)]. (1)

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

sw(S , u) 2m W1 min( m, t) + m W2

2 max( m, m/t) (W1 + W2),

which yields the desired distortion bound of 4 max( 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

dist(f) = Ω min m

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 modiﬁed 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 deﬁne our harmonic score based rule f hc for committee selection. The rule is independent of p. Given a top-t preference proﬁle σ, 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 deﬁned in Section 3. At this point, Caragiannis et al. [2017], whose rule is only deﬁned for complete rankings with t = m, hence using hsc instead of hsct, deﬁne a marginal probability qa = α (k/m)+(1 α) k hsc(a) P

c C hsc(c), ﬁnd α such that qa 1 for all a, and compute a distribution over committees matching these marginal probabilities (which can be done efﬁciently using an extension of the

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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) P

c C hsct(c), 1). It can be shown that this is always feasible (indeed, P a C qa k and qa [0, 1] for all a) and efﬁciently 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

distp(f hc) 2 min

4p max (Ht m kp 1)

5.2 Lower Bounds Next, we establish two lower bounds via different proof methodologies. The ﬁrst 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

distp(f) = Ω min m

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

( Ω kΘ(p) , if k = O( m),

k p , if k = Ω( m log m).

Proof sketch. At a high level, the proof works as follows. We construct a simple proﬁle with n = m voters, each ranking a different candidate ﬁrst; the rest of the proﬁle is arbitrary. Further, the utilities are always such that there is a unique optimal committee S . All voters that rank a candidate a S ﬁrst 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 proﬁle, we can ﬁnd some S and its corresponding utility proﬁle so that the rule only achieves expected p-th moment social welfare of at most 1 ( m k) Pk h=0 k h 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 is at least 1 2 min k + 1

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

6 Discussion

Our work identiﬁes exciting technical open questions. While we identify tight distortion bounds for single winner selection (k = 1), for committee selection (k > 1) with the ﬁrst 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].

References [Amanatidis et al., 2021] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artiﬁcial Intelligence, 296:103488, 2021. [Anagnostides et al., 2021] Ioannis Anagnostides, Dimitris Fotakis, and Panagiotis Patsilinakos. Metric-distortion bounds under limited information. In Proc. of 14th SAGT, pages 299 313, 2021. [Anshelevich et al., 2021] Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in social choice problems: The ﬁrst 15 years and beyond. In Proc. of 30th IJCAI, pages 4294 4301, 2021. Survey Track. [Arrow, 1951] Kenneth Arrow. Social Choice and Individual Values. Wiley, 1951. [Aziz, 2020] Haris Aziz. Justiﬁcations of welfare guarantees under normalized utilities. ACM SIGecom Exchanges, 17(2):71 75, 2020. [Benade et al., 2021] Gerdus Benade, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813 2827, 2021. [Bentham, 1780] Jeremy Bentham. An Introduction to the Principles of Morals and Legislation. Dover Publications, 1780.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

[Borodin et al., 2019] Allan Borodin, Omer Lev, Nisarg Shah, and Tyrone Strangway. Primarily about primaries. In Proc. of 33rd AAAI, pages 1804 1811, 2019. [Boutilier et al., 2015] Craig Boutilier, Ioannis Caragiannis, Simir Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. Artiﬁcial Intelligence, 227:190 213, 2015. [Brill, 2019] Markus Brill. Interactive democracy: New challenges for social choice theory. In The Future of Economic Design, pages 59 66. Springer, 2019. [Budish et al., 2013] Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom. Designing random allocation mechanisms: Theory and applications. American economic review, 103(2):585 623, 2013. [Caragiannis et al., 2017] Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artiﬁcial Intelligence Research, 58:123 152, 2017. [Cheng et al., 2020] Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang. Group fairness in committee selection. ACM Transactions on Economics and Computation (TEAC), 8(4):1 18, 2020. [Condorcet, 1785] Marquis de Condorcet. Essai sur l application de l analyse a la probabilit e de d ecisions rendues a la pluralit e de voix. Imprimerie Royal, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York. [Drummond and Boutilier, 2013] Joanna Drummond and Craig Boutilier. Elicitation and approximately stable matching with partial preferences. In Proc. of 23rd IJCAI, pages 97 105, 2013. [Dwork et al., 2001] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proc. of 10th WWW, pages 613 622, 2001. [Ebadian et al., 2022] Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized fairness and distortion in voting. In Proc. of 23rd EC, 2022. Available at https://arxiv.org/ abs/2205.15760. [Ephrati and Rosenschein, 1997] Eithan Ephrati and Jeffrey S. Rosenschein. A heuristic technique for multi-agent planning. Annals of Mathematics and Artiﬁcial Intelligence, 20(1):13 67, 1997. [Fain et al., 2017] Brandon Fain, Ashish Goel, Kamesh Munagala, and Sukolsak Sakshuwong. Sequential deliberation for social choice. In Proc. of 13th WINE, pages 177 190, 2017. [Fain et al., 2020] Brandon Fain, William Fan, and Kamesh Munagala. Concentration of distortion: The value of extra voters in randomized social choice. In Proc. of 29th IJCAI, pages 110 116, 7 2020. [Filmus and Oren, 2014] Yuval Filmus and Joel Oren. Efﬁcient voting via the top-k elicitation scheme: a probabilistic approach. In Proc. of 15th EC, pages 295 312, 2014. [Filos-Ratsikas et al., 2019] Aris Filos-Ratsikas, Evi Micha, and Alexandros A. Voudouris. The distortion of distributed voting. In Proc. of 12th SAGT, pages 312 325. Springer, 2019. [Flanigan et al., 2021] Bailey Flanigan, Paul G olz, Anupam Gupta, Brett Hennig, and Ariel D. Procaccia. Fair algorithms for selecting citizens assemblies. Nature, 596(7873):548 552, 2021. [Gkatzelis et al., 2020] Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion conjecture. In Proc. of 61st FOCS, pages 1427 1438. IEEE, 2020.

[Gross et al., 2017] Stephen Gross, Elliot Anshelevich, and Lirong Xia. Vote until two of you agree: Mechanisms with small distortion and sample complexity. In Proc. of 31st AAAI, 2017. [Halpern and Shah, 2021] Daniel Halpern and Nisarg Shah. Fair and efﬁcient resource allocation with partial information. In Proc. of 30th IJCAI, pages 224 230, 2021. [Haynes et al., 1997] Thomas Haynes, Sandip Sen, Neeraj Arora, and Rajani Nadella. An automated meeting scheduling system that utilizes user preferences. In Proc. of 1st AGENTS, pages 308 315, 1997. [Hosseini et al., 2021] Hadi Hosseini, Vijay Menon, Nisarg Shah, and Sujoy Sikdar. Necessarily optimal one-sided matchings. In Proc. of 35th AAAI, pages 5481 5488, 2021. [Kempe, 2020a] David Kempe. An analysis framework for metric voting based on lp duality. In Proc. of 34th AAAI, pages 2079 2086, 2020. [Kempe, 2020b] David Kempe. Communication, distortion, and randomness in metric voting. In Proc. of 34th AAAI, pages 2087 2094, 2020. [Lang and Xia, 2016] J erˆome Lang and Lirong Xia. Voting in combinatorial domains. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 9, pages 197 222. Cambridge University Press, 2016. [Lee et al., 2014] David T. Lee, Ashish Goel, Tanja Aitamurto, and H el ene Landemore. Crowdsourcing for participatory democracies: Efﬁcient elicitation of social choice functions. In Proc. of 2nd AAAI Conference on Human Computation and Crowdsourcing (HCOMP), pages 133 142, 2014. [Lesser et al., 2003] Victor Lesser, Charles L. Ortiz Jr., and Milind Tambe. Distributed sensor networks: A multiagent perspective, volume 9. Springer Science & Business Media, 2003. [Lu and Boutilier, 2011] Tyler Lu and Craig Boutilier. Vote elicitation with probabilistic preference models: Empirical estimation and cost tradeoffs. In Proc. of 2nd ADT, pages 135 149, 2011. [Mandal et al., 2019] Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, and David P. Woodruff. Efﬁcient and thrifty voting by any means necessary. In Proc. of 33rd NIPS, pages 7178 7189, 2019. [Mandal et al., 2020] Debmalya Mandal, Nisarg Shah, and David P. Woodruff. Optimal communication-distortion tradeoff in voting. In Proc. of 21st EC, pages 795 813, 2020. [Oren et al., 2013] Joel Oren, Yuval Filmus, and Craig Boutilier. Efﬁcient vote elicitation under candidate uncertainty. In Proc. of 23rd AAAI, 2013. [Pitt et al., 2006] Jeremy Pitt, Lloyd Kamara, Marek Sergot, and Alexander Artikis. Voting in multi-agent systems. The Computer Journal, 49(2):156 170, 2006. [Procaccia and Rosenschein, 2006] Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. In Proc. of 10th CIA, pages 317 331, 2006. [Procaccia et al., 2012] Ariel D. Procaccia, Sashank J. Reddi, and Nisarg Shah. A maximum likelihood approach for selecting sets of alternatives. In Proc. of 28th UAI, pages 695 704, 2012. [Shoham and Leyton-Brown, 2008] Yoav Shoham and Kevin Leyton-Brown. Multiagent systems: Algorithmic, gametheoretic, and logical foundations. Cambridge University Press, 2008.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)