Measuring and Controlling Divisiveness in Rank Aggregation

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 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/CenterForCollectiveLearning/ divisiveness-theoretical-IJCAI2023.

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

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; AlcaldeUnzu 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) = ∑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)} m-1 .

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:

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:

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

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.

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

The most divisive issue for DIV Borda 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 DIV Borda 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) = 1n ∑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:

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:

The rank-variance and the divisiveness using Borda and α = 0 for each issue is the following:

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 terminology 2 ) 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.

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

Proposition 1. If profile P is rank-unanimous on a then DIV Borda α (a,P) = 0, while not necessarily true for DIV Cop α . If P is unanimous, then DIV Cop α (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 DIV Cop : 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, DIV Cop 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 DIV Borda α (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 DIV Cop α (a,P) equals the α-factor.

Proof. If P is fully polarised and n is even, then each summand of DIV Borda α (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, DIV Borda α (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, DIV Cop α (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, DIV Borda α (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 DIV Cop α (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.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 DIV Borda 0 and DIV Cop 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 PrefLib 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 (DIV Borda 0 , DIV Cop 0 ) and KT(DIV Cop 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 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 DIV Borda 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 DIV Borda 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 DIV Borda (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 DIV Borda 0 (a,Xk,P). Clearly, in each of these partitions Xk, calculating DIV Borda 0 (a, Xk , P) can be done in polynomial time.

We now prove that any X that maximises DIV Borda 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 DIV Borda 0 (a,X ′ ,P) ≥ DIV Borda 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 DIV Borda 0 (a,X ′ ,P) ≥ DIV Borda 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 DIV Cop 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

(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 #(Na>b)

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 divisiveness 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: DIV Borda (a,P) = 12/27, DIV Borda (b,P) = 7/27, DIV Borda (c,P) = 8/27, and DIV Borda (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: DIV Borda (a,P ′ ) = 19/54, DIV Borda (b,P ′ ) = 38/54, DIV Borda (c,P ′ ) = 19/54, and DIV Borda (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 DIV Borda (a, P ′ ) > DIV Borda (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 DIV Borda (a,N ′a≻b ,P ′ ) > DIV Borda (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 DIV Borda (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, DIV Cop 0 (a,P ′ ) = 1/m-1 ∑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 DIV Cop 0 (a,P ′ ) = 1. By the uniqueness of a Condorcet winner, we have that no other issue b ̸= a can have DIV Cop 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 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 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 FutureWork

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.

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 3iA: ANR-19PI3A-0004.