# ranking_wily_people_who_rank_each_other__ba64e4ea.pdf

Ranking Wily People Who Rank Each Other

Anson Kahng Computer Science Department Carnegie Mellon University

Yasmine Kotturi Human-Computer Interaction Institute Carnegie Mellon University

Chinmay Kulkarni Human-Computer Interaction Institute Carnegie Mellon University

David Kurokawa Computer Science Department Carnegie Mellon University

Ariel D. Procaccia Computer Science Department Carnegie Mellon University

We study rank aggregation algorithms that take as input the opinions of players over their peers, represented as rankings, and output a social ordering of the players (which reflects, e.g., relative contribution to a project or fit for a job). To prevent strategic behavior, these algorithms must be impartial, i.e., players should not be able to influence their own position in the output ranking. We design several randomized algorithms that are impartial and closely emulate given (nonimpartial) rank aggregation rules in a rigorous sense. Experimental results further support the efficacy and practicability of our algorithms.

1 Introduction Our work is primarily motivated by two applications. The first is ordering authors on a scientific paper based on contribution. In medical research, for example, author lists tend to be long, and the difference between being listed second or third on an important paper can make or break a career. We would like to employ an algorithm that receives from each author a ranking, which reflects his own opinion regarding the relative contribution of different authors, and outputs an aggregate ranking. The second application is online labor markets, such as Upwork or Freelancer. In the bigger markets, employers typically receive dozens of applications for a job, but there is an embarrassment of riches, because employers do not have the knowledge required to accurately evaluate applicants. For the past year we have been building a prototype of a new online labor market, where applicants for a job who are well-suited to evaluate applications for that same job rank each other.1 We would like to implement a mechanism that aggregates these rankings into a single ranking that is then shown to the employer. As the reader has no doubt realized by now, the foregoing applications share a common problem, which gets in the way of applying standard rank aggregation rules: strategic behavior. Specifically, in these relatively high-stakes scenarios, it is likely that a player would try to improve his own

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1To be more accurate, they submit pairwise comparisons of other applicants, but, as we discuss in Section 7, that is essentially the same setting.

position in the output ranking by manipulating his reported ranking. For example, he might weaken a strong contender for the top position by ranking him last. Our goal, therefore, is to design rank aggregation rules that are impartial, in the sense that the position of a player in the output ranking is completely independent of the report of that player.

1.1 Our Approach and Results

On a high level, our approach is to design randomized rank aggregation rules that are impartial and closely emulate standard rank aggregation rules that are not impartial. Specifically, we focus on providing impartial approximations to the important class of pairwise rules, which, as input, only require information about the fraction of players ranking any one player above another. Our theoretical results crucially depend on the notion of approximation or measure of error in question. In Section 4, we introduce the k-PARTITE algorithm, which, in a nutshell, randomly partitions the players into subsets, builds a probability distribution over the positions of members of one subset based on the aggregate opinion of members of other subsets, and then generates a distribution over rankings that is consistent with these distributions over positions. We prove that k-PARTITE is impartial, and, when used in conjunction with any pairwise rule, it provides small backward error with respect to that rule: With high probability, k-PARTITE places each player in the same position that the given pairwise rule would have placed him had the input rankings been slightly perturbed. In Section 5, we present the COMMITTEE algorithm. It randomly chooses a subset of players, who serve as the eponymous committee. Each committee member is positioned based on the opinions of other committee members, and then all other players are ordered by the committee. The key idea is that, to avoid conflicts and achieve impartiality, each committee member has slots that are reserved for him, and he is inserted into the reserved slot that most closely matches the aggregate opinion of other committee members. We prove that COMMITTEE provides mixed error guarantees with respect to any given pairwise rule, that is, with high probability, COMMITTEE places each player in a position that is close to where the given pairwise rule would have placed him had the input rankings been slightly perturbed. Taking on some forward error a mismatch between the

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

positions allows for improved backward error compared to k-PARTITE. In Section 6, we empirically measure the performance of our impartial algorithms with respect to the popular Kemeny rule, which is defined via a natural optimization objective. The experimental results demonstrate that our impartial algorithms, when coupled with the Kemeny rule, output nearoptimal rankings with respect to the Kemeny objective, despite the impartiality constraint.

1.2 Related Work

At this point there is a significant body of work on the design of impartial mechanisms (de Clippel, Moulin, and Tideman 2008; Alon et al. 2011; Holzman and Moulin 2013; Bousquet, Norin, and Vetta 2014; Tamura and Ohseto 2014; Berga and Gjorgjiev 2014; Fischer and Klimm 2014; Mackenzie 2015), including several papers in major AI conferences (Kurokawa et al. 2015; Aziz et al. 2016). We only elaborate on the papers that are most closely related to ours. The paper of de Clippel et al. (2008) introduced the notion of impartiality, in the context of dividing credit for a joint project. Specifically, the output of their mechanism is the fraction of the total credit each player receives, and impartiality means that a player cannot affect his own share of the credit. This mechanism is deployed on the fair division website Spliddit.org, where one of the suggested applications is ordering authors on scientific papers. However, an impartial credit division mechanism does not induce an impartial ranking mechanism, because, when players are sorted by credit, a player can improve his own position by decreasing another player s share. Berga and Gjorgjiev (2014) study the impartial rank aggregation problem from an axiomatic viewpoint, but focus on deterministic rules and a stronger notion of impartiality (which we discuss in Section 7). Their results suggest that deterministic impartial rank aggregation methods are severely limited, and support our focus on randomized algorithms.2

On a technical level, our k-PARTITE algorithm is reminiscent of an algorithm of Alon et al. (2011), in that it randomly partitions the players into subsets, and the outcome of players in one subset is only determined by players in other subsets. But the details of the algorithm, and its analysis, are completely different.

2 Preliminaries

In this section we introduce terminology and notations that are standard in computational social choice (Brandt et al. 2016), as well as the formal instantiation of the concept of impartiality in our setting.

2In addition, it is easy to prove that there are no deterministic rank aggregation rules that are both impartial (according to our definition) and Pareto efficient (Moulin 2014). The latter property means that if everyone ranks one player above another, so does the output ranking.

2.1 Rankings and Aggregation For any k N, let [k] = {1, . . . , k}. Our setting involves a set of players [n] = {1, . . . , n}. The opinions of players are represented as rankings over [n], which we think of as permutations. Let Π represent the set of all permutations of [n], and let Πn represent the set of all input profiles. For any σ Π, let σ(j) be the player at position j in σ and let σ 1(i) be the position of player i in the ranking σ (where position 1 is the highest and position n is the lowest). A deterministic rank aggregation rule (also known as a social welfare function) is a function f : Πn Π, which takes in an input profile and returns a ranking. A randomized rank aggregation rule returns a probability distribution over rankings. We sometimes find it convenient to slightly abuse notation and think of the domain of a rank aggregation rule as Πn 2[n] for σ = (σ1, . . . , σn) and X [n], f( σ, X) is the application of the rule to the input profile (σi)i X.

2.2 Pairwise Rank Aggregation Rules An input profile σ = (σ1, . . . , σn) induces a pairwise comparison matrix A( σ), where

A( σ)ij = |{k [n] : σ 1 k (i) < σ 1 k (j)}| n .

In words, the (i, j) entry is the fraction of players who rank i above j. Let Ω be the set of pairwise comparison matrices. Therefore, we can think of A : Πn Ω as a function that takes in an input profile and returns its associated pairwise comparison matrix. As before, we will also use the notation A( σ, X), for a subset of players X [n], to denote the pairwise comparison matrix associated with the rankings of the players in X. Some rank aggregation rules only require the information encoded in the pairwise comparison matrix to compute their output. Formally, a deterministic pairwise rank aggregation rule is a function f : Ω Π. We denote the class of all deterministic pairwise rules by P.3 We pay special attention to two popular pairwise rules: The Borda Rule: Given σ Πn, the score of each player i is n j=1(n σ 1 j (i)) (that is, each player awards n k points to the player in position k), and the players are ranked by non-increasing score. It may not be immediately apparent that Borda is a pairwise rule proving this well-known fact is left to the curious reader as an easy exercise. The Kemeny Rule: The Kendall tau distance d KT between two rankings σ, τ Π is the number of pairs of players on which the two rankings disagree. Given σ Πn, the Kemeny rule returns a ranking in argminτ Π n i=1 d KT (τ, σi). Computing the output of the Kemeny rule is hard, but can be done in practice using integer programming or heuristic algorithms (Conitzer, Davenport, and Kalagnanam 2006). Other well-known rules, such as Copeland and Maximin, are also pairwise.

3We do not consider randomized pairwise rules in this paper. Strictly speaking, we do not require this determinism, but we assume it as it makes the proofs more transparent.

2.3 Impartiality Recall that we are interested in designing rank aggregation rules that are impartial, that is, no player i can affect his probability of being ranked in position j, for all i, j [n]. Formally: Definition 2.1. A (possibly randomized) rank aggregation rule f is impartial if for all i [n], all input profiles (σ1, . . . , σn) Πn, and all σi Π, it holds that x = y, where xj is the probability i is ranked in position j in f (σ1, . . . , σi 1, σi, σi+1, . . . , σn), and yj is the probability i is ranked in position j in f (σ1, . . . , σi 1, σi, σi+1, . . . , σn). In an alternative model, we may assume that each player i has a value vij for being ranked in position j, and then impartiality would mean no player can affect his expected value for the outcome, regardless of his value function. Although this definition may seem weaker than Definition 2.1 at first glance, it is easy to verify that the two definitions are, in fact, equivalent.

3 Measures of Error Given that our goal is to approximate rank aggregation rules, the measure of error is critical to the statement of the formal problem. To define appropriate notions, we adapt concepts that are standard in scientific computing (e.g., in numerical stability analysis): forward error, backward error, and mixed error. We view these imported definitions as part of our conceptual contribution. Definition 3.1. Let f be a rank aggregation rule. A rank aggregation rule g is said to have (ΔP , ΔF ) forward error with respect to f if for every input profile σ Πn, the probability that for all i [n] it holds that f( σ) 1(i) g( σ) 1(i)

is at least 1 ΔP . Intuitively, a low amount of forward error implies that every player i is placed near his correct rank (as determined by f) with high probability. Unfortunately, as the next theorem states, impartial rank aggregation rules cannot approximate the Borda rule. Since Borda is a pairwise rule, the theorem rules out the possibility of approximating all pairwise rules. Theorem 3.2. For all n 2 and ε > 0, there exists no impartial rank aggregation rule g that gives a (1/2 ε, 1/3) forward error with respect to the Borda rule f.

Proof. For n = 2, a direct analysis (which we omit) gives the result. Let us therefore consider only the case n 3. Let g be an impartial rank aggregation rule. Suppose we have the input profile σ where i = 2 gives the ranking (i 1, . . . , n, 1, . . . , i 2). Note that if player 2 continued this trend and gave the ranking 1, . . . , n then all players would have the same Borda score. Now let us consider player 2 in more depth, and define the probability vector x [0, 1]n, where xi denotes the probability player 2 will be in position i when g determines the ranking. By impartiality we know that x does not depend on

the ranking of player 2. As x is a probability vector, we must have one of the following. Case 1: The first n/2 entries of x sum to at most 1/2. In this case, if player 2 has the ranking (2, 1, 3, 4, 5, . . . , n) in σ, then f( σ) 1(2) = 1. Case 2: The last n/2 entries of x sum to at most 1/2. In this case, if player 2 has the ranking (1, 3, 2, 4, 5, . . . , n) in σ, then f( σ) 1(2) = n. In either case, we find that with probability at least 1/2, g will place 2 in a position at distance at least n/2 from f s placement. That is, with probability at least 1/2 we have f( σ) 1(2) g( σ) 1(2) n/2 n/3, giving at best a forward error of (1/2, 1/3).

With this impossibility in hand, we set our sights on an alternate error measure, which is well defined only with respect to pairwise rank aggregation rules. For this definition and throughout the paper, we use the Frobenius norm and denote A = maxi,j |Ai,j|.

Definition 3.3. Let f P. A rank aggregation rule g is said to have (ΔP , ΔB) backward error with respect to f if for every input profile σ Πn the probability that for all i [n] there exists a matrix A Ω such that

1. A( σ) A < ΔB, and

2. f( A) 1(i) = g( σ) 1(i),

is at least 1 ΔP .

Intuitively, a low amount of backward error implies that every player i is placed in a rank that had the players altered their opinions slightly, i would be in the correct rank (according to f) with high probability. See Section 7 for further discussion of this concept. Finally, we define a third measure of error, which, in a sense, is a union of the two previous notions.

Definition 3.4. Let f P. A rank aggregation rule g is said to have (ΔP , ΔB, ΔF ) mixed error with respect to f if for every input profile σ Πn, the probability that for all i [n] there exists a matrix A Ω such that

1. A( σ) A < ΔB, and

2. |f( A) 1(i) g( σ) 1(i)|

is at least 1 ΔP .

4 The k-PARTITE Algorithm We now introduce and analyze our first impartial rule, k PARTITE, which is formally given as Algorithm 1. As it appears somewhat opaque, it is best to understand its ideas when we assume that all the Xi are the same size, i.e., k divides n, |Xi| = n/k, and γi = k for all i [k]. Slight adjustments are made when this is not the case, which for purposes of intuition can be safely ignored. First, players are randomly split into k groups of equal size X1, . . . , Xk, and then each such group separately ranks all n players producing rankings τi. The crux of the algorithm is the construction of the matrix Z, which, in turn, is

the sum of Z(i) matrices. Intuitively, the Z(i) matrix represents Xi s contribution to Z, and its (a, b) entry indicates the probability that a should be placed in position b overall. Specifically, each player not in Xi is placed in his exact position dictated by τi with probability 1/k, and in all positions that the players in Xi themselves were assigned to in τi with probability 1/(n(k 1)). This information is encoded as the only non-zero entries in Z(i) each column then sums to 1/k, each row representing a player in Xi is zero, and all other rows sum to 1/(k 1). As we show in Appendix A, Z is doubly stochastic (its rows and columns sum to 1); hence we can apply the Birkhoff-von Neumann Theorem (Birkhoff 1946; von Neumann 1953) to sample from this distribution and remain faithful to the probabilities.

input: f P and σ Πn

1: Randomly split all n players into k groups X1, . . . , Xk where |Xi| { n/k , n/k } 2: for i = 1, . . . , k do 3: τi f( σ, Xi) 4: γi n/ |Xi| 5: Let Z(i) Rn n where

1 γi if a Xi and τi(b) = a 1 γi(γi 1)|Xi| if a Xi and τi(b) Xi 0 otherwise

6: end for 7: Z

8: Sample a ranking σ such that a is ranked in position b with probability Za,b 9: return σ

Algorithm 1: k-PARTITE

Our goal is to prove the following theorem, which states the guarantees of k-PARTITE. Theorem 4.1. k-PARTITE is impartial, and, for every f P and σ Πn, if k = (n/ ln n)1/3 , it gives at most

backward error with respect to f. Note that, in particular, the error goes to 0 as n grows. Turning to the proof, it is clear that the algorithm is impartial because of the inability of any player i to affect the ith row of the Z matrix. We therefore focus on establishing the error bound. To this end, we first prove several lemmas. Lemma 4.2. If t players X = {x1, . . . , xt} are sampled without replacement from [n] with input profile σ Πn, then

P [ A( σ) A( σ, X) ε] < n2 exp tε2

P [ A( σ) A( σ, X) ε]

i<j P [|A( σ)i,j A( σ, X)i,j| ε]

i<j 2 exp tε2

< n2 exp tε2

where the first transition follows from the union bound, and the second transition follows from Hoeffding s Inequality.

Lemma 4.3. For every f P, σ Πn, and ε > 0, k PARTITE gives at most 1 k 2

1 n2k exp n/k ε2

backward error to f.

Proof. Observe that

P [ i [k] s.t. A( σ) A( σ, Xi) ε]

i=1 P [ A( σ) A( σ, Xi) ε]

i=1 n2 exp |Xi| ε2

i=1 n2 exp n/k ε2

= n2k exp n/k ε2

where the second inequality follows from Lemma 4.2. Further observe that, by Lines 5 and 7 of k-PARTITE, for any player a he is placed directly where one of the Xi places him with probability

i [k]: a Xi

i [k]: a Xi

k 1 1 n |Xi|

= 1 1 n(k 1)

i [k]: a Xi |Xi|

= 1 1 n(k 1)n

Now, if for all i [n], A( σ) A( σ, Xi) < ε, and each player a is placed in the position that some Xia places him, then we can set A = A( σ, Xia) for all a [n] to satisfy the conditions of backward error. Moreover, these events are independent. We conclude that k-PARTITE gives at most 1 k 2

1 n2k exp n/k ε2

backward error, as stated.

Proof of Theorem 4.1. From Lemma 4.3 it suffices to show that if we have ε = 4/k,

1 n2k exp n/k ε2

Observe that

n2k exp n/k ε2

n2k exp (n/k 1)ε2

= n2k exp (n/k 1)(4/k)2

= n2k exp 8

n2 n1/3 exp 8

Thus we see that

1 n2k exp n/k ε2

= 1 k 1 + k 2

n2k exp n/k ε2

1 k 1 + n 2

2/k + 2/k = 4/k.

A natural question is why we insist on what appears to be a somewhat convoluted algorithm, instead of a more natural approach such as the impartial NAIVE-BIPARTITE, formally given as Algorithm 2. The reason is that this algorithm does not even guarantee tolerable mixed error in general. Indeed, consider f P that is defined as follows. Let X {2, . . . , n} be the set of players such that at least one player ranks i above 1; return the ranking starting with the players of X ordered lexicographically, followed by the players of [n] \ ({1} X) ordered lexicographically, and player 1 inserted into position n/3 overall (shifting appropriately). Now consider the input profile where i reports the ranking (i, 1, 2, . . . , i 1, i + 1, . . . , n). Then NAIVEBIPARTITE will always return a ranking where player 1 is placed first or second as he will always top his set. This means that the algorithm cannot even provide a mixed error of (1/2, 1, 1/4).

5 The COMMITTEE Algorithm k-PARTITE demonstrates that there exist impartial rules that accurately imitate any f P. Observe, however, that the

input: f P and σ Πn

1: Randomly split the n players into two sets X and Y where |X| = n

2 and |Y | = n

2: τ1 f( σ, X) restricted to the players only in Y 3: τ2 f( σ, Y ) restricted to the players only in X 4: σ interlaces τ1 and τ2, that is,

σ(i) τ1 ((i + 1)/2) if i is odd τ2 (i/2) if i is even

5: return σ

Algorithm 2: NAIVE-BIPARTITE

algorithm is somewhat hamstrung by the fact that a player must be (with high probability) ranked in exactly the location that a small perturbation of the input rankings would give. To allow more flexibility, we focus on mixed error, and consider COMMITTEE, given as Algorithm 3. Intuitively, this algorithm selects a random committee X = {x1, . . . , xk}, which then determines the entire ranking. First, for each committee member xi, we determine their rank using only the rankings given by the remaining k 1 members. However, as directly placing each committee member in this fashion may cause collisions (i.e., multiple members may be assigned the same rank) we restrict placement of xi to only the positions i, i + k, i + 2k, . . . Specifically, we assign xi to the closest such position to the rank given to xi by the other committee members. There are then k of the n positions assigned. Second, the committee ranks all of the n players, and the non-committee members are placed in the order ranked by the committee in the remaining n k slots.

input: f P and σ Πn

1: Randomly select a subset X = {x1, . . . , xk} [n] 2: for i = 1, . . . , k do 3: c arg minj {i,i+k,...} j f ( σ, X \ {xi}) 1 (xi) 4: σ(c) xi 5: end for 6: τ f( σ, X) 7: j 1 8: for i = 1, . . . , n do 9: if τ(i) X then 10: while σ(j) is occupied do 11: j j + 1 12: end while 13: σ(j) τ(i) 14: end if 15: end for 16: return σ

Algorithm 3: COMMITTEE

The algorithm yields the following guarantees Theorem 5.1. COMMITTEE is impartial, and, for every f P, σ Πn, and ε > 0, if k = 1 + 2 ε2 ln n3

ε , it gives at

most (ε, ε, (k + 1) /n) mixed error with respect to f.

Importantly, this theorem allows for an incomparable error to Theorem 4.1. That is, we can reduce the backward error so long as we are willing to take on some forward error. For example, setting ε appropriately gives at most n 2/5, n 2/5, 2/n + (34/5)n 1/5 ln n mixed error. As in the case of k-PARTITE, the impartiality of COMMITTEE is obvious, because the position of each committee member is only determined by other committee members, and the position of non-committee members is determined by committee members. The proof of Theorem 5.1 therefore focuses on establishing the stated mixed error guarantee; it is relegated to the full version of the paper.4

6 Experiments Our theoretical results indicate that impartial rules like k PARTITE and COMMITTEE are likely to yield rankings that are close, in a sense (backward error or mixed error), to the output of a given rank aggregation rule. In this section we investigate a more natural metric, which is beyond the reach of our theory, and empirically demonstrate that our rules perform well with respect to this metric, too. In our experiments, we focus on the Kemeny rule (see Section 2), as it is defined via an optimization problem, so we can use its objective function as our measure. Specifically, we interpret the Kemeny rule as maximizing the number of agreements with the input rankings, that is, given σ Πn, it chooses a ranking τ Π that maximizes

Kem(τ, σ) =

d KT (τ, σi) . (1)

We quantify the error of an impartial rule by comparing how well it does with respect to measure (1) with the performance of the optimal ranking returned by the Kemeny rule. In more detail, let f be the Kemeny rule, and let g be an impartial rule; given an input profile σ, we are interested in the Kemeny approximation ratio Kem(g( σ), σ)/Kem(f( σ), σ); this ratio is upper-bounded by 1 due to the definition of the Kemeny rule. We use the number of agreements, instead of the number of disagreements, as our measure because in cases where the number of disagreements is very small, the ratio would be misleadingly large. The input profiles are generated according to the popular Mallows (1957) model. In this model, there is a base ranking of the alternatives τ , and rankings are drawn i.i.d. from a probability distribution over Π, defined by

Pr[σ | τ ] = φd KT (σ,τ ) σ Π φd KT (σ ,τ ) ,

for a dispersion parameter φ [0, 1]. Note that φ = 1 corresponds to uniformly random rankings (and therefore input rankings disagree on pairs of alternatives with probability 1/2), whereas φ = 0 means, by convention, that all rankings coincide with the base ranking, that is, there is unanimous agreement. We empirically study the Kemeny approximation ratio of the impartial rules NAIVE-BIPARTITE, COMMITTEE, and k-PARTITE, for multiple values of φ, each of which represents a different level of agreement.

4Available from http://procaccia.info/research.

Throughout our experiments, we let k = n/4, n/8 for COMMITTEE and let k = 4, 8 for k-PARTITE. The intuition behind these choices is that the size of the initial committee and each subset in the partition should grow with n, and choosing these values of k works reasonably in practice. We ran experiments with n {8, 16, 24, 32, 40} players and φ {0, 0.1, 0.3, 0.5, 0.7, 0.9, 1}. Our results for the three impartial rules NAIVEBIPARTITE, COMMITTEE, and k-PARTITE and φ = 0.3 are shown in Figures 1(a), 1(b), and 1(c), respectively; the results for other values of φ, which can be found in the full version of the paper, are qualitatively similar. In each figure, the x axis shows the values of n, and the y axis shows the Kemeny approximation ratio obtained by the impartial rule. All three impartial rules perform well as n increases. As a baseline, a straightforward calculation shows that with φ = 0.3, a ranking drawn from the Mallows model would agree with the base ranking (which is typically the output of Kemeny when the input profile is drawn from Mallows) with probability 0.77 on any given pair of alternatives, and that probability is 0.5 if the latter ranking is replaced with a uniformly random ranking, so the (impartial) rule that chooses a ranking uniformly at random gives a Kemeny approximation ratio of 0.5/0.77 = 0.65. On a high level, the three impartial rules achieve excellent Kemeny approximations despite their very different theoretical guarantees. But k-PARTITE has by far the highest variance. This phenomenon is due to the fact that if the position of a player is chosen from a setting in which he was not placed in his exact place as prescribed by players in some partition, he is essentially placed in a random location in the final ranking. In NAIVE-BIPARTITE and COMMITTEE, this is not an issue, as players are always placed in some sense close to a position in which a subset of players believes they belong. As can be seen in the full version of the paper, this phenomenon is more pronounced for lower values of φ because placing players in a random location is penalized more heavily when the population is generally sharply clustered around a certain ranking. Furthermore, the performance of our impartial algorithms depends on the specific choice of k (except for NAIVEBIPARTITE, which does not depend on any parameter k). The following observations can be seen in the full version of the paper. COMMITTEE performs better with the smaller value of k, but this effect lessens as φ increases (i.e., it helps more when players have generally similar opinions). With small φ, because most committees will agree on a consistent ranking, the additional error from inserting players into larger buckets leads to a noticeable difference. However, as players start to disagree more, the benefit of getting better estimates from larger committees counteracts the insertion error. k-PARTITE acts similarly: the larger value of k leads to better performance for low φ, but this effect again lessens as φ increases. This is because each player is placed exactly where one of the groups places him with probability (k 2)/(k 1), which increases with k, but being placed in one of these positions is most beneficial when players generally agree. As opinions become increasingly random and diffuse, groups disagree more strongly about where to place

8 16 24 32 40 0.0

Kemeny approximation ratio

(a) NAIVE-BIPARTITE

8 16 24 32 40 0.0

Kemeny approximation ratio

k = n/8 k = n/4

(b) COMMITTEE

8 16 24 32 40 0.0

Kemeny approximation ratio

k = 8 k = 4

(c) k-PARTITE

Figure 1: Kemeny approximation ratio of three impartial mechanisms for φ = 0.3. The median of each boxplot is marked with a black line, the edges of each box denote the quartile values, and the whiskers extend to data within 1.5 times the interquartile range from the edges of each box.

a specific player.

7 Discussion We conclude with a discussion of several important points that were referenced earlier.

Pairwise comparisons. In practice, players would often be asked to compare pairs of players, rather than giving a complete ranking. Crucially, our results seamlessly extend to that setting. Indeed, standard measure concentration inequalities show that a small number of random caparisons are sufficient to accurately estimate the pairwise comparison matrix (see, e.g., Procaccia and Shah 2016). Because we focus on pairwise rank aggregation rules, this means that the input to the rule is qualitatively unaffected by the transition from complete rankings to pairwise comparisons.

Strong impartiality. A natural notion of impartiality that is stronger than ours (call it strong impartiality) requires that a player would not be able to affect the subset of players that are ranked above himself. In the context of online labor markets, for example, the rationale is that an employer is more likely to select the applicant in position k if the applicants in positions 1, . . . , k 1 are relatively weak, so it is not just the applicant s position that determines his chances of getting the job. Unfortunately, strong impartiality seems too stringent to admit reasonable rules. In fact, we can prove that no strongly impartial rule can give a (1/3, 1/7, 1/10) mixed error with respect to Borda, but this statement requires the additional assumption that strongly impartial randomized rules are distributions over strongly impartial deterministic rules.5 We believe that a similar statement holds without the additional assumption.

Flipping the quantifiers. Our definitions of backward error and mixed error include the words for all i [n] there exists a matrix A Ω. That is, for each player we can find a pairwise comparison matrix close to the original one, such that our rule puts i in a position that is identical or close to that in which the given rule would put i on the input A. The definitions would be even more compelling if the quantifiers were flipped, i.e., there exists a matrix A Ω such that for all i [n]. Under this alternative formulation, we are not allowed to tailor A to i, but rather there is one pairwise comparison matrix that achieves the desired property for every i. It remains an open problem whether our theorems (or variants thereof) still hold under these more demanding notions of error, and, if not, whether these notions are feasible at all.

Acknowledgments This work was partially supported by NSF grants IIS1350598, IIS-1714140, CCF-1525932, and CCF-1733556; by ONR grants N00014-16-1-3075 and N00014-17-1-2428; by the Manufacturing Futures Initiative at CMU; and by a Sloan Research Fellowship.

5Note that COMMITTEE and NAIVE-BIPARTITE can be represented as distributions over impartial (not strongly impartial) deterministic rules, but k-PARTITE cannot.

References Alon, N.; Fischer, F.; Procaccia, A. D.; and Tennenholtz, M. 2011. Sum of us: Strategyproof selection from the selectors. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 101 110. Aziz, H.; Lev, O.; Mattei, N.; Rosenschein, J. S.; and Walsh, T. 2016. Strategyproof peer selection: Mechanisms, analyses, and experiments. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 397 403. Berga, D., and Gjorgjiev, R. 2014. Impartial social rankings. Manuscript. Birkhoff, G. 1946. Three observations on linear algebra. Universidad Nacional de Tucum an, Revista A 5:147 151. Bousquet, N.; Norin, S.; and Vetta, A. 2014. A near-optimal mechanism for impartial selection. In Proceedings of the 10th Conference on Web and Internet Economics (WINE), 133 146. Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds. 2016. Handbook of Computational Social Choice. Cambridge University Press. Conitzer, V.; Davenport, A.; and Kalagnanam, H. 2006. Improved bounds for computing Kemeny rankings. In Proceedings of the 21st AAAI Conference on Artificial Intelligence (AAAI), 620 626. de Clippel, G.; Moulin, H.; and Tideman, N. 2008. Impartial division of a dollar. Journal of Economic Theory 139:176 191. Fischer, F., and Klimm, M. 2014. Optimal impartial selection. In Proceedings of the 15th ACM Conference on Economics and Computation (EC), 803 820. Holzman, R., and Moulin, H. 2013. Impartial nominations for a prize. Econometrica 81(1):173 196. Kurokawa, D.; Lev, O.; Morgenstern, J.; and Procaccia, A. D. 2015. Impartial peer review. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 582 588. Mackenzie, A. 2015. Symmetry and impartial lotteries. Games and Economic Behavior 94:15 28. Mallows, C. L. 1957. Non-null ranking models. Biometrika 44:114 130. Moulin, H. 2014. Personal communication. Procaccia, A. D., and Shah, N. 2016. Optimal aggregation of uncertain preferences. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 608 614. Tamura, S., and Ohseto, S. 2014. Impartial nomination correspondences. Social Choice and Welfare 43:47 54. von Neumann, J. 1953. A certain zero-sum two-person game equivalent to the optimal assignment problem. In Kuhn, W., and Tucker, A. W., eds., Contributions to the Theory of Games, volume 2. Princeton University Press. 5 12.

A Z is Doubly Stochastic In this appendix, we verify that the matrix Z constructed in k-PARTITE (Algorithm 1) is indeed doubly stochastic.

Let us first consider the row sums of the Z(i). Denote the sum of the ath row by

b=1 Z(i) ab .

If a Xi, clearly S(i) a = 0. Otherwise for a Xi, we find that

γi + |Xi| 1 γi(γi 1) |Xi| = 1 γi 1.

We therefore find that the ath row of Z sums to

i [k]: a Xi

i [k]: a Xi

i [k]: a Xi

Next we consider the column sums of the Z(i), denoted T (i)b. If τi(b) Xi we have that the column has only one non-zero entry with a value of 1/γi = |Xi|/n. Otherwise, if τi(b) Xi, we find that

T (i) b = (n |Xi|) 1 γi(γi 1) |Xi|

= (γi |Xi| |Xi|) 1 γi(γi 1) |Xi|

Therefore, all columns of Z(i) sum to |Xi|/n, and we find that the bth column of Z sums to

= 1 k 1 (k 1)