# lowdistortion_social_welfare_functions__f9e8ede1.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Low-Distortion Social Welfare Functions

Gerdus Benad e Tepper School of Business Carnegie Mellon University

Ariel D. Procaccia Computer Science Department Carnegie Mellon University

Mingda Qiao Computer Science Department Stanford University

Work on implicit utilitarian voting advocates the design of preference aggregation methods that maximize utilitarian social welfare with respect to latent utility functions, based only on observed rankings of the alternatives. This approach has been successfully deployed in order to help people choose a single alternative or a subset of alternatives, but it has previously been unclear how to apply the same approach to the design of social welfare functions, where the desired output is a ranking. We propose to address this problem by assuming that voters utilities for rankings are induced by unknown weights and unknown utility functions, which, moreover, have a combinatorial (subadditive) structure. Despite the extreme lack of information about voters preferences, we show that it is possible to choose rankings such that the worst-case gap between their social welfare and that of the optimal ranking, called distortion, is no larger (up to polylogarithmic factors) than the distortion associated with much simpler problems. Through experiments, we identify practical methods that achieve nearoptimal social welfare on average.

1 Introduction Classical social choice theory typically approaches the problem of preference aggregation from an axiomatic viewpoint, that is, researchers formulate attractive properties, and ask whether there are methods that satisfy them. By contrast, research in computational social choice (Brandt et al. 2016) is often guided by optimization, in that researchers specify quantitative measures of the desirability of different alternatives, and construct methods that optimize them. One such approach is known as implicit utilitarian voting (Procaccia and Rosenschein 2006; Boutilier et al. 2015; Caragiannis et al. 2017). In a nutshell, the idea is that each voter i has a utility function ui that assigns a value to each alternative. However, these utility functions are implicit, in the sense that they cannot be communicated by the voters (because they are unknown or difﬁcult to pin down). Instead, voters report rankings of the alternatives that are consistent with the underlying utility functions, that is, each voter sorts the alternatives in non-increasing order of utility. The goal is to choose an alternative a that maximizes (utilitarian) social welfare the sum of utilities P

i ui(a) using the reported rankings as a proxy for the latent utility functions.

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

From that viewpoint, the best method is the one that minimizes a measure called distortion, deﬁned by Procaccia and Rosenschein (2006) as the ratio between the social welfare of the best alternative, and the social welfare of the alternative selected by the method, in the worst case over all utility functions that are consistent with the observed rankings. Put another way, this is the approximation ratio to the welfaremaximizing solution, and the need for approximation stems from lack of information about the true utilities. In recent years, implicit utilitarian voting has emerged as a practical approach for helping groups of people make joint decisions. In particular, optimal social choice functions and social choice correspondences, based on the implementation of Caragiannis et al. (2017), are deployed on the notfor-proﬁt website Robo Vote.org for the case where the desired output is a single alternative or a subset of winning alternatives, respectively. However, Robo Vote also has a third output type, a ranking of the alternatives, and for this case the website currently does not take the same approach instead it uses the wellknown rule by Kemeny (1959). Indeed, it is unclear how to even view the problem of designing a social welfare function, which returns a ranking, through the lens of implicit utilitarian voting if a voter has a utility for each alternative, what is his utility for a ranking of the alternatives? One could assume that a voter i has a weight wi,j for each position j, so his utility for the ranking (a1, a2, . . . , am) would be Pm j=1 wi,jui(aj); but any particular choice of weights would be ad hoc.

1.1 Our Approach and Results The insight underlying our approach is that the worst-case perspective also extends to the choice of weights. That is, when we measure the social welfare of an output ranking given reported input rankings, we consider the worst case over both utility functions and weights. Of course, this is a very conservative approach, and one might worry that it would lead to massive distortion. But our main theoretical result is that the distortion of optimal social welfare functions is asymptotically identical to that of optimal social choice functions (where there are no weights whatsoever), up to a polylogarithmic factor in both cases it is Θ( m), where m is the number of alternatives. In fact, we establish a signiﬁcantly stronger result, as we

allow voters to have combinatorial utility functions over subsets of alternatives, and we measure the utility of a voter for a ranking as the weighted sum of his utilities for preﬁxes of that ranking; the foregoing distortion bound holds when the utility functions are monotonic and subadditive. We ﬁnd it striking that it is possible to formulate the problem in such generality with no tangible increase in distortion. Our computational results demonstrate that it is practical to compute deterministic distortion-minimizing rankings for instances with up to 10 alternatives. This constraint on the instance size is not unreasonable, as 98.3% of Robo Vote instances have 10 or fewer alternatives. For larger instances we test several heuristics and ﬁnd that the Borda and Kemeny rules typically lead to low distortion and near-optimal social welfare.

1.2 Related Work

Generally speaking, the implicit utilitarian voting literature can be partitioned into two complementary strands of research. One does not constrain the structure of voters utility functions (Procaccia and Rosenschein 2006; Caragiannis and Procaccia 2011; Boutilier et al. 2015; Caragiannis et al. 2017; Benade et al. 2017). The other (which is more recent) assumes that utility functions are derived from an underlying metric space, naturally leading to smaller distortion (Anshelevich et al. 2018; Anshelevich and Postl 2017; Feldman, Fiat, and Golumb 2016; Goel, Krishnaswamy, and Munagala 2017; Gross, Anshelevich, and Xia 2017). Our setup is consistent with the former line of work. On a technical level, two of the foregoing papers are most closely related to ours. The ﬁrst is by Boutilier et al. (2015), who study the distortion minimization problem when the output is a distribution over winning alternatives. They prove an upper bound of O ( m log m) on the distortion of optimal social choice functions, and a lower bound of Ω( m). Their setting coincides with ours when wi,1 = 1 for each voter i, because in that case social welfare depends only on the utility of each voter for the top-ranked alternative. Achieving low distortion is much more difﬁcult in our setting, and, in particular, their lower bound directly carries over (whereas their upper bound clearly does not). The second paper, by Benade et al. (2017), studies distortion-minimizing rules for the participatory budgeting problem, where each alternative has a cost, and the goal is to choose a subset of alternatives that satisﬁes a budget constraint. Voters are assumed to have additive utility functions. Their results are incomparable to ours their problem is harder in that they have to deal with (known) costs and budget constraints, but easier in that they choose a single subset, whereas we, in a sense, choose m nested subsets (the m preﬁxes of our ranking), which are weighted according to unknown weights. Furthermore, our results hold for richer (subadditive) combinatorial utility functions.

2 The Model

Our setting involves a set of voters [n] = {1, . . . , n}, and a set of alternatives [m] = {1, . . . , m}. We are interested in the set Sm of rankings, or permutations, over [m]. We

think of a ranking τ Sm as a function from positions to alternatives, i.e., τ(j) is the alternative in position j in τ, and τ 1(j) is the position in which τ places alternative j. The preferences of each voter i are represented as a ranking σi Sm. A preference proﬁle is a vector σ = (σ1, . . . , σn) of the rankings of all voters. A (randomized) social choice function is a function f : (Sm)n ([m]), which takes a preference proﬁle as input, and returns a distribution over winning alternatives. In this paper we focus on (randomized) social welfare functions, whose range is instead (Sm), i.e., they also take a preference proﬁle as input, but return a distribution over rankings. A novel component of our model is that we assume that each voter i [n] is associated with a combinatorial utility function ui : 2[m] R+ and a weight vector wi Rm +. Following previous work (Caragiannis and Procaccia 2011; Boutilier et al. 2015; Caragiannis et al. 2017; Benade et al. 2017), both are assumed to be normalized, that is, for all i [n], ui( ) = 0 and Pm j=1 ui({j}) = Pm j=1 wi,j = 1. Moreover, our results make use of the following properties of utility functions: Monotonicity: ui(S) ui(T) for all S T [m]. Subadditivity: ui(S) + ui(T) ui(S T) for all S, T [m]. The utility of voter i for a ranking τ Sm is given by the weighted sum of his utilities for the preﬁxes of τ, that is,

j=1 wi,j ui({τ(1), τ(2), . . . , τ(j)}).

We remark that even additive utility functions are able to capture the simpler setting discussed in Section 1, which can be formalized by assigning each voter a utility function u i : [m] R+ and weights such that w i,j w i,j+1 for all j [m 1], and letting u i(τ) = Pm j=1 w i,j u i(τ(j)). But subadditive utility functions can model realistic settings that are not captured by utility functions that are merely additive. For example, suppose that we want to rank faculty candidates, and plan to make offers to the top candidates in our ranking. Then the weight wi,j reﬂects the perceived probability that there would be j slots available, and the utility function ui is naturally subadditive, but not additive, due to complementarities between candidates: The contribution of a candidate is typically small if the set of candidates already contains another candidate working in the exact same area. We assume that each voter reports a ranking that is consistent with his utility function, which, in our general formulation with combinatorial utilities, we take to mean that voter i reports σi only if

ui({σi(1)}) ui({σi(2)}) ui({σi(m)}).

We denote this notion of consistency by ui σi, and, when σi is consistent with ui for all i [n], u σ. Our goal is to optimize (utilitarian) social welfare, that is, the sum of utilities voters have for the output ranking. Formally,

However, since we only observe the given preference proﬁle, we cannot directly optimize social welfare. To measure how far a social welfare function is from maximizing this objective, we adapt the concept of distortion (Procaccia and Rosenschein 2006). Formally, the distortion of a social welfare function f on a preference proﬁle σ is

dist(f, σ) max u: u σ max w maxτ Sm sw(τ)

Eµ f( σ)[sw(µ)] .

In words, distortion measures the ratio between the social welfare of the welfare-maximizing ranking, and the expected social welfare of the distribution over rankings produced by f, in the worst case over all possible weights w = (wi,j)i [n],j [m], and all possible utility proﬁles that are consistent with the given preference proﬁle. Finally, the distortion of f is the worst case distortion over all possible preference proﬁles: dist(f) max σ dist(f, σ).

3 Distortion Bound In this section we establish a tight (up to polylogarithmic factors) bound on the distortion of optimal social welfare functions. As noted under related work, Boutilier et al. (2015) prove a lower bound of Ω( m) on the distortion of optimal social choice functions, which carries over to our setting. Therefore, to show that optimal social welfare functions have distortion Θ( m), it is sufﬁcient to prove the following theorem, which is our main result.

Theorem 3.1. Under the monotonicity and subadditivity assumptions, there exists a randomized social welfare function with distortion O m ln3/2 m .

The construction of our social welfare function relies on the harmonic scoring function (Boutilier et al. 2015), deﬁned as follows. Recall that σ 1 i (j) denotes the position of alternative j in the ranking of voter i. The harmonic score of alternative j is score(j) Pn i=1 1/σ 1 i (j). We will make use of the following two properties of the harmonic scoring function.

Lemma 3.2. For any m 2, Pm j=1 score(j) 3n ln m.

Proof of Lemma 3.2. By deﬁnition,

j=1 score(j) =

i=1 1/σ 1 i (j) =

n(ln m + 1) 3n ln m.

Lemma 3.3. Under the subadditivity assumption, for any S [m] it holds that Pn i=1 ui(S) P

j S score(j).

Proof of Lemma 3.3. For any voter i [n] and alternative a [m],

j=1 ui(σi(j))

σ 1 i (a) X

j=1 ui(σi(j)) σ 1 i (a) ui({a}).

Thus, ui({a}) 1/σ 1 i (a). Moreover, by the subadditivity of ui, ui(S) P j S ui({j}). It follows that

j S ui({j}) X

i=1 1/σ 1 i (j)

j S score(j).

We require one other lemma that is quite technical. Denote by T k S the experiment of drawing a subset T of size k from S uniformly at random. Lemma 3.4. Suppose A B C and k |B| |C|. Function g : 2A R+ satisﬁes the monotonicity and subadditivity conditions. Then

T k B [g(T A)] 4|C| E

T k C [g(T A)].

Proof of Lemma 3.4. Fix set A, integer k, and function g : 2A R+ that satisﬁes the monotonicity and subadditivity conditions. For n max(k, |A|), deﬁne f(n) as

T k Sn [g(T A)] ,

where Sn is a superset of A with n elements.1 It sufﬁces to prove that f(n) is approximately non-decreasing in the sense that for any n1 n2, f(n1) 4f(n2). Deﬁne aj E T j A[g(T)] for 0 j |A|, and let aj = a|A| for j > |A|. We require the following property, which we prove in the full version of the paper.2

Lemma 3.5. The sequence (aj) j=0 is monotonic, and 2ak a2k for any 1 k |A|.

For each j [|A|], deﬁne bj as bj aj /j , where j = 2 log2 j . Moreover, let b|A|+1 = 0. We show that (bj)|A| j=1 is

non-increasing and approximates (aj/j)|A| j=1. By construction,

(bj)|A| j=1 = a1

8 , . . . .

Since 2ak a2k for any k [|A|] by Lemma 3.5, we have a1

This proves that (bj)|A| j=1 is non-increasing. Let j = 2 log2 j . Since j j 2j, it follows from Lemma 3.5 that aj aj a2j 2aj. Therefore,

i.e., bj approximates aj/j up to a factor of 2.

1Any such set Sn gives the same deﬁnition of f(n). 2Available at http://procaccia.info/research.

Next, ﬁx n max(k, |A|). Recall that

T k Sn [g(T A)] .

For 0 j |A|, let Ej denote the event that |T A| = j. When conditioning on Ej, T A is uniformly distributed among all subsets of size j in A, i.e., E[g(T A)|Ej] = aj. Moreover,

|A| j n |A| k j

By the law of total expectation,

j=0 Pr[Ej] E[g(T A)|Ej]

|A| j n |A| k j

j |A| 1 j 1 n |A| k j

n k n 1 k 1 aj

|A| 1 j 1 n |A| k j

where the second equality holds because a0 = g( ) = 0, and the third because n m = n

m n 1 m 1 for 1 m n. Let

|A| 1 j 1 n |A| k j

and qn,j = Pj l=1 pn,l. Recall that b|A|+1 = 0. Using Equations (1) and (2), we have

f(n) = k|A|

j=1 pn,j aj

j=1 pn,j bj

j=1 (bj bj+1) qn,j.

Similarly, we have

j=1 (bj bj+1) qn,j.

Lemma 3.6. For any j [|A|], (qn,j) n=max(k,|A|) is nondecreasing in n.

Proof. Fix set A, j [|A|] and k. Recall that

|A| 1 j 1 n |A| k j

and qn,j = Pj l=1 pn,l. For every n max(k, |A|), deﬁne

random variable Tn k 1 [n 1], i.e., Tn is a random subset of size k 1 drawn from [n 1]. It can be veriﬁed that

pn,j = Pr[|Tn [|A| 1]| = j 1],

qn,j = Pr[|Tn [|A| 1]| < j].

To show that (qn,j) n=max(k,|A|) is non-decreasing in n, we consider the following experiment:

Draw X k 1 [n]. Let Y = X if n / X; otherwise, let Y = X \ {n} {x}, where x is drawn uniformly from [n 1] \ X.

By construction, the marginal distributions of X and Y are identical to those of Tn+1 and Tn, respectively. Moreover, as Y is either equal to X, or obtained from X by replacing n with a smaller element, we have

|X [|A| 1]| |Y [|A| 1]|.

I [|X [|A| 1]| < j] I [|Y [|A| 1]| < j] ,

where I [ ] denotes the indicator function. Taking the expectation over the randomness in (X, Y ) yields

Pr[|Tn+1 [|A| 1]| < j] Pr[|Tn [|A| 1]| < j],

i.e., qn+1,j qn,j. This proves the monotonicity of (qn,j), and thus completes the proof of Lemma 3.6.

We can now ﬁnish the proof of Lemma 3.4, as for any max(k, |A|) n1 n2, we have

f(n1) 2k|A|

j=1 (bj bj+1) qn1,j

j=1 (bj bj+1) qn2,j

We are now ready to prove the theorem.

Proof of Theorem 3.1. We construct a randomized social welfare function that, given a preference proﬁle σ, proceeds as follows.

Sort the alternatives into a ranking ν such that score(ν(1)) score(ν(2)) score(ν(m)). Let tmax = log2 m and α =

m ln m. Draw t uniformly at random from [tmax] and set m t = min ( 2tα , m). With probability 1/2, return a uniformly random permutation of [m]. Otherwise, shufﬂe the ﬁrst m t elements of ν uniformly at random, and return the resulting ordering.

The rest of the proof analyzes the distortion of the foregoing function. By the monotonicity of utility functions, the social welfare of every ranking τ Sm is at least

j=1 wi,j ui({τ(1), τ(2), . . . , τ(j)})

j=1 wi,j ui({τ(1)}) =

i=1 ui({τ(1)}),

where the last transition follows from Pm j=1 wi,j = 1. When the mechanism returns a random permutation τ, τ(1) is uniformly distributed in [m], and thus the expected social welfare is at least

i=1 ui({τ(1)}) = 1

j=1 ui({j}) = n

On the other hand, consider the case where the mechanism randomly shufﬂes the ﬁrst m t elements in ν. Let mt min{2t, m}, and Rt {ν(1), ν(2), . . . , ν(m t)}. The resulting expected social welfare is at least

T j Rt [ui(T)].

Let SOLt denote the expected social welfare conditioning on the value of t. Then the above discussion implies that

T j Rt [ui(T)]. (3)

Let µ denote the welfare-maximizing ranking. Let St {µ (1), µ (2), . . . , µ (mt)}, and

T j St [ui(T)].

In the following, we show that

t=1 OPTt sw(µ )

and for any t [tmax],

SOLt OPTt 12

m ln m . (5)

Inequalities (4) and (5) directly imply that the expected social welfare obtained by the mechanism is at least

t=1 SOLt 1 log2 m

O m ln3/2 m ,

which concludes the proof.

Proof of Equation (4). Note that for any t [tmax] and j [mt/2, mt],

T j St [ui(T)] E

T mt/2 St [ui(T)] E

T mt St [ui(T)] 1

ui({µ (1), µ (2), . . . , µ (j)}) 1

where the ﬁrst transition follows from the monotonicity of ui, the second from its subadditivity, the third from |St| = mt, and the last again from monotonicity. Therefore,

j=mt/2 wi,j E

T j St [ui(T)]

j=mt/2 wi,jui({µ (1), . . . , µ (j)})

j=1 wi,j ui({µ (1), . . . , µ (j)})

where the second inequality follows from Equation (6), and the third holds because m1/2 = 1 and mtmax = m.

Proof of Equation (5). Let S+ t = St Rt and S t = St \Rt. The subadditivity of ui implies that for any T St, ui(T) ui(T S+ t ) + ui(T S t ). Thus, we can derive an upper bound on OPTt as follows:

T j St [ui(T)]

ui(T S+ t ) + ui(T S t )

ui(T S+ t )

ui(T S t ) . (7)

We establish upper bounds on the two terms on the right hand side of Equation (7) separately. For the ﬁrst term, note that S+ t St Rt and |St| = mt m t = |Rt|. For any i [n] and j [mt], applying Lemma 3.4 with g = ui, k = j, A = S+ t , B = St and C = Rt gives

ui(T S+ t ) 4|Rt| E

ui(T S+ t ) .

It follows that

ui(T S+ t ) 4m t mt E

ui(T S+ t )

ui(T S+ t ) .

Summation over i and j yields

ui(T S+ t )

ui(T S+ t )

T j Rt [ui(T)] .

We next bound the second term on the right hand side of Equation (7). Note that

j=1 wi,j ui(S t )

i=1 ui(S t ) X

Here the ﬁrst step is due to the monotonicity of ui, the second step holds since Pmt j=1 wi,j Pm j=1 wi,j = 1, while last step applies Lemma 3.3. For each alternative a S t , it follows from Lemma 3.2 that

j=1 score(j)

j=1 score(ν(j)) m t score(a),

so score(a) 3n ln m/m t for any a S t . Therefore, we have

ui(T S t ) 3n ln m |S t | m t .

Recall that m t = min ( 2tα , m), and S t = St \ Rt = St \ {ν(1), . . . , ν(m t)}. If m t = m, we have S t = and |S t |/m t = 0. When m t < m, it holds that m t = 2tα 2t 1α and mt = 2t. Thus, |S t |/m t mt/m t 2/α. In either case,

ui(T S t ) 3n ln m |S t | m t

2m 12α. (9)

Putting everything together, we have that

ui(T S+ t )

T j Rt [ui(T)] + 12α n

12α SOLt = 12

m ln m SOLt,

where the ﬁrst inequality follows from Equation (7), the second from (8) and (9), and the third from (3). This proves Equation (5) and completes the proof of the theorem.

As is the case in previous work (Boutilier et al. 2015; Benade et al. 2017; Caragiannis et al. 2017), the social welfare function we analyze relies on randomization and returns a uniformly random outcome in our case, a random ranking with constant probability (note that any constant, even 1/106, will do). It is important to understand that this social welfare function is (almost) optimal only in the sense that its worst-case distortion guarantees are close to the lower bound. By contrast, the instance-optimal social welfare function f minimizes the distortion dist(f, σ) on each and every given preference proﬁle σ. Naturally, given a particular preference proﬁle, it would usually be possible to get much lower distortion than the worst-case bound. For example, if the preference proﬁle σ consists of n identical rankings, returning that ranking would have distortion 1 on σ, yet the function constructed in the proof of Theorem 3.1 would still blindly return a uniformly random ranking with probability 1/2. Crucially, the upper bound given by Theorem 3.1 obviously applies to the instance-optimal function, and therein lie the practical implications of the theorem. In Section 4 we revisit the instance-optimal social welfare function, albeit only in the deterministic case, and compare its performance with that of several common competitors. Finally, we remark that some restriction on the combinatorial structure of the valuation functions, beyond monotonicity, is necessary to achieve sublinear distortion. Indeed, in the following example we construct non-subadditive utility functions such that any social welfare function must have distortion Ω(m).3

Example 3.7. Consider the following utility function: for two distinct alternatives a, b [m],

ua,b(S) = 1, {a, b} S, |S|/m, otherwise.

Note that ua,b is monotonic. Moreover, the function is consistent with any ranking of [m], so we can assume that a voter with utility function ua,b reports the same ranking σ regardless of a and b. Let there be a single voter with weight vector (0, 1, 0, 0, . . .). The utility of a ranking τ is given by ua,b({τ(1), τ(2)}). In order to achieve a utility of 1 (rather than 2/m), it is necessary to place a and b in the top two slots. Any randomized welfare function has two alternatives that, given σ as input, are placed in the ﬁrst two positions with probability at most 2/m(m 1). By choosing these two alternatives to be a and b, we can guarantee

3Ranking the alternatives uniformly at random achieves distortion O (m). Thus, in such cases we cannot signiﬁcantly outperform a random guess.

that the function achieves expected social welfare at most 2 m(m 1) 1 + (1 2 m(m 1)) 2

m, whereas the optimum is 1. The ratio is Ω(m).

4 Empirical Results For our computational experiments we focus on deterministic social welfare functions, and on additive utility functions. We also generalize the position-weighted model slightly. The reason for this generalization is that it makes the problem of computing the instance-optimal deterministic social welfare function easier, by allowing for linear constraints in a subproblem. Any upper bound on the distortion found under the generalized model is also a valid upper bound for the position-weighted model. To elaborate, let voter i [n] have ranking σi consistent with the utility matrix U i Rm m, where U i ap is the utility voter i has for alternative a appearing in position p. As before, voter i s preferences impose constraints on U i. Specifically, higher ranked alternatives have utility at least as large as lower ranked alternatives, for any speciﬁc position, that is, U i σi(p),j U i σi(p+1),j for all p [m 1], j [m], and U i a,p U i a,p+1 for all a [m], p [m 1]. Utilities are normalized to have P

p [m] U i ap = 1. The utility proﬁle

is U = (U 1, . . . , U n). Let us represent a ranking τ by a permutation matrix X(τ) Πm. The social welfare of a ranking τ is P

i [n] U i, X(τ) , where A, B = P

ij Aij Bij is the Frobenius inner product. We can now write the mathematical program that ﬁnds the (deterministic) ranking X with minimum distortion z given an input proﬁle σ as

min z,τ Sm z

Pn i=1 U i,X(ρ) Pn i=1 U i,X(τ) U σ , ρ Sm (10)

This formulation has intractably many constraints in Equation (10). But these constraints may be omitted and added as needed, by solving the subproblem

min U σ,ρ Sm z

i=1 U i, X( τ)

i=1 U i, X(ρ)

where z, τ are the current optimal solutions to the master problem. A violated constraint is found if the objective function value of the subproblem is strictly less than 0. The procedure terminates with the optimal z, τ when no violated constraints are found. The subproblem is nonconvex even when the integrality constraints are relaxed, and, therefore, ﬁnding violated constraints is computationally expensive. Nevertheless, Figure 1 shows that it is currently practical to compute distortionminimizing rankings exactly for instances with up to 10 alternatives within a couple of minutes. We expect that this will be sufﬁcient for the vast majority of instances seen in practice. Indeed, 98.3% of the instances submitted to Robo Vote (as of January 19, 2018) have 10 or fewer alternatives. For larger instances, we evaluate the performance of the following, more scalable, heuristics:

10 20 30 Number of alternatives

Exact Iterative Kemeny Plurality Harmonic Borda

Figure 1: Runtime (in seconds) for increasing instance size, on an a machine with an Intel Core i5-4200U CPU and 8 GB RAM.

1. Kemeny: Return the ranking that minimizes the total number of disagreements on pairs of alternatives with the input proﬁle.

2. Borda: Rank alternatives by their Borda scores, deﬁned as Pn i=1(m σ 1 i (a)).

3. Plurality: Rank alternatives based on the number of times they are ranked ﬁrst. Break ties by considering subsequent positions.

4. Harmonic: Return a ranking according to Theorem 3.1.

5. Iterative: Iteratively ﬁnd and remove the alternative that minimizes distortion for the problem of returning a single alternative with maximum social welfare.

We evaluate these heuristics on instances with n = 10 and m {3, . . . , 30}. Every alternative a is assigned a quality ca, and ui({a}) is drawn from a truncated normal distribution around ca. Vector ui = (ui({a}))a [m] induces σi. Weights wi are drawn uniformly at random in [0, 1], and ordered. Voter i s utility matrix U i = wiui is normalized. Every social welfare function f only has access to σ and is evaluated on two metrics: the distortion of the returned ranking ρ = f( σ), and the social welfare ratio maxτ Sm sw(τ, U)/sw(ρ, U). Note that the latter measure estimates the average case with respect to utility proﬁles, rather than the worst case. The distortion and social welfare ratios of the proposed heuristics are shown in Figures 2 and 3. Distortion is reported for m 10, where it is possible to compare to the optimal distortion, and 100 repetitions; social welfare for m 30 and 200 repetitions. The distortion of Borda, Kemeny and especially Iterative compares well with the optimal distortion. Kemeny and Borda also lead to very high efﬁciency, with average social welfare within 1% of optimal.

4 6 8 10 Number of alternatives

Plurality Harmonic Borda Kemeny Iterative Exact

Figure 2: Average distortion of heuristic and exact methods.

10 20 30 Number of alternatives

Social Welfare Ratio

Plurality Harmonic Iterative Kemeny Borda

Figure 3: Average social welfare ratio of different heuristics.

5 Discussion

Much like previous papers on implicit utilitarian voting (Caragiannis et al. 2017; Benade et al. 2017), there is a certain gap between the theoretical and empirical results, in the sense that the theoretical distortion bound of Theorem 3.1 holds for randomized social welfare functions, whereas the empirical results hold for deterministic functions. The value of theoretical distortion bounds is that they tell us whether rankings inherently provides useful information for optimizing social welfare. The fact that the bound is essentially no worse than for the case of a single winner means that the implicit utilitarian voting approach does extend to the design of social welfare functions. On a practical level, our empirical results suggest that classic methods like the Kemeny rule (which is currently deployed on Robo Vote) and Borda count provide near-optimal performance from the viewpoint of implicit utilitarian voting. Alternatively, it is possible to compute the distortionminimizing social welfare function if instances are restricted to at most ten alternatives. Although almost all instances arising from small-group decisions (of the type made on

Robo Vote) are of that size, some high-stakes decisions, such as ranking applicants for a job or candidates for a Ph D program, involve a much larger number of alternatives, and motivate the development of faster algorithms.

Acknowledgments This work was partially supported by the National Science Foundation under grants IIS-1350598, IIS-1714140, CCF1525932, and CCF-1733556; by the Ofﬁce of Naval Research under grants N00014-16-1-3075 and N00014-17-12428; and by a Sloan Research Fellowship and a Guggenheim Fellowship.

References Anshelevich, E., and Postl, J. 2017. Randomized social choice functions under metric preferences. Journal of Artiﬁcial Intelligence Research 58:797 827. Anshelevich, E.; Bhardwaj, O.; Elkind, E.; Postl, J.; and Skowron, P. 2018. Approximating optimal social choice under metric preferences. Artiﬁcial Intelligence 264:27 51. Benade, G.; Nath, S.; Procaccia, A. D.; and Shah, N. 2017. Preference elicitation for participatory budgeting. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), 376 382. Boutilier, C.; Caragiannis, I.; Haber, S.; Lu, T.; Procaccia, A. D.; and Sheffet, O. 2015. Optimal social choice functions: A utilitarian view. Artiﬁcial Intelligence 227:190 213. Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds. 2016. Handbook of Computational Social Choice. Cambridge University Press. Caragiannis, I., and Procaccia, A. D. 2011. Voting almost maximizes social welfare despite limited communication. Artiﬁcial Intelligence 175(9 10):1655 1671. Caragiannis, I.; Nath, S.; Procaccia, A. D.; and Shah, N. 2017. Subset selection via implicit utilitarian voting. Journal of Artiﬁcial Intelligence Research 58:123 152. Feldman, M.; Fiat, A.; and Golumb, I. 2016. On voting and facility location. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), 269 286. Goel, A.; Krishnaswamy, A. K.; and Munagala, K. 2017. Metric distortion of social choice rules: Lower bounds and fairness properties. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), 287 304. Gross, S.; Anshelevich, E.; and Xia, L. 2017. Vote until two of you agree: Mechanisms with small distortion and sample complexity. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), 544 550. Kemeny, J. 1959. Mathematics without numbers. Daedalus 88:571 591. Procaccia, A. D., and Rosenschein, J. S. 2006. The distortion of cardinal preferences in voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA), 317 331.