# measuring_and_controlling_divisiveness_in_rank_aggregation__bf005a60.pdf

Measuring and Controlling Divisiveness in Rank Aggregation

Rachael Colley1 , Umberto Grandi1 , C esar Hidalgo2,3,4 , Mariana Macedo2 , Carlos Navarrete2

1IRIT, Universit e Toulouse Capitole, France 2Center for Collective Learning, ANITI, TSE, IAST, IRIT, Universit e de Toulouse, France 3Alliance Manchester Business School, University of Manchester, UK 4Center for Collective Learning, CIAS, Corvinus University, Hungary {rachael.colley,umberto.grandi}@irit.fr, {cesar.hidalgo, mariana.macedo, carlos.navarrete}@univ-toulouse.fr

In rank aggregation, members of a population rank issues to decide which are collectively preferred. We focus instead on identifying divisive issues that express disagreements among the preferences of individuals. We analyse the properties of our divisiveness measures and their relation to existing notions of polarisation. We also study their robustness under incomplete preferences and algorithms for control and manipulation of divisiveness. Our results advance our understanding of how to quantify disagreements in collective decision-making.

1 Introduction Rank aggregation is the problem of ordering a set of issues according to a set of individual rankings given as input. This problem has been studied extensively in computational social choice (see, e.g., Brandt et al. [2016]) when the rankings are assumed to represent human preferences over, for example, candidates in a political election, projects to be funded, or more generally alternative proposals. The most common approach in this literature is to find normative desiderata for the aggregation process, including computational requirements such as the existence of tractable algorithms for its calculation and characterisations of the aggregators that satisfy them. Rank aggregation also has a wide spectrum of applications from metasearch engines [Dwork et al., 2001] to bioinformatics [Kolde et al., 2012], receiving attention also in the statistical ML literature [Korba et al., 2017]. Previous work on rank aggregation has focused on how to best elicit which issues are the most agreed upon, without identifying the issues that divide them. Instead, a wide literature in economics and the social sciences has developed measures of social, economic, and political polarisation. Classical work analysed polarisation in the distribution of wealth, goods, and opinions [Esteban and Ray, 1994; Duclos et al., 2004], showing that well-studied notions of inequality are unfit to measure polarisation as they do not consider the weight of sub-populations. Another common approach in social science uses the variance of distributions to measure polarisation (see, e.g., Musco et al. [2018]; Gaitonde et al. [2020]). In this paper, we put forward a family of functions that starting from a collection of individual rankings are able to

order issues based on their divisiveness. We compute an issue s divisiveness by aggregating the disagreement among all possible sub-populations defined by the relative preference among the other issues. Our proposal relates to the literature on three important aspects. First, a parameter in our definition allows us to move from an adaptation of the classical measure of polarisation from Esteban and Ray [1994] at one end of the spectrum to the detection of disagreements from minorities at the other end. Second, our measures are parameterised by the rank aggregation function that is used to compute the most agreed-upon issues. In this way, we can align our notions of divisiveness with the functions chosen to measure the agreement of the population.1 Third, while existing work focused on comparing different sets of rankings based on polarisation [Can et al., 2015], diversity [Hashemi and Endriss, 2014], or cohesiveness [Alcantud et al., 2015], here, we aim at identifying the most divisive issues within a complete profile of rankings. In doing so, we do not need to assume that issues are independent, as common in the social choice literature. Our work can further guide how to query a population towards being more inclusive and unified, e.g., through deliberative instances. This can include measures that go towards decreasing divisiveness, such as recent work suggesting the construction of recommender systems to depolarise a population [Stray, 2022], or simply take advantage of this information when steering the public debate (recent work from Ash et al. [2017] suggests that politicians spend more time on divisive topics than on neutral ones). Our work also contributes to social choice theory, where related notions of preference diversity have shown to have effects on the probability of paradoxes [Gehrlein and Lepelley, 2010], the competitiveness in matching markets [Hałaburda, 2010], or the computational complexity of manipulating an election [Wu et al., 2022]. Moreover, our work can be useful in refining the preference analysis of applications, such as online forums or surveys, that query a population on their opinions and return aggregated information about the group as a whole.

Contribution and Paper Structure. We extend the notion of divisiveness, introduced by Navarrete et al. [2022], to a family of measures which take into account the size

1This is particularly important in social choice applications, where the individual preferences collected are a (possibly strategic) response to the collective decision-making rule chosen.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

of a sub-population and use the well-studied scoring functions. These extensions allow us to connect divisiveness to measures of polarisation. We give a theoretical and experimental analysis of our divisiveness measures by relating them to other notions and giving bounds on their limit cases (Section 3). Importantly, we show that our measures can distinguish between key profiles which other measures cannot. We then inspect two aspects of control, first, by studying the effect of removing pairwise comparisons from the agent s rankings (Section 4.2 ) and second, by adding additional controlled agents (Section 4.2). All our code is available at https://github.com/Center For Collective Learning/ divisiveness-theoretical-IJCAI2023.

Related Work. The notion of divisiveness studied in this paper builds on the work of Navarrete et al. [2022], who identify the most divisive issues from proposed government programs from crowdsourced political preferences. Many papers start from a profile of rankings and compare them based on how consensual (equivalently, cohesive) they are [Bosch, 2005; Garc ıa-Lapresta and P erez-Rom an, 2010; Alcalde Unzu and Vorsatz, 2008, 2013], or in the opposite direction, i.e., how diverse is the set of preferences [Hashemi and Endriss, 2014; Karpov, 2017]. In particular, Alcantud et al. [2015] measures the cohesiveness of a group by aggregating the dissimilarity of their orderings (similarly to Can et al. [2015] who however focus on polarisation). Most of these settings are based on pairwise comparisons, except for Alcalde-Unzu and Vorsatz [2016] and Xue et al. [2020], who look at patterns of varying sizes in the rank profile. One of the methods proposed by Hashemi and Endriss [2014] to measure preference diversity is to average the distance between the individual rankings and the aggregated one. This is in line with our approach, but it only provides a measure to compare different populations of rankings without going to the level of single issues. We note that also an influential theory of diversity not based on preferences but on (binary) features of not necessarily independent alternatives has been proposed by Nehring and Puppe [2002].

2 Basic Definitions

This section introduces the basics of rank aggregation and scoring rules. We put forward our definition of divisiveness, then we compare it with existing notions of polarisation.

2.1 Preliminaries

Rankings. Let I = {a, b . . . } be a finite non-empty set of m issues. A strict ranking (aka. linear order) on I is an asymmetric, transitive, and complete binary relation on I. We let a b denote the fact that a is strictly preferred to b in the ranking . In what follows, we will write = acdb for = a c d b, reading preferences from left to right. The set of all strict rankings over I will be denoted by L(I). We denote with rank(a, ) the rank of a in with the first position being 1 and the last being m.

Individual Rankings. Let a finite non-empty set of N = {1, . . . , n} agents express a strict rankings over I (sometimes referred to as preferences). We let P = ( 1, . . . , n) denote

the resulting profile of rankings, where i is agent s i ranking over I. We let Na b = {i N | a i b} be the set of voters in N who prefer a to b. The restriction of profile P to the agents in X is denoted by PX = i| i X . When X = Na b we simply write Pa b. We call P a consensual profile if for all i, j N we have that i= j. Every preference profile P can be represented as a weighted (anonymous) profile, i.e., as a set of pairs (wj, j) indicating that wj N agents have preference j. Collective Scoring of Issues. Rank aggregation functions define a collective ranking of issues based on the agreements among the individual rankings in a profile. A large number of rules have been proposed and analysed in the literature on (computational) social choice and artificial intelligence. We focus on rank aggregators defined by a scoring function, where the collective ranking over issues is obtained via a function s : I L(I) [0, 1] that assigns a score to each issue in a given profile. Notable examples are the (normalised) Borda score, which counts the number of issues strictly preferred to a given issue, Borda(a, P) = P b I\{a} #(Na>b)

n (m 1) , where #(X) is the cardinality of a set X. Or the normalised Copeland score, which counts the number of majority contests won by an issue, Cop(a, P) = #{b I\{a} | #(Na>b)>#(Nb>a)}

2.2 Divisiveness For a given sub-population X N and issue a I, we measure the divisiveness of a for X as the difference between the collective scoring of a in sub-population X and in its complement sub-population N\X. Definition 1. [Navarrete et al., 2022] The divisiveness of an issue a I with respect to a sub-population X N in profile P is defined as:

DIVs(a, X, P) = |s(a, PX ) s(a, PN \X )|.

If X = or X = N, we set DIVF(a, X, P) = 0. Examples of a sub-population X can be descriptive, such as agents living in cities (thus N\X are agents living in rural areas) or agents with a given political orientation (thus, N\X would be those who do not ascribe to this orientation). We can now give a definition of divisiveness for issue a that is independent of a given sub-population by averaging over all sub-populations Na b for all other issues b. We include an additional parameter α that allows us to take into consideration the size of a sub-population allowing for a weighted average version of an issue s divisiveness. Definition 2. The α-divisiveness DIVs α(a, P) of an issue a I in profile P, with α [0, 1] and ℓ R+, is defined as:

ℓ#(Na>b) #(Nb>a)

α DIVs(a, Na b, P).

When α = 0 and s = Borda, our definition is a reformulation of the divisiveness measure from Navarrete et al. [2022]. When α = 1, Definition 2 can be interpreted as one of the polarisation measures of Duclos et al. [2004] and Esteban and Ray [1994], calculated on the distribution of ranks

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

that issue a received from individuals. We refer to the multiplicative factor of the measure defined in Definition 2 in each summand as the α-factor. The α-factor is maximal when #(Na b) = #(Nb a) = n/2, and we will often set ℓ= 4 so that the α-factor is at most 1. ℓis a normalising factor left open in line with Esteban and Ray [1994]. Intuitively, as α increases in Definition 2, the relevance of the size of the disagreeing sub-population increases. The following example presents the limit case of α = 0 where the size of disagreeing sub-populations is ignored, resulting in a different divisiveness ranking than α = 1.

Example 1. Consider 2k agents giving their preferences in profile P over issues I = {a, b, c, d, e, f} as such:

1 (1 agent) cadfeb 2 (k 1 agents) badfec 3 (k agents) bedfac

Assume now that k = 5 and ℓ= 4 (the normalising factor). Table 1 presents, for issue a, the table of disagreements (in terms of Borda score difference) between the 5 possible subpopulations defined by the pairwise comparisons of a with the remaining issues.

Issue x s(Pa x) s(Px a) disagreement α-factor

b 0.8 0.46 0.3 0.36 c 0.46 0.8 0.3 0.36 d 0.8 0.2 0.6 1 e 0.8 0.2 0.6 1 f 0.8 0.2 0.6 1

Table 1: Details of the calculations for divisiveness for issue a, setting ℓ= 4 and k = 5 and with s = Borda.

From Table 1, we can compute DIVBorda 0 (a, P) by averaging the disagreements and weighting by the α-factors to obtain DIVBorda 1 (a, P). Repeating this process for every issue gives us the values of divisiveness in Table 2.

x Borda(x, P) DIVBorda 0 (x, P) DIVBorda 1 (x, P)

a 0.5 0.493 0.408 b 0.9 1 0.36 c 0.1 1 0.36 d 0.6 0 0 e 0.5 0.493 0.408 f 0.4 0 0

Table 2: Normalised Borda score and divisiveness for α = 0, 1 of issues in the profile of Example 1 with k = 5 and ℓ= 4.

The most divisive issue for DIVBorda 0 is b and c, who are at the opposite extreme of the ordering for the first agent with respect to the rest of the population, while the most divisive for DIVBorda 1 are a and e, who are second or second-to-last for all agents, yet this divides the population into two. Observe that this holds for any k 5, showing a class of examples where the ranking of α-divisiveness differs significantly depending on if α = 0 or α = 1.

2.3 Rank-variance Related literature in the social sciences often measures polarisation using notions of variance, which we now adapt to rankings. Let µP(a) = 1 n P i N rank(a, i) be the average rank of an issue a I in a profile of rankings P. The rank-variance of issue a is defined as follows:

V ar(a, P) = 1

i N (rank(a, i) µP(a))2

The following example shows a profile in which the ranking of issues by variance differs from divisiveness (assuming α = 0 and s = Borda). Example 2. Consider the following preference profile: 1 (10 agents) abcde 2 (10 agents) ebcda 3 (1 agent) acbde 4 (1 agent) ebdca The rank-variance and the divisiveness using Borda and α = 0 for each issue is the following: a b c d e

V ar(x, P) 4 0.045 0.090 0.045 4 DIVBorda(x) 1 0.074 0.037 0.074 1 This shows that issue c has higher variance than issues b and d but lower divisiveness (Kendall s tau correlation between the two rankings is τ 0.5). Unlike other notions of polarisation, we focus on the comparisons between our divisiveness measures and rankvariance as they both return information about a single issue rather than about the population as a whole.

3 Measuring Divisiveness and Polarisation In this section, we present some basic properties of our definition of divisiveness, showing in particular that with α = 0 it does not coincide nor is correlated with standard notions of polarisation. We also show how our definitions can be used to identify the sub-population that is most divided on an issue.

3.1 Divisiveness Bounds We first observe that if s is a polynomially computable function, then so is DIVs α for any α. Moreover, if s is anonymous and neutral (as in the classical social choice terminology2) so is DIVs α for any α. A direct consequence of our definitions is that 0 DIVs α(a, P) 1, for any α. We now characterise the extremes of the spectrum. First we give the sufficient conditions for minimal divisiveness with the Borda and Copeland scorings. Let a profile P be rank-unanimous on a if for all i, j N we have that rank(a, i)=rank(a, j). Profile P is unanimous if i= j for all i, j N. The next result shows that divisiveness is minimal when consensus is maximal, following this, we will discuss the converse of this statement in a few different ways.

2A function taking profiles of linear orders as input is anonymous if permuting the individual rankings does not change the result. It is neutral if all issues are treated equally, i.e., permuting the name of the issues results in the ranking obtained by applying the same name permutation to the previous result.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Proposition 1. If profile P is rank-unanimous on a then DIVBorda α (a, P) = 0, while not necessarily true for DIVCop α . If P is unanimous, then DIVCop α (a, P) = 0 for all a I.

Proof. If P is rank-unanimous on a, then for all b I\{a} we have that Borda(a, Pa b) Borda(a, Pb a) = 0, and thus DIVs α(a, P) = 0. This does not necessarily hold for DIVCop: consider 3 agents with the following rankings over issues I = {a, b, c, d}, forming profile P: 1= abcd, 2= cbad, and 3= dbac. Observe that for all i N that rank(b, i) = 2, hence P is rank-unanimous on b. However, DIVCop 0 (b, P) = 1

3. Finally, if P is unanimous, any notion of divisiveness will be equal to zero, as either Na b or Nb a is empty for any pair a, b I.

Profile P is fully polarised if it is split into two equallysized sub-populations with completely opposite preferences (m is even). If n is even, P is fully polarised if i= 1 for i = 1, . . . , n/2, and i= 2 for i = n/2 + 1, . . . , n, where rank(a, 1) = m rank(a, 2) for all a I. If n is odd, one of the sub-populations has one more agent than the other. Let a be the top-ranked issue in 1 (hence ranked last in 2). We show that divisiveness is maximal in such profiles: Proposition 2. If P is fully polarised and n is even, then DIVBorda α (a, P) = 1 when ℓ= 4, where a is the top-ranked issue in one of the two sub-populations. If P is fully polarised and n is odd, then DIVCop α (a, P) equals the α-factor.

Proof. If P is fully polarised and n is even, then each summand of DIVBorda α (a, P) is 1, as all agents in Na b rank a first, all in Nb a rank a last, and #(Na b)=#(Nb a). Thus, DIVBorda α (a, P)=1. If P is fully polarised and n is odd, then a is a Condorcet winner in the larger sub-population and a Condorcet loser in the other. Thus, DIVs(a, Na>b, P)=1 for each b I\{a}. As sub-populations differ by 1,

DIVCop α (a, P) = n2 1

n2 α when ℓ= 4.

In fully polarised profiles, two issues have maximal divisiveness: the top-ranked issues in 1 and 2. Moreover, in any profile, at most two issues can have maximal divisiveness. Finally, uniform profiles contain each of the m! possible rankings over the m issues, and each ranking is equally represented in the profile (note that n is even). They represent a fully noisy population of preferences. While the measure of polarisation proposed by Can et al. [2015] cannot distinguish between uniform and fully polarised profiles, we show that the ranking of divisiveness is strict in the former while in the latter all issues have the same divisiveness. The following proposition is straightforward due to the symmetry of uniform profiles: Proposition 3. If P is a uniform profile, then DIVs α(a, P) = DIVs α(a, P) for all a, b I.

For a uniform profile P, DIVBorda α (a, P) = 1 m 1 when ℓ = 4, as the average Borda score between two subpopulations Na b and Nb a differs by 1/m 1. Whereas DIVCop α (a, P) = 1 when ℓ= 4, as the divide of the two subpopulations always ensures that a always wins every majority contest in Na b and always loses in Nb a.

3 6 9 12 15 18 # issues

KT(Div Borda,Div Copeland)

KT(Div Borda,Variance)

KT(Div Copeland,Variance)

Figure 1: The average Kendall s tau correlation between each pair of divisiveness rankings using Borda and Copeland with α = 0, and the rank variance, varying the number of issues. The average is taken from 100 profiles with 100 agents generated by UM10.

3.2 Divisiveness and Rank Variance We conducted experiments on synthetic preference profiles to test whether divisiveness with α = 0 correlates with the rank-variance defined in Section 2.3. We computed Kendall s tau correlation (KT) of DIVBorda 0 and DIVCop 0 with the rank variance (cf. Section 2.3). We tested 100 profiles of rankings generated via the impartial culture (IC) and the Urn model with a correlation of 10% and 50% (named UM10 and UM50, respectively). Rankings were generated using the Pref Lib library [Mattei and Walsh, 2017, 2013]. Using the Urn model with 10% correlation as an example, we plot in Figure 1 the average Kendall s tau correlation. We observe that the three measures are correlated when profiles are on a few issues but that the values of correlation decrease significantly as we increase the number of issues, and therefore increase the possible rankings for the measures to return. The correlation between the rank variance and the divisiveness computed using Borda is higher than using Copeland. The correlation between divisiveness using Borda and divisiveness using Copeland shows a similar decreasing trend. Similar results are captured for the impartial culture scenario, but the correlation decreases even more for the case of KT(DIVBorda 0 , DIVCop 0 ) and KT(DIVCop 0 , Variance). A possible explanation of this decreasing correlation is that rank-variance only considers an issue s position in each individual ranking discarding which the rankings structures (which are ranked above or below the issue in question).

3.3 Maximally Divided Sub-Populations In addition to providing a ranking of issues based on their divisiveness, Definition 2 can also be used to identify the partition that maximally divides the population for an issue. This is a seemingly hard computational problem, as there is an

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

exponential number of sub-populations to consider, but we show that it can be solved efficiently for the Borda score. Proposition 4. For any profile P and issue a I, finding the sub-population X N that maximises DIVBorda 0 (a, X, P) can be done in polynomial time.

Proof. Consider an arbitrary preference profile P. For an arbitrary issue a I, we will use the following algorithm to find the sub-population X such that DIVBorda 0 (a, X, P) is maximal. We first order the agents with respect to their ranking of issue a. Thus, without loss of generality, we can assume that for each i [1, n 1] we have that rank(a, i) rank(a, i+1). Note that if two agents rank a at the same level, their ordering is irrelevant. We will now prove that any sub-population X that gives the maximum value of DIVBorda(a, X, P) will partition N such that for some k [1, n 1] we have that X = {1, k} and thus N\X = {k + 1, , n}. Our polynomial algorithm then tests each of the n 1 partitions defined by Xk = {1, , k} and returns the one that maximises DIVBorda 0 (a, Xk, P). Clearly, in each of these partitions Xk, calculating DIVBorda 0 (a, Xk, P) can be done in polynomial time. We now prove that any X that maximises DIVBorda 0 (a, X, P) is of the form Xk = {1, , k} for some k. To do so, we consider some X such that there exists some i X yet i z / X, for z [1, i 1]. We need to show that the set X = (X\{i}) {i z} is more divisive than X, thus DIVBorda 0 (a, X , P) DIVBorda 0 (a, X, P). It is clear that Borda(a, PX ) Borda(a, PX ) due to our assumption on the ordering of the agents in P in decreasing order of rank of a. For similar reasons, we have that Borda(a, PN\X ) Borda(a, PN\X ). Therefore, it must be the case that DIVBorda 0 (a, X , P) DIVBorda 0 (a, X, P). Thus, we can transform any X that maximises divisiveness into a sub-population of the form Xk by performing a finite number of swaps, as described above.

Determining the complexity of finding maximally divided sub-populations under DIVCop 0 does not seem trivial, and we leave it as an open problem.

4 Divisiveness Control Manipulation and control have been widely studied for rank aggregation procedures. Manipulation is when an individual misrepresents their reported ranking to improve the score of their favourite candidate. A classical result showed that manipulation can be performed in polynomial time for the Borda score [Bartholdi et al., 1989]. Instead, control is when an external agent aims at altering the score of a designated candidate by performing actions such as removing agents or candidates from the profile of ranking. To give an example, preventing a candidate from being the Copeland winner by adding new rankings was shown to be a computationally hard problem. For an introduction to the computational complexity of these problems, we refer to the survey from Faliszewski and Rothe [2016]. In this section, we focus on two approaches to control the measure of divisiveness: (i) by removing pairwise comparisons from the agents rankings and

Figure 2: The average Kendall s tau correlation between the divisiveness ranking under DIVBorda 0 computed on the full ranking with respect to incomplete rankings. The horizontal axis shows the percentage of pairwise comparisons of the incomplete profile with respect to the complete one. The experiment is run on 100 preference profiles drawn from UM10. The different markers on the lines represent different numbers of issues in {4, 6, 8, 10, 14, 18}

(ii) by adding new agents (which could, e.g., be performed by bots on any platform that crowdsources individual preferences). This section focuses on the less studied divisiveness measure with α=0 and hence we omit α from DIVs α.

4.1 Removing Pairwise Comparisons This section studies the disruption of the divisiveness measure by the deletion of pairwise comparisons from the rankings. This can be thought of as sabotage, as the control actions here do not have a clear goal, e.g., making a single issue the most divisive one. Instead, the aim of this control problem is to disrupt the divisiveness ranking such that it no longer resembles the ranking under complete preferences. To do so, we evaluate through simulations what percentage of pairwise comparisons of the agents full rankings are required to be able to compute the divisiveness measure accurately. As we are removing parts of the rankings given by the agents, we need to compute divisiveness on incomplete rankings as in the original definition by Navarrete et al. [2022]. When s = Cop, we see that the definition of divisiveness is well-defined on incomplete rankings. However, on incomplete rankings, we use the win rate instead of Borda when calculating the divisiveness, noting that they are equivalent on complete rankings. We define the win rate of an issue a to be P b I\{a} #(Na>b) #(Na b Nb a) (m 1). We generated 100 profiles for each of the three preference generation methods IC, UM10, and UM50, varying the number of issues m [3, 18]. We compared the average Kendall s tau correlation between the divisiveness ranking computed on the full rankings and the adapted measure of divisive-

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

ness computed on sub-profiles containing X% of the pairwise comparisons of the complete one (X [10, 100] increasing by increments of 10). Here, pairwise comparisons are deleted from the profile at random. The main message of this simulation is that disrupting divisiveness by deleting pairwise comparisons is easy. Figure 2 focuses on the case when the average KT is taken over 100 profiles with 100 agents created via the UM10 method. It shows that if there are sufficiently many issues (say more than 10), then deleting between 10 and 20% of the pairwise comparisons in the profile is sufficient to significantly decrease the accuracy of divisiveness (the correlation between complete and incomplete divisiveness is below 0.5). We also observe an inversion of the curves when the number of issues exceeds 6, tending towards an exponential shape. Our findings imply that with a large number of issues and under the assumption of moderately correlated preferences, the almosttotality of the pairwise comparisons needs to be elicited from agents to obtain an accurate measure of divisiveness.

4.2 Control by Adding Rankings The next form of control we study is the addition of fake rankings by an external agent. Modelling this type of control is particularly realistic when the divisiveness measures are used in online forums, where attacks by bots are commonplace (such as in the experimental setting of Navarrete et al. [2022]). Similar problems were previously studied in the literature, such as Sybil attacks in online elections [Meir et al., 2022]. We start by presenting an example in which a single agent is able to alter the divisiveness ranking.

Example 3. Consider four agents and four issues I = {a, b, c, d}. Consider that three agents have submitted their preferences, one agent with 1, and two with 2. The fourth agent has the truthful preference of 3: 1 (1 agent) bcad 2 (2 agents) abcd 3 (1 agent) acbd

If the fourth agent submits their truthful preference, we have that: DIVBorda(a, P) = 12/27, DIVBorda(b, P) = 7/27, DIVBorda(c, P) = 8/27, and DIVBorda(d, P) = 0. Thus, a is currently the most divisive issue. As all agents agree that d is the worst of all the issues, it is the least divisive issue. If the agent with truthful preference 3 wants to manipulate the divisiveness measure in order to make the issue b more divisive, then they can submit a preference 3= cadb giving profile P = ( 1, (2, 2), 3). In doing so, the measure of divisiveness changes as such: DIVBorda(a, P ) = 19/54, DIVBorda(b, P ) = 38/54, DIVBorda(c, P ) = 19/54, and DIVBorda(d, P ) = 6/54. Thus, by submitting 3, the agent succeeded in making b the most divisive issue.

Example 3 shows that one agent can manipulate the divisiveness measure. We now show that the problem of control by adding rankings can be solved easily by showing a simple heuristic, which we call INJECTs. INJECTs takes as input a profile P and an issue a which it aims to make the most divisive by adding new agents to the profile. It first computes the ranking over issues defined by

s(x, P), which we denote by s. This is used to create the two rankings which will be added to the profile to increase the divisiveness of a, namely odd and even. The former modifies s by putting issue a first and leaving the rest of the ranking unchanged. The latter modifies s symmetrically by putting a in the last position and leaving the remaining part of the order unchanged. In this way, odd and even resemble the ranking of agreements computed using s, with the only difference being the position of a that alternates between first and last. INJECTs then alternates between adding odd and even to profile P until the issue a is the most divisive. We show that INJECTs always terminates and succeeds in making the target issue the most divisive.

Proposition 5. INJECTBorda always terminates for α = 0.

Proof. Let a be the target issue. If a is already the most divisive issue in P then INJECTBorda terminates immediately. Else, we first prove that DIVBorda(a, P ) > DIVBorda(a, P) for any profile P obtained by using INJECTBorda on a profile P. Take an arbitrary profile P, issue a I, and k such that P = (P, (k, odd), (k, even)), where N are the agents in P . Take an arbitrary b I\{a}, we have that DIVBorda(a, N a b, P ) > DIVBorda(a, Na b, P) as Borda(a, P a b) Borda(a, Pa b) and Borda(a, Pb a) Borda(a, P b a), with at least one of the two inequalities being strict. To see this, observe that all injected agents rank a the highest in P a b and the lowest in P b a (and a is not the most divisive issue). Thus, we proved that DIVBorda(a, P ) tends to 1 as k increases. To conclude, note that the rank of any issue b I\{a} in the injected subprofile ((k, even),(k, odd)) varies only by one position. Thus, with k large enough the divisiveness of any issue b = a cannot tend to 1.

Proposition 6. INJECTCop always terminates in polynomial time for α = 0.

Proof. Let k = 2n + 2 and a be the target issue, where n is the number of voters in P. By definition, DIVCop 0 (a, P ) = 1/m 1 P b I\{a} |Cop(a, P a b) Cop(a, P a b)|. As k is sufficiently large, for all b I\{a} we have that a is a Condorcet winner in P a b, since n + 1 copies of odd were added with a as the top issue. Symmetrically, a is a Condorcet loser in P b a. Thus, we have that Cop(a, PNa b) = 1 and Cop(a, PNb a) = 0, which in turn implies that DIVCop 0 (a, P ) = 1. By the uniqueness of a Condorcet winner, we have that no other issue b = a can have DIVCop 0 (b, P ) = 1, concluding the proof.

The previous result shows that INJECTs can manipulate the divisiveness ranking. However, it does not provide a bound on how many agents INJECTBorda are required and only provides a large bound for INJECTCop, namely k = 2n + 2. To complement this, we conducted simulations to estimate how many new agents INJECTs needs to alter the divisiveness ranking. For each m [2, 11] and each of three profile generation methods (IC, UM10, UM50), we considered 100 profiles to test how many new agents INJECTs required to make

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

0% 20% 40% 60% 80% New agents (%)

Issue ranking

Borda, 8 issues, IC

Figure 3: Percentage of new agents added by INJECTBorda to make the least divisive issue the most divisive. The average divisiveness of the other issues is also plotted in grey. Averages are computed over 100 IC profiles of 100 agents and 8 issues.

the target issue the most divisive. Figure 3 focuses on IC profiles with 8 issues. It shows the divisiveness rankings of the 8 issues in the initial profile (at 0%) and their evolution when INJECTBorda inserts additional rankings to make the least divisive issue the most divisive (the highlighted line at the 8th position). In particular, by adding around 35% new agents we can make the least divisive issue the most via our simple algorithm. In crowdsourcing applications with wide participation this percentage implies that too many additional agents might need to be injected without being noticed. Yet, we recall that INJECTs is a simple heuristic, and this percentage could be lower with a more efficient procedure. Furthermore, we see that the average divisiveness ranking of the other issues converges to the middle of the ranking. We obtained similar results by varying the number of issues and the profile generation methods. We also tested how many additional agents INJECTBorda required to reach easier targets, such as making either the second most divisive issue or an issue in the middle of the divisiveness ranking the most divisive issue. Figure 4 presents our findings for s = Borda and m = 8, computed on 100 profiles generated using either IC or UM50. Clearly, if the task of control is harder, INJECTBorda needs additional agents to meet its target. More importantly, if we compare the performance of INJECTBorda on different preference generation methods, we see that more correlated profiles (using UM50 in our case) are harder to control no matter the target issue. Given the results, we see that INJECTs can be an effective way of manipulating, but it simulates a static scenario. We also note that this way of manipulating requires very little information about the original profile, i.e., the controlling agent just need to know the current ranking of agreement given by

0% 25% 50% 75% New agents (%)

Issue ranking

8 issues, Borda

Figure 4: Percentage of agents added by INJECTBorda with 8 issues, to make the 2nd, 4th or 8th most divisive issue the most. The average is taken over 100 profiles for 100 agents generated using IC and UM50 (represented by a solid or dashed line, respectively).

the scoring s. Furthermore, our results show that INJECTs can be used just to increase an issue s rank in the divisiveness ranking, rather than insisting that it becomes the most divisive.

5 Conclusions and Future Work This paper extends the notion of divisiveness given by Navarrete et al. [2022] to a family of measures and applies them to complete rankings over issues. We ground these measures by highlighting their behaviour at limit cases and comparing them to other notions of disagreement and polarisation. We also point out how we can find a sub-population for which an issue is most divisive in polynomial time when considering the Borda score, yet, no such algorithm was found for the Copeland score. The main contribution of this paper is the study of the robustness of the divisiveness measures to external control. We showed via simulations that by randomly removing pairwise comparisons from the rankings, the correlation between the divisiveness ranking of the full vs partial rankings can drop significantly, especially when there are many issues. Furthermore, we show that a simple algorithm can affect the divisiveness ranking by inserting (a possibly large number of) controlled fake rankings. This paper opens many directions for future work. First, how can our divisiveness measures be modified to be more robust to external control. Second, our divisiveness measures can be used to compare how divisive or polarised is a given population (instead of focusing on comparisons of single issues). Finally, following in the social choice theory tradition, we will explore axiomatic characterisations of divisiveness.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Acknowledgments Rachael Colley and Umberto Grandi acknowledge the support of the ANR JCJC project SCONE (ANR 18-CE23-000901). This work was conducted while Umberto Grandi was on leave at CNRS. C esar Hidalgo, Mariana Macedo, and Carlos Navarrete were supported by the Artificial and Natural Intelligence Toulouse Institute (ANITI) - Institut 3i A: ANR-19PI3A-0004.

References Jorge Alcalde-Unzu and Marc Vorsatz. The measurement of consensus: an axiomatic analysis. FEDEA (Working Paper), 2008. Jorge Alcalde-Unzu and Marc Vorsatz. Measuring the cohesiveness of preferences: an axiomatic analysis. Social Choice and Welfare, 41(4):965 988, 2013. Jorge Alcalde-Unzu and Marc Vorsatz. Do we agree? measuring the cohesiveness of preferences. Theory and Decision, 80(2):313 339, 2016. Jos e Carlos Rodr ıguez Alcantud, R de Andr es Calle, and JM Casc on. Pairwise dichotomous cohesiveness measures. Group Decision and Negotiation, 24(5):833 854, 2015. Elliott Ash, Massimo Morelli, and Richard Van Weelden. Elections and divisiveness: Theory and evidence. The Journal of Politics, 79(4):1268 1285, 2017. John J Bartholdi, Craig A Tovey, and Michael A Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227 241, 1989. Rob Bosch. Characterizations of Voting Rules and Consensus Measures. Ph D thesis, Tilburg University, 2005. Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016. Burak Can, Ali Ihsan Ozkes, and Ton Storcken. Measuring polarization in preferences. Mathematical Social Sciences, 78:76 79, 2015. Jean-Yves Duclos, Joan Esteban, and Debraj Ray. Polarization: concepts, measurement, estimation. Econometrica, 72(6):1737 1772, 2004. Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web (WWW), 2001. Joan-Maria Esteban and Debraj Ray. On the measurement of polarization. Econometrica: Journal of the Econometric Society, pages 819 851, 1994. Piotr Faliszewski and J org Rothe. Control and bribery in voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice. Cambridge University Press, 2016.

Jason Gaitonde, Jon Kleinberg, and Eva Tardos. Adversarial perturbations of opinion dynamics in networks. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), 2020.

Jos e Luis Garc ıa-Lapresta and David P erez-Rom an. Consensus measures generated by weighted Kemeny distances on weak orders. In Proceedings of the 10th International Conference on Intelligent Systems Design and Applications (ISDA), 2010. William V. Gehrlein and Dominique Lepelley. Voting paradoxes and group coherence: the Condorcet efficiency of voting rules. Springer Science & Business Media, 2010. Hanna Hałaburda. Unravelling in two-sided matching markets and similarity of preferences. Games and Economic Behavior, 69(2):365 393, 2010. Vahid Hashemi and Ulle Endriss. Measuring diversity of preferences in a group. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), 2014. Alexander Karpov. Preference diversity orderings. Group Decision and Negotiation, 26(4):753 774, 2017. Raivo Kolde, Sven Laur, Priit Adler, and Jaak Vilo. Robust rank aggregation for gene list integration and metaanalysis. Bioinformatics, 28(4):573 580, 2012. Anna Korba, Stephan Cl emenc on, and Eric Sibony. A learning theory of ranking aggregation. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017. Nicholas Mattei and Toby Walsh. Preflib: A library of preference data HTTP://PREFLIB.ORG. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT), 2013. Nicholas Mattei and Toby Walsh. A PREFLIB.ORG retrospective: Lessons learned and new directions. Trends in Computational Social Choice. AI Access Foundation, pages 289 309, 2017. Reshef Meir, Nimrod Talmon, Gal Shahaf, and Ehud Shapiro. Sybil-resilient social choice with low voter turnout. In Proceedings of the 19th European Conference on Multi-Agent Systems (EUMAS), 2022. Cameron Musco, Christopher Musco, and Charalampos E Tsourakakis. Minimizing polarization and disagreement in social networks. In Proceedings of the 2018 world wide web conference (WWW), 2018. Carlos Navarrete, Nicole Ferrada, Mariana Macedo, Rachael Colley, Jingling Zhang, Umberto Grandi, Jerome Lang, and C esar A Hidalgo. Understanding political agreements and disagreements: Evidence from the 2022 French presidential election. ar Xiv preprint ar Xiv:2211.04577, 2022. Klaus Nehring and Clemens Puppe. A theory of diversity. Econometrica, 70(3):1155 1198, 2002. Jonathan Stray. Designing recommender systems to depolarize. First Monday, 27(5), 2022. Junlin Wu, Andrew Estornell, Lecheng Kong, and Yevgeniy Vorobeychik. Manipulating elections by changing voter perceptions. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022. Zhengui Xue, Zhiwei Lin, Hui Wang, and Sally Mc Clean. Quantifying consensus of rankings based on q-support patterns. Information Sciences, 518:396 412, 2020.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)