Subset Selection via Implicit Utilitarian Voting

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 et al., 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

Swaprava Nath

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

Nisarg Shah

Carnegie Mellon University, USA nkshah@cs.cmu.edu

makes preference elicitation much easier, it does seem to be at odds with the utilitarian viewpoint.

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 et al. [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 Cf. utilitarian voting, which has sporadically been used to refer to both approval voting and range voting.

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 (www.spliddit.org), a fair division website [Goldman and 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.

Since May 2015, some of us have been working on the design and implementation of a new not-for-profit social choice website, RoboVote (www.robovote.org), which is scheduled to launch in May 2016. The novelty of RoboVote is that it relies on optimization-based approaches. For the case of objective votes - when a ground truth ranking of the alternatives exists (e.g., the order of different stocks by the relative change in their prices tomorrow) - RoboVote implements voting rules that pinpoint the most likely best alternative [Young, 1988], or the set most likely to contain it [Procaccia et al., 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 RoboVote.

1.2 RelatedWork

In addition to the aforementioned papers [Procaccia and 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 and Procaccia, 2011; Anshelevich et al., 2015; Anshelevich and 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. 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 ChamberlinCourant 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 and Courant, 1983; Procaccia et al., 2008]. Skowron et al. [2015] generalize 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 2 [n] submits a ranking σi 2 L over the alternatives, and 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 ~σ 2 Ln .

Next we need to define the utility of a voter for a set of alternatives. For S ✓ A, we define ui(S) = maxa2S 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 and Courant, 1983; Monroe, 1995; Procaccia et al., 2008; Lu and Boutilier, 2011a]. Then, the (utilitarian) social welfare of S given the utility profile ~u is sw(S↪ ~u) = Pni=1 ui(S).

We assume the rankings are induced by comparisons between the voters' underlying utilities. For i 2 N and a 2 A, let ui(a) 2 [0↪ 1] be the utility of voter i for alternative a. As in previous papers [Boutilier et al., 2015; Caragiannis and Procaccia, 2011], we assume that the utilities are normalized such that Pa2A ui(a) = 1 for all i 2 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 2 A and i 2 N, a ≻σi b implies ui(a) ≥ ui(b).

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.

The distortion [Procaccia and Rosenschein, 2006] of a

2 Formally, this is a special case of social choice correspondences with fixed output cardinality [Campbell and Kelly, 1996].

(randomized) voting rule f on a preference profile ~σ is

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~σ2Ln 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 and Boutilier, 2011b]; similar measures have been extensively studied in decision theory and machine learning [Blum and Mansour, 2007; Bubeck and CesaBianchi, 2012]. The regret of a (randomized) voting rule f on a preference profile ~σ is given by

As before, define the regret of a rule f to be reg(f) = max~σ2Ln 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(pm · 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 worstcase distortion is always ⌦(pm).

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, it is easy to show that the voting rule f that selects a subset from Ak uniformly at random has dist(f)  m◁k. However, since we can already achieve O(pm· log⇤m) distortion for k = 1, a bound of m◁k provides an improvement only for k = ⌦(pm◁ 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 ⌦(pm) for all values of k up to ⇥(pm).

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

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,

These bounds are tight up to a constant factor of 7▷3.

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

where Hm = ⇥(logm) is the mth harmonic number. Moreover, for every randomized voting rule f,

These bounds are tight up to a factor of 9▷4 · m1◁6 .

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

and this upper bound is completely tight.

1. Regret, randomized rules: There exists a randomized voting rule f ⇤ such that reg(f ⇤ )  1◁2 · (1-k2 ◁m2 ). Moreover, for every randomized voting rule f,

All the upper bounds above can be achieved via polynomialtime 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

The intricate proof of Theorem 1 appears in the full version of the paper. 4 Below, we just sketch one part of the proof that we find especially interesting.

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.

4 Available at: www.cs.cmu.edu/⇠arielpro/papers.html

Proof sketch of the upper bound in part 2 of Theorem 1. Our construction builds on the one used by Boutilier et al. [2015] for k = 1, but uses 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 2 A, let us define its quality by its harmonic score har(a) = Pi2[n] 1◁σi(a). Then, we wish to choose alternative a with marginal "probability" k · har(a)◁ Pb2A 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 2 A define

Using the bihierarchy extension [Budish et al., 2013] of the Birkhoff-von 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 are consistent with Equation (1) if and only if

Suppose such a distribution D exists. Consider a preference profile ~σ and a utility profile ~u . ~σ. Let S⇤ 2 argmaxS2Ak sw(S↪ ~u). Define

where Hm = Pmt=1 1◁t is the mth harmonic number. Note that Pa2A har(a) = n · Hm. Now, consider two cases.

Case 1: Suppose sw(S⇤ ↪ ~u)  n · X. Then,

Hence, the distortion is

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

Let swNa (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 = Pi2Na ui(a). It can be shown (although it is nontrivial) that har(a) ≥ Ta for all a 2 A. Because ¶Na♦a2S⇤ is a partition of the set of voters, we have

Here, the fourth transition uses har(a) ≥ Ta, the fifth transition uses the power-mean inequality, and the final transition uses sw(S⇤ ↪ ~u) = Pa2S⇤ Ta. Now, the distortion is

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 pmHm◁(↵(1-↵)). The final step involves choosing the optimal value of ↵ by minimizing this quantity subject to our constraints: pa  1 for all a 2 A. Simplifying the bound obtained along with our universal distortion bound of m◁k yields the required upper bound. ⌅

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 RoboVote (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 averagecase 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. 5

Figure 4: Preference profiles from the Sushi and the T-Shirt datasets, uniformly random consistent utility profiles.

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 datasets [Goldberg et al., 2001], and (iii) drawing a realworld preference profile from the PrefLib datasets [Mattei and 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 2 [4]. 6 For each setting, we perform 10000 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 .

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

6 In RoboVote, we expect typical instances to have few voters and alternatives. But we chose m > 2k because otherwise the problem would be trivial: for k ≥ m◁2, picking the top k alternatives based on plurality scores is optimal for both distortion and regret.

Figure 2 shows the results for the first experiment where we choose the utility profile uniformly at random. Figure 3 shows the results for the second experiment where real-world utility profiles are drawn from one of the Jester datasets, in which more than 50000 voters rated 150 jokes on a realvalued scale; the results from the other Jester dataset are almost identical. Finally, Figure 4 shows the results for the third experiment where real-world preference profiles are drawn from the Sushi dataset (5000 voters ranking 100 different kinds of sushi) and the T-Shirt dataset (30 voters ranking 11 T-shirt designs) from PrefLib. Experiments on other datasets from PrefLib (AGH Course Selection, Netflix, Skate, and Web Search) yielded similar results.

Right off the 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 regretbased 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; the proof of this nontrivial result appears in the full version.

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.

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 RoboVote. We therefore devoted our efforts to developing a scalable implementation for f ⇤ reg .

The first step is to simplify the description of f ⇤ reg . Given a ranking σ and an alternative a 2 A, recall that σ(a) denotes the position of a in σ. For a set S ✓ A, let σ(S) = mina2S σ(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 in σ to every alternative in S. Using these notations, it is relatively straightforward to prove that

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

Note that this voting rule is very similar to the classical maximin rule: replacing 1◁σi(b) with 1 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.

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

1. Na¨ıve: This uses Equation (2), and requires ⌦(n · (mk )2 ) operations, which is prohibitive even for small m.
2. Submodular: The regret for set S in choosing set T, i.e., Pi2[n]:S≻σi T 1◁σi(S), is submodular in S. Hence, for each T 2 Ak we can optimize over S 2 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. MultiILP: Instead of using SMCC, for each T 2 Ak we optimize over S 2 Ak by solving an integer linear program (ILP) with roughly n · m variables and n · m2 constraints. Note that (mk ) such ILPs need to be solved.
5. MultiILP+Greedy: This improves the MultiILP approach by using a greedy pruning procedure as before.
6. SingleILP: This approach solves a single but huge ILP with (mk ) additional constraints.

Figure 5 shows the average running times of these approaches (and 95% confidence intervals) over 10000 instances with n = 15, k = 3, and m varying from 10 to 50. 7 The 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 MultiILP approaches, SingleILP still computes f ⇤ reg much faster than any other approach, solving instances with 50 alternatives in less than 10 seconds. We have therefore implemented SingleILP on RoboVote.

6 Discussion

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.

We also remark that we consider the empirical dominance of f ⇤ reg , 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 averagecase distortion of f ⇤ dist and f ⇤ reg under uniformly random utility profiles.

7 The running time scales linearly in n, and increases with (mk ).

Acknowledgments

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