| paper | Measuring and Controlling Divisiveness in Rank Aggregation |
| authors | Rachael Colley, Umberto Grandi, César Hidalgo, Mariana Macedo, Carlos Navarrete |
| venue | IJCAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 4
statement extracted from the paper’s text layer
Given \(m\ge2\) issues \(I\), ranking types \(\mathcal T\subseteq L(I)\), rational masses \(\mu_t\ge0\) summing to \(1\), and an issue \(a\), choose \(\nu\) with \(0\le\nu_t\le\mu_t\) to maximize \(D(\nu)\), where \(D(\nu)=0\) if \(\nu=0\) or \(\nu=\mu\), and otherwise \(D(\nu)=|B(a,\nu)-B(a,\mu-\nu)|\), with \(B(a,z)=\frac{\sum_t z_t(m-\operatorname{rank}_t(a))}{(m-1)\sum_t z_t}\). Return an optimal mass vector \(\nu\) and the optimum value.
A weighted anonymous rank profile: \(\mathcal T\) consists of complete ranking types, \(\mu\) gives their population masses, and \(\nu\) selects a subpopulation mass whose normalized Borda disagreement with its complement is maximized.
The mirror's optimizer-selected subpopulation may lack an independent social interpretation, and the Borda objective collapses to \(m\) rank classes rather than exploiting the full type distribution.
fatal: False
The mirror directly covers Proposition 4 and can extend to the balanced two-template injection in Proposition 6; it leaves the axiomatic propositions, incomplete-preference experiments, Proposition 5, the Copeland maximization open problem, and unrestricted control untouched.
The strongest positive case is a genuine, author-recognisable high-multiplicity mirror, with Proposition 4 as the lead. The paper is unusually hospitable to this reading: it explicitly represents profiles as weighted anonymous profiles, and its motivating applications include crowdsourcing, online forums, and bot-generated rankings.
The regime is a large survey or forum population in which users submit complete rankings from a relatively small collection of recurring preference templates. Let \(I\) be the \(m\) issues, let \(\mathcal T\subseteq L(I)\) be the listed ranking types, and let \(\mu_t\in\mathbb Q_{\ge 0}\) be the fraction of respondents of type \(t\), with \(\sum_t\mu_t=1\). Here \(\tau=|\mathcal T|\) is moderate while the number of respondents is much larger. A type is exactly a complete ranking, which is all the paper uses to compute divisiveness. Clearing denominators in \(\mu\) recovers a finite profile of repeated ranking clones.
My lead problem is Continuous Maximally Divided Subpopulation\({}_\infty^{\mathrm{Borda}}\), mirroring Proposition 4, proved in this paper. Given \((I,\mathcal T,\mu)\) and an issue \(a\), choose a subpopulation mass vector \(\nu\) satisfying \(0\le\nu_t\le\mu_t\). The complement has mass \(\mu-\nu\). Define the normalized Borda score of \(a\) on a nonempty mass vector \(\nu\) by \(B(a,\nu)=\frac{\sum_t\nu_t(m-\operatorname{rank}_t(a))}{(m-1)\sum_t\nu_t}\), and set \(B(a,0)=0\). The task is to return \(\nu\) maximizing
\[ \left|B(a,\nu)-B(a,\mu-\nu)\right|, \]
with value \(0\) when \(\nu=0\) or \(\nu=\mu\). This is precisely the continuous version of finding the subpopulation \(X\) maximizing \(\mathrm{DIV}^{\mathrm{Borda}}_0(a,X,P)\).
I expect this problem to be in Class A. Sort the ranking types by the position of \(a\), and inspect the prefix partitions induced by the cumulative type masses, allowing a boundary type to be split if necessary. Proposition 4’s exchange argument survives unchanged: a maximizer can be rearranged into a threshold population consisting of those who rank \(a\) highest or lowest. The continuous algorithm therefore runs in time polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\). Rational solutions have an exact finite interpretation after clearing denominators.
This is not merely a cosmetic replacement of \(n\) by \(1\). In the authors’ setting, the actual object of interest is disagreement between population blocs, and mass is the natural quantity: “the \(23\%\) of respondents who rank \(a\) above \(b\)” is more meaningful than an arbitrary named subset of respondents. The continuous problem preserves complete rankings, the Borda score, the pairwise-defined subpopulation, the absolute disagreement objective, and the maximally-divided-subpopulation question.
A second, narrower anchor is Proposition 6, proved here: “\(\mathrm{INJECT}^{\mathrm{Cop}}\) always terminates in polynomial time for \(\alpha=0\).” Its continuous counterpart is Continuous Copeland-INJECT\({}_\infty\). Given \((I,\mathcal T,\mu)\) and target issue \(a\), compute the Copeland ranking of the base population, using a fixed tie-breaking order. Let \(\rho^+\) be the ranking obtained by putting \(a\) first and leaving the other issues in that order, and let \(\rho^-\) put \(a\) last while preserving the other relative positions. The control variable is \(q\ge0\), the mass of each injected type. The resulting population is
\[ \pi(q)=\mu+q\,e_{\rho^+}+q\,e_{\rho^-}. \]
For any population \(\pi\), define \(\pi^{a\succ b}\) as the mass of types ranking \(a\) above \(b\), and define
\[ D_s(a,\pi)=\frac{1}{m-1}\sum_{b\ne a} \left|s(a,\pi^{a\succ b})-s(a,\pi^{b\succ a})\right|. \]
The task is to find a finite rational \(q\) such that \(a\) is a most-divisive issue under \(D_{\mathrm{Cop}}\), returning \(q\) and \(\pi(q)\) as the certificate. This preserves the proposition’s termination objective; it does not pretend that the paper solved minimum-mass arbitrary control.
This restricted continuous problem is tractable. Since the initial population has mass \(1\), taking \(q=2\) gives the injected “put \(a\) first” and “put \(a\) last” types more mass than the entire original population. Thus, in every \(a\succ b\) subpopulation, \(a\) becomes a Copeland Condorcet winner, and in every \(b\succ a\) subpopulation it becomes a Condorcet loser, exactly as in Proposition 6’s proof. Computing the two types, the Copeland scores, and the final divisiveness ranking is polynomial in \(m\), \(\tau\), and the input bit length. A natural strengthening asks for the least balanced \(q\); along this one-dimensional family, all Copeland changes occur at affine majority-tie breakpoints, so that version also appears polynomial.
The regime is especially plausible for this anchor because the paper itself proposes fake rankings by bots as a realistic attack in online forums. A large population of genuine users may have many repeated ranking types, while the controller injects mass using only two repeated bot templates. The continuous action is not a change from preferences to fractional preferences: rankings remain complete and indivisible; only the number of agents submitting each ranking becomes mass.
I do not count Proposition 5 separately as a third anchor. Its Borda-INJECT result gives an analogous continuous feasibility problem, but it proves termination without the polynomial-time bound established for Copeland, so it adds little beyond the two stronger anchors.
The scope is deliberately limited. These mirrors cover Proposition 4 and Proposition 6, with Proposition 5 as supporting evidence. They do not claim to cover the incomplete-preference experiments, the rank-variance comparisons, Propositions 1–3, the open Copeland maximally-divided-subpopulation question, or unrestricted optimal control by arbitrary added rankings.
The weakest point is that Proposition 4 was already polynomial-time in the finite model, so its continuous mirror demonstrates a clean Class A object more than a dramatic new tractability phenomenon. The Copeland mirror is also deliberately restricted to the paper’s prescribed injection family; minimum-mass control over all \(m!\) possible ranking types remains a separate problem and could be continuum-specifically hard. But that limitation does not undermine the core case: the paper’s own weighted-profile representation, its repeated ranking types, and its bot-injection application make these two mass problems faithful continuous-population formulations rather than invented mean-field re-modelings.
The strongest negative case is that both anchors are formally faithful but too thin to justify a continuization programme.
Proposition 4’s mirror is valid: rankings can be types, masses can replace multiplicities, and arbitrary subpopulations can be represented by \(0\leq\nu_t\leq\mu_t\). But its continuous aspect contributes almost nothing. For fixed issue \(a\), Borda depends only on \(\operatorname{rank}_t(a)\), not on the rest of the ranking. If
\[ w_r=\sum_{t:\operatorname{rank}_t(a)=r}\mu_t, \]
then every candidate \(\nu\) can be rearranged into a threshold population over these rank classes. The problem therefore reduces to checking at most \(m-1\) cumulative rank masses, with at most one boundary class split. This is an order-statistic calculation, not a problem whose structure emerges from a continuous society. The same compression works for named voters and for arbitrary integer multiplicities; the full type distribution is irrelevant.
That does not make the question ill-posed, and “the answer is easy” is not by itself an objection under the programme’s rules. It does mean that this anchor is a weak contribution to continuous computational social choice: it does not expose a meaningful population-level optimization phenomenon or an exponential-type pricing issue. If the intended subpopulation is instead a genuine bloc—say, rural voters or a political faction—then that bloc must be included as part of the type and the selection problem must constrain \(\nu\) accordingly. That would be a different problem from Proposition 4. With unconstrained \(\nu\), the “subpopulation” is simply an optimizer-created cut through ranking classes, not a socially meaningful population.
Proposition 6 is weaker still. The proposed continuous task is to find any \(q\) for which
\[ \pi(q)=\mu+q e_{\rho^+}+q e_{\rho^-} \]
makes \(a\) most divisive. After normalising the population, \(q=2\) is a universal certificate, independent of the profile. Thus “find a finite \(q\)” is not really a control problem with an instance-dependent computational question; it is the continuous restatement of a fixed construction. The continuous variable has no substantive role.
One could repair this by asking for the minimum \(q\), but that is no longer the result proved in Proposition 6. Along the prescribed two-ranking path, Copeland outcomes change only at finitely many affine majority breakpoints, so the strengthened problem is likely just a small breakpoint enumeration. Alternatively, one could allow arbitrary injected ranking types and minimise injected mass. That could be an interesting control problem, but it is a new problem, not a mirror of the proposition; its difficulty would come from choosing rankings, not from continuizing the population.
The usual decisive objections do not work here. The paper explicitly uses weighted anonymous profiles, so high multiplicity is a sensible regime. Rankings contain all information used by the measures, so identity is not essential. The bot-injection application supplies a plausible repeated-template scenario. Nor does existing high-multiplicity work count against the proposal.
Consequently, the honest negative case is limited: Proposition 4 is a very thin mirror, and Proposition 6’s stated continuous task is nearly vacuous. But that is not enough to sustain the universal claim that no worthwhile mirror exists. In particular, Proposition 4 is an author-recognisable high-multiplicity computational problem, and a minimum-mass or unrestricted injection variant could make the control direction substantially stronger. The negative case should therefore be treated as weak rather than as a reason to reject the paper.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.