# correlated_voting__1a91520a.pdf

Correlated Voting

Debmalya Mandal dmandal@g.harvard.edu

Harvard University

David C. Parkes parkes@eecs.harvard.edu

Harvard University

We study the social choice problem where a group of n voters report their preferences over alternatives and a voting rule is used to select an alternative. We show that when the preferences of voters are positively correlated according to the Kendall-Tau distance, the probability that any scoring rule is not ex post incentive compatible (EPIC) goes to zero exponentially fast with the number of voters, improving over the previously known rate of 1/pn for independent preferences. Motivated by rank-order models from machine learning, we introduce two examples of positively-correlated models, namely Conditional Mallows and Conditional Plackett-Luce. Conditional Mallows satisﬁes Kendall-Tau correlation and ﬁts our positive result. We also prove that Conditional Plackett-Luce becomes EPIC exponentially quickly.

1 Introduction

Social choice theory studies how to aggregate preferences and select an outcome. A canonical problem is voting, where reports are preferences over a list of candidates and a voting rule selects the winning candidate.

The problem of voting is ubiquitous systems in which multiple agents interact with each other. Several tools and ideas from social choice theory have found applications in different areas of multi-agent systems including resource allocation [Parkes et al., 2015], rank aggregation [Altman and Tennenholtz, 2010], recommender systems [Pennock et al., 2000], choosing between multiple issues [Lang and Xia, 2009], and crowdsourcing [Mao et al., 2013]. Voting also has strong connections to rank aggregation models in machine learning. These models view rank data as a noisy version of a true underlying rank, and try to recover the true rank.

It is typical to ignore the possibility that data is misreported in order to change the aggregate view. Consider, for example, the problem of a conference review system where a reviewer gives a ranking over a subset of submitted papers. The committee wants to aggregate truthful reports of opinion on submitted papers while different subcommunities may want to push decisions in one direction or another.

Indeed, the problem of incentive-aligned social choice is generally hopeless. Gibbard [1973] and Satterthwaite [1975] prove that when the number of alternatives is at least three, a voting rule is unanimous and strategy-proof if and only if it is dictatorial. There are two standard ways of circumventing the Gibbard-Satterthwaite impossibility result. First, the preferences of voters may arise from a restricted preference class [Barber a, 2011]. Second, some have appealed to worst-case and average-case computational intractability of the problem of strategic manipulation, arguing that this provides robustness to strategic behavior ([Faliszewski and Procaccia, 2010] and for a recent survey, see [Conitzer and Walsh, 2016]).

However, these approaches do not consider a probabilistic model of social choice, with preferences sampled from a distribution. The relevant incentive question is to consider the situation that each voter may have information about how likely the preferences of other voters are. Our particular interest is in studying the problem of incentive-aligned preference aggregation when voters preferences are not necessarily independent. Whereas it is typical to assume that individual rank preferences of voters are independent, this is not always true. For example, in a conference review mechanism, once a reviewer realizes that paper A is signiﬁcantly better than paper B, they may be more likely to place more probability on others thinking the same about the papers.

Majumdar and Sen [2004] initiated the study of ordinally Bayesian incentive compatible (OBIC) voting rules for the setting in which voters have incomplete information about each others preferences. OBIC is a weaker form of strategyproofness, stating that truthful reporting is a Bayes-Nash equilibrium for any cardinal utility consistent with agent preferences. Later, Sen et al. [2015] prove that the Gibbard Satterthwaite impossibility result breaks down if beliefs are positively correlated. These authors start with a social choice function f satisfying certain properties and exhibit a class of positively correlated distributions for which f is OBIC.

Instead of OBIC, we adopt the notion of ex post incentive compatibility (EPIC). EPIC is a weaker solution concept than strategy-proofness, and requires truth-telling to be a best response to every preference proﬁle of others provided they are also truthful. Our goal is to understand the following question: given positively correlated beliefs that are neither uniform nor extremely correlated, how do common voting rules,

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

and in particular scoring rules, perform with regard to EPIC?

We take an asymptotic view along the lines of Baharad and Neeman [2002], who prove that when the preferences of agents are drawn uniformly and independently at random the probability that any scoring rule is not EPIC goes to zero at a rate proportional to 1/pn for n agents.1 Their result also holds for small, local correlations among preferences, but fails when the correlation is global or large enough. We ﬁrst prove that positive correlation helps dramatically. Our main result is that the probability that any scoring rule is not EPIC goes to zero exponentially fast when an agent s belief is that the preferences of others are positively correlated with his own preference order according to the Kendall-Tau distance. We also establish a general result for any conditionally independent and identical beliefs, showing convergence of scoring rules to EPIC at a rate proportional to 1/pn.

Motivated by rank-order models from machine learning [Marden, 1996], we introduce two examples of positivelycorrelated belief systems, namely Conditional Mallows and Conditional Plackett-Luce. These two families of belief systems span a wide range of positively correlated beliefs from being arbitrarily close to uniform to being extremely correlated. Conditional Mallows is Kendall-Tau correlated and ﬁts our main positive result. Conditional Plackett-Luce model is not, but we provide a different proof of exponential convergence to EPIC for this model.

2 Setup The set of alternatives is A = {1, . . . , m} and the set of voters is N = {1, . . . , n}. Let P be the set of all linear orders over A. Voter i has a preference order Pi 2 P over the m alternatives. Any voting rule is represented by a social choice function f : Pn ! A. We will write P i to denote a preference proﬁle of all the voters other than i. We will use a Pib to denote that alternative a is preferred over alternative b according to the preference order Pi.

Given preference Pi, let µi(P i|Pi) denote the probability that voter i ascribes to voters other than i having preference proﬁle P i 2 Pn 1. Note that like Sen et al. [2015], we do not insist that the conditional probabilities µi(P i|Pi) should be generated from a given underlying common prior over the entire proﬁle of n voters. We will call a collection of conditional probability distributions µ1, . . . , µn a belief system.

We adopt ex post incentive compatibility (EPIC) as a solution concept. A voting rule is strategy-proof if truthful reporting is a dominant strategy for each voter. EPIC provides truthful reporting as a best response to any preference proﬁle of others, provided they are also truthful. Deﬁnition 2.1. A social choice function f : Pn ! A is EPIC with respect to the belief system {µi}n

i=1, if for each agent i and 8Pi, P 0

i f(Pi, P i)Pif(P 0

i, P i) 8P i in support of µi( |Pi) (1)

For µi( |Pi) with full support over Pn 1 for every Pi, then f is EPIC iff it is also strategy-proof. However, EPIC and

1Although Baharad and Neeman [2002] use the term asymptotic strategyproofness , they actually consider EPIC as the notion of equilibrium

strategy-proof social choice functions become very different when we compute the probability that an agent can manipulate. Suppose agent i has preference Pi and L(Pi) = {P i 2 Pn 1 : 9P 0

i, P i)Pif(Pi, P i)}, the set of all preference proﬁles of others such that agent i wants to deviate. Then the probability that i can manipulate in the sense of a dominant strategy is either 0 or 1 (it is 0 if L(Pi) = ;, and 1 otherwise). On the other hand, the probability that i can manipulate in the sense of an ex post Nash equilibrium is P

P i2L(Pi) µi(P i). We are interested in showing that the last probability becomes exponentially small in the number of agents when the belief system is positively correlated.

2.1 Positively Correlated Preferences

Sen et al. [2015] introduce two types of correlation for a given belief system {µi}n

i=1: Top-Set correlation and Kendall-Tau correlation. Let Bk(Pi) denote the set of top k alternatives as ranked by Pi. A belief system is Top-Set correlated (TScorrelated) if every voter i believes that the event where every other voter has the same top-k set of alternatives as i is strictly more likely than the event where every other voter has some other subset T as their top-k set.

Deﬁnition 2.2 (Top-Set Correlated). Belief system {µi}n

i=1 is TS-correlated if 8k 2 {1, . . . , m 1}, 8i, 8Pi, 8T 6= Bk(Pi) and |T| = k:

{P i: 8j6=i Bk(Pj)=Bk(Pi)}

µi(P i|Pi) >

{P i: 8j6=i Bk(Pj)=T }

µi(P i|Pi) (2)

A belief system is Kendall-Tau correlated (KT-correlated) if every voter i believes that the preference proﬁles of other voters are ordered in decreasing probability according to increasing sum Kendall-Tau distance between the preferences of others and voter i s true preference Pi. Let d(Pi, Pj) be the Kendall-Tau distance (i.e., the number of pairwise disagreements) between preferences Pi and Pj.

Deﬁnition 2.3 (Kendall-Tau Correlated). Belief system {µi}n

i=1 is KT-correlated if for all Pi, P i, P 0

µi(P i|Pi) > µi(P 0

d(Pj, Pi) <

We use D(P i|Pi) in place of P

j6=i d(Pj, Pi). It is easy to show that any KT-correlated belief system is also TScorrelated, but not vice-versa. [Bhargava et al., 2011]

Deﬁnition 2.4. A belief system {µ}n

i=1 is conditionally independent and identically distributed (c.i.i.d.) if

8i, 8Pi, 8P i : µi(P i|Pi) =

(Pj|Pi) (3)

where ( |Pi) is a probability distribution over orders P.

We work with c.i.i.d. belief systems. We will see examples of different families of positively correlated and c.i.i.d. belief systems in Section 4.

3 Scoring Rules Scoring rules [Young, 1975] are deﬁned in the following way. Fix a non-decreasing sequence of real numbers, s1 s2 . . . sm, such that s1 > sm. If a voter ranks an alternative x at position j then x gets a score of sj. We will write sc(j, Pi) to denote the score of an alternative j according to the preference Pi. The score of an alternative is the sum of the scores received from all the voters. The alternative with the highest score is chosen as the outcome of the election. In case there is a tie, a winning alternative is selected according to some tie-breaking rule. We insist that s1 > sm, otherwise if s1 = sm, every alternative receives the same score and the resulting social choice function just depends on the tie-breaking rule. Some popular scoring rules are: Plurality (1, 0, 0, . . . , 0), Borda (m 1, m 2, . . . , 1, 0) and Veto (1, 1, 1, . . . , 1, 0).

Baharad and Neeman [2002] prove that the probability that any scoring rule is not EPIC goes to zero at rate of 1/pn with the number of agents n. They consider the following setting: (1) each voter is equally likely to have any preference order, i.e. the marginal distribution is uniform, and (2) the preferences of the voters are locally correlated, i.e. the voters can be numbered in a sequence such that the further they are apart, the more independent their preferences become. In an independent work, Slinko [2002] shows that the number of manipulable preference proﬁles (proﬁles where some agent can beneﬁt by deviating unilaterally) goes to zero at a rate of 1/pn for any scoring rule. This result also proves the same rate of convergence to EPIC for uniform i.i.d. preferences. We prove that when the preferences of the voters are KT-correlated and c.i.i.d., the probability that any given scoring rule is not EPIC goes to zero exponentially fast. Our result strengthens what is known about the asymptotic nonmanipulability of scoring rules.

3.1 EPIC Convergence for KT-correlation Suppose {µi}n

i=1 is a c.i.i.d. belief system, that is, for all i, we have µi(P i|Pi) = Q

j6=i (Pj|Pi). Consider any preference Pi 2 P and any two alternatives a and b such that a Pib. Let

µa,b(Pi) = EP ( |Pi) [sc(a, Pi) sc(b, Pi)] (4) denote the expected difference of scores between alternatives a and b for a random preference order of some other agent, this preference drawn according to the conditional distribution ( |Pi). Let σ2

a,b(Pi) denote the variance of the difference in score between a and b. We now state our main result. Theorem 1. Suppose a belief system {µi}n

i=1 is c.i.i.d. and KT-correlated. Then the probability that any given scoring rule is not EPIC w.r.t. {µi}n

i=1 goes to zero at a rate proportional to O (e cn), for some constant c > 0.

A useful lemma establishes that µa,b(Pi) > 0, for any preference Pi and alternatives a, b such that a Pib. Lemma 2. Suppose the belief system {µi}n

i=1 is c.i.i.d. and KT-correlated. Consider a preference ordering Pi, and alternatives a and b such that a Pib. Then µa,b(Pi) > 0.

Proof. Select two preference orderings Pj and P 0

j such that d(Pj, Pi) < d(P 0

j, Pi). Now consider the following two preference proﬁles for voters other then i:

i = (Pi, . . . , Pi, Pj, Pi, . . . , Pi)

i = (Pi, . . . , Pi, P 0

j, Pi, . . . , Pi)

i, Pi) = d(Pj, Pi) < d(P 0

j, Pi) = D(P 2

i, Pi). Since {µi}n

i=1 is KT-correlated, we have µi(P 1

i|Pi) > µi(P 2

i|Pi). Furthermore, {µi}n

i=1 is c.i.i.d., therefore there exists a function such that µi(P i|Pi) = Q

j6=i (Pj|Pi). µi(P 1

i|Pi) > µ(P 2

i|Pi) implies

(Pi|Pi)n 2 (Pj|Pi) > (Pi|Pi)n 2 (P 0

Therefore, we have d(Pj, Pi) < d(P 0

j, Pi) implies (Pj|Pi) > (P 0

j|Pi). Now, partition the set of all preference orderings P into Pa b and Pb a. Every preference ordering P in Pa b ranks a above b and vice versa for Pb a. Note that there exists a one-to-one mapping f : Pa b ! Pb a, namely f(P) be the same as P except positions of alternatives a and b exchanged. Then

(sc(a, P) sc(b, P)) (P|Pi)

(sc(a, P) sc(b, P))( (P|Pi) (f(P)|Pi)).

Now for all P 2 Pa b, d(P, Pi) < d(f(P), Pi) and therefore (P|Pi) > (f(P)|Pi). Moreover there exists at least one P such that sc(a, P) > sc(b, P) (e.g. when P places a at top and b at bottom). This proves that µa,b(Pi) > 0.

We will also use the Chernoff-Hoeffding inequality for bounded random variables. Lemma 3. (Theorem 2,[Hoeffding, 1963]) Let X1, X2, . . . , Xn be independent and for all i, ai Xi bi. Let Xn = 1

i=1 Xi and µ = E

i=1(bi ai)2

Proof. (of Theorem 1.) Suppose voter 1 observes a preference order x1. Let Xi be the random variable corresponding to the preference ordering seen by agent i. Conditioned on the event X1 = x1, voter 1 believes that the random variables X2, X3, . . . are i.i.d. with distribution ( |x1).

Fix any two alternatives a and b such that a x1 b. We show that the probability that agent 1 can improve the ordering of a vs b in the social ranking, through making some misreport of his preference order, falls exponentially quickly in the number of agents n. For i = 2, 3, . . . , let Zi

a,b = sc(a, Xi) sc(b, Xi) be the difference of scores between alternatives a and b assigned by voter i s true preference Xi. Since X2, X3, . . . are i.i.d., so are Z2

a,b, . . .. As introduced

= µa,b(x1) and Var(Zi

a,b(x1). De-

a,b (where voters 2 through n + 1 each have c.i.i.d. preferences).

Now voter 1 wants to manipulate and report a preference ordering different from x1 only if sm s1 Zn

sc(b, x1) sc(a, x1). To see this, ﬁrst suppose Zn

a,b < sm s1 < 0. Then even by placing a at top and b at bottom, voter 1 can increase the difference in scores between a and b by at most s1 sm and this still fails to cause a to rank higher than b. So, in this case, voter 1 is happy to report x1.

On the other hand, suppose Zn

a,b > sc(b, x1) sc(a, x1). If 1 reports truthfully then the net difference of scores between a and b is Zn

a,b + sc(a, x1) sc(b, x1) > 0 and a and b are already ordered according to 1 s preferences.

Let a,b = sc(b, x1) sc(a, x1). Note that, a,b 0 since a x1 b. Then the probability of manipulation by voter 1 is bounded by Pr

, which we bound using Chernoff-Hoeffding inequality (Lemma 3) as follows :

a,b µa,b(x1) t

Where t = µa,b(x1) 1

n a,b. Since Zi

a,b is the difference of scores between alternatives a and b according to Xi, we have Zi

a,b 2 [sm s1, s1 sm]. Now applying Chernoff Hoeffding inequality we get an upper bound of

+ µa,b(x1) a,b

As n goes to inﬁnity, e γ/n goes to 1 for any constant γ > 0. Therefore, for large enough n, the probability of manip-

ulation is O

e ca,b(x1)n2

where ca,b(x1) = 1 2

. Since the preference ordering x1 and the alternatives a and b can arbitrary, using a union bound we get the actual probability of manipulation is e cn where the constant c takes the worst-case, and

Lemma 2 proves that for any KT-correlated and c.i.i.d. belief system, µa,b(x1) > 0 for any x1 and any a and b such that a x1 b. This proves that c > 0, and ﬁnishes the proof.

3.2 EPIC Convergence for TS-correlation

Lemma 2 need not be true for a TS-correlated belief system. Here is a counter-example. Consider a situation with 2 voters, 3 alternatives, and Borda scoring rule (2, 1, 0). Suppose voter 1 s preference ordering is 1 P1 2 P1 3 (in short 123). We now construct a TS-correlated belief system for which µ1,2(123) = EX2 ( |123)

Any TS-correlated belief system needs to satisfy the following system of inequalities (we drop the conditioning on preference ordering 123 for notational convenience):

µ1(123) + µ1(132) > µ1(213) + µ1(231) µ1(123) + µ1(132) > µ1(312) + µ1(321) µ1(123) + µ1(213) > µ1(132) + µ1(312) µ1(123) + µ1(213) > µ1(231) + µ1(321)

Let us choose the following distribution: µ1(123) = 1 6", µ1(132) = µ1(213) = µ1(312) = µ(321) = ", µ1(231) = 2". It can be easily veriﬁed that µ1 satisﬁes the inequalities above as long as " < 1/8. Now µ1,2(123) = 1 9" < 0 if " > 1/9. To get a counter-example, one can choose any " 2 (1/9, 1/8).

However, we now prove that the rate of convergence is not worse than O (1/pn) for any c.i.i.d. belief system. Our proof uses the Berry-Esseen theorem which quantiﬁes the rate of convergence of the central limit theorem. Lemma 4. (Berry-Esseen) Let X1, X2, . . . , Xn be i.i.d. with E [Xi] = 0, E

= < 1. If Fn(x) is

the distribution function of (X1+. . .+Xn)/σpn and Φ(x) is the distribution function of standard normal random variable then, 8x 2 R,

|Fn(x) Φ(x)| 3 σ3pn.

See [Durrett, 2010] (Theorem 3.4.9) for a proof. Theorem 5. Suppose a belief system {µi}n

i=1 is c.i.i.d. Then the probability that any given scoring rule is not EPIC w.r.t. {µi}n

i=1 goes to zero at a rate proportional to O

Proof. As proved in Theorem 1, the probability of manipulation is bounded by Pr

. Now, we use the central limit theorem instead of Chernoff Hoeffding inequality to bound the probability of manipulation. Z2

a,b, . . . are iid with mean µa,b(x1) and variance σ2

a,b(x1). Therefore, by the central limit theorem

a,b nµa,b(x1)

d ! N(0, 1). (6)

Let us write Tn =

a,b nµa,b(x1)

σa,b(x1)pn . Then

sm s1 nµa,b(x1)

σa,b(x1)pn Tn a,b nµa,b(x1)

a,b nµa,b(x1)

sm s1 nµa,b(x1)

Here FTn is the distribution function of Tn. Now we use the following relation :

8l u, FTn(u) FTn(l) |FTn(u) FTn(l)|

|FTn(u) Φ(u)| + |Φ(u) Φ(l)| + |Φ(l) FTn(l)| .

(sm s1)/n a,b/n 0 µa,b(x1)

(a) Kendall-Tau Correlated Belief

(sm s1)/n µa,b(x1) a,b/n 0

(b) Any c.i.i.d. Belief

Figure 1: The blue regions determine the probability of manipulation. For a KT-correlated belief (1a) we use the tail probability and for any general c.i.i.d. belief (1b) we use the area of the surrounding rectangle.

We can bound the ﬁrst and the third term by the Berry Esseen Theorem (Lemma 4) (since Zi

a,b is a discrete distribution, its third absolute moment a,b(x1) is ﬁnite) to get

FTn(u) FTn(l) 6 a,b(x1) σ3

a,b(x1)pn +

φ(t)dt. (7)

Using the last relation, we can ﬁnally prove the following bound on probability of manipulation :

6 a,b(x1) σ3

a,b(x1)pn +

Z a,b nµa,b(x1)

sm s1 nµa,b(x1)

Since e t2/2 1, the last integral can be bounded above by 1 p

σa,b(x1)pn . This proves that the probability of manipulation is O (1/pn).

4 Rank-Order Models

Now we present some examples of belief systems that are c.i.i.d. and positively correlated. Our main source of examples is the rank-order models from machine learning.

Mallows Model The Mallows [1957] model was originally deﬁned with respect to a ﬁxed (latent) preference ordering σ and a dispersion parameter r 2 (0, 1]. Let be any preference ordering, then the Mallows model speciﬁes Pr [ |σ, r] / rd( ,σ), i.e. the probability of observing the ordering decays exponentially with its Kendall-Tau distance from σ. We are not aware of any adaptation of the Mallows model for a conditional belief system. However any such adaptation should capture the idea that once a voter i observes a preference ordering Pi, then she believes that the preference ordering of any other agent is a noisy version of Pi, with its probability decaying exponentially with the Kendall-Tau distance from Pi. This motivates the following belief system:

Deﬁnition 4.1. A belief system {µi}n

i=1 is a Conditional Mallows model if 9r 2 (0, 1] such that

µi(P i|Pi) / r

j6=i d(Pj,Pi). (8)

Theorem 6. Every Conditional Mallows model is c.i.i.d. and KT-correlated.

The proof is trivial since if {µi}n

i=1 is a conditional belief system then (Pj|Pi) / rd(Pj,Pi). As a consequence of Theorem 6, if {µi}n

i=1 is a conditional Mallows model, then any scoring rule becomes EPIC at a rate proportional to O (e cn) where c is as deﬁned in Equation (5).

Plackett-Luce Model The Plackett-Luce model [Plackett, 1975; Luce, 1959] on a set of alternatives {1, . . . , m} has m parameters: γj > 0 for each alternative j, such that Pm

j=1 γj = 1. For a permutation of the m alternatives, let [k] denote the alternative placed at position k. The probability of permutation is given as:

= γ [1] γ [1] + . . . + γ [m]

γ [2] γ [2] + . . . + γ [m]

. . . γ [m 1] γ [m 1] + γ [m]

We propose the following belief system {µi}n

i=1 based on the Plackett-Luce Model. Deﬁnition 4.2. A belief system {µi}n

i=1 is a Conditional Plackett-Luce model if there exists m parameters γ1 > γ2 > . . . > γm and Pm

l=1 γl = 1 such that µi(P i|Pi) = Q

j6=i (Pj|Pi), where

(Pj|Pi) = Pr

Pj|{γPi[l]}m

To compute (Pj|Pi), we ﬁrst permute the m parameters {γl}m

l=1 according to Pi so that γPi[1] > γPi[2] > . . . > γPi[m], and then use the standard Plackett-Luce model.

The Conditional Plackett-Luce model is not KT-correlated. Suppose there are two voters (n = 2) and four alternatives (m = 4). We will write 1234 to denote the preference ordering 1 P1 2 P1 3 P1 4. We now construct a set of parameters {γl}4

l=1 such that µ1(1342 | 1234) > µ1(2134 | 1234). Since d(1342, 1234) = 2 > 1 = d(2134, 1234), µ1( ) is not KTcorrelated. Let γ1 = 1 6", γ2 = 3", γ3 = 2", γ4 = ". For, γ1 > γ2, we require 1 6" > 3" or " < 1/9. Now,

µ1(1342 | 1234) > µ1(2134 | 1234)

γ3 γ3 + γ4 + γ2

γ1 γ1 + γ3 + γ4

γ3 γ3 + γ4 , 1/12 > 2"/(1 3") , " < 1/27. Therefore, as long as " < 1/27, the belief system fails to be KT-correlated. However, we now prove that the Conditional PL model is TS-correlated. We use the following lemma about the likelihoods in the Conditional PL model.

Lemma 7. For all k, all 1 k m, such that l1, . . . , lk distinct, P

: [1]=l1,..., [k]=lk Pr [ |{γl}m

γl2 1 γl1 . . .

γlk 1 γl1 ...γlk 1 .

See Hunter [2004] for an outline of the proof. Theorem 8. Every Conditional PL Model is TS-correlated.

Proof. Let {µi}n

i=1 be a Conditional PL belief system with parameters {γl}m

l=1 where γ1 > γ2 > . . . > γm > 0 and Pm

l=1 γl = 1. For any set T of size k (1 k m 1),

{P i : Bk(Pj )=T

µi(P i|Pi) =

{P :Bk(P )=T }

This follows from two observations : (1) {µi}n

i=1 is c.i.i.d., so µi(P i|Pi) = Q

j6=i (Pj|Pi), and (2) Using the multinomial

{P :Bk(P )=T } (P|Pi)

can be written as X

8j6=i Pj2{P :Bk(P )=T }

(Pj|Pi) (11)

Now, from the deﬁnition of a TS-correlated belief system (2), it is enough to show that P

P :Bk(P )=Bk(Pi) (P|Pi) > P

P :Bk(P )=T (P|Pi). Without loss of generality, we can assume that Pi places i-th alternative at position i. Let T = {t1, . . . , tk} such that γt1 > γt2 > . . . > γtk. We will write S ([k]) to denote the set of all permutations over the set {1, . . . , k}. We have:

P :Bk(P )=Bk(Pi)

P :Bk(P )=T

P :P [j]= [j], 1 j k

Pr [P|{γl}m

P :P [j]=t [j], 1 j k

Pr [P|{γl}m

{using Lemma 7}

γ [2] 1 γ [1]

. . . γ [k] 1 γ [1] . . . γ [k 1]

γt [2] 1 γt [1]

. . . γt [k] 1 γt [1] . . . γt [k 1]

Since T is different from Bk(P), the set of top-k alternatives in preference ordering P, we have for any 2 S ([k]), γ [j] γt [j] for j = 1, . . . , k and 9t γ [t] > γt [t]. This implies that for all l t

γ [l] 1 γ [1] . . . γ [l 1]

> γt [l] 1 γt [1] . . . γt [l 1]

which is sufﬁcient to guarantee (12).

Since the Conditional PL model is not KT-correlated, we cannot use Theorem 1 to claim exponential EPIC convergence of any scoring rule under this model. However, the next theorem shows that the convergence is indeed exponential, and that this is true for any scoring rule.

Theorem 9. The probability that any scoring rule is not EPIC w.r.t. a Conditional Plackett-Luce model goes to zero at a rate proportional to O (e cn), for some constant c > 0.

Proof. Let the belief system {µi}n

i=1 be a Conditional Plackett-Luce model with parameters {γl}m

l=1 where γ1 > γ2 > . . . > γm > 0 and Pm

l=1 γl = 1. Consider a voter i with preference ordering Pi and two alternatives a and b such that a Pib. As we have argued in Theorem 1, it is sufﬁcient to show that µa,b(Pi) > 0. Without loss of generality we can assume that Pi places the i-th alternative at position i. We have:

µa,b(Pi) = EXj ( |Pi) [sc(a, Xj) sc(b, Xj)]

(sl1 sl2) {Pr [Xj[l1] = a, Xj[l2] = b|{γt}m

Pr [Xj[l1] = b, Xj[l2] = a|{γt}m

Therefore, it is enough to show that for any l2 > l1, Pr [Xj[l1] = a, Xj[l2] = b|{γl}m

l=1] > Pr [Xj[l1] = b, Xj[l2] = a|{γl}m

l=1]. Now, suppose alternatives a and b are placed respectively at positions r and s of Pi. Therefore, γr > γs. Then by Lemma 7 we have,

Pr [Xj[l1] = a, Xj[l2] = b|{γl}m

i1,...,il2 22[m]\{a,b}

σ2S({i1,...,il2 2})

f(γσ[i1], . . . , γσ[il1 1], γr, γσ[il1], . . . , γσ[il2 2], γs) where

f(λ1, . . . , λk) = λ1

. . . λk 1 λ1 . . . λk 1

It is easy to see that γr > γs implies f(γσ[i1], . . . , γσ[il1 1], γr, γσ[il1], . . . , γσ[il2 2], γs) > f(γσ[i1], . . . , γσ[il1 1], γs, γσ[il1], . . . , γσ[il2 2], γr), as γrγs cancels out from both sides, and for all j such that l1 j l2 2, we have (1 γσ[i1] . . . γσ[ij] γr) 1 > (1 γσ[i1] . . . γσ[ij] γs) 1.

5 Conclusion We have provided a positive result for incentive-aligned social choice in the presence of correlation between voter preferences. When the beliefs of agents are positively correlated in terms of Kendall-Tau distance, we show that all scoring rules become EPIC exponentially quickly in the number of voters. We have instantiated the general framework to conditional variations on the popular Mallows and Plackett-Luce models for rank aggregation. One question for future work is whether exponential, EPIC convergence holds for correlated distributions that are not conditionally independent and identical. We also leave open the question of closing the gap between exponential convergence and 1/pn for the class of TS-correlated beliefs.

6 Acknowledgements This work is supported in part by NSF grant CCF-1301976 and a grant from the FLI. We also thank Yang Liu for technical feedback on an earlier version.

References [Altman and Tennenholtz, 2010] Alon Altman and Moshe

Tennenholtz. An Axiomatic Approach to Personalized Ranking Systems. J. ACM, 57(4), 2010. [Baharad and Neeman, 2002] Eyal Baharad and Zvika Nee-

man. The Asymptotic Strategyproofness of Scoring and Condorcet Consistent Rules. Review of Economic Design, 7(3):331 340, 2002. [Barber a, 2011] Salvador Barber a. Strategyproof Social Choice. Handbook of social Choice and Welfare, 2:731 831, 2011. [Bhargava et al., 2011] Mohit Bhargava, Dipjyoti Majum-

dar, and Arunava Sen. Incentive-Compatible Voting Rules with Positively Correlated Beliefs. Available at http:// www.isid.ac.in/ asen/papers/ms.pdf/, version : April 10, 2011. [Conitzer and Walsh, 2016] Vincent Conitzer and Toby Walsh. Barriers to Manipulation in Voting. Handbook of Computational Social Choice, Forthcoming, 2016. [Durrett, 2010] Rick Durrett. Probability: Theory and Ex-

amples. Cambridge university press, 2010. [Faliszewski and Procaccia, 2010] Piotr Faliszewski and Ariel D Procaccia. AI s War on Manipulation: Are We Winning? AI Magazine, 31(4):53 64, 2010. [Gibbard, 1973] Allan Gibbard. Manipulation of Voting Schemes: A General Result. Econometrica, pages 587 601, 1973. [Hoeffding, 1963] Wassily Hoeffding. Probability Inequali-

ties for Sums of Bounded Random Variables. Journal of the American statistical association, 58(301):13 30, 1963. [Hunter, 2004] David R Hunter. MM Algorithms for Gener-

alized Bradley-Terry Models. Annals of Statistics, pages 384 406, 2004. [Lang and Xia, 2009] J erˆome Lang and Lirong Xia. Sequen-

tial Composition of Voting Rules in Multi-Issue Domains. Mathematical Social Sciences, 57(3):304 324, 2009. [Luce, 1959] R.. Ducan Luce. Individual Choice Behavior :

A Theoretical Analysis. John Wiley and sons, 1959. [Majumdar and Sen, 2004] Dipjyoti Majumdar and Arunava

Sen. Ordinally Bayesian Incentive Compatible Voting Rules. Econometrica, 72(2):523 540, 2004. [Mallows, 1957] Colin L Mallows. Non-Null Ranking Mod-

els. Biometrika, pages 114 130, 1957. [Mao et al., 2013] Andrew Mao, Ariel D. Procaccia, and Yil-

ing Chen. Better Human Computation Through Principled Voting. In Proceedings of the Twenty-Seventh AAAI Conference on Artiﬁcial Intelligence, July 14-18, 2013, Bellevue, Washington, USA., 2013. [Marden, 1996] John I Marden. Analyzing and Modeling Rank Data. CRC Press, 1996. [Parkes et al., 2015] David C. Parkes, Ariel D. Procaccia,

and Nisarg Shah. Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities. ACM Transactions on Economics and Computation, 3(1):3, 2015.

[Pennock et al., 2000] David M. Pennock, Eric Horvitz, and

C. Lee Giles. Social Choice Theory and Recommender systems: Analysis of the Axiomatic Foundations of Collaborative Filtering. In Proceedings of the Seventeenth National Conference on Artiﬁcial Intelligence and Twelfth Conference on Innovative Applications of Artiﬁcial Intelligence, pages 729 734. AAAI Press, 2000. [Plackett, 1975] Robin L Plackett. The Analysis of Permuta-

tions. Applied Statistics, pages 193 202, 1975. [Satterthwaite, 1975] Mark Allen Satterthwaite. Strategy Proofness and Arrow s Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions. Journal of Economic Theory, 10(2):187 217, 1975. [Sen et al., 2015] Arunava Sen, Mohit Bhargava, and Dipjy-

oti Majumdar. Incentive-Compatible Voting Rules with Positively Correlated Beliefs. Theoretical Economics, 10(3):867 885, 2015. [Slinko, 2002] Arkadii Slinko. On Asymptotic Strategy Proofness of Classical Social Choice Rules. Theory and Decision, 52(4):389 398, 2002. [Young, 1975] H Peyton Young. Social Choice Scoring Functions. SIAM Journal on Applied Mathematics, 28(4):824 838, 1975.