# subset_selection_via_implicit_utilitarian_voting__462494e2.pdf

Subset Selection Via Implicit Utilitarian Voting

Ioannis Caragiannis University of Patras, Greece

caragian@ceid.upatras.gr

Swaprava Nath Carnegie Mellon University, USA

swapravn@cs.cmu.edu

Ariel D. Procaccia Carnegie Mellon University, USA

arielpro@cs.cmu.edu

Nisarg Shah Carnegie Mellon University, USA

nkshah@cs.cmu.edu

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 an upcoming social choice website.

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

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

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

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

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 (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, Robo Vote (www.robovote.org), which is scheduled to launch in May 2016. The novelty of Robo Vote 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) Robo Vote 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 Robo Vote.

1.2 Related Work

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 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 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.

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 P

a2A 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).

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) = 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.

The distortion [Procaccia and Rosenschein, 2006] of a

2Formally, 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

dist(f,~σ) = sup

max S2Ak 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~σ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 Cesa Bianchi, 2012]. The regret of a (randomized) voting rule f on a preference profile ~σ is given by

reg(f,~σ) = 1

max S2Ak sw(S, ~u) E[sw(f(~σ), ~u)]

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 determin-

istic 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 7.3. 2. Distortion, randomized rules: There exists a random-

ized voting rule f such that

2pm 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 (pm 1)

m k+m/k otherwise.

These bounds are tight up to a factor of 9.4 m1/6. 3. Regret, deterministic rules: There exists a deterministic

voting rule f such that

m otherwise,

and this upper bound is completely tight. 4. Regret, randomized rules: There exists a randomized

voting rule f such that reg(f ) 1/2

. Moreover, for every randomized voting rule f,

( 1 4 if k m/2

All the upper bounds above can be achieved via polynomialtime algorithms.

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

0 50 100 100

(a) Distortion

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

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.

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

4Available 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) = P

i2[n] 1/σi(a). Then, we wish to choose alternative a with marginal probability k har(a)/ P

b2A 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

m + (1 ) k har(a) P

b2A har(b). (1)

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

8a 2 A, 0 pa 1 and

Suppose such a distribution D exists. Consider a preference profile ~σ and a utility profile ~u . ~σ. Let S 2 arg max S2Ak sw(S, ~u). Define

where Hm = Pm

t=1 1/t is the mth harmonic number. Note that P

a2A har(a) = n Hm. Now, consider two cases.

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

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

ui(a) Pr S D[a 2 S]

Hence, the distortion is

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

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

Na = {i 2 [n] : 8b 2 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

i2Na 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

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

sw Na(S, ~u)

Ta Pr S D[a 2 S]

Ta (1 ) k har(a) P

(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

a2S Ta. Now, the distortion is

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

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 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 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.

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

dist Plurality Borda STV Other

1 2 3 4 1.05

(a) Avg. Distortion

(b) Avg. Regret

Figure 2: Uniformly random utility profiles.

(a) Avg. Distortion

1 2 3 4 0.02

(b) Avg. Regret

Figure 3: Utility profiles from the Jester dataset.

(a) Sushi: Avg. Distortion

(b) Sushi: Avg. Regret

(c) T Shirt: Avg. Distortion

(d) T Shirt: Avg. Regret

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

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

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 Pref Lib 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 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

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

6In Robo Vote, 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.

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

reg. 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 50 000 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 (5 000 voters ranking 100 different kinds of sushi) and the T-Shirt dataset (30 voters ranking 11 T-shirt designs) from Pref Lib. Experiments on other datasets from Pref Lib (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

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 Robo Vote. 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

reg,k(~σ) = arg min

1 σi(S). (2)

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

reg(~σ) 2 arg min

i2[n]:b σia

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

1. Na ıve: This uses Equation (2), and requires (n

)2) operations, which is prohibitive even for small m. 2. Submodular: The regret for set S in choosing set T, i.e., P

i2[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 ap-

proach 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 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

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

additional constraints.

Figure 5 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 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.

10 20 30 40 50 0

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

Figure 5: Running times of six approaches to computing f

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

reg under uniformly random utility profiles.

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

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

References [Anshelevich and Sekar, 2016] E. Anshelevich and S. Sekar.

Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 2016. Forthcoming. [Anshelevich et al., 2015] E. Anshelevich, O. Bhardwaj, and

J. Postl. Approximating optimal social choice under metric preferences. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pages 777 783, 2015. [Arrow, 1951] K. Arrow. Social Choice and Individual Val-

ues. Wiley, 1951. [Birkhoff, 1946] G. Birkhoff. Three observations on linear

algebra. Universidad Nacional de Tucum an, Revista A, 5:147 151, 1946. [Blum and Mansour, 2007] A. Blum and Y. Mansour. Learn-

ing, regret minimization, and equilibria. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 4. Cambridge University Press, 2007. [Boutilier et al., 2015] C. Boutilier, I. Caragiannis, S. Haber,

T. Lu, A. D. Procaccia, and O. Sheffet. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227:190 213, 2015. [Brandt et al., 2016] F. Brandt, V. Conitzer, U. Endress,

J. Lang, and A. D. Procaccia, editors. Hanbook of Computational Social Choice. Cambridge University Press, 2016. [Bubeck and Cesa-Bianchi, 2012] S. Bubeck and N. Cesa-

Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1 122, 2012. [Budish et al., 2013] E. Budish, Y.-K. Che, F. Kojima, and

P. Milgrom. Designing random allocation mechanisms: Theory and applications. American Economic Review, 103(2):585 623, 2013. [Campbell and Kelly, 1996] D. E. Campbell and J. S. Kelly.

Arrovian social choice correspondences. International Economic Review, 37(4):803 823, 1996. [Caragiannis and Procaccia, 2011] I. Caragiannis and A. D.

Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(9 10):1655 1671, 2011. [Chamberlin and Courant, 1983] J. R. Chamberlin and P. N.

Courant. Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3):718 733, 1983. [Goldberg et al., 2001] K. Y. Goldberg, T. Roeder, D. Gupta,

and C. Perkins. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, 4(2):133 151, 2001.

[Goldman and Procaccia, 2014] J. Goldman and A. D. Pro-

caccia. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges, 13(2):41 46, 2014. [Krause, 2010] A. Krause. SFO: A toolbox for submodular

function optimization. Journal of Machine Learning Research, 11:1141 1144, 2010. [Lu and Boutilier, 2011a] T. Lu and C. Boutilier. Budgeted

social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 280 286, 2011. [Lu and Boutilier, 2011b] T. Lu and C. Boutilier. Robust ap-

proximation and incremental elicitation in voting protocols. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 287 293, 2011. [Mattei and Walsh, 2013] N. Mattei and T. Walsh. Preflib:

A library of preference data. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT), pages 259 270, 2013. [Monroe, 1995] B. L. Monroe. Fully proportional represen-

tation. American Political Science Review, 89(4):925 940, 1995. [Procaccia and Rosenschein, 2006] A. D. Procaccia and J. S.

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

and A. Zohar. On the complexity of achieveing proportional representation. Social Choice and Welfare, 30(3):353 362, 2008. [Procaccia et al., 2012] A. D. Procaccia, S. J. Reddi, and

N. Shah. A maximum likelihood approach for selecting sets of alternatives. In Proceedings of the 28th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 695 704, 2012. [Skowron et al., 2015] P. Skowron, P. Faliszewski, and J. Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pages 2131 2137, 2015. [von Neumann, 1953] J. von Neumann. A certain zero-sum

two-person game equivalent to the optimal assignment problem. In W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume 2, pages 5 12. 1953. [Young, 1988] H. P. Young. Condorcet s theory of voting.

The American Political Science Review, 82(4):1231 1244, 1988.