# proportional_rankings__c999fca5.pdf

Proportional Rankings

Piotr Skowron TU Berlin, Germany p.k.skowron@gmail.com

Martin Lackner University of Oxford, UK martin.lackner@cs.ox.ac.uk

Markus Brill TU Berlin, Germany markus.brill@campus.tu-berlin.de

Dominik Peters University of Oxford, UK dominik.peters@cs.ox.ac.uk

Edith Elkind University of Oxford, UK edith.elkind@cs.ox.ac.uk

We extend the principle of proportional representation to rankings: given approval preferences, we aim to generate aggregate rankings so that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Such rankings are desirable in situations where initial segments of different lengths may be relevant, e.g., in recommender systems, for hiring decisions, or for the presentation of competing proposals on a liquid democracy platform. We define what it means for rankings to be proportional, provide bounds for well-known aggregation rules, and experimentally evaluate the performance of these rules.

1 Introduction Consider a population with dichotomous (approval) preferences over a set of 300 alternatives. Assume that 50% of the population approves of the first 100 alternatives, 30% of the next 100 alternatives, and 20% of the last 100. Suppose that we want to obtain a ranking of the alternatives that reflects the preferences of the population. Perhaps the most straightforward approach is to use Approval Voting (AV), which ranks the alternatives from the most frequently approved to the least frequently approved. A striking property of the resulting ranking is that half of the population does not approve any of the first 100 alternatives in the ranking. In many scenarios, rankings produced by Approval Voting are highly unsatisfactory; rather, it is desirable to interleave alternatives supported by different (sufficiently large) groups. For instance, consider an anonymous user running a search engine to find results for the query Armstrong . If 50% of the users performing this search would like to see results for Neil Armstrong, 30% for Lance Armstrong, and 20% for Louis Armstrong, it is not desirable to only place results referring to Neil Armstrong in the top part of the ranking; rather, results related to each of the Armstrongs should be displayed in appropriately high positions. There are numerous applications where such diversity within collective rankings is desirable. For instance, consider recommendation systems which aim at accommodating different types of users (the estimated preferences of these user types should be represented proportionally to their likelihood),

a human-resource department providing hiring recommendations when it is unclear how many positions are to be filled, or committee elections with some additional structure (e.g., when we want to elect a committee with a chairman and vicechairman, as well as substitute members). Another application in which diversity in rankings is relevant is liquid democracy [Behrens et al., 2014]. A defining feature of liquid democracy is that all participants are allowed (and encouraged) to contribute to the decision-making process. This may lead to situations where a very large number of proposals need to be considered. Since it cannot be expected that every participant studies all available alternatives before making a decision, the order in which competing alternatives are presented plays a crucial role [Behrens et al., 2014, Chapter 4.10]. In particular, the LIQUIDFEEDBACK system [Behrens et al., 2014], used by several political parties and other organisations, implements one of the rules (reverse Seq PAV) that we analyze in this paper. Thus, obtaining a better understanding of proportionality in rankings has direct relevance to real-world applications. The idea of rankings that are diversified with respect to the preferences of a population appears in several streams of research. For example, in the context of search engines, this aim is often referred to as diversifying search results [Welch et al., 2011; Santos et al., 2015; Kingrani et al., 2015; Wang et al., 2016]. There are also models which incorporate this idea into online advertising (see the work of Hu et al. [2011], and the references therein). In the context of liquid democracy, Behrens et al. observe that using AV gives rise to what they call the noisy minorities problem: relatively small groups of very active participants can flood the system with their contributions, creating the impression that their opinion is much more popular than it actually is. This is problematic insofar as other alternatives (that are potentially much more popular) run the risk of being buried and not getting sufficient exposure. Behrens et al. suggest that, in order to prevent this problem, the ranking mechanism needs to ensure that the order adequately reflects the opinions of the participants. In this paper, we propose an abstract model applicable to all these scenarios, and initiate a formal study of the problem of finding a proportional collective ranking. In our study, we use tools from political and social sciences, and in particular we adapt the concept of proportional representation [Balinski and Young, 1982; Monroe, 1995] to the case of rankings.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Informally, proportional representation requires that the extent to which a particular preference or opinion is represented in the outcome should be proportional to the frequency with which this preference or opinion occurs within the population. For instance, proportional representation is often a requirement in the context of parliamentary elections, where candidates are grouped into political parties and voters express preferences over parties. If a party receives, say, 20% of the votes, then proportional representation requires that this party should be allocated (roughly) 20% of the parliamentary seats (see the work of Laslier, 2012, for a discussion of arguments for and against proportional representation in a political context). The concept of proportional representation can be extended to the case of rankings in a very natural way. Informally, we say that a ranking τ is proportional if each prefix of τ, viewed as a subset of alternatives, satisfies (some form of) proportional representation. In more detail, inspired by the concepts of Extended or Proportional Justified Representation that have been recently introduced in the context of multiwinner elections [Aziz et al., 2017; S anchez-Fern andez et al., 2017], we require that, for each sufficiently large group of voters with consistent preferences, a proportional number of alternatives approved by this group is placed appropriately highly in the ranking. The position of such alternatives in the ranking depends on the level of their support, indicated by the size and the cohesiveness of the respective group of voters.

Our Contribution. (i) We formalize the concept of proportionality of a ranking and introduce a quantitative way of measuring it, (ii) we observe that several known multiwinner rules satisfying committee monotonicity can be viewed as ranking rules, (iii) we provide theoretical bounds on the quality of proportional representation of several ranking rules, and (iv) we experimentally evaluate ranking rules.

Related Work. Proportional representation is traditionally studied in scenarios where a subset of alternatives (such as a parliament or a committee) needs to be chosen (see the survey by Faliszewski et al. [2017]). The setting that is most commonly studied is that of closed party lists, where alternatives are grouped into pairwise disjoint parties and voters are restricted to selecting a single party [Gallagher, 1991]. In this setting, providing proportional representation reduces to solving an apportionment problem [Balinski and Young, 1982; Pukelsheim, 2014; Brill et al., 2017b]. In an influential paper, Monroe [1995] generalized the concept of proportional representation to settings where voters preferences are given as rank-orderings of the set of alternatives. For approval preferences, concepts capturing proportional representation have recently been studied by Aziz et al. [2017] and S anchez Fern andez et al. [2017]. The setting considered in this paper differs from all of the above settings in that we are interested in ranking the alternatives, rather than choosing a subset of them. To the best of our knowledge, proportional rankings based on approval preferences have not been considered in the literature. In the context of linear (i.e., rank-order) preferences, proportional rankings are discussed by Schulze [2011]. However, this paper neither

proposes a measure of proportionality, nor does it compare the proportionality provided by different rules.

An extended version of this paper, including all proofs, can be found on ar Xiv [Skowron et al., 2016].

2 Preliminaries For s N, we write [s] = {1, . . . , s}. For each set X, we let S(X) and Sk(X) denote the set of all subsets of X, and the set of all k-element subsets of X, respectively. Let N = [n] be a finite set of voters and A a finite set of m alternatives. Each voter i N approves a nonempty subset of alternatives Ai A. For each a A, we write Na for the set of voters who approve a, i.e., Na = {i N : a Ai}. We refer to |Na| as the approval score of a. A list P = (A1, . . . , An) of approval sets, one for each voter i N, is called a profile on (A, N). A ranking is a linear order over A. For a ranking r and for k [m], we denote the k-th element in r by rk. Thus, r can be represented by the list (r1, r2, . . . , rm). Given a ranking r = (r1, . . . , rm) and k [m], we let r k = {r1, . . . , rk} denote the subset of A consisting of the top k elements according to r. An (approval-based) ranking rule f maps a profile P on (A, N) to a ranking f(P) over A. In what follows, we consider several ranking rules that can be obtained by adapting existing multiwinner rules. An (approval-based) multiwinner rule takes as input a profile P on (A, N) and an integer k [m] and outputs a k-element subset of A, referred to as the winning committee. A generic adaptation of multiwinner rules to ranking rules is possible whenever the respective multiwinner rule R has the property that R(P, k 1) R(P, k) for all k m (this property is known as committee monotonicity or house monotonicity): if this is the case, we can produce a ranking by placing the unique alternative in R(P, k) \ R(P, k 1) in position k. Fix a profile P. We consider the following ranking rules:1

Approval Voting (AV). AV ranks the alternatives in order of their approval score, so that |Nr1| |Nrm|. Sequential Thiele Rules. This family of rules has been proposed by Danish polymath Thorvald N. Thiele [1895] (and is also known as Reweighted Approval Voting). It is parameterized by weight vectors, i.e., sequences (w1, w2, . . . ) of nonnegative reals. For a given weight vector w = (w1, w2, . . . ) and a subset S A of alternatives, define the w-Thiele score of S as w(S) = P

i N P|Ai S| j=1 wj. Usually, it is assumed that w1 w2 . . . ; the intuition behind this constraint is that voters prefer sets S that contain more of their approved alternatives, but there are decreasing marginal returns to adding further such alternatives to S. The sequential w Thiele rule constructs a ranking iteratively, starting with the empty partial ranking r = (). In step k [m], it appends to r an alternative a with maximum marginal contribution w(r k 1 {a}) w(r k 1) among all yet unranked alternatives. Many interesting rules belong to this family for suitable

1All rules that we describe may have to break ties at some point in the execution; we adopt an adversarial approach to tie-breaking, i.e., we say that a ranking rule satisfies a property only if it satisfies it for all possible ways of breaking ties.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

weight vectors w. For example, AV can be viewed as the sequential w-Thiele with w = (1, 1, 1, . . .), Sequential Proportional Approval Voting (Seq PAV) is defined by w PAV = (1, 1/2, 1/3, . . .), Greedy Chamberlin Courant (Greedy CC) is defined by w = (1, 0, 0, . . .), and for every p > 1, the p-geometric rule is defined by w = (1/p, 1/p2, 1/p3, . . .).

Reverse Seq PAV. This rule is a bottom-up variant of Seq PAV; it has been introduced by Thiele [1895] (in the multiwinner setting) and was independently proposed by Behrens et al. [2014] under the name harmonic weighting. Initially it sets S = A and r = (). Then, at each step it picks an alternative a minimizing w PAV(S) w PAV(S \ {a}), removes it from S and prepends it to r, i.e., the rule builds a ranking starting with the lowest-ranked alternative.

Phragm en s Rule. Swedish mathematician Edvard Phragm en [1895] proposed a committee selection rule that can be phrased as a load balancing procedure: every alternative incurs a load of one unit, and the load of alternative a has to be distributed among all voters in Na. Phragm en s rule constructs a ranking iteratively, starting with the empty partial ranking r = (). Initially, the load of each voter is 0. At each step, the rule picks a yet unranked alternative and distributes its associated load of 1 over the voters who approve it; the alternative and the load distribution scheme are chosen so as to minimize the maximum load across all voters. This alternative is then appended to the ranking r. (For details, see the work of Mora and Oliver [2015], Janson [2016], and Brill et al. [2017a]).

3 Measures of Proportionality

In this section, we define a measure of proportionality for rankings and then extend it to ranking rules. In what follows, let P be a profile on (A, N) with |A| = m and |N| = n. Given a group of voters N N and a set of alternatives S A, a natural measure of the group s satisfaction provided by S is the average number of alternatives in S that are approved by a voter in N . Thus, we define

avg(N , S) = 1 |N |

i N |Ai S|.

We refer to avg(N , S) as the average representation of N with respect to S. To extend this idea to rankings, we consider the case where the subset S is an initial segment of a given ranking r, i.e., S = r k for some k [m]. Intuitively, every group N wants to have an average representation avg(N , r k) that is as large as possible, for all k [m]. Now, in our model, whether a group of voters deserves to be represented in the top positions of a ranking depends on two parameters: its relative size and its cohesiveness, i.e., the number of alternatives that are unanimously approved by the group members. This motivates the following definition.

Definition 1. (Significant group) Fix a profile P on (A, N). The proportion of a group N N is α(N ) = |N |/|N|, and the cohesiveness of N is given by λ(N ) = | T i N Ai|. Given α (0, 1] and λ [m], we say that a group N is (α, λ)-significant in P if |N | = αn and λ(N ) λ.

The following definition captures the intuitively compelling idea that a group can demand to be represented in the top positions of the ranking in proportion to its significance, as long as the number of demanded alternatives does not exceed the cohesiveness of the group. Definition 2. (Justifiable demand) The justifiable demand of a group N N with respect to the top k positions of a ranking is defined as

jd(N , k) = min( α(N ) k , λ(N )).

For example, if a group contains 25% of the voters and has a cohesiveness of 3, it has a justifiable demand of 1 with respect to the top four positions, a justifiable demand of 2 with respect to the top eight positions, and a justifiable demand of 3 with respect to the top twelve positions, which is also its maximum justifiable demand. It would be desirable to find a rule that provides every group with an average representation that meets the group s justifiable demand. However, the following example shows that this is not always possible. Example 1. Let A = {a, b, c} and n = 6 and consider the profile P given by A1 = {a}, A2 = {a, b}, A3 = {b}, A4 = {b, c}, A5 = {c}, and A6 = {a, c}. Consider the ranking r = (a, b, c). The group N = {4, 5, 6} has α(N ) = 1/2, λ(N ) = 1. Therefore, its justifiable demand with respect to the top two positions is jd(N , 2) = min( 1/2 2 , 1) = 1. However, its average representation with respect to the top two positions of r is only avg(N , {a, b}) = 2/3. Since P is completely symmetric with respect to the alternatives, we can find such a group for every other ranking as well. Example 1 shows that it may not be feasible to provide each group with the level of representation that meets its justifiable demand, but it might be possible to guarantee a large fraction of it. For instance, in Example 1 one can ensure that avg(N , k) 2/3 jd(N , k) for all groups N and for all k 3. This observation leads to the following definition. Definition 3. (Optimal ranking) We define the quality of a ranking r for a profile P as

q P (r) = min k [m],N N: jd(N ,k)>0

avg(N , r k)

jd(N , k) .

An optimal ranking for P is a ranking in arg maxr q P (r). We observe that q P (r) is well-defined, i.e., there is always a pair (N , k) with jd(N , k) > 0. Indeed, take an alternative a with maximum approval score: as Ai = for all i N, we have |Na| n/m by the pigeonhole principle. Further, λ(Na) 1, so jd(Na, m) min( n/m

n m , 1) = 1. Example 2. Consider the profile from Example 1 and the ranking r = (a, b, c). For the first position in this ranking (i.e., for k = 1), there exists no group of voters with a positive justifiable demand, since such a group would need to consist of all the voters who all approve at least one common alternative. For k = 2, the justifiable demand of three groups of voters is equal to 1. These groups are N1 = {1, 2, 6}, N2 = {2, 3, 4}, and N3 = {4, 5, 6}, with commonly approved alternatives a, b, and c, respectively. The average representation of groups N1,

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

N2, and N3 is equal to 4/3, 4/3, and 2/3, respectively. There is no group with justifiable demand of 2 with respect to the top two positions. Finally, for k = 3 there are 9 groups with justifiable demand of 1 (these are {1, 2}, {1, 6}, {2, 3}, {2, 4}, {2, 6}, {3, 4}, {4, 5}, {4, 6}, and {5, 6}); each such group has an average representation of at least one. There is no group with a justifiable demand of two such a group would need to contain four voters, who all approve at least two common alternatives and, clearly, no group with a justifiable demand of three. Thus, the quality of our ranking is q P (r) = 2/3, and this is an optimal ranking. Unfortunately, good rankings are hard to compute. Theorem 1. Given a profile P, it is NP-hard to decide whether there exists a ranking r with q P (r) 1.

Proof. We give a reduction from VERTEX COVER. An instance of this problem is given by a graph G = (V, E) and an integer ℓ. It is a yes -instance if there is a subset of ℓ vertices S V such that each edge in E contains some vertex in S. We can assume that G is 3-regular, as VERTEX COVER remains NP-hard in this case [Garey and Johnson, 1979]. Given a vertex cover instance (G, ℓ) with G = (V, E), we construct an instance of the problem of finding an optimal ranking as follows. Since the degree of each vertex is exactly 3, we can assume that 3ℓ |E|: instances with 3ℓ< |E| are trivially no -instances. We set A = V {d}, where d is a dummy alternative. For every edge {a, b} E we create a voter that approves {a, b}. We also add 3ℓ+ 3 |E| 3 dummy voters who approve d only. Consequently, n = |N| = 3ℓ+ 3. Since the graph is 3-regular, we have m = |A| = 2|E|/3 + 1 3ℓ. This defines the profile P. It can be shown that G has a vertex cover of size ℓif and only if there exists a ranking r with q P (r) 1, i.e., avg(N , r k) jd(N , k) for all N N and k [m]. For details, see the full version of the paper [Skowron et al., 2016].

Further, a fairly straightforward reduction from the Maximum k-Subset Intersection problem [Xavier, 2012] shows that even the problem of deciding whether there exists an (α, λ)-significant group of voters is NP-hard. Proposition 1. The problem of deciding whether there exists an (α, λ)-significant group of voters is NP-complete. The measure q P (r) can be lifted from individual rankings to ranking rules: we can measure the quality of a ranking rule f as the minimum value of q P (f(P)), over all possible profiles P. However, in our theoretical analysis of ranking rules we take the following approach, which assumes more flexibility on the part of groups of voters that seek to be represented: given a group of proportion α and with cohesiveness at least λ, we ask at which point in the ranking the average satisfaction of this group reaches λ. This guarantee is given by the function κ(α, λ), which is formally defined as follows. Definition 4. (κ-group representation) Let κ(α, λ) be a function from ((0, 1] Q) N to N. A ranking r provides κ-group representation (κ-GR) for profile P if for all rational α (0, 1], all λ N, and all voter groups N N that are (α, λ)-significant in P it holds that

avg(N , r κ(α,λ)) λ.

A ranking rule f satisfies κ-group representation (κ-GR) if f(P) provides κ-group representation for every profile P. Example 3. Consider again the profile from Example 1 and the ranking r = (a, b, c). For the κ-group representation of this ranking we have κ(1/2, 1) 3. To establish this, we consider groups consisting of half of the voters who jointly approve at least one alternative, and look for the smallest value of k such that each such group on average approves at least one from the the top k alternatives in r. Let us now explore the differences between the two measures, the worst-case quality of the ranking q P (f(P)), and κgroup representation. While q P (f(P)) is just a single number, κ-group representation carries more information. In particular, it makes it possible to express the fact that some groups are better represented in the top parts of the resulting ranking than further below (this can be captured by making κ a convex function of λ). As a more concrete example, assume that q P (f(P)) < 1/2 and consider a group N that is (1/10, m/2)-significant. Since the justified demand of this group is upper-bounded by m/10, q P (f(P)) does not say anything about how far we need to go down the ranking to obtain an average representation greater than λ > m/20 (the justifiable demand of N is at most m/10 and f guarantees only half of it), while κ-group representation provides such information for each λ [1, m/2]. In the next section, we investigate guarantees in terms of κgroup representation provided by the ranking rules introduced in Section 2.

4 Theoretical Guarantees for Ranking Rules We start our analysis with the simplest of our rules, namely, Approval Voting (AV). Interestingly, AV provides very good guarantees to majorities, that is, groups with α(N ) > 1/2. For example, for α(N ) = 0.8 it guarantees an average satisfaction of λ within the top 1.5λ positions. However, for groups with α(N ) 1/2 it provides no guarantee at all. Theorem 2. For rational α > 1/2, AV satisfies κ(α, λ)- group representation for κ(α, λ) = λα 2α 1 , but fails it for κ(α, λ) = λα 2α 1 1. However, for α < 1/2, AV does not satisfy κ(α, λ)-group representation for any function κ(α, λ).

Proof. We first prove that for α > 1/2, AV satisfies κ(α, λ)- group representation for κ(α, λ) = λα 2α 1 . Consider a group of voters N N with n = |N | = αn , λ(N ) λ. Let k = λα 2α 1 , and let r be the ranking returned by AV. Assume for the sake of contradiction that avg(N , r k) < λ. Then there exists some alternative h that is approved by all voters in N , but does not appear in the top k positions of r. Thus, each alternative in r k is approved by at least αn voters and hence by at least 2 αn n voters in N . Hence,

avg(N , r k) k 2 αn n

This contradiction proves our first claim. Now, we show that AV does not satisfy κ(α, λ)-group representation for κ(α, λ) = λα 2α 1 1. Fix α (0, 1] Q and λ N and let k = λα 2α 1 1 < λα 2α 1. As α Q, there

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

exist integers x and n such that α = x/n. Let A = A A , where |A | = |A | = k and A A = . Consider a profile on (A, N) that contains two groups of voters G and F with sizes |G| = |F| = x = αn, such that G and F have the smallest possible intersection. That is, for α 1/2 the sets G and F are disjoint, and for α > 1/2 we have |G F| = (2α 1)n. Suppose that each voter in G approves all alternatives in A and each voter in F approves all alternatives in A . AV may rank A in the first k positions. Thus,

avg(F, r k) = k (2α 1)n

Finally, let us prove that for α 1/2, AV does not satisfy κ(α, λ)-group representation for any function κ(α, λ). For the sake of contradiction let us assume that this is not the case. Let us fix α (0, 1], λ N, and let k = κ(α, λ). Using the same idea as in the previous paragraph, we obtain an instance where there is a set of voters N with |N | = αn, λ(N ) = |N | λ such that no voter in N approves any of the alternatives appearing in the top k positions of the ranking returned by AV. This gives a contradiction.

In contrast, Phragm en s rule, Seq PAV and p-geometric rules give reasonable guarantees for all values of α and λ. Theorem 3. Seq PAV satisfies κ(α, λ)-group representation for κ(α, λ) = 2(λ+1)2

Proof. Fix α (0, 1], λ N, a profile P, and a group of voters N N such that n = |N | = αn and λ(N ) λ. Set k = 2(λ+1)2

α2 . Let r be the ranking returned by Seq PAV. Assume for the sake of contradiction that avg(N , r k) < λ and set z = n avg(N , r k); note that z < λn . By our assumption, at the end of each step t [k] there exists some alternative that is approved by all voters in N , but has not been ranked yet; let h be some such alternative. For t [k + 1], consider the moment just before the t-th step of Seq PAV. Let ai(t) denote the number of alternatives selected so far that appear in Ai, and let T(t) = P i N 1 ai(t)+1. Note that n = T(1) T(2) . . . T(k + 1) 0. For each t [k + 1] we have P i N ai(t) z. Using the arithmetic mean harmonic mean inequality, we infer

n P i N (ai(t) + 1)

i N 1 ai(t)+1 ,

1 ai(t) + 1 (n )2

z + n > (n )2

n (λ + 1) = n

Consider the alternative a selected by Seq PAV at step t, t [k]. Without loss of generality, assume that Na = {1, . . . , s}. Since alternative h is available at this step, it has to be the case that Seq PAV favors a over h, i.e., for the harmonic weight vector w = (1, 1/2, 1/3, . . . ) we have w(r t 1 {a}) w(r t 1) w(r t 1 {h}) w(r t 1). This implies

1 ai(t) + 1 X

1 ai(t) + 1 > n

Thus, we have

T(t) T(t + 1) =

1 ai(t) + 1 1 ai(t) + 2

1 (ai(t) + 1)(ai(t) + 2)

1 2(ai(t) + 1)2 .

Applying the Cauchy Schwarz inequality to (1, . . . , 1) and ( 1 a1(t)+1, . . . , 1 as(t)+1), we obtain

1 2(ai(t) + 1)2 1

1 ai(t) + 1

2(λ + 1)2 .

Since the above inequality holds for each t [k], we have

T(1) T(k + 1) =

T(t) T(t + 1) > knα2

2(λ + 1)2 .

Since knα2 2(λ+1)2 n, we have T(k+1) < T(1) n = n n = 0, a contradiction. This completes the proof.

The technique developed in the proof of Theorem 3 can be used to provide similar bounds for other sequential Thiele rules. For the p-geometric rule we obtain the following bound.

Theorem 4. For each p > 1, the p-geometric rule satisfies κ(α, λ)-group representation for κ(α, λ) = pλ+1

A much more involved analysis using a potential function argument gives us a bound for Phragm en s rule.

Theorem 5. Phragm en s rule satisfies κ(α, λ)-group representation for κ(α, λ) = 5λ

Theorem 4 establishes a linear relationship between the proportion of the group α and the guarantee κ(α, λ). Thus, our bound for the p-geometric rule is better than our bounds for Seq PAV and Phragm en s rule from Theorems 3 and 5, respectively. Further, as suggested by Example 1, a linear relationship is the best we can hope for. Unfortunately, as a tradeoff we obtain an exponential relationship between the required amount of representation λ and the guarantee κ(α, λ). Nevertheless, Theorem 4 shows that if we are only interested in optimizing κ(α, λ) for a constant value of λ > 1 (e.g., if we know that no agent desires more than λ objects in total), then the p-geometric rule provides very good guarantees for groups of different sizes. Furthermore, it can be shown that by taking p = λ/(λ + 1) we get the best possible guarantee in this setting (i.e., for a fixed λ). For Reverse Seq PAV, we have not been able to establish an analogous lower bound. However, we can obtain a bound on κ(α, λ) for each α (0, 1] and for some sufficiently large λ.

Theorem 6. Let α (0, 1], λ N, and let N N be an (α, λ)-significant group. Let r be the ranking returned by Reverse Seq PAV. Then, there exists y λ such that avg(N , r y/α) y.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

5/4-Geometric Rule

2-Geometric Rule

10-Geometric Rule

Reverse Seq PAV

Figure 1: Violations of justified demand encountered in our data sets. The x-axis shows the proportion of the respective group of voters, α(N ), and the y-axis shows the quotient of average representation and justified demand, yr(N , k). Roughly, ranking rules with more gray points perform worse according to our metrics; lower points correspond to more severe violations of proportionality. Points to the left correspond to small groups, points to the right correspond to large groups with unmet justified demand.

5 Experimental Evaluation of Ranking Rules

The results of the previous section provide worst-case guarantees for several interesting ranking rules. We now complement these results with upper bounds, i.e., observed violations of the justified demand of voter groups. To this end, we consider a large number of synthetic preferences (various variants of the Impartial Culture model, Mallows model, and Urn model) and real-world preference data sets taken from Pref Lib [Mattei and Walsh, 2013], and analyze the representation offered by ranking rules. In total, our experiments are based on 315,500 instances. Due to space constraints we only give a very brief description of the experiments and a short discussion of what we learned. A more complete description of the experimental setting and an analysis of the results are provided in the full version of the paper [Skowron et al., 2016].

5.1 Measures of Quality of Group Representation

In our experiments we record every violation of justified demand: If, for a ranking r and a k [m], there exists a group N with avg(N , r k) < jd(N , k), we set yr(N , k) = avg(N ,r k)

jd(N ,k) and plot a point at (α(N ), yr(N , k)) indicating this violation. Figure 1 shows these plots for different ranking rules, including the best-of rule, which selects a ranking r that has the highest quality q P (r) among the rankings generated by our rules (note that this need not be the optimal ranking according to Definition 3). Violations displayed in the lower part of the plots have a small ratio yr and thus are more

severe. Note that several points may originate from the same ranking, and different rankings may produce the same point. Hence, these plots do not display how often violations occur but rather in which regions (small/large groups, minor/major violations) violations have been recorded.

5.2 Results of the Simulations Our experiments indicate that (i) among the rules we consider, the 2-geometric rule, Seq PAV, Reverse Seq PAV, and Phragm en s rule are best suited to generate proportional rankings, and (ii) there is no single best choice among these four rules (the best-of rule outperforms all of them). In particular it is noteworthy that these four rules achieve a quality of at least 1/2 on our test instances, which is only surpassed by the best-of rule (which achieves at least 2/3). Unfortunately, the best-of rule is certainly not practical, as it is very expensive to compute q P (r). Further experiments and theoretical results are required to determine which (polynomial-time computable) rule is the best choice (for a given data set). Additional insight can be gained from the plots of geometric rules: The 5/4geometric rule resembles the plot for AV, and the 10-geometric rule shows mainly violations in the top part similarly to Greedy CC. This is a consequence of the fact that the 1-geometric rule is exactly AV and that the p-geometric rule approaches Greedy CC as p . Whether p = 2 is the sweet spot between these two extremes remains to be determined.

6 Conclusions

In this paper, we have formalized a fundamental concept that is relevant to many real-life applications: proportional rankings can provide diversified search results, can accommodate different types of users in recommendation systems, can support decision-making processes under liquid democracy, and can even produce committees with an internal hierarchical structure. Our formalization of this problem allows us to leverage voting rules introduced as far back as the 19th century and apply them to these modern application scenarios. After evaluating the proportionality of several appealing ranking rules both theoretically and experimentally, we identified four such rules that appear to perform very well in this regard: the 2-geometric rule, Sequential Proportional Approval Voting and its reverse variant, and Phragm en s rule. However, none of these rules clearly outperforms the other three, and there remains a need for an in-depth analysis to determine which rules are most appropriate for various applications. While all four of these rules are polynomial-time computable, we have shown that the optimal rule (i.e., the rule that outputs rankings maximizing the quality measure q P ) is NP-hard to compute. It would be desirable to develop ways to compute the outputs of this rule in reasonable time for practical instances, and to identify other ranking rules that may provide an even better approximation to the optimal rule than the rules we have considered in this work.

Acknowledgements This work was supported by the European Research Council (ERC) under grant number 639945 (ACCORD) and by the Alexander von Humboldt Foundation.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

References [Aziz et al., 2017] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2):461 485, 2017. [Balinski and Young, 1982] M. Balinski and H. P. Young. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press, 1982. (2nd Edition [with identical pagination], Brookings Institution Press, 2001). [Behrens et al., 2014] J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek. The Principles of Liquid Feedback. 2014. [Brill et al., 2017a] M. Brill, R. Freeman, S. Janson, and M. Lackner. Phragm en s voting methods and justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 406 413, 2017. [Brill et al., 2017b] M. Brill, J.-F. Laslier, and P. Skowron. Multiwinner approval rules as apportionment methods. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 414 420, 2017. [Faliszewski et al., 2017] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. In U. Endriss, editor, Trends in Computational Social Choice, chapter 2. 2017. To appear. [Gallagher, 1991] M. Gallagher. Proportionality, disproportionality and electoral systems. Electoral Studies, 10(1):33 51, 1991. [Garey and Johnson, 1979] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman and Company, 1979. [Hu et al., 2011] B. Hu, Y. Zhang, W. Chen, G. Wang, and Q. Yang. Characterizing search intent diversity into click models. In Proceedings of the 20th International Conference on World Wide Web, pages 17 26, 2011. [Janson, 2016] S. Janson. Phragm en s and Thiele s election methods. Technical Report ar Xiv:1611.08826 [math.HO], ar Xiv.org, 2016. [Kingrani et al., 2015] S. K. Kingrani, M. Levene, and D. Zhang. Diversity analysis of web search results. In Proceedings of the ACM Web Science Conference, pages 43:1 43:2, 2015. [Laslier, 2012] J.-F. Laslier. Why not proportional? Mathematical Social Sciences, 63(2):90 93, 2012. [Mattei and Walsh, 2013] N. Mattei and T. Walsh. Preflib: A library for preferences. In Proceedings of the 3nd International Conference on Algorithmic Decision Theory, pages 259 270, 2013. [Monroe, 1995] B. L. Monroe. Fully proportional representation. The American Political Science Review, 89(4):925 940, 1995. [Mora and Oliver, 2015] X. Mora and M. Oliver. Eleccions mitjanc ant el vot d aprovaci o. El m etode de Phragm en i algunes variants. Butllet ı de la Societat Catalana de Matem atiques, 30(1):57 101, 2015.

[Phragm en, 1895] E. Phragm en. Proportionella val. En valteknisk studie. Svenska sp orsm al 25. Lars H okersbergs f orlag, Stockholm, 1895. [Pukelsheim, 2014] F. Pukelsheim. Proportional Representation: Apportionment Methods and Their Applications. Springer, 2014. [S anchez-Fern andez et al., 2017] L. S anchez-Fern andez, E. Elkind, M. Lackner, N. Fern andez, J. A. Fisteus, P. Basanta Val, and P. Skowron. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 670 676, 2017. [Santos et al., 2015] R. L. T. Santos, C. Mac Donald, and I. Ounis. Search result diversification. Foundations and Trends in Information Retrieval, 9(1):1 90, 2015. [Schulze, 2011] M. Schulze. Free riding and vote management under proportional representation by the single transferable vote. Available at http://m-schulze. 9mail.de/schulze2.pdf, 2011. [Skowron et al., 2016] P. Skowron, M. Lackner, M. Brill, D. Peters, and E. Elkind. Proportional rankings. Technical Report ar Xiv:1612.01434 [cs.GT], ar Xiv.org, 2016. [Thiele, 1895] T. N. Thiele. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pages 415 441, 1895. [Wang et al., 2016] Y. Wang, Z. Luo, and Y. Yu. Learning for search results diversification in Twitter. In Proceedings of the 17th International Conference on Web-Age Information Management, pages 251 264, 2016. [Welch et al., 2011] M. J. Welch, J. Cho, and C. Olston. Search result diversity for informational queries. In Proceedings of the 20th International Conference on World Wide Web, pages 237 246, 2011. [Xavier, 2012] E. C. Xavier. A note on a maximum k-subset intersection problem. Information Processing Letters, 112(12):471 472, 2012.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)