# subset_selection_via_implicit_utilitarian_voting__dc2cb036.pdf

Journal of Artificial Intelligence Research 58 (2017) 123-152 Submitted 07/16; published 01/17

Subset Selection Via Implicit Utilitarian Voting

Ioannis Caragiannis caragian@ceid.upatras.gr University of Patras, Greece

Swaprava Nath swapravn@cs.cmu.edu Carnegie Mellon University, USA

Ariel D. Procaccia arielpro@cs.cmu.edu Carnegie Mellon University, USA

Nisarg Shah nisarg@g.harvard.edu Harvard University, USA

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach which we refer to as implicit utilitarian voting assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of Robo Vote.org, a not-for-profit website that helps users make group decisions via AI-driven voting methods.

1. Introduction

We are interested in the classic social choice problem of aggregating the preferences of a set of voters represented as rankings over a set of alternatives into a collective decision. Traditional social choice theory typically takes a normative approach, by specifying desirable axioms that the aggregation method (also known as a voting rule) should satisfy (Arrow, 1951). In contrast, researchers in computational social choice (Brandt, Conitzer, Endriss, Lang, & Procaccia, 2016) often advocate quantitative approaches to the same problem. The high-level idea is to identify a compelling objective function, and design voting rules that optimize this function.

Here we focus on a specific objective function: utilitarian social welfare. Specifically, we assume that each voter assigns a utility to each possible outcome, and the socially optimal outcome maximizes the sum of utilities. This sounds simple enough at first glance, but there is a major obstacle we must overcome: voters preferences are expressed as ordinal preferences (rankings), rather than cardinal preferences (utilities). While this reduces the cognitive load on voters, and makes preference elicitation much easier, it does seem to be at odds with the utilitarian viewpoint.

2017 AI Access Foundation. All rights reserved.

Caragiannis, Nath, Procaccia, & Shah

Procaccia and Rosenschein (2006) reconcile these differences via an approach that we refer to as implicit utilitarian voting.1 They propose that voters have latent utility functions, and report rankings that are consistent with these utilities, that is, the voters rank the alternatives by their utility. The performance of a voting rule which can only access the submitted rankings, not the implicit utility functions can then be quantified via a measure called distortion: the worst-case (over utility functions consistent with the reported profile of rankings) ratio between the social welfare of the optimal (welfare-maximizing) alternative, and the social welfare of the alternative selected by the voting rule. While Procaccia and Rosenschein focus on analyzing the distortion of existing voting rules, Boutilier, Caragiannis, Haber, Lu, Procaccia, and Sheffet (2015) design voting rules that minimize distortion. In particular, they bound the worst-case distortion, and show that the distortion-minimizing (randomized) voting rule can be implemented in polynomial time. The work of Boutilier et al. (2015) provides a good understanding of optimized aggregation of rankings from the utilitarian viewpoint but only when a single alternative is selected by the voting rule. Indeed, this understanding does not extend to common applications that require selection of a subset of alternatives, such as choosing a committee, or selecting restaurants for the next four group lunches. Our goal is therefore to

. . . build on the utilitarian approach to design optimal voting rules for selecting a subset of alternatives, and understand the guarantees they provide, as well as their performance in practice.

We make four main contributions. First, on a conceptual level, we introduce the additive notion of regret into the implicit utilitarian voting setting, as an alternative to the multiplicative notion of distortion. Second, in Section 3, we derive worst-case bounds on the distortion and regret of optimal deterministic and randomized voting rules. Third, in Section 4, we compare the worst-case-optimal deterministic voting rules with respect to distortion and regret denoted f dist and f reg, respectively with a slew of well-known voting rules, in terms of average-case distortion and regret, using experiments on synthetic and real data. We find that f reg outperforms all other rules on average, even when measuring distortion! Fourth, in Section 5, we develop a scalable implementation for f reg (which, we show, is NP-hard to compute).

1.1 Direct Real-World Implications

Research in computational social choice has frequently been justified by potential applications in multiagent systems. But recently researchers have begun to realize that, arguably, the most exciting products of this research are computer programs that help humans make decisions via AI-driven algorithms. One example is Spliddit.org, a fair division website (Goldman & Procaccia, 2014). In the voting space, existing examples include Whale (whale3.noiraudes.net/whale3/) and Pnyx (pnyx.dss.in.tum.de) but these websites generally adopt the axiomatic viewpoint. In November 2016, a new social choice website, Robo Vote.org, was launched; some of us have worked on its design and implementation. The novelty of this not-for-profit website is that it relies on optimization-based approaches. For the case of objective votes when

1. Cf. utilitarian voting, which has sporadically been used to refer to both approval voting and range voting.

Subset Selection Via Implicit Utilitarian Voting

a ground truth ranking of the alternatives exists (e.g., the order of different stocks by the relative change in their prices tomorrow) Robo Vote implements voting rules that pinpoint the most likely best alternative (Young, 1988), or the set most likely to contain it (Procaccia, Reddi, & Shah, 2012). For the case of subjective votes the classic setting which is the focus of this paper, with applications to everyday scenarios such as a group of friends selecting a movie to watch or a restaurant to go to we use the results of Boutilier et al. (2015) to select a single alternative. But, previously, the extension to subset selection was unavailable this is precisely the motivation for the work described herein. Based on the results of Sections 4 and 5, we have implemented the deterministic regret minimization rule on Robo Vote. Interestingly, while computing the outcome of this rule requires an intricate algorithm as it is a computationally intractable problem (see Section 5), the optimality guarantee provided by the outcome is rather easy to convey to the users. The quote below illustrates how Robo Vote explains the choice made by the rule on a particular instance.

Assuming that the rankings submitted by voters are consistent with the values they place on the alternatives, the group of winning alternatives returned by Robo Vote is guaranteed to maximize the total value up to an error of 0.2, measured on a scale in which the total value placed by all voters on all alternatives is 1. No other group of alternatives can give a better guarantee.

1.2 Related Work

In addition to the aforementioned papers (Procaccia & Rosenschein, 2006; Boutilier et al., 2015), several other papers employ the notion of distortion to quantify how close one can get to maximizing utilitarian social welfare when only ordinal preferences are available (Caragiannis & Procaccia, 2011; Anshelevich, Bhardwaj, & Postl, 2015; Anshelevich & Postl, 2016; Anshelevich & Sekar, 2016). In particular, Anshelevich et al. (2015) study the same setting as Boutilier et al. (2015), but in addition assume the preferences of voters are consistent with distances in a metric space. Approximating utilitarian social welfare given ordinal information has also been studied in mechanism design. Filos-Ratsikas, Frederiksen, and Zhang (2014) apply this notion for finding matchings in graphs; Krysta, Manlove, Rastegari, and Zhang (2014) apply it to the house allocation problem; and Chakrabarty and Swamy (2014) study approximation of welfare under the assumption that an agent s utility for an alternative depends only on the rank of the alternative in the agent s preference order, i.e., when the utilities of all agents are dictated by a common underlying positional scoring rule. We refer the reader to the paper by Boutilier et al. (2015, Section 1.2) for a thorough discussion of work (in philosophy, economics, and social choice theory) related to implicit utilitarian voting more broadly. There is quite a bit of work in computational social choice on voting rules that select subsets of alternatives. Typically it is assumed that ordinal preferences are translated into a position-based score for each alternative (in contrast to our work). Just to give a few examples, under the Chamberlin-Courant method, each voter assigns a score to a set equal to the highest score of any alternative in the set, and the (computationally hard) objective is to choose a subset of size k that maximizes the sum of scores (Chamberlin & Courant, 1983; Procaccia, Rosenschein, & Zohar, 2008). Skowron, Faliszewski, and Lang (2015) generalize

Caragiannis, Nath, Procaccia, & Shah

the way in which the score of a voter for a subset of alternatives is computed. The budgeted social choice framework of Lu and Boutilier (2011a) is more general in that the number of alternatives to be selected is not fixed; rather, each alternative has a cost that must be paid to add it to the selection.

2. The Model

Let [t] = {1, . . . , t}. Let A be the set of alternatives, and denote m = |A|. Let N = [n] be the set of voters. Let L = L(A) denote the set of rankings over the alternatives. Each voter i [n] submits a ranking σi L over the alternatives, which can alternatively be seen as a permutation of A. Therefore, σi(a) is the position in which voter i ranks alternative a (1 is best, m is worst). Moreover, a σi b denotes that voter i prefers alternative a to alternative b. The collection of voters (submitted) rankings is called the preference profile, and denoted by σ Ln. We assume the rankings are induced by comparisons between the voters underlying utilities. For i N and a A, let ui(a) [0, 1] be the utility of voter i for alternative a. As in previous papers (Boutilier et al., 2015; Caragiannis & Procaccia, 2011), we assume that the utilities are normalized such that P a A ui(a) = 1 for all i N. The collection of voter utilities, denoted u, is called the utility profile. We say that utility profile u is consistent with preference profile σ denoted u σ if for all a, b A and i N, a σi b implies ui(a) ui(b). Next we need to define the utility of a voter for a set of alternatives. For S A, we define ui(S) = maxa S ui(a), that is, each voter derives utility for his favorite alternative in the set; this is in the same spirit as previous papers on set selection (Chamberlin & Courant, 1983; Monroe, 1995; Procaccia et al., 2008; Lu & Boutilier, 2011a). While there exist domains in which other definitions for example, the case where each voter derives utility from all the alternatives in the set could more accurately describe voter utilities, our definition has an additional advantage: it alleviates the tyranny of the majority problem associated with utilitarian welfare maximization. For instance, if a group of five voters want to select a set of five alternatives, our definition ensures that the top choice of each voter is necessarily included in the set, whereas the alternative definition could lead to a set that comprises solely of alternatives that are desired by three of the five voters. Finally, the (utilitarian) social welfare of S given the utility profile u is sw(S, u) = Pn i=1 ui(S). We are interested in voting rules that, given a preference profile, select a subset of given cardinality k.2 Therefore, it will be useful to denote Ak = {S A : |S| = k}. In order to unify notation, we directly define a randomized voting rule as a function f : Ln (Ak), that is, the rule is allowed to select alternatives randomly, and formally f( σ) is a probability distribution over Ak. A deterministic voting rule simply gives probability 1 to a specific subset. A voting rule can only access the preference profile σ, yet the goal is to maximize social welfare with respect to the latent utility function u σ. We study two notions that quantify how well a rule achieves this goal: distortion and regret.

2. Formally, this is a special case of social choice correspondences with fixed output cardinality (Campbell & Kelly, 1996).

Subset Selection Via Implicit Utilitarian Voting

The distortion (Procaccia & Rosenschein, 2006) of a (randomized) voting rule f on a preference profile σ is

dist(f, σ) = sup u σ

max S Ak sw(S, u)

E[sw(f( σ), u)] .

In words, it is the worst-case over utility profiles consistent with the given preference profile ratio between the social welfare of the best subset, and the expected social welfare of the subset selected by the voting rule. We define the distortion of a voting rule f by taking the worst case over preference profiles: dist(f) = max σ Ln dist(f, σ). The second measure is regret. While it has not been studied as part of the agenda of implicit utilitarian voting, it has been explored in other social choice settings, especially partial preferences (Lu & Boutilier, 2011b); similar measures have been extensively studied in decision theory and machine learning (Blum & Mansour, 2007; Bubeck & Cesa-Bianchi, 2012). The regret of a (randomized) voting rule f on a preference profile σ is given by

reg(f, σ) = 1

max S Ak sw(S, u) E[sw(f( σ), u)] .

As before, define the regret of a rule f to be reg(f) = max σ Ln reg(f, σ). We divide by n because the total (worst-case) regret of any voting rule f is provably linear in n (so this is per vote regret). Note that distortion is a multiplicative measure of loss, whereas regret is its additive version.

3. Worst-Case Bounds

In this section we provide bounds on worst-case distortion and regret, for both deterministic and randomized voting rules. Boutilier et al. (2015) show that for selecting a single winner (k = 1), we can achieve O( m log m) distortion using a randomized rule, where log m is the iterated logarithm of m (the number of alternatives). This bound is asymptotically almost tight: they also show that the worst-case distortion is always Ω( m). For a large k, though, one can hope for a better bound. Clearly, when k = m there is only one voting rule (which selects every alternative), and its distortion is 1. More generally, the voting rule f that selects a subset from Ak uniformly at random picks each alternative in A with probability k/m, and thus achieves social welfare of n k/m in expectation. As social welfare cannot exceed n, we have dist(f) m/k. However, since we can already achieve O( m log m) distortion for k = 1, a bound of m/k provides an improvement only for k = Ω( m/ log m). Can we achieve better distortion for smaller values of k as well? It is not even clear whether the optimal worst-case distortion should monotonically decrease in k, because as our flexibility grows with k, so does the flexibility of the welfare-maximizing solution. In fact, a part of our main result shows that the worst-case distortion remains Ω( m) for all values of k up to Θ( m).

Theorem 1. Let m = |A|, and let k be the number of alternatives to be selected.

Caragiannis, Nath, Procaccia, & Shah

1. Distortion, deterministic rules: There exists a deterministic voting rule f with dist(f ) 1 + m (m k)/k. Moreover, for every deterministic voting rule f,

1 + m(m 3k)

9 , 1 + m if m

2 , 1 + m(m k)

k otherwise.

These bounds are tight up to a constant factor of 8.

2. Distortion, randomized rules: There exists a randomized voting rule f such that

2 m Hm if k 2 m Hm

m k if 2 m Hm

k otherwise,

where Hm = Θ(log m) is the mth harmonic number. Moreover, for every randomized voting rule f,

2 if k m ( m 1)

m k+m/k otherwise.

These bounds are tight up to a factor of 6.35 m1/6.

3. Regret, deterministic rules: There exists a deterministic voting rule f such that

( 1 2 if k m

m otherwise,

and this upper bound is completely tight.

4. Regret, randomized rules: There exists a randomized voting rule f such that

Moreover, for every randomized voting rule f,

( 1 4 if k m/2

m otherwise.

These bounds are tight up to a constant factor of 2.

All the upper bounds above can be achieved via polynomial-time algorithms.

The bounds presented above are simplified forms of the exact bounds that we derive. Figure 1 shows our exact bounds for m = 100.3

Before we dive into the proof, we simplify the formulae for the distortion and regret of deterministic voting rules.

3. The second upper bound in part 2 of Theorem 1 (which increases with k) does not play a role unless m is very large.

Subset Selection Via Implicit Utilitarian Voting

Det-UB Det-LB Rand-UB Rand-LB

0 50 100 100

(a) Distortion

0 50 100 0 0.25

Fig. 1: The upper and lower bounds on worst-case distortion and regret for m = 100.

Definition 1 (Comparing Sets). Given a ranking σ L and an alternative a A, recall that σ(a) denotes the position of a in σ. More generally, for a set S A let σ(S) = mina S σ(a). For sets S, T A, we say T σ S if σ(T) < σ(S), i.e., if there exists an alternative in T that is preferred to every alternative in S in σ.

Definition 2 (Plurality Score). The plurality score of an alternative a A in a preference profile σ is the number of votes in which a appears first, i.e.,

plu(a, σ) =

i=1 I[σi(1) = a],

where I is the indicator function. More generally, we define the plurality score of a set S A to be the number of votes in which an alternative in S is ranked first, i.e.,

plu(S, σ) =

i=1 I[σi(S) = 1] = X

a S plu(a, σ).

Lemma 1. For a deterministic voting rule f and a preference profile σ, the regret of f on σ is given by

reg(f, σ) = max S Ak 1 n

I[S σi f( σ)]

σi(S) , (1)

and the distortion of f on σ is given by

dist(f, σ) = 1 + m n reg(f, σ)

plu(f( σ), σ). (2)

Proof. First, note that reg(f, σ) and dist(f, σ) can be rewritten as follows.

reg(f, σ) = 1

max S Ak sw(S, u) sw(f( σ), u)

max S Ak sup u σ sw(S, u) sw(f( σ), u)

Caragiannis, Nath, Procaccia, & Shah

and similarly,

dist(f, σ) = sup u σ

max S Ak sw(S, u)

sw(f( σ), u) = max S Ak sup u σ

sw(S, u) sw(f( σ), u). (4)

If S = f( σ), then the regret term is 0 and the distortion term is 1. Fix S Ak \{f( σ)}. To maximize the regret (resp. distortion) term, we want to find the utility profile u that maximizes the difference (resp. ratio) of sw(S, u) and sw(f( σ), u) subject to u σ. For each voter i for which S i f( σ), we can maximize the discrepancy between ui(S) and ui(f( σ)), for both the regret and the distortion objectives, by letting ui(f( σ)) = 0, and maximizing ui(S) by setting the utility of the first σi(S) alternatives as 1/σi(S). For each voter i for which f( σ) i S, we have ui(S) ui(f( σ)). The best we can hope for is to make the two utilities equal. While this is sufficient to optimize the regret objective, optimizing distortion further requires the two utilities to be the smallest possible for such voters. Hence, for σi(f( σ)) > 1, we need both utilities to be 0, and for σi(f( σ)) = 1, we need both to be 1/m, which is the smallest possible value of ui(f( σ)) in this case. This intuition leads us to the following explicit utility profile u . For each voter i,

1. If σi(f( σ)) = 1, let ui(a) = 1/m for all a A.

2. If S i f( σ), let ui(a) = 1/σi(S) if σi(a) [σi(S)], and ui(a) = 0 otherwise.

3. If S i f( σ) and σi(f( σ)) = 1, let ui(a) = 1 if σi(a) = 1, and ui(a) = 0 otherwise.

First, it is easy to check that u σ. Also, note that this utility profile maximizes ui(S) ui(f( σ)) subject to ui σi, for each voter i in each of the three cases above. Hence, it maximizes the regret term sw(S, u) sw(f( σ), u). Further, we have

sw(f( σ), u ) = 1

m plu(f( σ), σ),

sw(S, u ) = 1

m plu(f( σ), σ) +

I[S i f( σ)]

This immediately gives us Equation (1) for the regret of f on σ. Now, the distortion of f on σ under the utility profile u is

sw(S, u ) sw(f( σ), u ) = 1 + m Pn i=1 I[S i f( σ)]/σi(S)

plu(f( σ), σ) = 1 + m n reg(f, σ)

plu(f( σ), σ) 1. (5)

Finally, take a utility profile u satisfying u σ. We want to show that the distortion under u, i.e., sw(S, u)/sw(f( σ), u) is no more than the distortion under u . Note that f( σ) has the least possible welfare under u . Hence, sw(f( σ), u) sw(f( σ), u ). To achieve a greater distortion, we must have sw(S, u) > sw(S, u ), i.e., the voters must assign a greater utility to S under u than under u . Let us revisit the three cases in the construction of u . All the voters covered under case 2 already assign S the highest possible utility. For all the other voters, the top-ranked alternative of f( σ) is at least as high as the top-ranked alternative of S. Hence, an increase of δ in the utility for S would require an increase of at least δ in the utility for f( σ).

Subset Selection Via Implicit Utilitarian Voting

That is, for any δ > 0, sw(S, u) = sw(S, u ) + δ implies sw(f( σ), u) sw(f( σ), u ) + δ. Finally,

sw(S, u ) sw(f( σ), u ) 1 sw(S, u) sw(f( σ), u) sw(S, u ) + δ sw(f( σ), u ) + δ sw(S, u ) sw(f( σ), u ).

Hence, the worst-case distortion is indeed 1 + m reg(f, σ)/plu(f( σ), σ), as required. Note that in finding the worst-case distortion, the distortion of 1 achieved with S = f( σ) is ignored because the distortion achieved by every S = f( σ) is at least 1.

One interesting consequence of Lemma 1 is that selecting a set of alternatives, none of which appear at the top position in any vote, results in an unbounded distortion. Hence, the rule that optimizes distortion would never select such a set. We are now ready for the proof of our main result.

Proof of Theorem 1. Below, we provide a proof for the upper and the lower bound in each of the four cases.

Distortion, deterministic rules:

Upper bound: Inspired by the denominator plu(f( σ), σ) = P a f( σ) plu(a, σ) in the formula for the distortion of f on σ from Lemma 1, let us analyze the rule f that selects the k alternatives with the highest plurality scores. We show that f achieves the required upper bound on the optimal distortion. Since the sum of plurality scores of all the alternatives is n, the sum of top k plurality scores is at least n k/m. Hence, plu(f ( σ), σ) n k/m. Next, for S Ak \ {f ( σ)}, note that the number of voters i for which S i f ( σ) is at most n plu(f ( σ), σ). Using Lemma 1, it follows that the distortion of f on σ is at most

1 + m n plu(f ( σ), σ)

plu(f ( σ), σ) = 1 + m n plu(f ( σ), σ) 1 1 + m m

which is the required upper bound.

Lower bound: Next, we establish three different lower bounds on the distortion of deterministic rules.

1. For k m/6, dist(f) 1 + m (m 3k)/(6k) for every deterministic rule f.

2. For k m/2, dist(f) 1 + m for every deterministic rule f.

3. For k m/2, dist(f) 1 + m (m k)/k for every deterministic rule f.

It is easy to check that for k m/9, the first bound is the strongest; for k [m/9, m/2], the second bound is the strongest; and, for k m/2, the third bound is the strongest. Hence, the optimal combination of these three bounds gives us the desired result. Let the set of alternatives be A = {a1, . . . , am}. Let us begin by proving the first bound. Fix a value of k m/6, and partition A into two sets: X = {a1, . . . , am 3k} and Y = A\X. Let Y = {b1, . . . , b3k}. Note that m 6k implies |X| |Y |. Construct a ranked profile σ as follows.

Caragiannis, Nath, Procaccia, & Shah

For each alternative aj X (thus j m 3k), let aj be ranked first in the votes of voters i [(j 1) n/(m 3k) + 1, j n/(m 3k)]. That is, we partition the set of voters into |X| = m 3k contiguous blocks, and have each alternative of X ranked first in one of the blocks.

For each alternative bj Y (thus j 3k), let bj be ranked second in the votes of voters i [(j 1) n/3k + 1, j n/3k]. That is, we partition the set of voters into |Y | = 3k contiguous blocks, and have each alternative of Y ranked second in one of the blocks.

Since we chose the blocks of voters to be contiguous in both cases, it follows that for every aj X, the set of voters ranking aj first can have at most two distinct alternatives in Y in their second position. Take a deterministic rule f for selecting a set of k alternatives. Let |f( σ) X| = t k. Then, we have plu(f( σ), σ) = t n/(m 3k). Consider the voters who rank an alternative of f( σ) first. Let Y denote the set of alternatives appearing in the second position in the votes of such voters. From the argument above, we have |Y | 2t 2k. Hence, |Y \ Y | 3k 2k = k. Choose an arbitrary set S Y \Y such that |S| = k. Now, there are (n/3k) k = n/3 voters that rank an alternative in S in their second position. Hence,

dist(f) dist(f, σ) 1 + m Pn i=1 I[S i f( σ)]/σi(S)

plu(f( σ), σ) 1 + m (n/3) (1/2)

where the second transition uses Lemma 1, and the final transition uses t k. For the second and the third lower bound, we simply construct a profile σ in which each alternative in A appears first in n/m votes, and the remaining positions in the votes are filled arbitrarily. Fix a deterministic rule f with |f( σ)| = k. Note that plu(f( σ), σ) = (n/m) k. If k m/2, choose a set S A \ f( σ) such that |S| = k. Note that S f( σ) = , and an alternative in S is ranked first in (n/m) k votes. Hence, by Lemma 1,

dist(f) dist(f, σ) 1 + m Pn i=1 I[S i f( σ)]/σi(S)

plu(f( σ), σ) 1 + m (n/m) k

(n/m) k = 1 + m.

If k > m/2, choose S A \ f( σ) such that |S| = k. In this case, an alternative in S \ f( σ) is ranked first in (n/m) (m k) votes. Hence, by Lemma 1,

dist(f) dist(f, σ) 1 + m Pn i=1 I[S i f( σ)]/σi(S)

plu(f( σ), σ) 1 + m (n/m) (m k)

= 1 + m m k

as required.

Gap between upper and lower bounds: Note that the gap between the upper and the lower bounds is max(G1, G2, G3), where

G1 = maxk [1, m

9 ] 1+m(m k)/k 1+m(m 3k)/(6k), G2 = maxk [ m

2 ] 1+m(m k)/k

1+m , and G3 = 1.

Subset Selection Via Implicit Utilitarian Voting

For G1, it can be checked that the ratio of the upper and lower bounds is an increasing function of k for m 3. Hence, the maximum is achieved at k = m/9, and is equal to 1 + 8 m/(1 + m) 8. For G2, the ratio of the upper and the lower bounds is clearly a decreasing function of k. Hence, the maximum is achieved at k = m/9, and is equal to G1 8. Hence, the upper and the lower bounds are tight up to a constant factor of 8.

Distortion, randomized rules:

Upper bound: In our opinion, the proof of this part is the most non-trivial. It uses a construction that builds on the one used by Boutilier et al. (2015) for k = 1, but requires additional tools and introduces novel techniques. As mentioned at the beginning of this section, choosing a set uniformly at random from Ak (under which the marginal probability of every alternative being chosen is k/m) has distortion at most m/k. However, this approach does not work well if some alternatives are significantly better than others. In that case, one may wish to choose the alternatives with probabilities proportional to their quality . For a A, let us define its quality by its harmonic score har(a, σ) = P i [n] 1/σi(a). Then, we wish to choose alternative a with marginal probability k har(a, σ)/ P b A har(b, σ). Note that this quantity may be greater than 1. Moreover, this approach fails when all sets are almost equally good. Hence, we employ a combination of the two approaches. Fix 0 α 1, and for an alternative a A define

m + (1 α) k har(a, σ) P b A har(b, σ). (6)

Using the bihierarchy extension (Budish, Che, Kojima, & Milgrom, 2013) of the Birkhoffvon Neumann theorem (Birkhoff, 1946; von Neumann, 1953), we can show that there exists a distribution over Ak under which the marginal probabilities of selected alternatives match those dictated by Equation (6) if and only if

a A, 0 pa 1 and X

a A pa = k.

Note that pa 0 and P a A pa = k. The constraint pa 1 will be applied later to restrict the feasible values of α. For now, suppose such a distribution D exists. Consider a preference profile σ and a utility profile u σ. Let S arg max S Ak sw(S, u). Define

where Hm = Pm t=1 1/t is the mth harmonic number. Note that P a A har(a, σ) = n Hm. Now, consider two cases.

Case 1: Suppose sw(S , u) n X. Then,

ES D[sw(S, u)] = X

S Ak Pr D[S]

i=1 max a S ui(a)

S Ak Pr D[S] P a S ui(a)

a A ui(a) Pr S D[a S] 1

a A ui(a) α k

Caragiannis, Nath, Procaccia, & Shah

Hence, the distortion is

sw(S , u) ES D[sw(S, u)] n X α n/m = X m

m Hm α (1 α).

Case 2: Suppose sw(S , u) > n X. Then, for each alternative a S , let Na denote the subset of voters who rank a above any other alternative of S , i.e.,

Na = {i [n] : b S \ {a}, a σi b, }.

Let sw Na(S, u) denote the welfare of the voters in Na for the set of alternatives S under the utility profile u. Let Ta denote the total utility that agents in Na have for alternative a, i.e., Ta = P i Na ui(a). For all a A, we have har(a, σ) Ta because ui(a) 1/σi(a) for each voter i [n]. Because {Na}a S is a partition of the set of voters, we have

ES D[sw(S, u)] = ES D

a S sw Na(S, u)

a S Ta Pr S D[a S]

a S Ta (1 α) k har(a, σ) P b A har(b, σ) (1 α) k

n Hm (sw(S , u))2 .

Here, the fourth transition uses har(a, σ) Ta, the fifth transition uses the power-mean inequality, and the final transition uses sw(S , u) = P a S Ta. Now, the distortion is

sw(S , u) ES D[sw(S, u)] n Hm (1 α) sw(S , u) <

m Hm α (1 α),

where the final transition uses our assumption sw(S , u) > n X along with the definition of X.

Combined analysis: In both cases, the distortion is at most p

m Hm/(α(1 α)). The final step involves choosing the optimal value of α by minimizing this quantity subject to our constraints: pa 1 for all a A. This translates to

m + (1 α) k har(a, σ) P b A har(b, σ) 1, a A.

Note that har(a, σ) n, and P b A har(b, σ) = n Hm. Hence, we can safely replace these constraints by the following constraint:

m + (1 α) k Hm 1.

We used Mathematica to minimizing the value of p

m Hm/(α(1 α)) subject to this constraint; see Figure 2 for the relevant code. The result is as follows.

Subset Selection Via Implicit Utilitarian Voting

OPT = Full Simplify h Minimize hnq

m Hm α (1 α), α 0 α 1 α k

m + (1 α) k Hm 1 o , α i , OPT = Full Simplify h Minimize hnq

m Hm α (1 α), α 0 α 1 α k

m + (1 α) k Hm 1 o , α i , OPT = Full Simplify h Minimize hnq

m Hm α (1 α), α 0 α 1 α k

m + (1 α) k Hm 1 o , α i ,

m 2 k < m k 1 Hm > 0 m > Hm] ; m 2 k < m k 1 Hm > 0 m > Hm] ; m 2 k < m k 1 Hm > 0 m > Hm] ;

OPT[[1]] (* Optimal Distortion *) OPT[[1]] (* Optimal Distortion *) OPT[[1]] (* Optimal Distortion *)

( k+m)(k Hm) km + (k 2m)Hm 0

2 m Hm True

OPT[[2]] (* Optimal α value *) OPT[[2]] (* Optimal α value *) OPT[[2]] (* Optimal α value *)

( 1 2 km + (k 2m)Hm < 0

m(k Hm) k(m Hm) True

Fig. 2: Optimizing the upper bound on distortion using Mathematica

For k 2m Hm/(m+Hm), the optimal distortion is achieved at α = 1/2, and is equal to 2 m Hm;

For k > 2m Hm/(m+Hm), the optimal distortion is achieved at α = m (k Hm)/(k (m Hm)), and is equal to

(m k) (k Hm) .

Note that Hm (7/8) k. Further, let k m/2 (as this bound will anyway be replaced by a better bound for k > m/2). Hence, m k m/2. Substituting these, we get that the optimal distortion in this case is at most 4

Finally, recall that we have a universal upper bound of m/k, achieved by choosing from Ak uniformly at random. One can check that m/k < 4

m k for k > (m/4)1/3. Hence, combining the upper bounds from the analysis above with this universal upper bound gives us the desired result.

Lower bound: Fix a set of alternatives T = {a1, . . . , at}, where t k (the exact value of t will be determined later). Partition the set of voters into t buckets; each bucket i, denoted by Ni, consists of n/t voters. Construct a ranked profile σ in which for all i [t], all voters in bucket Ni rank alternative ai first, and the remaining alternatives arbitrarily. Let us analyze the output of a randomized rule f on this profile. For each alternative a A, define pa = Pr S f( σ)[a S]. Let X [t] be the indices corresponding to the lowest k values in the sequence (pai)i [t]; in other words, let X be such that {ai : i X} is the set of k alternatives from T with the lowest values of p. We now construct a utility profile u that is a modification of the one used in the lower bound for the deterministic case; instead of letting voters have high utility for alternatives that are not selected, we let voters have high utility for alternatives that are selected with the lowest probabilities.

1. For each i [t] \ X, every voter in bucket Ni has utility 1/m for each alternative.

Caragiannis, Nath, Procaccia, & Shah

(* Variable x = k/t *) (* Variable x = k/t *) (* Variable x = k/t *)

OPT = Full Simplify h Maximize hn (1 x)(1/m)+x (1 x)(1/m)+x2 , x k

m x 1 o , x i , OPT = Full Simplify h Maximize hn (1 x)(1/m)+x (1 x)(1/m)+x2 , x k

m x 1 o , x i , OPT = Full Simplify h Maximize hn (1 x)(1/m)+x (1 x)(1/m)+x2 , x k

m x 1 o , x i ,

m > 1 k < m k 1]; m > 1 k < m k 1]; m > 1 k < m k 1];

OPT[[1]] (* Optimal Distortion Bound *) OPT[[1]] (* Optimal Distortion Bound *) OPT[[1]] (* Optimal Distortion Bound *)

( k( 1+m)+m

( 1+k)k+m k(2 + k) + p

k3(4 + k) 2m (1+ m) 2

Solve h k(2 + k) + p

k3(4 + k) == 2m, k i (* Simplify the condition on k *) Solve h k(2 + k) + p

k3(4 + k) == 2m, k i (* Simplify the condition on k *) Solve h k(2 + k) + p

k3(4 + k) == 2m, k i (* Simplify the condition on k *)

nn k m m3/2

1+m o , n k m+m3/2

Fig. 3: Optimizing the lower bound on distortion using Mathematica

2. For each i X, every voter in bucket Ni has utility 1 for the alternative it ranks first (i.e., ai), and utility 0 for the remaining alternatives.

First, note that u σ. Further, under u the optimal set of k alternatives is clearly {ai : i X}, and its corresponding welfare is

because it provides utility 1/m to every voter in bucket Ni for i [t] \ X, and utility 1 to every voter in bucket Ni for i X. In contrast, the expected welfare under f is

i X pai. (7)

Next, note that P a T pa P a A pa = k, where the last equality follows because f always returns a set of size k. Hence, the sum of the lowest k values from {pa : a T} (i.e., P i X pai, by the definition of X) is at most (k/t) k. Substituting this in Equation (7), we obtain that the worst-case distortion is bounded from below by n n

Finally, we minimize this with respect to t using Mathematica; the relevant code, in which k/t is represented as variable x, is presented in Figure 3. The result is as follows.

dist(f) dist(f, σ)

1+2 m if k m( m 1)

m+k(k 1) otherwise.

Subset Selection Via Implicit Utilitarian Voting

Finally, note that

1 + 2 m ( m + 1)2

2 (1 + m) = m + 1

and m + k(m 1)

m + k(k 1) = m k + m k

k2 + m k m k k2 + m = m k + m/k,

which are the required bounds.

Gap between upper and lower bounds: In this case, the gap between the upper and the lower bounds is max(G1, G2, G3, G4), where

G1 = max k h 1, 2m Hm

i 2 m Hm m/2 4 p

k 2m Hm m+Hm ,( m

m k m/2 max

k 2m Hm m+Hm ,( m

k 28/3 m1/6,

4 ) 1 3 , m( m 1)

m/k m/2 max

4 ) 1 3 , m( m 1)

k 2 m (m/4)1/3 = 25/3 m1/6,

G4 = max k m( m 1)

m/k m/(k + m/k) = max k m( m 1)

k2 = 1 + m (m 1)2

= 1 + ( m + 1)2

It is easy to check that 28/3 m1/6 6.35 m1/6 is the highest among all four factors, for all values of m. Hence, the upper and the lower bounds are tight by a factor of at most 6.35 (m/4)1/6.

Regret, deterministic rules:

Upper bound: We show that the upper bound in this case is achieved by the rule f that selects the k alternatives with the highest plurality scores. Fix a profile σ and a set of alternatives T Ak \ {f ( σ)}. Let us calculate the worst-case regret due to T in the simplified regret formula from Lemma 1. Recall that there are plu(f ( σ), σ) votes i in which σi(f ( σ)) = 1, and thus we cannot have T i f ( σ). Further, there are exactly plu(T \ f ( σ), σ) votes i in which T i f ( σ) and σi(T) = 1. Hence, there are at most n plu(T \ f ( σ), σ) plu(f ( σ), σ) votes i in which T i f ( σ) and σi(T) 2. Substituting these into the formula from Lemma 1, we get that the worst-case regret due to T is at most

1 n plu(T \ f ( σ), σ)

1 + n plu(T \ f ( σ), σ) plu(f ( σ), σ)

= n + plu(T \ f ( σ), σ) plu(f ( σ), σ)

Caragiannis, Nath, Procaccia, & Shah

Next, note that plu(T \ f ( σ), σ) plu(T, σ) plu(f ( σ), σ), where the last equation follows due to the definition of f . Substituting this into Equation (9), we get that the regret is at most 1/2, as desired. For k > m/2, we can derive a better bound because we know T f ( σ) = . Note that T \ f ( σ) A \ f ( σ). Because f ( σ) consists of the k alternatives with the highest plurality scores, and the plurality scores sum to n, we have

plu(f ( σ), σ) k

Similarly, A \ f ( σ) consists of the m k alternatives with the lowest plurality scores. Hence, we have plu(A \ f ( σ), σ) (m k) n/m. Hence, we have

plu(T \ f ( σ), σ) plu(A \ f ( σ), σ) m k

Substituting Equations (10) and (11) into Equation (9), we get that the worst-case regret caused by T is at most

m n 2n = 1 k

Since the choices of T and σ were arbitrary, we have that reg(f ) 1 k/m, as required.

Lower bound: Next, we prove the matching lower bound. For k m/2, fix a set X A of 2k alternatives. Construct a profile σ in which every alternative in X appears first in n/(2k) votes. In this case, for any deterministic rule f with |f( σ)| = k, one can find a set T X \ f( σ) with |T| = k. Note that T f( σ) = , and there are exactly k n/(2k) = n/2 votes in which T i f( σ) and σi(T) = 1. Hence, due to Lemma 1, we have reg(f) reg(f, σ) (1/n) (n/2) = 1/2, as required. For k > m/2, we construct a profile σ in which every alternative appears first in exactly n/m votes. Once again, for any deterministic rule f with |f( σ)| = k, we can choose a set T A \ f( σ) with |T| = k. Note that |T \ f( σ)| = m k. Hence, there are (m k) n/m votes in which T i f( σ), and σi(T) = 1. Thus, due to Lemma 1, we have that reg(f) reg(f, σ) (1/n) (m k) n/m = 1 k/m, as required.

Regret, randomized rules:

Upper bound: We explicitly construct the randomized rule f that provides the required upper bound. Fix a preference profile σ. Without loss of generality, let us relabel the set of alternatives as A = {a1, a2, . . . , am} such that plu(ai, σ) plu(ai+1, σ) for i [m 1]. Further, define Ai {a1, a2, . . . , ai} for i [m]. We now prove an important technical result.

Lemma 2. There exists an integer value of t [k, m] such that

t k + plu(a, σ) X

1 plu(b, σ), a At, (12)

t k + plu(a, σ) X

1 plu(b, σ), a / At. (13)

Subset Selection Via Implicit Utilitarian Voting

Proof. Due to our ordering of the alternatives, the two conditions on t can be reduced to

k + plu(at+1, σ) X

1 plu(b, σ) t k + plu(at, σ) X

1 plu(b, σ), (14)

where we let plu(at+1, σ) = 0 if t = m. To prove that such a value of t exists, let us consider

f(t) = k + plu(at, σ) X

1 plu(b, σ) t.

If f(m) 0, one can check that t = m satisfies Equation (14). Suppose f(m) < 0. It is easy to check that f(k) 0. Further, f(t) is monotonically non-increasing in t. To see this, note that

f(t + 1) = k + plu(at+1, σ) X

1 plu(b, σ) (t + 1)

= k + plu(at+1, σ) X

1 plu(b, σ) + 1 (t + 1)

= k + plu(at+1, σ) X

1 plu(b, σ) t. (15)

Substituting plu(at+1, σ) plu(at, σ) in Equation (15), we get f(t + 1) f(t). Finally, consider the largest value of t satisfying f(t) 0. We have f(t) 0 and f(t+1) < 0. We can show that this value of t satisfies the two inequalities in Equation (14). The first inequality follows by substituting the value of f(t + 1) from Equation (15) into f(t + 1) < 0, and the second inequality follows directly from f(t) 0.

Using Lemma 2, fix a value of t [k, m] that satisfies Equation (13) and (12). Define

1 t k plu(a, σ) P b At 1/plu(b, σ) if a At,

0 otherwise.

Observe that 0 pa 1 for each a A due to Equation (12), and P a A pa = k. The bihierarchy extension (Budish et al., 2013) of the Birkhoff-von Neumann theorem (Birkhoff, 1946; von Neumann, 1953) implies that there exists a distribution over Ak (which can be computed in polynomial time) under which the probability of each alternative a A being selected is pa. We let our rule f return this distribution. Next, we bound reg(f ). Fix T Ak. Using Lemma 1, the worst-case regret due to T is 1 from each voter that ranks an alternative from T \ f ( σ) first, and at most 1/2 from each voter that ranks an alternative from A \ (f ( σ) T) first. Hence, the expected regret

Caragiannis, Nath, Procaccia, & Shah

a T\f ( σ) plu(a, σ) + 1

a A\(f ( σ) T) plu(a, σ)

a T\f ( σ) plu(a, σ)

a A\f ( σ) plu(a, σ)

a T (1 pa) plu(a, σ) + 1

a At pa plu(a, σ)

k (t k) 2n P a At 1/plu(a, σ) + 1

a At plu(a, σ) + t (t k) 2n P a At 1/plu(a, σ)

2n P a At 1/plu(a, σ) 1

a At plu(a, σ)

a At plu(a, σ) 1

2n t (m/n) 1

as desired. The first two equalities follow from the definitions of f , T, At, and pa. To see why the first inequality holds, note that

(1 pa) plu(a, σ) t k P b At 1/plu(b, σ), a A.

For a / At, this reduces to Equation (13). For a At, this follows from the definition of pa. The second inequality follows by the power mean inequality, the third inequality follows because the t alternatives in At have the highest plurality scores (hence, P a At plu(a, σ) t n/m), and the final inequality follows because t m.

Lower bound: This proof is very similar to the proof of the deterministic case. For k m/2, fix a set of alternatives X A such that |X| = 2k. Construct a profile σ in which every alternative in X appears first in n/(2k) votes. Now, let us consider a randomized rule f that returns a distribution over Ak. Let T denote the set of k alternatives from X with the least probability of being picked in S. Because P a X Pr[a f( σ)] k, we have P a T Pr[a f( σ)] k/2. Hence, P a T Pr[a / f( σ)] k/2. Now, from Lemma 1, the expected regret of f due to T is at least

a T I[a / f( σ)] n

a T Pr[a / f( σ)] 1

as required. Similarly, for k > m/2, once again construct a profile σ in which every alternative appears first in n/m votes. Consider a randomized rule f that returns a distribution over Ak. Let T be the set of k alternatives with the least probability of being picked in f( σ). Because P a A Pr[a f( σ)] k, we have P a T Pr[a f( σ)] k k/m. Hence,

Subset Selection Via Implicit Utilitarian Voting

P a T Pr[a / f( σ)] k (1 k/m). Once again, from Lemma 1, the expected regret of f due to T is at least

a T I[a / f( σ)] n

a T Pr[a / f( σ)] k

as required.

Gap between upper and lower bounds: Note that for k m/2, the ratio between the upper and the lower bounds is

(1/2) (1 k2/m2)

1/4 = 2 1 k2

For k > m/2, the ratio between the upper and the lower bounds is

(1/2) (1 k2/m2) (1/2) (k/m) (1 k/m).

It can be checked easily that this is a decreasing function of k. Hence, the maximum ratio is achieved at k = m/2, and is equal to 2. Thus, in both cases, the upper and the lower bounds in this case are tight up to a constant factor of 2.

Running time: Note that rules from our upper bounds only require calculating the plurality scores and finding a decomposition according to (the bihierarchy extension of) the Birkhoff-von Neumann theorem, both of which can be accomplished in polynomial time.

4. Empirical Comparisons

In Section 3 we provided analytical results for both deterministic and randomized rules. In our view, randomized rules are especially practicable when the output distribution is sampled multiple times, or when the voters are well-informed, or when the voters are indifferent about the outcome (e.g., they are software agents). Moreover, we believe that the results for randomized rules are of substantial theoretical interest. But our work is partly driven by its direct applications in Robo Vote (see Section 1.1), which does not satisfy the above conditions. This leads us to use deterministic voting rules, which is what we focus on hereinafter. Let f dist and f reg be the deterministic rules that minimize the worst-case distortion and regret, respectively, on every given preference profile. The deterministic results of Section 3 establish upper and lower bounds on their worst-case distortion/regret. In this section, we evaluate their average-case performance on simulated as well as real data, and compare them against nine well-known voting rules: plurality, approval voting, Borda count, STV, Kemeny s rule, the maximin rule, Copeland s rule, Bucklin s rule, and Tideman s rule.4

We perform three experiments: (i) choosing a utility profile uniformly at random from the simplex of all utility profiles, (ii) drawing a real-world utility profile from the Jester

4. For the score-based rules, the k-subset is selected by picking the top k alternatives based on their scores.

Caragiannis, Nath, Procaccia, & Shah

f reg f dist Plurality Borda STV Other

1 2 3 4 1.05

(a) Avg. Distortion

(b) Avg. Regret

Fig. 4: Uniformly random utility profiles.

(a) Avg. Distortion

1 2 3 4 0.02

(b) Avg. Regret

Fig. 5: Utility profiles from the Jester dataset.

datasets (Goldberg, Roeder, Gupta, & Perkins, 2001), and (iii) drawing a real-world preference profile from the Pref Lib datasets (Mattei & Walsh, 2013), and choosing a consistent utility profile uniformly at random. For each experiment, we have 8 voters and 10 alternatives, and test for k [4].5 For each setting, we perform 10 000 random simulations, and measure both distortion and regret for the actual utility profile, as opposed to the worst-case utility profile. The figures show the average performance with 95% confidence intervals. In all of our simulations, we observed that three of the classical voting rules stand out: Borda count performs well for choosing a single alternative (but not for choosing larger subsets) whereas plurality and STV perform well for choosing larger subsets (but not for choosing a single alternative). Hence, all of our graphs specifically distinguish these three rules in addition to f dist and f reg. Figure 4 shows the results for the first experiment where we choose the utility profile uniformly at random. Figure 5 shows the results for the second experiment where real-world utility profiles are drawn from one of the Jester datasets, in which more than 50 000 voters rated 150 jokes on a real-valued scale; the results from the other Jester dataset are almost identical. Finally, Figure 6 shows the results for the third experiment where real-world preference profiles are drawn from the Sushi dataset (5 000 voters ranking 100 different kinds of sushi) and the T-Shirt dataset (30 voters ranking 11 T-shirt designs) from Pref Lib.

5. In Robo Vote, we expect typical instances to have few voters and alternatives.

Subset Selection Via Implicit Utilitarian Voting

(a) Sushi: Avg. Distortion

(b) Sushi: Avg. Regret

(c) T Shirt: Avg. Distortion

(d) T Shirt: Avg. Regret

Fig. 6: Preference profiles from Sushi and T-Shirt datasets, uniformly random consistent utility profiles.

Experiments on other datasets from Pref Lib (AGH Course Selection, Netflix, Skate, and Web Search) yielded similar results. Right offthe bat, one can observe that the average-case distortion and regret values are much lower than their worst-case counterparts. For example, average regret is generally lower than 0.1 compare with the tight worst-case deterministic bound of 1/2 for k m/2. Much to our surprise, in all of our experiments, f reg outperforms f dist in terms of both average-case distortion (multiplicative loss) and regret (additive loss). While both measures of loss have been studied extensively in the literature, we are not aware of any previous work that compares the two approaches. At least in our social choice domain, the regret-based approach is clearly better on average. Moreover, in all cases but one (k = 1 in the Jester experiment), f reg also outperforms all the classical voting rules under consideration. We therefore conclude that, on random as well as on real-world instances, f reg provides superior performance in terms of social welfare maximization.

5. Computation and Implementation

In this section, we analyze and compare the two deterministic optimal rules f dist and f reg from a computational viewpoint. Selecting optimal subsets turns out to be challenging, as both rules are NP-hard to compute.

Caragiannis, Nath, Procaccia, & Shah

Theorem 2. Given a preference profile σ and an integer k, computing a k-subset of alternatives that has the minimum distortion or the minimum regret on σ is NP-hard.

Proof. We present a polynomial-time reduction from the minimum dominating set problem, which is known to be NP-hard (in fact, APX-hard) even in 3-regular graphs (see, e.g., Papadimitriou & Yannakakis, 1991). A set of nodes S is called a dominating set in a graph G = (V, E) if any node in V \ S is adjacent to a node in S, and is called a minimum dominating set if it is a dominating set of the minimum possible size. Let V = {v1, . . . , vn} (thus, n = |V |). Observe that 3-regularity of G implies |E| = 3n/2. Let c and d be positive integers such that c is a multiple of 12n, c 96n2Hd (where Hd is the dth harmonic number), and d = 3nc + 3c + P3n/2 i=2 5c c i

3n . Clearly, there exist such values of c and d satisfying c = O(n2 ln n) and d = O(n3 ln n), and they can be computed in polynomial time. Now, set k = 1 + 3n/4 , and construct a profile σ as follows. The set of alternatives is the union of three sets:

A = {a1, . . . , an} (each ai corresponds to the node vi V );

B = {b1, . . . , b3n/2} (each bi corresponds to an edge in E);

D = {f1, . . . , fd}.

The set of voters N is the union of the following sets:

Ne, which consists of 2c edge voters n nj e o

j {0,1,...,2c 1} for each edge e E;

N1, which consists of 3c voters;

Ni consisting of 14c

12n voters, for each i = 2, . . . , 3n/2.

The reader may check that the total number of voters is exactly d. Next, the votes in σ are as follows:

For each edge e = (vi1, vi2) E with i1 < i2, voter nj e ranks alternatives ai1 and ai2 at positions 2 and 3, respectively, when j is even, and at positions 3 and 2, respectively, when j is odd. Alternatives in A\{ai1, ai2} B are ranked at the bottom, in arbitrary order. Positions 1 and 4 through d + 2 are reserved for alternatives in D (see below for the way the alternatives in D are placed in these positions).

Voters in N1 rank alternative b1 in the first position, and alternatives in A B \ {b1} in the last positions, in arbitrary order. Positions 2 through d + 1 are reserved for alternatives in D.

For i = 2, . . . , 3n/2, voters in Ni rank alternative bi in the second position, and alternatives in A B \ {bi} in the last positions, in arbitrary order. Positions 1 and 3 through d + 1 are reserved for alternatives in D.

Alternatives in D are shuffled in a cyclic fashion in the votes within the positions reserved for them. More specifically, fix an order among the votes. Then, for i, j [d], let t = 1 + (i + j 2 mod d). Alternative fi appears in the tth reserved position of the jth vote.

Subset Selection Via Implicit Utilitarian Voting

Given this construction, the next lemma establishes a strong relation between the ksized set of alternatives with the minimum regret or distortion in σ, and the minimum dominating set in graph G. Theorem 2 then follows as our reduction is polynomial time.

Lemma 3. A k-sized set of alternatives has the minimum regret or the minimum distortion on σ if and only if it consists of the alternatives in A corresponding to the nodes of a minimum dominating set S of G and the alternatives b1, b2, . . . , bk |S |.

Proof. Let K denote the k-sized set of alternatives that consists of the alternatives in A corresponding to the nodes of a minimum dominating set S of G, and the alternatives b1, b2, . . . , bk |S |. We prove an upper and a lower bound on the regret of K on σ, which establishes that it is the unique k-sized set of alternatives with the minimum regret. We later provide the argument that shows it is also the unique k-sized set of alternatives with the minimum distortion.

Upper bound: Let K be a k-sized set of alternatives that is disjoint from K .6. We now show that the regret of K on σ due to K is at most

reg(K , σ) T

24n + 1 . (16)

Since T is independent of K itself, it would follow that the worst-case regret of K is also upper bounded by T. Consider an alternative ai A\K . Recall that this corresponds to the node vi V . Let vℓbe a node in S that is adjacent to vi. From Equation 1, the contribution of alternative ai to the regret is

0 in the c edge voters nj e corresponding to edge e = (vi, vℓ) that have alternative ai ranked third;

at most 1/3 in each of the remaining 2c edge voters that have alternative ai ranked third;

at most 1/2 in each of the 3c edge voters that have alternative ai ranked second;

smaller than 1/d in any other voter (because it is ranked below all alternatives in D).

Thus, the total contribution of ai to the regret is at most 2c/3 + 3c/2 + 1 = 13c/6 + 1. Due to cyclic shuffling, the contribution of an alternative in D to the regret is at most Hd. For i k + 1 |S |, the contribution of alternative bi to the regret is at most 1/2 from the voters in Ni, and at most 1/d in any other voter. In total, this contribution is in [7c/3 c i

24n, 7c/3 c i

24n + 1], and therefore is higher than the contribution of any alternative in (A D) \ K . Hence, the k alternatives that contribute the highest regret are bk+1 |S |, . . . , b2k |S |,

and their total contribution to the regret is at most P2k |S | i=k+1 |S | 7c

24n + 1 as desired.

6. If K shares alternatives with K , such alternatives do not cause any regret in the simplified regret formula from Equation (1). Hence, to compute the worst-case regret, it is sufficient to focus on sets K

that are disjoint from K .

Caragiannis, Nath, Procaccia, & Shah

Lower bound: Next, let K be a k-sized set of alternatives that does not follow the characterization of the lemma (i.e., does not consist of exactly the alternatives in A corresponding to the nodes of a minimum dominating set S of G and the alternatives b1, . . . , bk |S |). We show that reg(K, σ) > T. Let S be the set of nodes of G corresponding to the alternatives in K A. Let I(S) denote an independent set of nodes of G (i.e., no two nodes in I(S) are connected to each other) such that no node in I(S) is adjacent to any node in S. Construct a k-sized set K that consists of the alternatives in A corresponding to the nodes of I(S) (if any), and the k |I(S)| alternatives from B \ K with the smallest indices. We show that the regret of K on σ due to K is more than T. We do so by considering the contribution of the alternatives of K to the regret only from the votes in which they appear among the first three positions. For now, let us ignore the alternatives in D that appear in K; we will later the regret calculated to account for such alternatives. Let X = I[(B\K) {b1, . . . , bk |S| |K D|} = ]. Consider an alternative ai corresponding to the node vi I(S). Because the nodes in I(S) are mutually non-adjacent and non-adjacent to any node in S, ai K is ranked above all alternatives in K \ D in the edge voters nj e for j = 0, 1, . . . , 2c 1 and each edge e adjacent to node vi. Ignoring the alternatives in K D (that may be ranked in the first position of these voters), the contribution of ai to the regret is 1/2 from each of the 3c edge voters that rank ai in the second position, and 1/3 from each of the 3c edge voters that rank ai in the third position. Thus, the total contribution of the alternatives that correspond to the nodes in I(S) is 5c

2 . Next, consider the k |I(S)| alternatives from B \ K that have the smallest indices. If K contains all of b1, . . . , bk |S| |K D|, then K contains the alternatives bi for i = k |S| |K D| + 1, . . . , 2k |S| |K D| |I(S)|. Again, ignoring the alternatives in K D (that may be ranked in the first position in the votes of the voters in Ni), the contribution of bi to the regret of K is 1/2 from each of the 14c

12n voters in Ni that rank bi in the second position. If X = 1, we know that K does not use the alternatives of B with the smallest indices, and the contribution of the alternatives of B to the regret increases by at least c X

24n. Finally, we consider the fact that K may include alternatives from D. Each such alternative may be ranked first by a voter, for which we have incorrectly added a regret of at most 1/2. Hence, the actual regret may be (1/2) |K D| lower than our calculated regret. Combining the entire analysis, and observing that the regret due to K is a lower bound on the worst-case regret of K on σ, we get that

2k |S| |K D| |I(S)| X

i=k |S| |K D|+1

2k |S| |K D| X

i=k |S| |K D|+1

24n + 1 + c

6 |I(S)| ck

24n (|S | |S|) + ck

|K D| k + c X

reg(K , σ) + c

6 |I(S)| c k

24n (|S | |S|) + c k

|K D| k + c X

Subset Selection Via Implicit Utilitarian Voting

Finally, we analyze the quantities on the RHS of Equation (17) to derive that

reg(K, σ) reg(K , σ) > 7k

9 |K D|, (18)

which implies that reg(K, σ) > reg(K , σ), as required. We now perform a case-by-case analysis to establish Equation (18). First, suppose S is a dominating set of G.

If S is a minimum dominating set of G (i.e., |S| = |S |), we must have X = 1 or |K D| > 0.

* If X = 1, Equation (17) yields

reg(K, σ) reg(K , σ) c k

|K D| k + c 24n,

which in turn implies Equation (18) because the definition of c and the fact that k 1 imply c 24n > k and (c k)/(24n) (1/2) > (7k)/9.

* If X = 0 and |K D| > 0, Equation (17) yields

reg(K, σ) reg(K , σ) c k

k |K D| > 7k

where the last inequality follows from the definition of c.

If |S| > |S |, Equation (17) yields

reg(K, σ) reg(K , σ) c

24n 1 k + c k

where the last inequality follows from the definition of c.

Next, suppose S is not a dominating set of G. Here, we distinguish between two cases.

If |S| |S |, using |I(S)| 1, Equation (17) yields

reg(K, σ) reg(K , σ) c

24n 1 |K D| k.

Equation (18) now follows because the definition of c implies (c/6) > k and (c k)/(24n) 1 > (7k)/9.

If |S| < |S |, then we claim that |I(S)| (|S | |S|)/4. Indeed, because the minimum dominating set of G has size |S |, the set of nodes S must leave |S | |S| nodes of G

Caragiannis, Nath, Procaccia, & Shah

undominated. Because G is 3-regular, any independent set I(S) among these nodes should have size at least (|S | |S|)/4. Hence,

reg(K, σ) reg(K , σ) c

(|S | |S|) + c k

6n 1 |K D| k

which implies Equation (18) because the definition of c implies (c/24) (c k)/(24n) > k and c/(24n) (3/2) > (7/9).

This completes the proof of Equation (18) in all cases, and hence, concludes the proof of the regret part of the lemma. Let us now prove the distortion part of the lemma. Again, consider a k-sized set K that does not follow the characterization of the lemma (i.e., does not consist of exactly alternatives in A corresponding to the nodes of a minimum dominating set S of G and the alternatives b1, . . . , bk |S |). If K D = , then we have plu(K, σ) plu(K , σ). Hence,

dist(K, σ) = 1 + m reg(K, σ)

plu(K, σ) > 1 + m reg(K , σ)

3c = dist(K ),

where the second transition uses Equation (18). If K D = , we have plu(K, σ) 3c + |K D|, which, together with Equation (18), implies

dist(K, σ) = 1 + m reg(K, σ)

plu(K, σ) > 1 + m reg(K , σ) + 7k

9 |K D| 3c + |K D| > 1 + m reg(K )

3c = dist(K , σ).

The final transition holds because Equation (16) implies 7k/9 > reg(K , σ)/(3c). (Proof of Lemma 3)

This concludes the entire proof. (Proof of Theorem 2)

Given that f reg outperforms f dist in the experiments of Section 4, and that both rules are computationally hard, f reg stands out as the clear choice for implementation in our website Robo Vote. We therefore devoted our efforts to developing a scalable implementation for f reg. First, let us note the simplified formula for f reg that follows from Lemma 1:

f reg,k( σ) = arg min T Ak max S Ak

σi(S) . (19)

To better understand this formula, we consider the special case of k = 1. In this case,

f reg( σ) arg min a A max b A

Subset Selection Via Implicit Utilitarian Voting

Note that this voting rule is very similar to the classical maximin rule: replacing σi(b) with 1 in the denominator would yield the maximin rule. Thus, in some sense, this is a smooth version of the maximin rule, where the victory of b over a in voter i s vote is weighted by the strength of b in this vote (measured by 1/σi(b)). In our view, this intuitive structure makes f reg even more compelling.

10 20 30 40 50 0

Naive Submodular Submodular+Greedy Multi ILP Multi ILP+Greedy Single ILP Time Limit

Fig. 7: Running times of six approaches to computing f reg.

We now briefly describe six approaches we have developed for computing f reg:

1. Na ıve: This uses Equation (19), and requires Ω(n m k 2) operations, which is prohibitive even for small m.

2. Submodular: The regret for set S in choosing set T, i.e., P i [n]:S σi T 1/σi(S), is submodular in S. Hence, for each T Ak we can optimize over S Ak using any algorithm for the submodular maximization subject to cardinality constraint (SMCC) problem. We use the SFO toolbox for Matlab (Krause, 2010).

3. Submodular+Greedy: This improves the previous approach by first computing a 1 1/e greedy approximation to the SMCC instance for set T, and pruning T if this is already greater than the best regret found so far.

4. Multi ILP: Instead of using SMCC, for each T Ak we optimize over S Ak by solving an integer linear program (ILP) with roughly n m variables and n m2 constraints. Note that m k such ILPs need to be solved.

5. Multi ILP+Greedy: This improves the Multi ILP approach by using a greedy pruning procedure as before.

6. Single ILP: This approach solves a single but huge ILP with m k additional constraints.

Figure 7 shows the average running times of these approaches (and 95% confidence intervals) over 10 000 instances with n = 15, k = 3, and m varying from 10 to 50.7 The

7. The running time scales linearly in n, and increases with m k .

Caragiannis, Nath, Procaccia, & Shah

experiments were performed on a single machine with quad-core 2.9 GHz CPU and 32 GB RAM. A time limit of 2 minutes was set because a running time greater than this would not be helpful for our website, where the results need to be delivered quickly to the users. While the greedy pruning procedure does help reduce the running time of both the Submodular and Multi ILP approaches, Single ILP still computes f reg much faster than any other approach, solving instances with 50 alternatives in less than 10 seconds. We have therefore implemented Single ILP on Robo Vote.

6. Discussion

In this paper, we study a central problem in social choice theory that involves collectively selecting a set of k alternatives given ordinal preferences of n individuals over m alternatives. We take the viewpoint of implicit utilitarian voting, where our goal is to maximize the utilitarian social welfare according to underlying cardinal utilities given only ordinal information about these utilities available from the input preferences. Prior work by Boutilier et al. (2015) measures the loss due to incomplete information using the multiplicative notion of distortion, and analyzes this problem for the special case of k = 1 (i.e., selection of a single alternative). We introduce an additional loss measure, namely (additive) regret, provide a comprehensive theoretical analysis of the optimal distortion and regret for all k [1, m 1], and empirically show that the optimal rules f reg and f dist derived from this framework are superior to classical social choice rules for optimizing social welfare. We consider the empirical dominance of f reg over f dist, in terms of both regret and (surprisingly) distortion, to be especially significant. It would be interesting to understand, on a theoretical level, why this happens. A promising starting point is to derive analytical bounds on the average-case distortion of f reg and f dist under uniformly random utility profiles. We find it exciting that new theoretical questions in computational social choice are driven by concrete real-world applications. And while research in the field is often motivated by potential applications to multiagent systems, we focus on helping people not software agents make joint decisions.

Acknowledgments

This work was supported in part by NSF grants CCF-1215883, CCF-1525932, and IIS1350598; and by a Sloan Research Fellowship.

Anshelevich, E., Bhardwaj, O., & Postl, J. (2015). Approximating optimal social choice under metric preferences. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pp. 777 783.

Anshelevich, E., & Postl, J. (2016). Randomized social choice functions under metric preferences. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pp. 46 59.

Subset Selection Via Implicit Utilitarian Voting

Anshelevich, E., & Sekar, S. (2016). Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 390 396.

Arrow, K. (1951). Social Choice and Individual Values. Wiley.

Birkhoff, G. (1946). Three observations on linear algebra. Universidad Nacional de Tucum an, Revista A, 5, 147 151.

Blum, A., & Mansour, Y. (2007). Learning, regret minimization, and equilibria. In Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. (Eds.), Algorithmic Game Theory, chap. 4. Cambridge University Press.

Boutilier, C., Caragiannis, I., Haber, S., Lu, T., Procaccia, A. D., & Sheffet, O. (2015). Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227, 190 213.

Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016). Handbook of Computational Social Choice. Cambridge University Press.

Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1), 1 122.

Budish, E., Che, Y.-K., Kojima, F., & Milgrom, P. (2013). Designing random allocation mechanisms: Theory and applications. American Economic Review, 103(2), 585 623.

Campbell, D. E., & Kelly, J. S. (1996). Arrovian social choice correspondences. International Economic Review, 37(4), 803 823.

Caragiannis, I., & Procaccia, A. D. (2011). Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(9 10), 1655 1671.

Chakrabarty, D., & Swamy, C. (2014). Welfare maximization and truthfulness in mechanism design with ordinal preferences. In Proceedings of the 5th conference on Innovations in Theoretical Computer Science, pp. 105 120.

Chamberlin, J. R., & Courant, P. N. (1983). Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3), 718 733.

Filos-Ratsikas, A., Frederiksen, S. K. S., & Zhang, J. (2014). Social welfare in one-sided matchings: Random priority and beyond. In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pp. 1 12.

Goldberg, K. Y., Roeder, T., Gupta, D., & Perkins, C. (2001). Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, 4(2), 133 151.

Goldman, J., & Procaccia, A. D. (2014). Spliddit: Unleashing fair division algorithms. SIGecom Exchanges, 13(2), 41 46.

Krause, A. (2010). SFO: A toolbox for submodular function optimization. Journal of Machine Learning Research, 11, 1141 1144.

Krysta, P., Manlove, D., Rastegari, B., & Zhang, J. (2014). Size versus truthfulness in the house allocation problem. In Proceedings of the 15th ACM Conference on Economics and Computation (EC), pp. 453 470.

Caragiannis, Nath, Procaccia, & Shah

Lu, T., & Boutilier, C. (2011a). Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 280 286.

Lu, T., & Boutilier, C. (2011b). Robust approximation and incremental elicitation in voting protocols. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 287 293.

Mattei, N., & Walsh, T. (2013). Preflib: A library of preference data. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT), pp. 259 270.

Monroe, B. L. (1995). Fully proportional representation. American Political Science Review, 89(4), 925 940.

Papadimitriou, C. H., & Yannakakis, M. (1991). Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3), 425 440.

Procaccia, A. D., Reddi, S. J., & Shah, N. (2012). A maximum likelihood approach for selecting sets of alternatives. In Proceedings of the 28th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pp. 695 704.

Procaccia, A. D., & Rosenschein, J. S. (2006). The distortion of cardinal preferences in voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA), pp. 317 331.

Procaccia, A. D., Rosenschein, J. S., & Zohar, A. (2008). On the complexity of achieveing proportional representation. Social Choice and Welfare, 30(3), 353 362.

Skowron, P., Faliszewski, P., & Lang, J. (2015). Finding a collective set of items: From proportional multirepresentation to group recommendation. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pp. 2131 2137.

von Neumann, J. (1953). A certain zero-sum two-person game equivalent to the optimal assignment problem. In Kuhn, W., & Tucker, A. W. (Eds.), Contributions to the Theory of Games, Vol. 2, pp. 5 12.

Young, H. P. (1988). Condorcet s theory of voting. The American Political Science Review, 82(4), 1231 1244.