Efficient Elicitation of Collective Disagreements

# Efficient Elicitation of Collective Disagreements
Source: [https://arxiv.org/html/2605.19521](https://arxiv.org/html/2605.19521)
Mohamed Ouaguenouni1Felipe Garrido\-Lucero1Umberto Grandi1 César Hidalgo2,3,4Magdalena Tydrichova5

1\. IRIT, Université Toulouse Capitole, Toulouse, France 2\. Center for Collective Learning, IAST, Toulouse School of Economics, Toulouse, France 3\. Center for Collective Learning, CIAS, Corvinus University of Budapest, Budapest, Hungary 4\. AMBS, University of Manchester, Manchester, UK 5\. Centrale Supélec, Paris Saclay, France

###### Abstract

We analyze the structure of the disagreement among a population of voters over a set of alternatives\. Surveys typically ask either for pairwise comparisons, simple and intuitive for participants, or full rankings over alternatives, eliciting the entire voters’ preferences\. Building on the observation that pairwise comparisons cannot distinguish structural disagreement from noise, we propose a stratified framework to identify the minimal aggregated preference information needed to compute a number of disagreement measures from the literature\. Specifically, we introduce the plurality matrix, a generalization of pairwise comparisons that records, for every subsetSSof alternatives, the probability that eacha∈Sa\\in Sranks first inSS\. We define the level of a disagreement measure as the smallest subset size needed to express it, showing that many existing notions, including rank\-variance and divisiveness, sit at level33, proving that pairwise comparisons are not enough\. In addition, we demonstrate the interest of going beyond level33both theoretically and experimentally\. To make these results actionable, we design two elicitation protocols to estimate the plurality matrix, exploring the trade\-off between the number of required participants and the cognitive load requested to each of them\.

## 1Introduction

Social choice theory seeks to model and improve how a society makes collective decisions\. A large part of the literature addressed this question by proposing preference aggregation rules, which aim to select the most preferred alternative\(s\) from a set of options given the agents’ declared preferences, by characterizing them axiomatically, and by designing efficient elicitation protocols for their computation\(Arrowet al\.,[2010](https://arxiv.org/html/2605.19521#bib.bib51); Brandtet al\.,[2016b](https://arxiv.org/html/2605.19521#bib.bib52); Fürnkranz and Hüllermeier,[2011](https://arxiv.org/html/2605.19521#bib.bib55)\)\. However, consensus is only half of the story: society must often confront and resolve disagreements before reaching agreement\(Waldron,[1999](https://arxiv.org/html/2605.19521#bib.bib29)\)\. This is well illustrated by the deliberative platform Pol\.is\(Smallet al\.,[2021](https://arxiv.org/html/2605.19521#bib.bib40),[2023](https://arxiv.org/html/2605.19521#bib.bib41)\), where proposals with the narrowest voting margins are highlighted alongside consensual ones\. Despite growing interest, relatively little attention has been devoted to disagreements in the \(computational\) social choice literature\. Intuitively, an alternative is divisive when a group of individuals favors it while others oppose it\. Still, a canonical definition has not yet been established: existing approaches rely on polarization measures\(Esteban and Ray,[1994](https://arxiv.org/html/2605.19521#bib.bib35)\), the variance of an alternative’s ranking across users\(Gaitondeet al\.,[2020](https://arxiv.org/html/2605.19521#bib.bib25); Muscoet al\.,[2018](https://arxiv.org/html/2605.19521#bib.bib26)\), or relative rankings to identify population factions\(Navarreteet al\.,[2024](https://arxiv.org/html/2605.19521#bib.bib62)\)\.

Beyond the choice of aggregation rules, an equally important aspect of collective decision\-making lies in how preferences are elicited\. A substantial body of work has focused on designing efficient elicitation protocols, aiming to reduce cognitive and communication burdens while preserving enough information for accurate decision\-making\(Conitzer and Sandholm,[2005](https://arxiv.org/html/2605.19521#bib.bib72); Procaccia,[2009](https://arxiv.org/html/2605.19521#bib.bib71)\)\. A particularly simple and widely used elicitation primitive is that ofpairwise comparisons\(Thurstone,[1927](https://arxiv.org/html/2605.19521#bib.bib54)\), where agents are asked to choose between two alternatives\. However, relying only on pairwise comparisons may fail to reveal important features of collective preferences, in particular those related to disagreement and polarization, as illustrated in the following example:

Pairwise comparisons are not enough to capture collective disagreement\.Consider two populations ranking three alternativesa,b,ca,b,c\. In Population 1, all six possible rankings appear equally often\. In Population 2, voters are split into two opposing groups: half rankaafirst andcclast, while the other half do the opposite\. From a pairwise comparison perspective, these two populations are identical: for any pair of alternatives, each is equally likely to be ranked above the other\. However, the underlying structures of disagreement are very different\. In Population 1, the position of every alternative is spread uniformly over all three ranks, while Population 2 is split with alternativesaaandccbeing ranked equally either first or last\.

Contributions\.Building on the previous observation, we introduce a novel preference representation that encodes, for each subset of alternatives, the likelihood that each member of the subset is its top\-ranked alternative\. Leveraging this representation, we study the minimal information required to compute several well\-known disagreement measures from the literature and design elicitation protocols suited to different settings\. Our main contributions are the followings:

- •We introduce theplurality matrix, which, for each subset of alternativesSSand eacha∈Sa\\in S, records the probability thataais ranked first withinSS\. The rows are ordered by increasing size ofSS, defining differentdegrees, with pairwise comparisons corresponding to degree22\.
- •We show that computing theagreement indexFaliszewskiet al\.\([2023](https://arxiv.org/html/2605.19521#bib.bib16)\), therank varianceKendall and Smith \([1939](https://arxiv.org/html/2605.19521#bib.bib49)\), and the divisiveness measureNavarreteet al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib62)\)requires information of degrees22,33, and33, respectively, demonstrating that some disagreement measures inherently require more information than pairwise comparisons\.
- •We prove that, for any degreekk, there exist instances with identical information up to degreekkbut differing at degreek\+1k\+1, showing that the hierarchy of degrees is strict\. Moreover, we construct, for every degreekk, a disagreement measure of exactly that degree\.
- •We show that under single\-peaked preferences or the Plackett–Luce model, the hierarchy collapses to degree22\.
- •We propose two elicitation protocols and analyze the trade\-off they induce between per\-voter cognitive load and population size\.

Related work\. The related literature spans three complementary directions: measuring disagreement in social choice, enhancing elicitation beyond pairwise comparisons, and designing cost\-efficient elicitation protocols\. First, a number of works in social choice have studied how to define measures orthogonal to agreement\. Existing approaches typically capture either the diversity of voters’ preferences\(Ammann and Puppe,[2025](https://arxiv.org/html/2605.19521#bib.bib34); Faliszewskiet al\.,[2026](https://arxiv.org/html/2605.19521#bib.bib28); Hashemi and Endriss,[2014](https://arxiv.org/html/2605.19521#bib.bib19); Karpov,[2017](https://arxiv.org/html/2605.19521#bib.bib15)\)or polarization\(Canet al\.,[2015](https://arxiv.org/html/2605.19521#bib.bib32); Faliszewskiet al\.,[2023](https://arxiv.org/html/2605.19521#bib.bib16)\)\. These notions are generally defined at the level of full preference profiles and often rely on complete rankings\. Closer to our perspective are measures defined at the level of alternatives, such as the divisiveness measure of Navarrete et al\.Colleyet al\.\([2023a](https://arxiv.org/html/2605.19521#bib.bib60)\); Navarreteet al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib62)\), and the axiomatic analysis of conflicting pairs by Delemazure et al\.Delemazureet al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib18)\)\. Second, several works consider richer query models than pairwise comparisons for preference elicitation and are closely related to our framework\. In particular, subset\-wise queries, where a set of alternatives is presented and the best one is returned, have been studied in learning and ranking settingsSaha and Gopalan \([2019](https://arxiv.org/html/2605.19521#bib.bib64)\)\. Related models include top\-kkqueries, which extract more information per interactionAyadiet al\.\([2022](https://arxiv.org/html/2605.19521#bib.bib36)\); Chenet al\.\([2018](https://arxiv.org/html/2605.19521#bib.bib65)\), as well as recent work on eliciting full rankings over queried subsets of alternativesHalpernet al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib23)\)\. Third, a complementary line of work studies elicitation protocols under cognitive constraints and relates to our goal of designing viable alternatives to full ranking elicitation\. In voting, the recent work of TerzopoulouTerzopoulou \([2023](https://arxiv.org/html/2605.19521#bib.bib37)\)introduces the notion of voters’ energy in reporting preferences, capturing the limitation on the number of alternatives that can be ranked by each voter, and studies the resulting loss in social welfare for plurality and Borda rules\. More broadly, behavioral decision theory highlights the impact of cognitive load and task complexity on response qualityGriffinet al\.\([2005](https://arxiv.org/html/2605.19521#bib.bib74)\), motivating the design of hybrid or adaptive elicitation formats that balance informational richness with practical usabilityBrams and Sanver \([2009](https://arxiv.org/html/2605.19521#bib.bib75)\); Dery \([2024](https://arxiv.org/html/2605.19521#bib.bib76)\)\.

## 2The Model

This section is devoted to introducing a probabilistic model of agents’ preferences over alternatives, to define theplurality matrix, and to define three disagreement measures as our use\-cases\.

Let𝒜=\{a,b,…\}\\mathcal\{A\}=\\\{a,b,\\ldots\\\}be a finite set ofm≥3m\\geq 3alternatives,Πm\\Pi\_\{m\}the set of allm\!m\!strict rankings of𝒜\\mathcal\{A\}, and𝒮:=\{S⊆𝒜:2≤\|S\|≤m\}\\mathcal\{S\}:=\\\{S\\subseteq\\mathcal\{A\}:2\\leq\|S\|\\leq m\\\}\(sorted by size, then lexicographically\)\. For a statementτ\\tau,𝟙​\{τ\}\\mathbbm\{1\}\\\{\\tau\\\}denotes the indicator ofτ\\tau\. Apreference profile\(or voter population\) is a probability distributionπ\\pionΠm\\Pi\_\{m\}, and avotercorresponds to a ranking≻∈Πm\{\\succ\}\\in\\Pi\_\{m\}sampled fromπ\\pi\.

We adopt a probabilistic view as many applications, e\.g\. online platforms, involve in general a large number of participants\. We now introduce one of the main concept of our paper, theplurality matrix, which will serve as the basis for first analyzing disagreement and later designing elicitation protocols\.

###### Definition 2\.1\.

Letπ\\pibe a preference profile\. We define theplurality matrix𝒫π∈\[0,1\]𝒮×𝒜\\mathcal\{P\}\_\{\\pi\}\\in\[0,1\]^\{\\mathcal\{S\}\\times\\mathcal\{A\}\}, where, for eachS∈𝒮S\\in\\mathcal\{S\}anda∈𝒜a\\in\\mathcal\{A\}, the entry\(S,a\)\(S,a\)is given by,

pSπ​\(a\):=ℙπ​\(a​is ranked first among the alternatives in​S\)⋅𝟙​\{a∈S\}\.\\displaystyle p^\{\\pi\}\_\{S\}\(a\):=\\mathbb\{P\}\_\{\\pi\}\(a\\text\{ is ranked first among the alternatives in \}S\)\\cdot\\mathbbm\{1\}\\\{a\\in S\\\}\.For simplicity, we writepx​y​w​zπp\_\{xywz\}^\{\\pi\}instead ofp\{x,y,w,z\}πp\_\{\\\{x,y,w,z\\\}\}^\{\\pi\}\. Givenk∈\{2,…,m\}k\\in\\\{2,\.\.\.,m\\\}, we refer to thedata or information of degreekkto the sub\-matrix containing only the rows related to sets of sizekk\. We say a real\-value statisticΦ\\Phiis oflevelkkif for any preference profileπ\\piand alternativeaa,Φ​\(π,a\)\\Phi\(\\pi,a\)can be expressed using data of degree at mostkkbut not at mostk−1k\-1\.

We assume throughout the article thatpSπ​\(a\)\>0p\_\{S\}^\{\\pi\}\(a\)\>0for every profileπ\\pi, everyS∈𝒮S\\in\\mathcal\{S\}, anda∈Sa\\in S: an alternative violating this is dominated on every voter’s ranking, hence never a locus of disagreement\. For simplicity, we make one exception in Example[2\.3](https://arxiv.org/html/2605.19521#S2.Thmtheorem3)below\. We writepSπ​\(a\)=⋅p\_\{S\}^\{\\pi\}\(a\)=\\cdotwhenevera∉Sa\\not\\in S\.

###### Definition 2\.2\.

Letπ\\pibe a preference profile,≻∈Πm\\succ\\,\\in\\,\\Pi\_\{m\}be a ranking, anda∈𝒜a\\in\\mathcal\{A\}\. We define therankofaaand theBorda scoreofaa, respectively by,

ra​\(≻\):=1\+\|\{b∈𝒜∖\{a\}:b≻a\}\|​and​Borπ⁡\(a\):=∑b∈𝒜∖\{a\}pa​bπ​\(a\)=m−𝔼π​\[ra\]\.\\displaystyle r\_\{a\}\(\\succ\):=1\+\|\\\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}:b\\succ a\\\}\|\\text\{ and \}\\operatorname\{Bor\}\_\{\\pi\}\(a\):=\\sum\\nolimits\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}p\_\{ab\}^\{\\pi\}\(a\)=m\-\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\]\.Moreover, givenx,y∈𝒜x,y\\\!\\in\\\!\\mathcal\{A\}, we define the Borda score ofaaover the subpopulation preferringxxtoyy:

Borπ⁡\(a;𝒩πx≻y\):=∑b∈𝒜∖\{a\}ℙπ​\(a≻b∣x≻y\),\\displaystyle\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{x\\succ y\}\_\{\\pi\}\\bigr\):=\\sum\\nolimits\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}\\mathbb\{P\}\_\{\\pi\}\(a\\succ b\\mid x\\succ y\),

Pairwise comparisons \(more precisely, their aggregation over all voters\) correspond to the data of degree22\. In particular, the Borda score is a measure of level22\. Pairwise comparisons are widely used in the literature to compute many voting rules\(Brandtet al\.,[2016a](https://arxiv.org/html/2605.19521#bib.bib57); Fischeret al\.,[2016](https://arxiv.org/html/2605.19521#bib.bib59); Navarreteet al\.,[2024](https://arxiv.org/html/2605.19521#bib.bib62)\)\. At the other extreme, data of degreemmcorrespond to plurality scores, i\.e\. the proportion of voters ranking each alternative first\. In general, data of different degrees in the plurality matrix are unrelated, in the sense that none can be recovered from the other\. We illustrate the notion of plurality matrix and give some first insights next\.

###### Example 2\.3\.

Let𝒜=\{a,b,c\}\\mathcal\{A\}=\\\{a,b,c\\\}and consider two preference profiles:111Note the two profiles sit at opposite poles of the visualization compass of Szufa et al\.Szufaet al\.\([2025](https://arxiv.org/html/2605.19521#bib.bib22)\)\.the impartial\-culture profileπIC\\pi\_\{\\mathrm\{IC\}\},222Preference profiles in our terminology are typically called*cultures*or*distributions*in the social choice literature\. In this example we consider the impartial culture, but see Figure[2](https://arxiv.org/html/2605.19521#S3.F2)for profiles corresponding to other distributions\.where all alternatives are uniformly ranked, and the antagonism profileπAN\\pi\_\{\\mathrm\{AN\}\}, wherebbandccare uniformly ranked butaais ranked either first or last, each with probability1/21/2\. Formally,rar\_\{a\}verifies,

ℙπIC​\[ra=i\]=13,for​i∈\{1,2,3\}​and​ℙπAN​\[ra=i\]=12⋅𝟙​\{i=1\}\+12⋅𝟙​\{i=3\}\\displaystyle\\mathbb\{P\}\_\{\\pi\_\{\\mathrm\{IC\}\}\}\[r\_\{a\}=i\]=\\tfrac\{1\}\{3\},\\text\{ for \}i\\in\\\{1,2,3\\\}\\text\{ and \}\\mathbb\{P\}\_\{\\pi\_\{\\mathrm\{AN\}\}\}\[r\_\{a\}=i\]=\\tfrac\{1\}\{2\}\\cdot\\mathbbm\{1\}\\\{i=1\\\}\+\\tfrac\{1\}\{2\}\\cdot\\mathbbm\{1\}\\\{i=3\\\}[Table˜1](https://arxiv.org/html/2605.19521#S2.T1)shows the plurality matrix for the two aforementioned profiles\.

Table 1:Plurality matrices forπIC\\pi\_\{\\mathrm\{IC\}\}andπAN\\pi\_\{\\mathrm\{AN\}\}over𝒜=\{a,b,c\}\\mathcal\{A\}=\\\{a,b,c\\\}
Notice that the two matrices coincide on all entries of degree22but differ at degree33\. Any measure based solely on pairwise comparisons, therefore, will not be able to distinguish them\. Yet, both profiles clearly differ in terms of disagreement\.

The plurality matrix will be shown to be rich enough to express disagreement notions studied in this paper \(as well as several pairwise\-based social choice concepts\), yet simple enough to define efficient elicitation protocols under limited cognitive load\. Moreover, by working with aggregate proportions, we adopt a privacy\-preserving approach that does not require storing individual preferences\.

In the rest of the article, unless required, we will drop the dependence of all defined terms on the preference profileπ\\pifor simplicity\.

### 2\.1Three Measures of Disagreement

We introduce three measures of disagreement from the literature to be the use\-cases of the article, namely, theagreement indexof Faliszewski et al\.Faliszewskiet al\.\([2023](https://arxiv.org/html/2605.19521#bib.bib16)\), therank varianceof Kendall and SmithKendall and Smith \([1939](https://arxiv.org/html/2605.19521#bib.bib49)\), and thedivisivenessof Navarrete et al\.Navarreteet al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib62)\)\.

###### Definition 2\.4\.

Given a profileπ\\pi, we define itsagreement indexas

A​\(π\):=1\(m2\)​∑\{x,y\}⊆𝒜\|2⋅px​y​\(x\)−1\|\.\\displaystyle A\(\\pi\):=\\frac\{1\}\{\\binom\{m\}\{2\}\}\\sum\\nolimits\_\{\\\{x,y\\\}\\subseteq\\mathcal\{A\}\}\\bigl\|2\\cdot p\_\{xy\}\{\(x\)\}\-1\\bigr\|\.

The agreement index aggregates pairwise comparisons into a single scalar ranging from0\(all pairwise comparisons are perfectly split\) to11\(unanimity on all pairs\)\. Notice that Definition[2\.4](https://arxiv.org/html/2605.19521#S2.Thmtheorem4)is entirely determined by pairwise comparisons, thus, as illustrated in[Example˜2\.3](https://arxiv.org/html/2605.19521#S2.Thmtheorem3), it might fail to detect any disagreement that is not already visible at the pairwise level\.

###### Definition 2\.5\.

Letπ\\pibe a preference profile anda∈𝒜a\\in\\mathcal\{A\}an alternative\.

- •We define therank varianceofaaasVarπ⁡\(a\):=𝔼π​\[\(ra−𝔼π​\[ra\]\)2\]\\operatorname\{Var\}\_\{\\pi\}\(a\):=\\mathbb\{E\}\_\{\\pi\}\[\(r\_\{a\}\\\!\-\\\!\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\]\)^\{2\}\]\.
- •We define thedivisivenessofaaas Divπ⁡\(a\):=1m−1​∑b∈𝒜∖\{a\}\|Borπ⁡\(a;𝒩πa≻b\)−Borπ⁡\(a;𝒩πb≻a\)\|\.\\displaystyle\\operatorname\{Div\}\_\{\\pi\}\(a\):=\\frac\{1\}\{m\-1\}\\sum\\nolimits\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}\\bigl\|\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{a\\succ b\}\_\{\\pi\}\\bigr\)\\;\-\\;\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{b\\succ a\}\_\{\\pi\}\\bigr\)\\bigr\|\.

The rank variance quantifies how much the rank ofaafluctuates across the population\. Following Navarrete et al\.Navarreteet al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib62)\), we consider divisiveness combined with Borda scores \(although, note that any scoring function could be used, such as the Copeland score\)\. Intuitively, for each alternativeb∈𝒜∖\{a\}b\\in\\mathcal\{A\}\\setminus\\\{a\\\}, divisiveness partitions the population into those preferringaatobband those preferringbbtoaa, and compares the \(Borda\) score ofaaacross these two groups\. We conclude this section by illustrating the three introduced measures of disagreement\.

###### Example 2\.6\.

Consider an instance with\|𝒜\|=15\|\\mathcal\{A\}\|=15alternatives anda∈𝒜a\\in\\mathcal\{A\}fixed\. Consider the two preference profilesπIC\\pi\_\{\\mathrm\{IC\}\}andπAN\\pi\_\{\\mathrm\{AN\}\}as defined in Example[2\.3](https://arxiv.org/html/2605.19521#S2.Thmtheorem3), extended to1515alternatives\. In addition, consider the preferences profilesπmin\\pi\_\{\\mathrm\{min\}\}andπsym\\pi\_\{\\mathrm\{sym\}\}such that, for anyb∈𝒜∖\{a\}b\\in\\mathcal\{A\}\\setminus\\\{a\\\}, the rank ofbbis uniformly distributed, and, givenε1,ε2\>0\\varepsilon\_\{1\},\\varepsilon\_\{2\}\>0,

ℙπmin​\[ra=i\]=ε1⋅𝟙​\{i=1\}\+\(1−ε1\)⋅𝟙​\{i=15\},\\displaystyle\\mathbb\{P\}\_\{\\pi\_\{\\mathrm\{min\}\}\}\[r\_\{a\}=i\]=\\varepsilon\_\{1\}\\cdot\\mathbbm\{1\}\\\{i=1\\\}\+\(1\-\\varepsilon\_\{1\}\)\\cdot\\mathbbm\{1\}\\\{i=15\\\},ℙπsym​\[ra=i\]=ε2⋅𝟙​\{i=1\}\+ε2⋅𝟙​\{i=15\}\+\(1−2​ε2\)⋅𝟙​\{i=8\}\.\\displaystyle\\mathbb\{P\}\_\{\\pi\_\{\\mathrm\{sym\}\}\}\[r\_\{a\}=i\]=\\varepsilon\_\{2\}\\cdot\\mathbbm\{1\}\\\{i=1\\\}\+\\varepsilon\_\{2\}\\cdot\\mathbbm\{1\}\\\{i=15\\\}\+\(1\-2\\varepsilon\_\{2\}\)\\cdot\\mathbbm\{1\}\\\{i=8\\\}\.In words, inπIC\\pi\_\{\\mathrm\{IC\}\}all rankings are equally likely\. InπAN\\pi\_\{\\mathrm\{AN\}\}, half of the population ranksaafirst while the other half ranks it last\. Inπmin\\pi\_\{\\mathrm\{min\}\}, most of the population ranksaalast while a small portion ranks it first\. Finally, inπsym\\pi\_\{\\mathrm\{sym\}\}, small populations rankaarespectively first and last, while most of the voters rank it in the middle\. Figure[1](https://arxiv.org/html/2605.19521#S2.F1)illustrates the four distributions\.

13579111315πIC\\pi\_\{\\mathrm\{IC\}\}115\\tfrac\{1\}\{15\}

1357911131512\\tfrac\{1\}\{2\}πAN\\pi\_\{\\mathrm\{AN\}\}12\\tfrac\{1\}\{2\}

13579111315ε1\\varepsilon\_\{1\}πmin\\pi\_\{\\mathrm\{min\}\}1−ε11\-\\varepsilon\_\{1\}

13579111315ε2\\varepsilon\_\{2\}πsym\\pi\_\{\\mathrm\{sym\}\}1−2​ε21\-2\\varepsilon\_\{2\}ε2\\varepsilon\_\{2\}

Figure 1:Distribution ofrar\_\{a\}for each profile represented as probability mass functions\.Table[2](https://arxiv.org/html/2605.19521#S2.T2)shows the metrics on the four profiles\. As expected, the agreement index struggles to differ a uniform profile from profiles with split populations, while the other metrics manages to do it\. However, rank variance is maximized atπAN\\pi\_\{\\mathrm\{AN\}\}, asaais equally often ranked first or last, while divisiveness is maximized for bothπAN\\pi\_\{\\mathrm\{AN\}\}andπmin\\pi\_\{\\mathrm\{min\}\}, showing that only the presence, not the frequency, of extreme ranks might matter\. Interestingly, forπIC\\pi\_\{\\mathrm\{IC\}\}andπsym\\pi\_\{\\mathrm\{sym\}\}, both metrics coincide\.

Table 2:Agreement index, rank variance, and divisiveness of four profiles, withε1=0\.05\\varepsilon\_\{1\}=0\.05andε2=421\\varepsilon\_\{2\}=\\frac\{4\}\{21\}\.

## 3The Plurality Hierarchy

This section is dedicated to study the hierarchy of the different degrees information of the plurality matrix\. We begin by determining the level of the disagreement measures introduced in Section[2\.1](https://arxiv.org/html/2605.19521#S2.SS1), complemented by an extensive analysis in Appendix[D](https://arxiv.org/html/2605.19521#A4)of a large number of agreement, disagreement, and polarization measures from the literature\. We then prove that the induced level hierarchy is strict and that it collapses under standard structural assumptions on voters’ preferences\.

### 3\.1Level of Disagreement Measures

Our first result is a straighforward corollary of the definition of the agreement index\.

###### Proposition 3\.1\.

The Agreement IndexA​\(π\)A\(\\pi\)is a measure of level22\.

Regarding the rank variance and the divisiveness, we prove two important results: first, they are fully captured by our framework and second, they require entries of degree strictly higher than two\.

###### Proposition 3\.2\.

The rank variance is a measure of level33\. Moreover, for any preference profileπ\\piand alternativea∈𝒜a\\in\\mathcal\{A\}, it holds,

Var⁡\(a\)=∑b∈𝒜∖\{a\}pa​b​\(a\)⋅\(1−pa​b​\(a\)\)\+∑b,c∈𝒜∖\{a\},b≠c\(pa​b​c​\(a\)−pa​b​\(a\)⋅pa​c​\(a\)\)\.\\displaystyle\\operatorname\{Var\}\(a\)\\;=\\;\\sum\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}\\\!\\\!p\_\{ab\}\(a\)\\cdot\(1\-p\_\{ab\}\(a\)\)\\;\+\\\!\\\!\\sum\_\{\\begin\{subarray\}\{c\}b,c\\in\\mathcal\{A\}\\setminus\\\{a\\\},b\\neq c\\end\{subarray\}\}\\\!\\\!\\\!\\\!\\bigl\(\\,p\_\{abc\}\{\(a\)\}\-p\_\{ab\}\(a\)\\cdot p\_\{ac\}\(a\)\\bigr\)\.

###### Proposition 3\.3\.

The divisiveness is a measure of level33\. Moreover, for any preference profileπ\\piand alternativea∈𝒜a\\in\\mathcal\{A\}, it holds,

Div⁡\(a\)=1m−1​∑b∈𝒜∖\{a\}\|1\+∑c∈𝒜∖\{a,b\}\[pa​b​c​\(a\)⋅\(11−pa​b​\(a\)\+1pa​b​\(a\)\)−pa​c​\(a\)1−pa​b​\(a\)\]\|\.\\displaystyle\\operatorname\{Div\}\(a\)=\\frac\{1\}\{m\-1\}\\sum\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}\\biggl\|1\+\\sum\_\{c\\in\\mathcal\{A\}\\setminus\\\{a,b\\\}\}\\left\[p\_\{abc\}\(a\)\\cdot\\biggl\(\\frac\{1\}\{1\-p\_\{ab\}\(a\)\}\+\\frac\{1\}\{p\_\{ab\}\(a\)\}\\biggr\)\-\\frac\{p\_\{ac\}\(a\)\}\{1\-p\_\{ab\}\(a\)\}\\biggr\]\\right\|\.

The proofs of[Propositions˜3\.2](https://arxiv.org/html/2605.19521#S3.Thmtheorem2)and[3\.3](https://arxiv.org/html/2605.19521#S3.Thmtheorem3)are deferred to Appendix[B](https://arxiv.org/html/2605.19521#A2)\. Note that, since rank variance and divisiveness can be expressed with entries of degree22and33, both are of level at most33\. To show tightness, considerπIC\\pi\_\{\\mathrm\{IC\}\}andπAN\\pi\_\{\\mathrm\{AN\}\}as in[Example˜2\.6](https://arxiv.org/html/2605.19521#S2.Thmtheorem6): they coincide at degree22\(px​y​\(x\)=1/2p\_\{xy\}\(x\)=\\nicefrac\{\{1\}\}\{\{2\}\}for anyx,y∈𝒜x,y\\in\\mathcal\{A\}\), yetVarπIC⁡\(a\)≠VarπAN⁡\(a\)\\operatorname\{Var\}\_\{\\pi\_\{\\mathrm\{IC\}\}\}\(a\)\\neq\\operatorname\{Var\}\_\{\\pi\_\{\\mathrm\{AN\}\}\}\(a\)andDivπIC⁡\(a\)≠DivπAN⁡\(a\)\\operatorname\{Div\}\_\{\\pi\_\{\\mathrm\{IC\}\}\}\(a\)\\neq\\operatorname\{Div\}\_\{\\pi\_\{\\mathrm\{AN\}\}\}\(a\), as shown in[Table˜2](https://arxiv.org/html/2605.19521#S2.T2)\. Hence, neither measure can be expressed using only information of degree22\.

The previous observation actually extends beyond level33: for any integerk≥2k\\geq 2, there exist two profiles that coincide on all degrees from22tokk, but differ on at least one entry of degreek\+1k\+1\. In particular, although the two profiles are different, no measure of levelkkcan distinguish them\.

###### Proposition 3\.4\.

For everyk≥2k\\geq 2, there existsm∈ℕm\\in\\mathbb\{N\}, a set𝒜\\mathcal\{A\}ofmmalternatives, and two preference profilesπ,π′\\pi,\\pi^\{\\prime\}such thatpSπ​\(a\)=pSπ′​\(a\)p\_\{S\}^\{\\pi\}\(a\)=p\_\{S\}^\{\\pi^\{\\prime\}\}\(a\)for anyS⊆𝒜S\\subseteq\\mathcal\{A\}with\|S\|≤k\|S\|\\leq kanda∈𝒜a\\in\\mathcal\{A\}, whilepTπ​\(a\)≠pTπ′​\(a\)p\_\{T\}^\{\\pi\}\(a\)\\neq p\_\{T\}^\{\\pi^\{\\prime\}\}\(a\)for someT⊆𝒜T\\subseteq\\mathcal\{A\}with\|T\|=k\+1\|T\|=k\+1and somea∈𝒜a\\in\\mathcal\{A\}\. In particular, no measure of levelkkdistinguishesπ\\pifromπ′\\pi^\{\\prime\}\.

The proof of[Proposition˜3\.4](https://arxiv.org/html/2605.19521#S3.Thmtheorem4)\(in Appendix[B](https://arxiv.org/html/2605.19521#A2)\) constructs the two stated profilesπ\\piandπ′\\pi^\{\\prime\}\. However, the question of whether a measure of levelkk, for anyk∈ℕk\\in\\mathbb\{N\}, actually exists, rises\. The answer isyes\.

###### Definition 3\.5\.

Let𝒜\\mathcal\{A\}be a set ofmmalternatives\. For any preference profileπ\\piandk∈\{1,…,m\}k\\in\\\{1,\.\.\.,m\\\}, define thekk\-central momentMkπM\_\{k\}^\{\\pi\}as,

Mkπ​\(a\):=𝔼π​\[\(ra−𝔼​\[ra\]\)k\],for any​a∈𝒜\.\\displaystyle M\_\{k\}^\{\\pi\}\(a\):=\\mathbb\{E\}\_\{\\pi\}\\bigl\[\(r\_\{a\}\-\\mathbb\{E\}\[r\_\{a\}\]\)^\{k\}\\bigr\],\\text\{ for any \}a\\in\\mathcal\{A\}\.

The following result generalizes[Proposition˜3\.2](https://arxiv.org/html/2605.19521#S3.Thmtheorem2)to any degree\. The proof is included in Appendix[B](https://arxiv.org/html/2605.19521#A2)\.

###### Theorem 3\.6\.

Thekk\-central momentMkM\_\{k\}is a measure of levelk\+1k\+1\. Moreover, for any profileπ\\piand alternativea∈𝒜a\\in\\mathcal\{A\}, it holds,

Mk​\(a\)=\(−1\)k​∑s=0kcs​\(a\)⋅∑S⊆𝒜∖\{a\},\|S\|=spS∪\{a\}​\(a\)=\(−1\)k​∑s=0kcs​\(a\)⋅𝔼π​\[\(m−ras\)\],\\displaystyle M\_\{k\}\(a\)=\(\-1\)^\{k\}\\sum\_\{s=0\}^\{k\}\\ \\ c\_\{s\}\(a\)\\cdot\\\!\\\!\\\!\\\!\\\!\\sum\_\{\{S\\subseteq\\mathcal\{A\}\\setminus\\\{a\\\},\|S\|=s\}\}\\\!\\\!\\\!p\_\{S\\cup\\\{a\\\}\}\{\(a\)\}=\(\-1\)^\{k\}\\sum\_\{s=0\}^\{k\}\\ \\ c\_\{s\}\(a\)\\cdot\\mathbb\{E\}\_\{\\pi\}\\biggl\[\\binom\{m\-r\_\{a\}\}\{s\}\\biggr\],wherecs​\(a\):=∑j=0s\(−1\)s−j​\(sj\)​\(j−Bor⁡\(a\)\)kc\_\{s\}\(a\):=\\sum\_\{j=0\}^\{s\}\(\-1\)^\{s\-j\}\\binom\{s\}\{j\}\(j\-\\operatorname\{Bor\}\(a\)\)^\{k\}andpa​\(a\)=1p\_\{a\}\(a\)=1\.

Thekk\-central moments, for different values ofkk, measure different properties of the distributions of the alternatives’ ranks\. Notably, given a preference profileπ\\pi, fork=3k=3andk=4k=4, we obtain, respectively, theskewnessγ1π\\gamma\_\{1\}^\{\\pi\}and theexcess kurtosisγ2π\\gamma\_\{2\}^\{\\pi\}, formally given by,

γ1π​\(a\):=M3π​\(a\)\(M2π​\(a\)\)3/2​and​γ2π​\(a\):=M4π​\(a\)\(M2π​\(a\)\)2−3\.\\displaystyle\\gamma\_\{1\}^\{\\pi\}\(a\):=\\frac\{M\_\{3\}^\{\\pi\}\(a\)\}\{\(M\_\{2\}^\{\\pi\}\(a\)\)^\{\\nicefrac\{\{3\}\}\{\{2\}\}\}\}\\text\{ and \}\\gamma\_\{2\}^\{\\pi\}\(a\):=\\frac\{M\_\{4\}^\{\\pi\}\(a\)\}\{\(M\_\{2\}^\{\\pi\}\(a\)\)^\{2\}\}\-3\.The skewness measures the asymmetry of the distribution ofrar\_\{a\}while the excess kurtosis relates to tail extremity, reflecting the tendency of the distribution ofrar\_\{a\}to produce outliers\. From[Proposition˜3\.4](https://arxiv.org/html/2605.19521#S3.Thmtheorem4)and[Theorem˜3\.6](https://arxiv.org/html/2605.19521#S3.Thmtheorem6),γ1π\\gamma\_\{1\}^\{\\pi\}is a measure of level44whileγ2π\\gamma\_\{2\}^\{\\pi\}is a measure of level55\. In particular, they give a two\-dimensional summary of the rank distributions that no measure of level22and33can capture\.

To better illustrate these measures, we present a numerical experiment on synthetic preference profiles fromBoehmeret al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib73)\)\. For an experiment on real data, see Appendix[C\.2](https://arxiv.org/html/2605.19521#A3.SS2)\. In[Figure˜2](https://arxiv.org/html/2605.19521#S3.F2), we consider an instance with256256alternatives and77different preference profiles, namely, Mallows \(φ=0\.85\\varphi=0\.85\), Mallows mix\-22and mix\-44\(φ=0\.3\\varphi=0\.3\), Plackett\-Luce with linear strengths, Walsh single\-peaked, andkk\-Euclidean fork∈\{2,10\}k\\in\\\{2,10\\\}\.[Figure˜2](https://arxiv.org/html/2605.19521#S3.F2)plots\(γ1π​\(x\),γ2π​\(x\)\)\(\\gamma\_\{1\}^\{\\pi\}\(x\),\\gamma\_\{2\}^\{\\pi\}\(x\)\)for each alternativex∈𝒜x\\in\\mathcal\{A\}under each profileπ\\pi\(represented by the colored dots\)\. The solid parabola is the boundary of thePearson inequality, which states that for anyx∈𝒜x\\in\\mathcal\{A\},γ2π​\(x\)≥\(γ1π​\(x\)\)2−2\\gamma\_\{2\}^\{\\pi\}\(x\)\\geq\(\\gamma\_\{1\}^\{\\pi\}\(x\)\)^\{2\}\-2\. The dashed parabola marks the transition between unimodal \(above\) and bimodal \(below\) rank distributions, the latter indicating higher disagreement\. The figure has been zoomed on this transition region \- in particular, some dots were left out of the image\. Interestingly, ranks obtained from single\-peaked, Plackett\-Luce, andkk\-Euclidean distributions lie in the unimodal region, as they induce less disagreement among voters \(see Appendix[C\.1](https://arxiv.org/html/2605.19521#A3.SS1)for more detailed discussion\)\. In contrasts, Mallows mixtures shift toward the bimodal region, as alternatives ranked differently in the mixtures increase disagreement among voters\.

Additionally, we plot\(γ1π​\(a\),γ2π​\(a\)\)\(\\gamma\_\{1\}^\{\\pi\}\(a\),\\gamma\_\{2\}^\{\\pi\}\(a\)\)for a fixed alternativea∈𝒜a\\in\\mathcal\{A\}over five preference profilesπIC,πA,πB,πC\\pi\_\{\\mathrm\{IC\}\},\\pi\_\{A\},\\pi\_\{B\},\\pi\_\{C\}andπD\\pi\_\{D\}\. For each of them, all alternativesb∈𝒜∖\{a\}b\\in\\mathcal\{A\}\\setminus\\\{a\\\}are uniformly ranked, as well asaainπIC\\pi\_\{\\mathrm\{IC\}\}\. The distribution ofrar\_\{a\}under the rest of the profiles is represented on the right\-hand side of[Figure˜2](https://arxiv.org/html/2605.19521#S3.F2)\. Up to degree33, it follows that all five distributions present the same plurality matrix\. However, at degree44, the skewness is able to distinguishπIC,πC\\pi\_\{\\mathrm\{IC\}\},\\pi\_\{C\}, andπD\\pi\_\{D\}\. Similarly, at degree55, the excess kurtosis distinguishesπIC\\pi\_\{\\mathrm\{IC\}\},πA\\pi\_\{A\}, andπB\\pi\_\{B\}\. In particular, for a practitioner using an elicitation model considering only information of degrees22and33will never be able to distinguish the unimodal distributionπA\\pi\_\{A\}from the bimodal distributionsπB,πC,πD\\pi\_\{B\},\\pi\_\{C\},\\pi\_\{D\}, from impartial cultureπIC\\pi\_\{\\mathrm\{IC\}\}\.

![Refer to caption](https://arxiv.org/html/2605.19521v1/x1.png)Figure 2:Skewness versus Excess kurtosis produced by seven different preferences profiles fromBoehmeret al\.\([2024](https://arxiv.org/html/2605.19521#bib.bib73)\)over256256alternatives\. For each alternativex∈𝒜x\\in\\mathcal\{A\}, a colored dot represents\(γ1π​\(x\),γ2π​\(x\)\)\(\\gamma\_\{1\}^\{\\pi\}\(x\),\\gamma\_\{2\}^\{\\pi\}\(x\)\)for the respective profileπ\\pi\. The solid parabola represents the boundary of the Pearson inequality \(γ2π​\(x\)≥\(γ1π​\(x\)\)2−2\\gamma\_\{2\}^\{\\pi\}\(x\)\\geq\(\\gamma\_\{1\}^\{\\pi\}\(x\)\)^\{2\}\-2for anyx∈𝒜x\\in\\mathcal\{A\}\) while the dashed parabola marks the transition between unimodal \(above\) and bimodal \(below\) distributions\. The triangles show\(γ1π​\(a\),γ2π​\(a\)\)\(\\gamma\_\{1\}^\{\\pi\}\(a\),\\gamma\_\{2\}^\{\\pi\}\(a\)\)for a fixeda∈𝒜a\\in\\mathcal\{A\}whose rank is either uniform \(triangleUU\) or displayed on the right\-hand side\. The plurality matrix of the five distributionsπIC,πA,πB,πC\\pi\_\{\\mathrm\{IC\}\},\\pi\_\{A\},\\pi\_\{B\},\\pi\_\{C\}andπD\\pi\_\{D\}are identical up to degree33, so no measure of level33can detect the difference between them\. An interactive version of this plot is provided as supplementary material and presented in AppendixLABEL:app:supp\-viz\.
### 3\.2Disagreement Under Structural Assumptions

The strictness of the hierarchy shows that higher\-degree information cannot, in general, be recovered from lower\-degree observations\. However, this perspective may be overly pessimistic in structured settings\. We ask here whether structural assumptions can simplify the hierarchy introduced in this paper\. We focus on two classical models representing two distinct types of structure: the*Plackett\-Luce*model\(Luce and others,[1959](https://arxiv.org/html/2605.19521#bib.bib44); Plackett,[1975](https://arxiv.org/html/2605.19521#bib.bib43)\), a probabilistic latent\-utility model, where each alternative has a strengthva\>0v\_\{a\}\>0, and rankings are generated by sequential sampling without replacement, with probabilities proportional to these strengths; and*single\-peaked preferences*\(Black,[1948](https://arxiv.org/html/2605.19521#bib.bib46); Moulin,[1980](https://arxiv.org/html/2605.19521#bib.bib45)\), where alternatives are ordered on a fixed one\-dimensional axis and each voter’s preferences are monotone away from their personal peak\. We show that both models collapse the hierarchy to level22, that is, all higher\-degree data can be recovered from degree22data\. In particular, practitioners with reasons to believe that any of such structure holds can reduce elicitation to pairwise comparisons alone\. The proof is included in Appendix[B](https://arxiv.org/html/2605.19521#A2)\.

###### Proposition 3\.7\.

Let𝒜\\mathcal\{A\}be a set of alternatives\. ConsiderπPL\\pi\_\{\\text\{PL\}\}a preference profile following the Plackett\-Luce model\. Then, for anyS⊆𝒜S\\subseteq\\mathcal\{A\}anda∈Sa\\in S, it followspSπPL​\(a\)=va/∑x∈Svx\.p\_\{S\}^\{\\pi\_\{\\text\{PL\}\}\}\(a\)=\{v\_\{a\}\}/\{\\sum\_\{x\\in S\}v\_\{x\}\}\.

ConsiderπSP\\pi\_\{\\text\{SP\}\}a preference profile having in its support only preferences single\-peaked over an axis\(s1,…,sm\)\(s\_\{1\},\.\.\.,s\_\{m\}\)\. Then, for anyS=\{si1,…,sik\}⊆𝒜S=\\\{s\_\{i\_\{1\}\},\.\.\.,s\_\{i\_\{k\}\}\\\}\\subseteq\\mathcal\{A\}sorted along the axis andj∈\{1,…,k\}j\\in\\\{1,\.\.\.,k\\\}, it follows,

pSπSP​\(sij\)=psij​sij\+1πSP​\(sij\)−psij−1​sijπSP​\(sj−1\),where​psi0​si1πSP​\(s1\):=0​and​psik​sik\+1πSP​\(sk\):=1\.\\displaystyle p\_\{S\}^\{\\pi\_\{\\text\{SP\}\}\}\(s\_\{i\_\{j\}\}\)=p\_\{s\_\{i\_\{j\}\}s\_\{i\_\{j\+1\}\}\}^\{\\pi\_\{\\text\{SP\}\}\}\(s\_\{i\_\{j\}\}\)\-p\_\{s\_\{i\_\{j\-1\}\}s\_\{i\_\{j\}\}\}^\{\\pi\_\{\\text\{SP\}\}\}\(s\_\{j\-1\}\),\\text\{ where \}p\_\{s\_\{i\_\{0\}\}s\_\{i\_\{1\}\}\}^\{\\pi\_\{\\text\{SP\}\}\}\(s\_\{1\}\):=0\\text\{ and \}p\_\{s\_\{i\_\{k\}\}s\_\{i\_\{k\+1\}\}\}^\{\\pi\_\{\\text\{SP\}\}\}\(s\_\{k\}\):=1\.In particular, for each case, for anyk≥3k\\geq 3, the information of degreekkcan be obtained as a function of the information of degree22\.

Note that, although both structural assumptionscollapsethe hierarchy to level22, single\-peakedness requires knowing the axis in advance, which is rarely the case in practice\(Conitzer,[2009](https://arxiv.org/html/2605.19521#bib.bib66)\)\. In contrast, in the Plackett–Luce model, the latent strengths\(va\)a∈𝒜\(v\_\{a\}\)\_\{a\\in\\mathcal\{A\}\}need not to be accessed or estimated, thus, eliciting pairwise comparisons is sufficient to recover all higher\-degree quantities\.

## 4Elicitation Protocols for the Plurality Matrix

This section is devoted to studying protocols to approximate the plurality matrix\. In particular, we adopt a PAC approach, that is, to findε\\varepsilon\-approximations of each matrix entry with probability1−δ1\-\\delta\.

### 4\.1Elicitation Primitives and Protocols

Estimating the information of degree22of the plurality matrix trivially reduces to querying pairwise comparisons\. For\|S\|≥3\|S\|\\geq 3, estimatingpSπ​\(a\)p\_\{S\}^\{\\pi\}\(a\)is no longer direct, and the choice of elicitation primitive becomes nontrivial\. We consider two primitives, described as sequences of pairwise comparisons\.333Using pairwise comparisons as elicitation primitives allows us to compare protocols on their cognitive load, since pairwise comparisons are a standard proxy for cognitive load in elicitation studiesConitzer \([2009](https://arxiv.org/html/2605.19521#bib.bib66)\)\.

###### Definition 4\.1\.

LetS=\{a1,…,a\|S\|\}⊆𝒜S=\\\{a\_\{1\},\\ldots,a\_\{\|S\|\}\\\}\\subseteq\\mathcal\{A\}be a set of alternatives\.

- 1\.We define theSS\-chainas the primitive that performs\|S\|−1\|S\|\\\!\-\\\!1sequential pairwise comparisons: comparea1a\_\{1\}anda2a\_\{2\}, then iteratively compare the running winner withaja\_\{j\}forj∈\{3,…,\|S\|\}j\\in\\\{3,\\ldots,\|S\|\\\}\.
- 2\.We define theSS\-rankingas the primitive that elicits a full ranking ofSSvia pairwise comparisons\.

Based on these elicitation primitives, we design two elicitationprotocols\. For this, given a profileπ\\pi, we denote𝒱nπ\\mathcal\{V\}^\{\\pi\}\_\{n\}a set ofnnvoters drawn independently fromπ\\pi\.

###### Definition 4\.2\.

GivenN≤nN\\leq nandk≤mk\\leq m, akk\-chain \(resp\.kk\-ranking\) protocol of lengthNNsamples uniformly with replacementNNsubsetsS1,…,SNS\_\{1\},\.\.\.,S\_\{N\}each of sizekk, withSi⊆𝒜S\_\{i\}\\subseteq\\mathcal\{A\}, and uniformly without replacementNNvoters\{v1,…,vN\}\\\{v\_\{1\},\.\.\.,v\_\{N\}\\\}from𝒱nπ\\mathcal\{V\}^\{\\pi\}\_\{n\}, and for eachi∈\{1,…,N\}i\\in\\\{1,\.\.\.,N\\\}, asks voterviv\_\{i\}to answer theSiS\_\{i\}\-chain \(respectively,SiS\_\{i\}\-ranking\)\.

With this in mind, we define two cost axes to assess our protocols\.

###### Definition 4\.4\.

Given a protocol of lengthNN, letcjc\_\{j\}be the number of pairwise comparisons performed at stepjj\. We define thebudgetBBand themaximum cognitive loadλ\\lambdaof the protocol as:

B:=∑j=1Ncj​and​λ:=maxj∈\{1,…,N\}⁡cj\.\\displaystyle B:=\\sum\\nolimits\_\{j=1\}^\{N\}\\\!c\_\{j\}\\text\{ and \}\\lambda:=\\max\_\{j\\in\\\{1,\.\.\.,N\\\}\}c\_\{j\}\.

The budget of a protocol is the total number of pairwise comparisons it requires, and its maximum cognitive load is the most demanding query it poses to a voter, ranging from a single pairwise comparison to a full ranking\. Given a population of voters, estimating the plurality matrix involves a fundamental trade\-off between budget and maximum cognitive load\. Intuitively, when voters can only be asked simple queries, i\.e\., involving few pairwise comparisons, a larger number of queries is required to obtain accurate estimates\. Conversely, allowing more complex queries reduces their number at the cost of an increased cognitive burden per query\. Equivalently, this can be viewed as a tradeoff between the number of queried voters and the maximum cognitive load under a fixed budget\.

### 4\.2Estimating the Plurality Matrix

DenoteQkQ\_\{k\}the total number of non\-zero plurality matrix entries of degreekkto be estimated\. It follows thatQk=k​\(mk\)Q\_\{k\}=k\\binom\{m\}\{k\}\. In order to estimate these values, we will look at the aggregated number of samples we require over the entries\. Applying Hoeffding’s inequality plus a union bound \(see Appendix[A\.2](https://arxiv.org/html/2605.19521#A1.SS2)\), we obtain thatTk=ln⁡\(2​Qk/δ\)/\(2​ε2\)T\_\{k\}=\\ln\(2Q\_\{k\}/\\delta\)/\(2\\varepsilon^\{2\}\)is the minimum number of samples required to obtain anε\\varepsilon\-approximation with probability1−δ1\-\\deltaof all plurality matrix entries of degreekk\.

With this in mind, we can compare our two elicitation protocols with respect to the number of samples they produce\. AnSS\-chain yields\|S\|−1\|S\|\\\!\-\\\!1samples, one per degree, on the nested prefixespa1​a2,pa1​a2​a3,…,pa1​…​a\|S\|p\_\{a\_\{1\}a\_\{2\}\},p\_\{a\_\{1\}a\_\{2\}a\_\{3\}\},\\ldots,p\_\{a\_\{1\}\\ldots a\_\{\|S\|\}\}\. In particular, no extra information can be deduced from these values, as every time we ask a new pairwise comparison during anSS\-chain, the result is conditioned to the previous comparisons \(see Appendix[A\.1](https://arxiv.org/html/2605.19521#A1.SS1)for a detailed discussion\)\. Conversely, anSS\-ranking reveals the voter’s preference restricted toSSwhich, by transitivity, determines the winner of every setT⊆ST\\subseteq S, yielding\(\|S\|k\)\\binom\{\|S\|\}\{k\}independent samples at each degreek≤\|S\|k\\leq\|S\|, totaling2\|S\|−\|S\|−12^\{\|S\|\}\-\|S\|\-1values per voter\. Clearly, this connects with[Remark˜4\.3](https://arxiv.org/html/2605.19521#S4.Thmtheorem3)regarding the cognitive load of each primitive\.

The following result formally states the previous discussion\. Its proof and a more detailed analysis is included in Appendix[B\.4](https://arxiv.org/html/2605.19521#A2.Thmtheorem4)\.

###### Theorem 4\.5\.

Let𝒜\\mathcal\{A\}be a set ofmmalternatives andk≥2k\\geq 2be fixed\. Suppose we want to estimate allQkQ\_\{k\}entries of degreekkof the plurality matrix up to accuracyε\\varepsilonwith probability at least1−δ1\\\!\-\\\!\\delta\. Then,

- 1\.Akk\-chain requiresNchain:=\(mk\)​ln⁡\(2​Qk/δ\)/\(2​ε2\)N\_\{\\text\{chain\}\}:=\\binom\{m\}\{k\}\\ln\(2Q\_\{k\}/\\delta\)/\(2\\varepsilon^\{2\}\)voters and entails a maximum cognitive load ofλ=k−1\\lambda\\\!=\\\!k\-1per voter\.
- 2\.Akk\-ranking requires Nrank:=\(mk\)​ln⁡\(2​Qk/δ\)2​ε2⋅1k​log⁡kN\_\{\\text\{rank\}\}:=\\binom\{m\}\{k\}\\frac\{\\ln\(2Q\_\{k\}/\\delta\)\}\{2\\varepsilon^\{2\}\}\\cdot\\frac\{1\}\{k\\log\{k\}\}voters and entails a maximum cognitive loadλ=k​log⁡\(k\)\\lambda=k\\log\(k\)per voter\.

[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)characterizes the trade\-off induced by our protocols\. In particular, for fixed values ofε\\varepsilonandδ\\delta, the range of entries of the plurality matrix that can be accurately estimated depends on the number of available voters\. In applications such as online platforms, where the number of participants is typically large, designers may favor protocols with low cognitive load\. Conversely, in settings with a limited number of voters who are willing to answer more demanding queries, eliciting rankings appears to be more appropriate\.

Observe that, when estimating degreekkentries of the plurality matrix using rankings, the platform designer is not restricted tokk\-rankings: anyk′k^\{\\prime\}\-ranking withk′\>kk^\{\\prime\}\\\!\>\\\!kcan be used\. Indeed, the transitivity of rankings allows one to extract information about entries of degreekkmore efficiently, potentially reducing the number of required queries\. However, increasing the size of the ranking also increases the maximum cognitive load on each voter\. In particular, given a maximum cognitive load constraintλ∗\\lambda^\{\*\}, the largest ranking sizek∗k^\{\*\}that can be used isk∗:=max⁡\{k∈\{1,…,m\}∣⌈log2⁡\(k\!\)⌉≤λ∗\}k^\{\*\}:=\\max\\\{k\\in\\\{1,\.\.\.,m\\\}\\mid\\lceil\\log\_\{2\}\(k\!\)\\rceil\\leq\\lambda^\{\*\}\\\}\.

Clearly, as already observed in[Proposition˜3\.4](https://arxiv.org/html/2605.19521#S3.Thmtheorem4), the degree of the estimated entries of the plurality matrix will never be higher than the valuekkof the chain or ranking used\. This connects to the maximum cognitive load of the protocol, as stated in the following result proved in Appendix[B](https://arxiv.org/html/2605.19521#A2)\.

###### Proposition 4\.6\.

Any elicitation protocol estimating a plurality matrix entry of degreekkhas a maximum cognitive loadλ\\lambdaof value at leastk−1k\-1\. Thus,kk\-chains have the minimal cognitive load among all elicitation protocols for data of degreekk\.

We conclude this section by illustrating the tradeoff between maximum cognitive loadλ\\lambdaand the required number of votersNNfor our two protocols at different degrees, sampling from an impartial culture profile with1010alternatives\. For each pair\(λ,N\)\(\\lambda,N\),[Figure˜3](https://arxiv.org/html/2605.19521#S4.F3)shows which of the two protocols is optimal in terms of budget\. We observe that chains are optimal whenever voters present low maximal cognitive load values or when a large population of voters is available\. For the rest of the regimes, thanks to inferring prefrences via transitivity, rankings become the optimal choice\.

![Refer to caption](https://arxiv.org/html/2605.19521v1/x2.png)Figure 3:PopulationNN\(number of voters\) required as a function of maximum cognitive loadλ\\lambda, across degreesk∈\{2,3,4,5\}k\\in\\\{2,3,4,5\\\}, on an impartial\-culture profile withm=10m=10alternatives and accuracyε=0\.05\\varepsilon=0\.05\. For each pair\(λ,N\)\(\\lambda,N\)the optimal protocol in terms of budget is highlighted\. The intervals over the points represent the55th to the9595th percentile\.

## 5Conclusions

To identify the disagreements of a population over a set of alternatives we introduce the plurality matrix, a stratified framework for organizing aggregated preference data according to subset sizes\. Thus, we can define the level of a disagreement measure as the smallest subset size required to express it\. Our definitions allow us to chart an hierarchy of disagreement measures, with notable examples such as rank variance and divisiveness both lying at level33, showing, in particular, that neither of these measures can be recovered from pairwise comparisons alone\. We further establish that the induced hierarchy is strict, by constructing preference profiles that coincide up to levelkkbut differ at levelk\+1k\\\!\+\\\!1\. Moreover, for every levelkk, we exhibit a meaningful measure that inherently requires information from levelkk\. Interestingly, structural assumptions on voters’ preferences such as single\-peakedness or the Plackett–Luce model collapse the hierarchy to level22, indicating that in rare albeit well\-behaved settings disagreements can be fully captured through pairwise comparisons\. Finally, we propose two elicitation protocols and analyze the tradeoff they induce between the cognitive load demanded to each voter and the population size\.

Limitations\.Our framework is not able to capture measures such as thekk\-Kemeny family, its derived polarization and diversity indices\(Faliszewskiet al\.,[2023](https://arxiv.org/html/2605.19521#bib.bib16)\), or the rank\-distance\-based diversity measures\(Hashemi and Endriss,[2014](https://arxiv.org/html/2605.19521#bib.bib19); Karpov,[2017](https://arxiv.org/html/2605.19521#bib.bib15)\), due to the nature of the event we measure within the entries of the plurality matrix\. Additionally, our analysis relies on standard assumptions: voters are i\.i\.d\., truthful, and noiseless, and cognitive load is uniformly measured in terms of the number of pairwise comparisons\. Moreover, our empirical evaluation is based solely on complete preference reports\. Extending our framework to settings with top\-kklists, approval ballots, partial orders, or Bayesian variants with priors over response noise and cognitive load, suggest interesting directions for future work\.

## Acknowledgments

This work was supported by the ANR LabEx CIMI \(grant ANR\-11\-LABX\-0040\) within the French State Programme “Investissements d’Avenir\.”

Funded by the European Union\. Views and opinions expressed are however those of the author\(s\) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency\. Neither the European Union nor the granting authority can be held responsible for them\. This work is supported by ERC grant 101166894 “Advancing Digital Democratic Innovation” \(ADDI\)\. This project was supported by the European Union LearnData, GA no\. 101086712 a\.k\.a\. 101086712\-LearnDataHORIZON\-WIDERA–2022\-TALENTS–01 \(https://cordis\.europa\.eu/project/id/101086712\), IAST funding from the French National Research Agency \(ANR\) under grant ANR–17\-EURE–0010 \(Investissements d’Avenir program\), and the European Lighthouse of AI for Sustainability \[grant number 101120237\-HORIZON\-CL4–2022\-HUMAN–02\]\.

![[Uncaptioned image]](https://arxiv.org/html/2605.19521v1/figs/LOGO_ERC-FLAG_FP.png)
## References

- \[1\]\(2013\)Measuring the cohesiveness of preferences: an axiomatic analysis\.Social Choice and Welfare41\(4\),pp\. 965–988\.External Links:[Document](https://dx.doi.org/10.1007/s00355-012-0716-9)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.38.36.5.1.1)\.
- \[2\]M\. Ammann and C\. Puppe\(2025\)Preference diversity\.Review of Economic Design\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[3\]K\. J\. Arrow, A\. Sen, and K\. Suzumura\(2010\)Handbook of social choice and welfare\.Vol\.2,Elsevier\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[4\]M\. Ayadi, N\. Ben Amor, and J\. Lang\(2022\)Approximating voting rules from truncated ballots\.Autonomous Agents and Multi\-Agent Systems36\(1\),pp\. 24\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[5\]A\. Baujard, H\. Igersheim, and T\. Delemazure\(2025\)Voter Autrement 2007 \- Dataset of the In Situ Experiments\.Note:Paper available at[https://hal\.science/hal\-04986968](https://hal.science/hal-04986968)\. Data available at[10\.5281/zenodo\.14990025](https://arxiv.org/html/2605.19521v1/10.5281/zenodo.14990025)Cited by:[§C\.2](https://arxiv.org/html/2605.19521#A3.SS2.p1.1)\.
- \[6\]D\. Black\(1948\)On the rationale of group decision\-making\.Journal of political economy56\(1\),pp\. 23–34\.Cited by:[§3\.2](https://arxiv.org/html/2605.19521#S3.SS2.p1.3)\.
- \[7\]N\. Boehmer, P\. Faliszewski, Ł\. Janeczko, A\. Kaczmarczyk, G\. Lisowski, G\. Pierczyński, S\. Rey, D\. Stolicki, S\. Szufa, and T\. Wąs\(2024\)Guide to numerical experiments on elections in computational social choice\.InProceedings of the 33rd International Joint Conference on Artificial Intelligence \(IJCAI\),Cited by:[§C\.2](https://arxiv.org/html/2605.19521#A3.SS2.p1.1),[Figure 2](https://arxiv.org/html/2605.19521#S3.F2),[§3\.1](https://arxiv.org/html/2605.19521#S3.SS1.p8.14)\.
- \[8\]S\. J\. Brams and M\. R\. Sanver\(2009\)Voting systems that combine approval and preference\.InThe Mathematics of Preference, Choice and Order: Essays in Honor of Peter C\. Fishburn,Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[9\]F\. Brandt, M\. Brill, and P\. Harrenstein\(2016\)Tournament solutions\.\.InHandbook of Computational Social Choice,F\. Brandt, V\. Conitzer, U\. Endriss, J\. Lang, and A\. D\. Procaccia \(Eds\.\),pp\. 57–84\.Cited by:[§2](https://arxiv.org/html/2605.19521#S2.p5.3)\.
- \[10\]F\. Brandt, V\. Conitzer, U\. Endriss, J\. Lang, and A\. D\. Procaccia\(2016\)Handbook of computational social choice\.Cambridge University Press\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[11\]J\. W\. Bucklin\(1911\)The grand junction plan of city government and its results\.The Annals of the American Academy of Political and Social Science38\(3\),pp\. 87–102\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.31.29.5.1.1)\.
- \[12\]B\. Can, A\. I\. Ozkes, and T\. Storcken\(2015\)Measuring polarization in preferences\.Mathematical Social Sciences78,pp\. 76–79\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.38.36.5.1.1),[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[13\]B\. Can, A\. I\. Özkes, and T\. Storcken\(2017\)Generalized measures of polarization in preferences\.Technical reportTechnical ReportAMSE Working Paper 1734,Aix\-Marseille School of Economics\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.41.39.5.1.1)\.
- \[14\]X\. Chen, Y\. Li, and J\. Mao\(2018\)A nearly instance optimal algorithm for top\-kkranking under the multinomial logit model\.InProceedings of the 29th Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[15\]Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[16\]R\. Colley, U\. Grandi, C\. Hidalgo, M\. Macedo, and C\. Navarrete\(2023\)Measuring and controlling divisiveness in rank aggregation\.InProceedings of the 32nd International Joint Conference on Artificial Intelligence \(IJCAI\),Cited by:[§D\.5](https://arxiv.org/html/2605.19521#A4.SS5.p1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.53.51.5.1.1)\.
- \[17\]V\. Conitzer\(2009\-06\)Eliciting single\-peaked preferences using comparison queries\.Journal of Artificial Intelligence Research35,pp\. 161–191\.Cited by:[§3\.2](https://arxiv.org/html/2605.19521#S3.SS2.p2.2),[footnote 3](https://arxiv.org/html/2605.19521#footnote3)\.
- \[18\]V\. Conitzer and T\. Sandholm\(2005\)Communication complexity of common voting rules\.InProceedings of the 6th ACM conference on Electronic commerce,Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p2.1)\.
- \[19\]A\. H\. Copeland\(1951\)A ‘reasonable’ social welfare function\.Note:Mimeographed notes, Seminar on Applications of Mathematics to the Social Sciences, University of Michigan, Ann ArborCited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.8.6.4.1.1)\.
- \[20\]J\. de Borda\(1781\)Mémoire sur les élections au scrutin\.Histoire de l’Académie Royale des Sciences,pp\. 657–665\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.22.20.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.6.4.4.1.1)\.
- \[21\]T\. Delemazure, Ł\. Janeczko, A\. Kaczmarczyk, and S\. Szufa\(2024\)Selecting the most conflicting pair of candidates\.InProceedings of the 33rd International Joint Conference on Artificial Intelligence \(IJCAI\),Cited by:[§D\.9](https://arxiv.org/html/2605.19521#A4.SS9.p1.5),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.47.45.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.56.54.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.59.57.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.61.59.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.62.60.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.63.61.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.64.62.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.67.65.5.1.1),[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[22\]L\. Dery\(2024\)Interactive and iterative peer assessment\.InProceedings of the 27th European Conference on Artificial Intelligence \(ECAI\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[23\]J\. Esteban and D\. Ray\(1994\-02\)The measurement of polarization\.Econometrica62,pp\. 819–51\.External Links:[Document](https://dx.doi.org/10.2307/2951734)Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[24\]P\. Faliszewski, A\. Kaczmarczyk, K\. Sornat, S\. Szufa, and T\. Wąs\(2023\)Diversity, agreement, and polarization in elections\.InProceedings of the 32nd International Joint Conference on Artificial Intelligence \(IJCAI\),External Links:[Document](https://dx.doi.org/10.24963/ijcai.2023/299)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.73.71.8.1.1),[2nd item](https://arxiv.org/html/2605.19521#S1.I1.i2.p1.3),[§1](https://arxiv.org/html/2605.19521#S1.p5.1),[§2\.1](https://arxiv.org/html/2605.19521#S2.SS1.p1.1),[§5](https://arxiv.org/html/2605.19521#S5.p2.2)\.
- \[25\]P\. Faliszewski, K\. Sornat, S\. Szufa, and T\. Wąs\(2026\)Diversity of structured domains via k\-Kemeny scores\.Proceedings of the AAAI Conference on Artificial Intelligence \(AAAI\)40\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[26\]F\. Fischer, O\. Hudry, and R\. Niedermeier\(2016\)Weighted tournament solutions\.\.InHandbook of Computational Social Choice,F\. Brandt, V\. Conitzer, U\. Endriss, J\. Lang, and A\. D\. Procaccia \(Eds\.\),pp\. 85–102\.Cited by:[§2](https://arxiv.org/html/2605.19521#S2.p5.3)\.
- \[27\]J\. Fürnkranz and E\. Hüllermeier\(2011\)Preference learning\.\.Springer\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[28\]J\. Gaitonde, J\. Kleinberg, and É\. Tardos\(2020\)Adversarial perturbations of opinion dynamics in networks\.InProceedings of the 21st ACM Conference on Economics and Computation \(EC\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[29\]H\. Gilbert, T\. Portoleau, and O\. Spanjaard\(2020\)Beyond pairwise comparisons in social choice: a setwise Kemeny aggregation problem\.InProceedings of the 34th AAAI Conference on Artificial Intelligence \(AAAI\),External Links:[Document](https://dx.doi.org/10.1609/aaai.v34i02.5569)Cited by:[§D\.2](https://arxiv.org/html/2605.19521#A4.SS2.p1.4),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.18.16.4.1.1)\.
- \[30\]D\. Griffin, W\. Liu, and U\. Khan\(2005\)A new look at constructed choice processes\.Marketing Letters\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[31\]D\. Halpern, S\. Hossain, and J\. Tucker\-Foltz\(2024\)Computing voting rules with elicited incomplete votes\.InProceedings of the 25th ACM Conference on Economics and Computation \(EC\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[32\]V\. Hashemi and U\. Endriss\(2014\)Measuring diversity of preferences in a group\.\.InProceedings of the 21st European Conference on Artificial Intelligence \(ECAI\),Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.44.42.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.74.72.4.1.1),[Table 3](https://arxiv.org/html/2605.19521#A4.T3.75.73.4.1.1),[§1](https://arxiv.org/html/2605.19521#S1.p5.1),[§5](https://arxiv.org/html/2605.19521#S5.p2.2)\.
- \[33\]A\. Karpov\(2017\)Preference diversity orderings\.Group Decision and Negotiation26\(4\),pp\. 753–774\.External Links:[Document](https://dx.doi.org/10.1007/s10726-017-9532-z)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.76.74.4.1.1),[§1](https://arxiv.org/html/2605.19521#S1.p5.1),[§5](https://arxiv.org/html/2605.19521#S5.p2.2)\.
- \[34\]J\. G\. Kemeny\(1959\)Mathematics without numbers\.Daedalus88\(4\),pp\. 577–591\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.12.10.4.1.1)\.
- \[35\]M\. G\. Kendall and B\. B\. Smith\(1939\)The problem ofmmrankings\.The annals of Mathematical Statistics10\(3\),pp\. 275–287\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.49.47.4.1.1),[2nd item](https://arxiv.org/html/2605.19521#S1.I1.i2.p1.3),[§2\.1](https://arxiv.org/html/2605.19521#S2.SS1.p1.1)\.
- \[36\]G\. H\. Kramer\(1977\)A dynamical model of political equilibrium\.Journal of Economic Theory16\(2\),pp\. 310–334\.External Links:[Document](https://dx.doi.org/10.1016/0022-0531%2877%2990011-4)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.10.8.4.1.1)\.
- \[37\]R\. D\. Luceet al\.\(1959\)Individual choice behavior\.Vol\.4,Wiley New York\.Cited by:[§3\.2](https://arxiv.org/html/2605.19521#S3.SS2.p1.3)\.
- \[38\]H\. Moulin\(1980\)On strategy\-proofness and single peakedness\.Public Choice35\(4\),pp\. 437–455\.Cited by:[§3\.2](https://arxiv.org/html/2605.19521#S3.SS2.p1.3)\.
- \[39\]C\. Musco, C\. Musco, and C\. E\. Tsourakakis\(2018\)Minimizing polarization and disagreement in social networks\.InProceedings of the 2018 World Wide Web Conference \(WWW\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[40\]R\. B\. Myerson\(1993\)Incentives to cultivate favored minorities under alternative electoral systems\.American Political Science Review87\(4\),pp\. 856–869\.External Links:[Document](https://dx.doi.org/10.2307/2938820)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.24.22.4.1.1)\.
- \[41\]C\. Navarrete, M\. Macedo, R\. Colley, J\. Zhang, N\. Ferrada, M\. E\. Mello, R\. Lira, C\. Bastos\-Filho, U\. Grandi, J\. Lang,et al\.\(2024\)Understanding political divisiveness using online participation data from the 2022 French and Brazilian presidential elections\.Nature Human Behaviour8\(1\),pp\. 137–148\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.50.48.4.1.1),[2nd item](https://arxiv.org/html/2605.19521#S1.I1.i2.p1.3),[§1](https://arxiv.org/html/2605.19521#S1.p1.1),[§1](https://arxiv.org/html/2605.19521#S1.p5.1),[§2\.1](https://arxiv.org/html/2605.19521#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2605.19521#S2.SS1.p3.7),[§2](https://arxiv.org/html/2605.19521#S2.p5.3)\.
- \[42\]R\. L\. Plackett\(1975\)The analysis of permutations\.Journal of the Royal Statistical Society Series C: Applied Statistics24\(2\),pp\. 193–202\.Cited by:[§3\.2](https://arxiv.org/html/2605.19521#S3.SS2.p1.3)\.
- \[43\]A\. D\. Procaccia\(2009\)Thou shalt covet thy neighbor’s cake\.InProceedings of the 21st International Joint Conference on Artificial Intelligence \(IJCAI\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p2.1)\.
- \[44\]A\. Saha and A\. Gopalan\(2019\)Active ranking with subset\-wise preferences\.InProceedings of the 22nd International Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[45\]M\. Schulze\(2011\)A new monotonic, clone\-independent, reversal symmetric, and Condorcet\-consistent single\-winner election method\.Social Choice and Welfare36\(2\),pp\. 267–303\.External Links:[Document](https://dx.doi.org/10.1007/s00355-010-0475-4)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.14.12.4.1.1)\.
- \[46\]R\. J\. Serfling\(1974\)Probability inequalities for the sum in sampling without replacement\.The Annals of Statistics,pp\. 39–48\.Cited by:[§A\.2](https://arxiv.org/html/2605.19521#A1.SS2.SSS0.Px2.p1.7)\.
- \[47\]P\. B\. Simpson\(1969\)On defining areas of voter choice: Professor Tullock on stable voting\.The Quarterly Journal of Economics83\(3\),pp\. 478–490\.External Links:[Document](https://dx.doi.org/10.2307/1880533)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.10.8.4.1.1)\.
- \[48\]P\. Slater\(1961\)Inconsistencies in a schedule of paired comparisons\.Biometrika48\(3–4\),pp\. 303–312\.External Links:[Document](https://dx.doi.org/10.1093/biomet/48.3-4.303)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.14.12.4.1.1)\.
- \[49\]C\. T\. Small, I\. Vendrov, E\. Durmus, H\. Homaei, E\. Barry, J\. Cornebise, T\. Suzman, D\. Ganguli, and C\. Megill\(2023\)Opportunities and risks of LLMs for scalable deliberation with polis\.arXiv preprint arXiv:2306\.11932\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[50\]C\. T\. Small, M\. Bjorkegren, T\. Erkkilä, L\. Shaw, and C\. Megill\(2021\)Polis: scaling deliberation by mapping high dimensional opinion spaces\.Recerca: Revista de Pensament i Anàlisi26\(2\)\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.
- \[51\]S\. Szufa, N\. Boehmer, R\. Bredereck, P\. Faliszewski, R\. Niedermeier, P\. Skowron, A\. Slinko, and N\. Talmon\(2025\)Drawing a map of elections\.Artificial Intelligence343,pp\. 104332\.Cited by:[footnote 1](https://arxiv.org/html/2605.19521#footnote1)\.
- \[52\]Z\. Terzopoulou\(2023\)Voting with limited energy: a study of plurality and borda\.InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems \(AAMAS\),Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p5.1)\.
- \[53\]L\. L\. Thurstone\(1927\)The method of paired comparisons for social values\.The Journal of Abnormal and Social Psychology21\(4\),pp\. 384–400\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p2.1)\.
- \[54\]N\. Tideman\(1995\)The single transferable vote\.Journal of Economic Perspectives9\(1\),pp\. 27–38\.Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.34.32.5.1.1)\.
- \[55\]T\. N\. Tideman\(1987\)Independence of clones as a criterion for voting rules\.Social Choice and Welfare4\(3\),pp\. 185–206\.External Links:[Document](https://dx.doi.org/10.1007/BF00433944)Cited by:[Table 3](https://arxiv.org/html/2605.19521#A4.T3.14.12.4.1.1)\.
- \[56\]J\. Waldron\(1999\)Law and disagreement\.OUP Oxford\.Cited by:[§1](https://arxiv.org/html/2605.19521#S1.p1.1)\.

Appendix Table of Contents

## Appendix AExamples and omitted details

### A\.1Bias in chain transitivity

No additional*unbiased*observations can be inferred by transitivity fromkk\-chains\. Indeed, the probability that a given pair is resolved varies with the underlying ranking of each voter, inducing a selection bias\. As a result, empirical frequencies computed from such inferred comparison do not, in general, estimate the true pairwise proportion\. We illustrate this phenomenon on the following example\.

###### Example A\.1\.

Let𝒜=\{a,b,c\}\\mathcal\{A\}=\\\{a,b,c\\\}and

π=12σA\+12σB,σA:a≻c≻b,σB:b≻c≻a,\\pi\\;=\\;\\tfrac\{1\}\{2\}\\,\\sigma\_\{A\}\\;\+\\;\\tfrac\{1\}\{2\}\\,\\sigma\_\{B\},\\qquad\\sigma\_\{A\}:a\\succ c\\succ b,\\qquad\\sigma\_\{B\}:b\\succ c\\succ a,so thatpc​a=ℙπ​\[c≻a\]=12p\_\{ca\}=\\mathbb\{P\}\_\{\\pi\}\[c\\succ a\]=\\tfrac\{1\}\{2\}\. Run a33\-chain onS=\{a,b,c\}S=\\\{a,b,c\\\}with orderingτ\\taudrawn uniformly from the66permutations, independently of the voter\. For a voterσ\\sigma, record

Yc​a​\(σ,τ\)=\{𝟙​\[c≻σa\]if\{a,c\}is compared directly orw3∈\{a,c\}\(transitive inference\),⊥otherwise,Y\_\{ca\}\(\\sigma,\\tau\)=\\begin\{cases\}\\mathbbm\{1\}\[c\\succ\_\{\\sigma\}a\]&\\text\{if $\\\{a,c\\\}$ is compared directly or $w\_\{3\}\\in\\\{a,c\\\}$ \(transitive inference\),\}\\\\ \\bot&\\text\{otherwise,\}\\end\{cases\}and estimatepc​ap\_\{ca\}byp^c​a=ℙ​\[Yc​a=1∣Yc​a≠⊥\]\\hat\{p\}\_\{ca\}=\\mathbb\{P\}\[Y\_\{ca\}=1\\mid Y\_\{ca\}\\neq\\bot\]\. Enumerating all2×62\\times 6cases:

Aggregating over the uniform voter\-ordering distribution givesℙ​\[Yc​a=0\]=12⋅66=12\\mathbb\{P\}\[Y\_\{ca\}=0\]=\\tfrac\{1\}\{2\}\\cdot\\tfrac\{6\}\{6\}=\\tfrac\{1\}\{2\},ℙ​\[Yc​a=1\]=12⋅26=16\\mathbb\{P\}\[Y\_\{ca\}=1\]=\\tfrac\{1\}\{2\}\\cdot\\tfrac\{2\}\{6\}=\\tfrac\{1\}\{6\}, andℙ​\[Yc​a≠⊥\]=23\\mathbb\{P\}\[Y\_\{ca\}\\neq\\bot\]=\\tfrac\{2\}\{3\}, so

p^c​a=1/62/3=14,bias=p^c​a−pc​a=−14\.\\hat\{p\}\_\{ca\}\\;=\\;\\frac\{1/6\}\{2/3\}\\;=\\;\\tfrac\{1\}\{4\},\\qquad\\text\{bias\}\\;=\\;\\hat\{p\}\_\{ca\}\-p\_\{ca\}\\;=\\;\-\\tfrac\{1\}\{4\}\.
The estimator’s observation rate depends on the voter: a voter withtopσ​\(S\)∈\{a,c\}\\text\{top\}\_\{\\sigma\}\(S\)\\in\\\{a,c\\\}always resolves\{a,c\}\\\{a,c\\\}via transitivity \(6/66/6orderings\), whereas a voter withtopσ​\(S\)∉\{a,c\}\\text\{top\}\_\{\\sigma\}\(S\)\\notin\\\{a,c\\\}resolves it only whenaaandccare placed at positions11–22\(2/62/6orderings\)\. Equal\-mass voter types therefore produce unequal observation counts, and the conditional distribution ofYc​aY\_\{ca\}given a non\-⊥\\botrecord differs fromπ\\pi’s marginal on\{a,c\}\\\{a,c\\\}\. The asymmetry is between voters, not between orderings, so uniform randomization ofτ\\taudoes not correct it\. Only the nested prefix winnersw2=topσ​\(\{x1,x2\}\)w\_\{2\}=\\text\{top\}\_\{\\sigma\}\(\\\{x\_\{1\},x\_\{2\}\\\}\)andw3=topσ​\(S\)w\_\{3\}=\\text\{top\}\_\{\\sigma\}\(S\)yield unbiased samples, since their reference subsets are fixed by the protocol independently ofσ\\sigma\.

### A\.2Hoeffding union bound

[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)states a per\-quantity sample budgetTℓT\_\{\\ell\}in terms of accuracyε\\varepsilonand confidenceδ\\delta\. We derive that bound here under i\.i\.d\. sampling, and then refine the analysis under the without\-replacement assumption that each voter responds at most once\.

#### Hoeffding’s inequality and the union bound\.

We seekTℓT\_\{\\ell\}small enough to be cheap and large enough to guarantee

ℙ\[∀\(T,a\)with\|T\|=ℓanda∈T:\|pT​\(a\)^−pT\(a\)\|≤ε\]≥1−δ\.\\mathbb\{P\}\\bigl\[\\,\\forall\(T,a\)\\text\{ with \}\|T\|=\\ell\\text\{ and \}a\\in T:\\,\|\\widehat\{p\_\{T\}\{\(a\)\}\}\-p\_\{T\}\{\(a\)\}\|\\leq\\varepsilon\\,\\bigr\]\\;\\geq\\;1\-\\delta\.For each such pair,pT​\(a\)p\_\{T\}\{\(a\)\}is a Bernoulli parameter, andpT​\(a\)^\\widehat\{p\_\{T\}\{\(a\)\}\}is the empirical frequency of the event “aatopsTT” acrossTℓT\_\{\\ell\}observations\. Hoeffding’s inequality gives, for each\(T,a\)\(T,a\)separately,

ℙ​\[\|pT​\(a\)^−pT​\(a\)\|\>ε\]≤2​exp⁡\(−2​Tℓ​ε2\)\.\\mathbb\{P\}\\bigl\[\\,\|\\widehat\{p\_\{T\}\{\(a\)\}\}\-p\_\{T\}\{\(a\)\}\|\>\\varepsilon\\,\\bigr\]\\;\\leq\\;2\\exp\(\-2T\_\{\\ell\}\\varepsilon^\{2\}\)\.A union bound over theQℓ:=ℓ​\(mℓ\)Q\_\{\\ell\}:=\\ell\\binom\{m\}\{\\ell\}such quantities yields the simultaneous guarantee whenever

Tℓ≥12​ε2​ln⁡\(2​Qℓ/δ\)\.T\_\{\\ell\}\\;\\geq\\;\\frac\{1\}\{2\\varepsilon^\{2\}\}\\,\\ln\\\!\\bigl\(2Q\_\{\\ell\}/\\delta\\bigr\)\.\(1\)We refer toTℓT\_\{\\ell\}as the per\-quantity sample budget\. Population requirements depend on how many of theQℓQ\_\{\\ell\}quantities each query updates; the conversion is given in[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)\.

#### Without\-replacement refinement\.

The Hoeffding bound assumes i\.i\.d\. sampling with replacement\. In our setting each voter responds at most once, so the samples for a fixed quantitypT​\(a\)p\_\{T\}\{\(a\)\}are drawn without replacement from a finite population of sizenn\. Serfling\[[46](https://arxiv.org/html/2605.19521#bib.bib39)\]sharpens Hoeffding’s inequality in this regime: writingTTfor the sample size andf∗:=\(T−1\)/nf^\{\*\}:=\(T\-1\)/nfor the sampling fraction, the deviation exponent improves from−2​T​ε2\-2T\\varepsilon^\{2\}to−2​T​ε2/\(1−f∗\)\-2T\\varepsilon^\{2\}/\(1\-f^\{\*\}\)\. Substituting into the union bound and solving for the smallest sufficient sample sizeTℓ′T\_\{\\ell\}^\{\\prime\}, one obtains

Tℓ′=Tℓ⋅n\+1n\+Tℓ,T\_\{\\ell\}^\{\\prime\}\\;=\\;T\_\{\\ell\}\\cdot\\frac\{n\+1\}\{n\+T\_\{\\ell\}\},whereTℓT\_\{\\ell\}on the right\-hand side denotes the Hoeffding bound \([1](https://arxiv.org/html/2605.19521#A1.E1)\)\. The relative reduction is

1−Tℓ′Tℓ=Tℓ−1n\+Tℓ\.1\-\\frac\{T\_\{\\ell\}^\{\\prime\}\}\{T\_\{\\ell\}\}\\;=\\;\\frac\{T\_\{\\ell\}\-1\}\{n\+T\_\{\\ell\}\}\.Whenevern≥\(mℓ\)​Tℓ=Nchainn\\geq\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}=N\_\{\\mathrm\{chain\}\}, the population threshold above which the chain protocol is feasible \([Corollary˜A\.2](https://arxiv.org/html/2605.19521#A1.Thmtheorem2)\(iii\)\), this reduction is bounded by

Tℓ−1n\+Tℓ≤1\(mℓ\)\+1,\\frac\{T\_\{\\ell\}\-1\}\{n\+T\_\{\\ell\}\}\\;\\leq\\;\\frac\{1\}\{\\binom\{m\}\{\\ell\}\+1\},which falls below2%2\\%as soon as\(mℓ\)≥50\\binom\{m\}\{\\ell\}\\geq 50and decays asΘ​\(1/\(mℓ\)\)\\Theta\(1/\\binom\{m\}\{\\ell\}\)thereafter\. We therefore use the simpler Hoeffding bound \([1](https://arxiv.org/html/2605.19521#A1.E1)\) throughout the paper; under without\-replacement sampling, every stated sample size and population requirement may be tightened by the factor\(n\+1\)/\(n\+Tℓ\)\(n\+1\)/\(n\+T\_\{\\ell\}\)at no cost to validity\.

### A\.3Achievable Pareto region

The corollary below describes the achievable region of\(λ,B\)\(\\lambda,B\)pairs from[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5), identifies its Pareto\-optimal subset, and translates the result into a protocol choice for a fixed population\.

###### Corollary A\.2\.

Fix degreeℓ≥2\\ell\\geq 2\. The achievable region of\(λ,B\)\(\\lambda,B\)pairs from[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)is the union of:

1. *\(i\)*At the low\-λ\\lambdaend, the chain point\(λ,B\)=\(ℓ−1,\(ℓ−1\)​\(mℓ\)​Tℓ\)\(\\lambda,B\)=\\bigl\(\\ell\-1,\\,\(\\ell\-1\)\\binom\{m\}\{\\ell\}T\_\{\\ell\}\\bigr\)\. Forℓ≥3\\ell\\geq 3, no ranking matches thisλ\\lambda, since⌈log2⁡\(ℓ\!\)⌉\>ℓ−1\\lceil\\log\_\{2\}\(\\ell\!\)\\rceil\>\\ell\-1\. Forℓ=2\\ell=2, the chain point coincides with thek=2k=2ranking, both reducing to pairwise comparisons\.
2. *\(ii\)*At the high\-λ\\lambdaend, the ranking curve indexed byk∈\{ℓ,…,m\}k\\in\\\{\\ell,\\ldots,m\\\}, withλ=⌈log2⁡\(k\!\)⌉\\lambda=\\lceil\\log\_\{2\}\(k\!\)\\rceil\(monotone increasing inkk\) andB=\(mℓ\)​Tℓ⋅⌈log2⁡\(k\!\)⌉/\(kℓ\)B=\\binom\{m\}\{\\ell\}T\_\{\\ell\}\\cdot\\lceil\\log\_\{2\}\(k\!\)\\rceil/\\binom\{k\}\{\\ell\}\(weakly decreasing inkk, strictly so forℓ≥3\\ell\\geq 3\)\. Forℓ=2\\ell=2,BBis flat fromk=2k=2tok=3k=3, and thek=3k=3ranking is therefore Pareto\-dominated by the chain endpoint atλ=1\\lambda=1\. The curve terminates at the budget\-minimisingmm\-ranking\.

The Pareto\-optimal subset of this region consists of clause*\(i\)*’s chain point together with the rankings\{k=ℓ,…,m\}\\\{k=\\ell,\\ldots,m\\\}forℓ≥3\\ell\\geq 3, and the rankings\{k=2\}∪\{k=4,…,m\}\\\{k=2\\\}\\cup\\\{k=4,\\ldots,m\\\}forℓ=2\\ell=2\(wherek=2k=2subsumes the chain point\)\.

1. *\(iii\)**Protocol choice givennnvoters\.*Under the without\-replacement assumption \(N≤nN\\leq n\), the minimum\-λ\\lambdafeasible protocol is theℓ\\ell\-chain whenn≥\(mℓ\)​Tℓn\\geq\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}\(so thatNchain≤nN\_\{\\mathrm\{chain\}\}\\leq n\); otherwise it is thek∗k^\{\*\}\-ranking, wherek∗k^\{\*\}is the smallestk∈\{ℓ,…,m\}k\\in\\\{\\ell,\\ldots,m\\\}satisfying\(kℓ\)≥\(mℓ\)​Tℓ/n\\binom\{k\}\{\\ell\}\\geq\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}/n\.

###### Proof\.

*Clause \(i\): chain endpoint\.*[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)\(i\) atλ=ℓ−1\\lambda=\\ell\-1givesNchain=\(mℓ\)​TℓN\_\{\\mathrm\{chain\}\}=\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}andB=\(ℓ−1\)​\(mℓ\)​TℓB=\(\\ell\-1\)\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}\. Theλ\\lambda\-optimality among ranking protocols requires⌈log2⁡\(ℓ\!\)⌉\>ℓ−1\\lceil\\log\_\{2\}\(\\ell\!\)\\rceil\>\\ell\-1forℓ≥3\\ell\\geq 3\. Direct verification:⌈log2⁡6⌉=3\>2\\lceil\\log\_\{2\}6\\rceil=3\>2,⌈log2⁡24⌉=5\>3\\lceil\\log\_\{2\}24\\rceil=5\>3,⌈log2⁡120⌉=7\>4\\lceil\\log\_\{2\}120\\rceil=7\>4\. Forℓ≥5\\ell\\geq 5, Stirling’s boundlog2⁡\(ℓ\!\)≥ℓ​log2⁡\(ℓ/e\)\\log\_\{2\}\(\\ell\!\)\\geq\\ell\\log\_\{2\}\(\\ell/e\)giveslog2⁡\(ℓ\!\)\>ℓ−1\\log\_\{2\}\(\\ell\!\)\>\\ell\-1, sincelog2⁡\(ℓ/e\)\>1−1/ℓ\\log\_\{2\}\(\\ell/e\)\>1\-1/\\ellholds forℓ≥5\\ell\\geq 5\. Forℓ=2\\ell=2,⌈log2⁡\(2\!\)⌉=1=ℓ−1\\lceil\\log\_\{2\}\(2\!\)\\rceil=1=\\ell\-1, and theℓ\\ell\-chain coincides with thek=2k=2ranking, both reducing to pairwise comparisons\.

*Clause \(ii\): ranking branch\.*Fork∈\{ℓ,…,m\}k\\in\\\{\\ell,\\ldots,m\\\},[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)\(ii\) withλ=⌈log2⁡\(k\!\)⌉\\lambda=\\lceil\\log\_\{2\}\(k\!\)\\rceilgivesλ=⌈log2⁡\(k\!\)⌉\\lambda=\\lceil\\log\_\{2\}\(k\!\)\\rceil\(monotone increasing inkk\) andNrank=\(mℓ\)​Tℓ/\(kℓ\)N\_\{\\mathrm\{rank\}\}=\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}/\\binom\{k\}\{\\ell\}\(monotone decreasing inkk\)\. WriteCℓ:=\(mℓ\)​TℓC\_\{\\ell\}:=\\binom\{m\}\{\\ell\}T\_\{\\ell\}, soB​\(k\)=Cℓ⋅⌈log2⁡\(k\!\)⌉/\(kℓ\)B\(k\)=C\_\{\\ell\}\\cdot\\lceil\\log\_\{2\}\(k\!\)\\rceil/\\binom\{k\}\{\\ell\}\. We establish the monotonicity ofBBinkkby computing the step ratio

B​\(k\+1\)B​\(k\)=⌈log2⁡\(\(k\+1\)\!\)⌉⌈log2⁡\(k\!\)⌉⋅\(kℓ\)\(k\+1ℓ\)=⌈log2⁡\(\(k\+1\)\!\)⌉⌈log2⁡\(k\!\)⌉⋅k\+1−ℓk\+1\.\\frac\{B\(k\+1\)\}\{B\(k\)\}\\;=\\;\\frac\{\\lceil\\log\_\{2\}\(\(k\+1\)\!\)\\rceil\}\{\\lceil\\log\_\{2\}\(k\!\)\\rceil\}\\cdot\\frac\{\\binom\{k\}\{\\ell\}\}\{\\binom\{k\+1\}\{\\ell\}\}\\;=\\;\\frac\{\\lceil\\log\_\{2\}\(\(k\+1\)\!\)\\rceil\}\{\\lceil\\log\_\{2\}\(k\!\)\\rceil\}\\cdot\\frac\{k\+1\-\\ell\}\{k\+1\}\.The conditionB​\(k\+1\)≤B​\(k\)B\(k\+1\)\\leq B\(k\)is therefore equivalent to

⌈log2⁡\(\(k\+1\)\!\)⌉⋅\(k\+1−ℓ\)≤⌈log2⁡\(k\!\)⌉⋅\(k\+1\)\.\\lceil\\log\_\{2\}\(\(k\+1\)\!\)\\rceil\\cdot\(k\+1\-\\ell\)\\;\\leq\\;\\lceil\\log\_\{2\}\(k\!\)\\rceil\\cdot\(k\+1\)\.\(2\)Using the identity⌈log2⁡\(\(k\+1\)\!\)⌉≤⌈log2⁡\(k\!\)⌉\+⌈log2⁡\(k\+1\)⌉\\lceil\\log\_\{2\}\(\(k\+1\)\!\)\\rceil\\leq\\lceil\\log\_\{2\}\(k\!\)\\rceil\+\\lceil\\log\_\{2\}\(k\+1\)\\rceiland rearranging, a sufficient condition for \([2](https://arxiv.org/html/2605.19521#A1.E2)\) is

⌈log2⁡\(k\+1\)⌉⋅\(k\+1−ℓ\)≤ℓ⋅⌈log2⁡\(k\!\)⌉\.\\lceil\\log\_\{2\}\(k\+1\)\\rceil\\cdot\(k\+1\-\\ell\)\\;\\leq\\;\\ell\\cdot\\lceil\\log\_\{2\}\(k\!\)\\rceil\.\(3\)Forℓ≥3\\ell\\geq 3andk≥ℓk\\geq\\ell,⌈log2⁡\(k\!\)⌉≥⌈log2⁡\(ℓ\!\)⌉≥⌈log2⁡6⌉=3\\lceil\\log\_\{2\}\(k\!\)\\rceil\\geq\\lceil\\log\_\{2\}\(\\ell\!\)\\rceil\\geq\\lceil\\log\_\{2\}6\\rceil=3, so the right\-hand side is at least3​ℓ≥93\\ell\\geq 9\. The left\-hand side is⌈log2⁡\(k\+1\)⌉⋅\(k\+1−ℓ\)\\lceil\\log\_\{2\}\(k\+1\)\\rceil\\cdot\(k\+1\-\\ell\), bounded by\(log2⁡\(k\+1\)\+1\)​\(k\+1−ℓ\)\(\\log\_\{2\}\(k\+1\)\+1\)\(k\+1\-\\ell\)\. A direct check on the boundaryk=ℓk=\\ellgives left\-hand side⌈log2⁡\(ℓ\+1\)⌉\\lceil\\log\_\{2\}\(\\ell\+1\)\\rceil, right\-hand sideℓ⋅⌈log2⁡\(ℓ\!\)⌉\\ell\\cdot\\lceil\\log\_\{2\}\(\\ell\!\)\\rceil, and the inequality is strict by inspection for everyℓ∈\{3,4,…,20\}\\ell\\in\\\{3,4,\\ldots,20\\\}\(and asymptotically forℓ→∞\\ell\\to\\inftysinceℓ​log2⁡\(ℓ\!\)/log2⁡\(ℓ\+1\)→∞\\ell\\log\_\{2\}\(\\ell\!\)/\\log\_\{2\}\(\\ell\+1\)\\to\\infty\)\. Fork\>ℓk\>\\ell, both sides grow but the right\-hand side dominates:⌈log2⁡\(k\!\)⌉\\lceil\\log\_\{2\}\(k\!\)\\rceilgrows byΘ​\(log⁡k\)\\Theta\(\\log k\)per step while the left\-hand side increment is⌈log2⁡\(k\+2\)⌉−⌈log2⁡\(k\+1\)⌉=O​\(1\)\\lceil\\log\_\{2\}\(k\+2\)\\rceil\-\\lceil\\log\_\{2\}\(k\+1\)\\rceil=O\(1\)per step on the logarithm and one unit per step on the\(k\+1−ℓ\)\(k\+1\-\\ell\)factor\. Hence \([3](https://arxiv.org/html/2605.19521#A1.E3)\) holds strictly forℓ≥3\\ell\\geq 3and everyk∈\{ℓ,…,m−1\}k\\in\\\{\\ell,\\ldots,m\-1\\\}, giving strict decrease ofBB\.

Forℓ=2\\ell=2andk=2k=2: left\-hand side of \([3](https://arxiv.org/html/2605.19521#A1.E3)\) is⌈log2⁡3⌉⋅1=2\\lceil\\log\_\{2\}3\\rceil\\cdot 1=2, right\-hand side is2⋅1=22\\cdot 1=2; equality holds,B​\(3\)=B​\(2\)B\(3\)=B\(2\)\. Forℓ=2\\ell=2andk≥3k\\geq 3: left\-hand side=⌈log2⁡\(k\+1\)⌉​\(k−1\)=\\lceil\\log\_\{2\}\(k\+1\)\\rceil\(k\-1\), right\-hand side=2​⌈log2⁡\(k\!\)⌉=2\\lceil\\log\_\{2\}\(k\!\)\\rceil; strict inequality holds \(verified by the same growth argument\)\. Hence forℓ=2\\ell=2,BBis flat on\{k=2,k=3\}\\\{k=2,k=3\\\}and strictly decreasing fork≥3k\\geq 3\.

In both cases themm\-ranking minimisesBB\.

*Clause \(iii\): protocol choice givennn\.*Ifn≥\(mℓ\)​Tℓn\\geq\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}, branch \(i\) atλ=ℓ−1\\lambda=\\ell\-1is feasible; by clause \(i\) of this corollary, no ranking matches thisλ\\lambdaforℓ≥3\\ell\\geq 3, so theℓ\\ell\-chain is the minimum\-λ\\lambdafeasible protocol\. \(Forℓ=2\\ell=2theℓ\\ell\-chain and thek=2k=2ranking are the same protocol\.\)

Ifn<\(mℓ\)​Tℓn<\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}, branch \(i\) is infeasible at everyλ\\lambdasinceNchainN\_\{\\mathrm\{chain\}\}is independent ofkk\. Branch \(ii\) makes thekk\-ranking feasible iffn≥\(mℓ\)​Tℓ/\(kℓ\)n\\geq\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}/\\binom\{k\}\{\\ell\}, equivalently\(kℓ\)≥\(mℓ\)​Tℓ/n\\binom\{k\}\{\\ell\}\\geq\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}/n\. Since\(kℓ\)\\binom\{k\}\{\\ell\}and⌈log2⁡\(k\!\)⌉\\lceil\\log\_\{2\}\(k\!\)\\rceilare both monotone increasing inkk, the minimum\-λ\\lambdafeasible ranking corresponds to the smallestkksatisfying the inequality, namelyk∗k^\{\*\}as defined\. ∎

## Appendix BDeferred proofs

### B\.1Proof of[Proposition˜3\.2](https://arxiv.org/html/2605.19521#S3.Thmtheorem2)

See[3\.2](https://arxiv.org/html/2605.19521#S3.Thmtheorem2)

###### Proof\.

WriteXb:=𝟙​\[a≻b\]X\_\{b\}:=\\mathbbm\{1\}\[a\\succ b\]for eachb≠ab\\neq a, so thatra=m−∑b≠aXbr\_\{a\}=m\-\\sum\_\{b\\neq a\}X\_\{b\}\. Since variance is invariant under translations and sign flips,

Varπ⁡\(ra\)\\displaystyle\\operatorname\{Var\}\_\{\\pi\}\(r\_\{a\}\)=Varπ⁡\(∑b≠aXb\)=𝔼π​\[\(∑b≠aXb\)2\]−\(𝔼π​\[∑b≠aXb\]\)2\\displaystyle\\;=\\;\\operatorname\{Var\}\_\{\\pi\}\\\!\\Bigl\(\\,\\textstyle\\sum\_\{b\\neq a\}X\_\{b\}\\,\\Bigr\)\\;=\\;\\mathbb\{E\}\_\{\\pi\}\\\!\\Bigl\[\\Bigl\(\\textstyle\\sum\_\{b\\neq a\}X\_\{b\}\\Bigr\)^\{\\\!2\}\\,\\Bigr\]\\,\-\\,\\Bigl\(\\mathbb\{E\}\_\{\\pi\}\\\!\\Bigl\[\\textstyle\\sum\_\{b\\neq a\}X\_\{b\}\\Bigr\]\\Bigr\)^\{\\\!2\}
We now compute each term separately\. Expanding the first term,

𝔼π​\[\(∑b≠aXb\)2\]\\displaystyle\\mathbb\{E\}\_\{\\pi\}\\\!\\Bigl\[\\Bigl\(\\textstyle\\sum\_\{b\\neq a\}X\_\{b\}\\Bigr\)^\{\\\!2\}\\,\\Bigr\]=∑b≠a𝔼π​\[Xb2\]\+∑b,c≠ab≠c𝔼π​\[Xb​Xc\]\\displaystyle=\\sum\_\{b\\neq a\}\\mathbb\{E\}\_\{\\pi\}\[X\_\{b\}^\{2\}\]\+\\sum\_\{\\begin\{subarray\}\{c\}b,c\\neq a\\\\ b\\neq c\\end\{subarray\}\}\\\!\\\!\\mathbb\{E\}\_\{\\pi\}\[X\_\{b\}X\_\{c\}\]
SinceXb∈\{0,1\}X\_\{b\}\\in\\\{0,1\\\}, we haveXb2=XbX\_\{b\}^\{2\}=X\_\{b\}, hence

𝔼π​\[Xb2\]=𝔼π​\[Xb\]=pa​b\.\\mathbb\{E\}\_\{\\pi\}\[X\_\{b\}^\{2\}\]=\\mathbb\{E\}\_\{\\pi\}\[X\_\{b\}\]=p\_\{ab\}\.
Moreover, forb≠cb\\neq c,

Xb​Xb=𝟙​\[a≻b​and​a≻c\],X\_\{b\}X\_\{b\}=\\mathbbm\{1\}\[a\\succ b\\text\{ and \}a\\succ c\],so that

𝔼π​\[Xb​Xc\]=pa​b​c​\(a\)\.\\mathbb\{E\}\_\{\\pi\}\[X\_\{b\}X\_\{c\}\]=p\_\{abc\}\{\(a\)\}\.Thus,

𝔼π\[\(∑b≠aXb\)2\]=∑b≠apa​b\+\+∑b,c≠ab≠cpa​b​c\(a\)\.\\mathbb\{E\}\_\{\\pi\}\\\!\\Bigl\[\\Bigl\(\\textstyle\\sum\_\{b\\neq a\}X\_\{b\}\\Bigr\)^\{\\\!2\}\\,\\Bigr\]=\\sum\\limits\_\{b\\neq a\}p\_\{ab\}\+\+\\\!\\\!\\sum\_\{\\begin\{subarray\}\{c\}b,c\\neq a\\\\ b\\neq c\\end\{subarray\}\}\\\!\\\!p\_\{abc\}\{\(a\)\}\.
Regarding the second term,

\(𝔼π​\[∑b≠aXb\]\)2=∑b,c≠apa​b​pa​c\.\\Bigl\(\\mathbb\{E\}\_\{\\pi\}\\\!\\Bigl\[\\textstyle\\sum\_\{b\\neq a\}X\_\{b\}\\Bigr\]\\Bigr\)^\{\\\!2\}=\\sum\\limits\_\{b,c\\neq a\}p\_\{ab\}\\,p\_\{ac\}\.Combining the both terms yields

Varπ⁡\(ra\)=∑b≠apa​b\+∑b,c≠ab≠cpa​b​c​\(a\)−∑b,c≠apa​b​pa​c\.\\operatorname\{Var\}\_\{\\pi\}\(r\_\{a\}\)=\\sum\_\{b\\neq a\}p\_\{ab\}\+\\\!\\\!\\sum\_\{\\begin\{subarray\}\{c\}b,c\\neq a\\\\ b\\neq c\\end\{subarray\}\}\\\!\\\!p\_\{abc\}\{\(a\)\}\-\\sum\\limits\_\{b,c\\neq a\}p\_\{ab\}\\,p\_\{ac\}\.
Finally, separating diagonal and off\-diagonal terms in the last sum gives

Varπ⁡\(ra\)=∑b≠apa​b​\(1−pa​b\)\+∑b,c≠ab≠c\(pa​b​c​\(a\)−pa​b​pa​c\)\.\\operatorname\{Var\}\_\{\\pi\}\(r\_\{a\}\)\\;=\\;\\sum\_\{b\\neq a\}p\_\{ab\}\\,\(1\-p\_\{ab\}\)\\;\+\\\!\\\!\\sum\_\{\\begin\{subarray\}\{c\}b,c\\neq a\\\\ b\\neq c\\end\{subarray\}\}\\\!\\\!\\bigl\(\\,p\_\{abc\}\{\(a\)\}\-p\_\{ab\}\\,p\_\{ac\}\\,\\bigr\)\.∎

### B\.2Proof of[Proposition˜3\.3](https://arxiv.org/html/2605.19521#S3.Thmtheorem3)

See[3\.3](https://arxiv.org/html/2605.19521#S3.Thmtheorem3)

###### Proof\.

We recall that, by definition,

Divπ⁡\(a\):=1m−1​∑b∈𝒜∖\{a\}\|Borπ⁡\(a;𝒩πa≻b\)−Borπ⁡\(a;𝒩πb≻a\)\|\.\\displaystyle\\operatorname\{Div\}\_\{\\pi\}\(a\):=\\frac\{1\}\{m\-1\}\\sum\\nolimits\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}\\bigl\|\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{a\\succ b\}\_\{\\pi\}\\bigr\)\\;\-\\;\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{b\\succ a\}\_\{\\pi\}\\bigr\)\\bigr\|\.with

Borπ⁡\(a;𝒩πx≻y\):=∑b∈𝒜∖\{a\}ℙπ​\(a≻b∣x≻y\),\\displaystyle\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{x\\succ y\}\_\{\\pi\}\\bigr\):=\\sum\\nolimits\_\{b\\in\\mathcal\{A\}\\setminus\\\{a\\\}\}\\mathbb\{P\}\_\{\\pi\}\(a\\succ b\\mid x\\succ y\),
Using the identityra=1\+∑c≠a𝟙​\[c≻a\]r\_\{a\}=1\+\\sum\_\{c\\neq a\}\\mathbbm\{1\}\[c\\succ a\], and by linearity of conditional expectation, we obtain

𝔼π​\[ra∣ℰ\]=1\+∑c≠aℙπ​\[c≻a∣ℰ\]\.\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid\\mathcal\{E\}\]\\;=\\;1\+\\sum\_\{c\\neq a\}\\mathbb\{P\}\_\{\\pi\}\[c\\succ a\\mid\\mathcal\{E\}\]\.\(4\)Therefore,

Borπ⁡\(a;𝒩πx≻y\)=∑c≠aℙπ​\(a≻c∣x≻y\)=\(m−1\)−∑c≠aℙπ​\(c≻a∣x≻y\)=m−𝔼π​\[ra∣x≻y\]\.\\operatorname\{Bor\}\_\{\\pi\}\\bigl\(a;\\mathcal\{N\}^\{x\\succ y\}\_\{\\pi\}\\bigr\)=\\sum\_\{c\\neq a\}\\mathbb\{P\}\_\{\\pi\}\(a\\succ c\\mid x\\succ y\)=\(m\-1\)\-\\sum\_\{c\\neq a\}\\mathbb\{P\}\_\{\\pi\}\(c\\succ a\\mid x\\succ y\)=m\-\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid x\\succ y\]\.Finally, the divisiveness formula rewrites as

Divπ\(a\)=1m−1∑b≠a\|𝔼π\[ra∣b≻a\]−𝔼π\[ra∣a≻b\]\|\.\\operatorname\{Div\}\_\{\\pi\}\(a\)=\\frac\{1\}\{m\-1\}\\sum\_\{b\\neq a\}\\bigl\|\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid b\\succ a\]\-\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid a\\succ b\]\\bigr\|\.We now compute these conditional expectations\.

Computing𝔼π​\[ra∣b≻a\]\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid b\\succ a\]:By \([4](https://arxiv.org/html/2605.19521#A2.E4)\), we have

𝔼π​\[ra∣b≻a\]=1\+∑c≠aℙπ​\[c≻a∣b≻a\]\.\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid b\\succ a\]=1\+\\sum\_\{c\\neq a\}\\mathbb\{P\}\_\{\\pi\}\[c\\succ a\\mid b\\succ a\]\.
Forc=bc=b, we haveℙπ​\[b≻a∣b≻a\]=1\\mathbb\{P\}\_\{\\pi\}\[b\\succ a\\mid b\\succ a\]=1\.

Forc≠a,bc\\neq a,b, inclusion–exclusion gives

ℙπ​\[b≻a​and​c≻a\]=1−ℙπ​\[a≻b​or​a≻c\]=1−pa​b−pa​c\+pa​b​c​\(a\),\\mathbb\{P\}\_\{\\pi\}\[b\\succ a\\text\{ and \}c\\succ a\]\\;=\\;1\-\\mathbb\{P\}\_\{\\pi\}\[a\\succ b\\text\{ or \}a\\succ c\]\\;=\\;1\-p\_\{ab\}\-p\_\{ac\}\+p\_\{abc\}\{\(a\)\},and dividing byℙπ​\[b≻a\]=1−pa​b\\mathbb\{P\}\_\{\\pi\}\[b\\succ a\]=1\-p\_\{ab\}yields

ℙπ​\[c≻a∣b≻a\]=1−pa​b−pa​c\+pa​b​c​\(a\)1−pa​b=1\+pa​b​c​\(a\)−pa​c1−pa​b\.\\mathbb\{P\}\_\{\\pi\}\[c\\succ a\\mid b\\succ a\]\\;=\\;\\frac\{1\-p\_\{ab\}\-p\_\{ac\}\+p\_\{abc\}\{\(a\)\}\}\{1\-p\_\{ab\}\}\\;=\\;1\+\\frac\{p\_\{abc\}\{\(a\)\}\-p\_\{ac\}\}\{1\-p\_\{ab\}\}\.Summing over allm−2m\-2termsc≠a,bc\\neq a,band adding thec=bc=bterm gives:

𝔼π​\[ra∣b≻a\]\\displaystyle\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid b\\succ a\]=1\+1\+\(m−2\)\+11−pa​b​∑c≠a,b\(pa​b​c​\(a\)−pa​c\)\\displaystyle\\;=\\;1\+1\+\(m\-2\)\+\\frac\{1\}\{1\-p\_\{ab\}\}\\\!\\\!\\sum\_\{c\\neq a,b\}\\\!\\\!\\bigl\(p\_\{abc\}\{\(a\)\}\-p\_\{ac\}\\bigr\)=m\+11−pa​b​∑c≠a,b\(pa​b​c​\(a\)−pa​c\)\.\\displaystyle\\;=\\;m\+\\frac\{1\}\{1\-p\_\{ab\}\}\\\!\\\!\\sum\_\{c\\neq a,b\}\\\!\\\!\\bigl\(p\_\{abc\}\{\(a\)\}\-p\_\{ac\}\\bigr\)\.
Computing𝔼π​\[ra∣b≻a\]\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid b\\succ a\]:By \([4](https://arxiv.org/html/2605.19521#A2.E4)\), we have

𝔼π​\[ra∣a≻b\]=1\+∑c≠aℙπ​\[c≻a∣a≻b\]\.\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid a\\succ b\]=1\+\\sum\_\{c\\neq a\}\\mathbb\{P\}\_\{\\pi\}\[c\\succ a\\mid a\\succ b\]\.Forc=bc=b, we haveℙπ​\[b≻a∣a≻b\]=0\\mathbb\{P\}\_\{\\pi\}\[b\\succ a\\mid a\\succ b\]=0\.

Forc≠a,bc\\neq a,b,

ℙπ​\[c≻a∣a≻b\]=1−ℙπ​\[a≻c∣a≻b\]=1−ℙπ​\[a≻b​and​a≻c\]pa​b=1−p\{a,b,c\}​\(a\)pa​b\.\\mathbb\{P\}\_\{\\pi\}\[c\\succ a\\mid a\\succ b\]\\;=\\;1\-\\mathbb\{P\}\_\{\\pi\}\[a\\succ c\\mid a\\succ b\]\\;=\\;1\-\\frac\{\\mathbb\{P\}\_\{\\pi\}\[a\\succ b\\text\{ and \}a\\succ c\]\}\{p\_\{ab\}\}\\;=\\;1\-\\frac\{p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\}\{p\_\{ab\}\}\.
Summing over all\(m−2\)\(m\-2\)termsc≠a,bc\\neq a,bin \([4](https://arxiv.org/html/2605.19521#A2.E4)\) gives

𝔼π​\[ra∣a≻b\]=1\+\(m−2\)−1pa​b​∑c≠a,bpa​b​c​\(a\)=m−1−1pa​b​∑c≠a,bpa​b​c​\(a\)\.\\displaystyle\\mathbb\{E\}\_\{\\pi\}\[r\_\{a\}\\mid a\\succ b\]\\;=\\;1\+\(m\-2\)\-\\frac\{1\}\{p\_\{ab\}\}\\\!\\\!\\sum\_\{c\\neq a,b\}\\\!\\\!p\_\{abc\}\{\(a\)\}\\;=\\;m\-1\-\\frac\{1\}\{p\_\{ab\}\}\\\!\\\!\\sum\_\{c\\neq a,b\}\\\!\\\!p\_\{abc\}\{\(a\)\}\.
Plugging these both expectation terms back to the divisiveness formula yields the desired result\. ∎

### B\.3Proof of[Proposition˜3\.4](https://arxiv.org/html/2605.19521#S3.Thmtheorem4)

See[3\.4](https://arxiv.org/html/2605.19521#S3.Thmtheorem4)

###### Proof\.

Setm=d\+2m=d\+2and fix a focal alternativea∈𝒜a\\in\\mathcal\{A\}\.

Letw=\(w1,…,wm\)w=\(w\_\{1\},\\ldots,w\_\{m\}\)be a probability distribution on rank positions ofaa, and defineπw\\pi\_\{w\}as follows: the rank ofaais drawn fromww, and the otherm−1m\-1alternatives are then placed uniformly at random among the remaining positions\.

We first computeSS\-plurality quantities involvingaa\. FixS∋aS\\ni awith\|S\|=s≥2\|S\|=s\\geq 2\. Conditioning on the positionra=jr\_\{a\}=j, the event thataais top withinSSoccurs exactly when all others−1s\-1alternatives ofSSare placed below positionjj\. Since these alternatives are distributed uniformly, this happens with probability

\(m−js−1\)m−1​s−1\.\\frac\{\\binom\{m\-j\}\{s\-1\}\}\{\{m\-1\}\{s\-1\}\}\.Taking expectation overrar\_\{a\}yields

pS​\(a\)​\(πw\)=∑j=1mwj​\(m−js−1\)\(m−1s−1\)\.p\_\{S\}\{\(a\)\}\(\\pi\_\{w\}\)\\;=\\;\\sum\_\{j=1\}^\{m\}w\_\{j\}\\,\\frac\{\\binom\{m\-j\}\{s\-1\}\}\{\\binom\{m\-1\}\{s\-1\}\}\.\(5\)
Thus,pS​\(a\)​\(πw\)p\_\{S\}\{\(a\)\}\(\\pi\_\{w\}\)is a linear functional ofwwdepending onSSonly through its sizess\. For subsetsS∌aS\\not\\ni a, symmetry among non\-focal alternatives implies that theirSS\-plurality quantities depend only onss, and therefore coincide across all profiles in the family\{πw\}\\\{\\pi\_\{w\}\\\}\.

Now letδ=w−w′∈ℝm\\delta=w\-w^\{\\prime\}\\in\\mathbb\{R\}^\{m\}\. From \([5](https://arxiv.org/html/2605.19521#A2.E5)\), two profilesπw\\pi\_\{w\}andπw′\\pi\_\{w^\{\\prime\}\}agree on all degreess≤ds\\leq dif and only if

∑j=1mδj​\(m−js−1\)=0for​s=\{1,…,d\},\\sum\_\{j=1\}^\{m\}\\delta\_\{j\}\\binom\{m\-j\}\{s\-1\}\\;=\\;0\\qquad\\text\{for \}s=\\\{1,\\ldots,d\\\},\(6\)a linear system ofddequations inm=d\+2m=d\+2unknowns\. Viewed as a function ofjj, the coefficient vector of an equation given a fixedssis a polynomial of degrees−1s\-1fors∈\{1,…,d\}s\\in\\\{1,\\ldots,d\\\}, producing polynomials of distinct degrees\. The coefficient matrix thus has rankddand the solution set of \([6](https://arxiv.org/html/2605.19521#A2.E6)\) has two free parameters\. The degree\-\(d\+1\)\(d\+1\)separation condition∑jδj​\(m−jd\)≠0\\sum\_\{j\}\\delta\_\{j\}\\binom\{m\-j\}\{d\}\\neq 0is governed by a polynomial of degreedd, which cannot be a linear combination of polynomials of strictly lower degree; it is therefore not implied by \([6](https://arxiv.org/html/2605.19521#A2.E6)\), and there existsδ∗\\delta^\{\*\}satisfying \([6](https://arxiv.org/html/2605.19521#A2.E6)\) while violating the separation equality\.

Takewwuniform on\{1,…,m\}\\\{1,\\ldots,m\\\}and setw′:=w\+t​δ∗w^\{\\prime\}:=w\+t\\,\\delta^\{\*\}for\|t\|\|t\|small\. Sinceδ∗\\delta^\{\*\}satisfies \([6](https://arxiv.org/html/2605.19521#A2.E6)\) ats=1s=1,∑jδj∗=0\\sum\_\{j\}\\delta^\{\*\}\_\{j\}=0, sow′w^\{\\prime\}still sums to11; sincewwhas strictly positive entries,w′w^\{\\prime\}stays non\-negative\. By construction,πw\\pi\_\{w\}andπw′\\pi\_\{w^\{\\prime\}\}agree at every degree≤d\\leq dand differ at degreed\+1d\+1\.

*Witness atd=3d=3,m=5m=5\.*Takew=\(15,15,15,15,15\)w=\\bigl\(\\tfrac\{1\}\{5\},\\tfrac\{1\}\{5\},\\tfrac\{1\}\{5\},\\tfrac\{1\}\{5\},\\tfrac\{1\}\{5\}\\bigr\)andw′=\(320,720,120,520,420\)w^\{\\prime\}=\\bigl\(\\tfrac\{3\}\{20\},\\tfrac\{7\}\{20\},\\tfrac\{1\}\{20\},\\tfrac\{5\}\{20\},\\tfrac\{4\}\{20\}\\bigr\), differing byδ∗=120⋅\(−1,3,−3,1,0\)\\delta^\{\*\}=\\tfrac\{1\}\{20\}\\cdot\(\-1,3,\-3,1,0\)\. Substituting in \([5](https://arxiv.org/html/2605.19521#A2.E5)\) givespS​\(a\)​\(πw\)=pS​\(a\)​\(πw′\)=1/\|S\|p\_\{S\}\{\(a\)\}\(\\pi\_\{w\}\)=p\_\{S\}\{\(a\)\}\(\\pi\_\{w^\{\\prime\}\}\)=1/\|S\|for every\|S\|∈\{2,3\}\|S\|\\in\\\{2,3\\\}; at\|S\|=4\|S\|=4the values are1/41/4and19/8019/80\. ∎

### B\.4Proof of[Theorem˜3\.6](https://arxiv.org/html/2605.19521#S3.Thmtheorem6)and consequences

###### Definition B\.1\(Aggregate plurality\)\.

Fora∈𝒜a\\in\\mathcal\{A\}ands≥0s\\geq 0,

Ps​\(a\):=∑T⊆𝒜∖\{a\}\|T\|=spT∪\{a\}​\(a\),P0​\(a\):=1\.P\_\{s\}\(a\)\\;:=\\;\\sum\_\{\\begin\{subarray\}\{c\}T\\subseteq\\mathcal\{A\}\\setminus\\\{a\\\}\\\\ \|T\|=s\\end\{subarray\}\}p\_\{T\\cup\\\{a\\\}\}\{\(a\)\},\\qquad P\_\{0\}\(a\):=1\.

###### Lemma B\.2\.

For everya∈𝒜a\\in\\mathcal\{A\}and everys≥0s\\geq 0,𝔼π​\[\(Was\)\]=Ps​\(a\)\\mathbb\{E\}\_\{\\pi\}\\bigl\[\\tbinom\{W\_\{a\}\}\{s\}\\bigr\]=P\_\{s\}\(a\)\.

###### Proof\.

ForT⊆𝒜∖\{a\}T\\subseteq\\mathcal\{A\}\\setminus\\\{a\\\}, the event “a≻ba\\succ bfor everyb∈Tb\\in T” has probabilitypT∪\{a\}​\(a\)p\_\{T\\cup\\\{a\\\}\}\{\(a\)\}and indicator∏b∈T𝟙​\[a≻b\]\\prod\_\{b\\in T\}\\mathbbm\{1\}\[a\\succ b\]\. Summing over\|T\|=s\|T\|=sand taking expectations,Ps​\(a\)=𝔼π​\[∑\|T\|=s∏b∈T𝟙​\[a≻b\]\]=𝔼π​\[\(Was\)\],P\_\{s\}\(a\)=\\mathbb\{E\}\_\{\\pi\}\\\!\\bigl\[\\sum\_\{\|T\|=s\}\\prod\_\{b\\in T\}\\mathbbm\{1\}\[a\\succ b\]\\bigr\]=\\mathbb\{E\}\_\{\\pi\}\\\!\\bigl\[\\tbinom\{W\_\{a\}\}\{s\}\\bigr\],where the second equality holds because∑\|T\|=s∏b∈T𝟙​\[a≻b\]\\sum\_\{\|T\|=s\}\\prod\_\{b\\in T\}\\mathbbm\{1\}\[a\\succ b\]counts the size\-sssubsets of\{b:a≻b\}\\\{b:a\\succ b\\\}\. ∎

See[3\.6](https://arxiv.org/html/2605.19521#S3.Thmtheorem6)

###### Proof\.

WriteXb:=𝟙​\[a≻b\]X\_\{b\}:=\\mathbbm\{1\}\[a\\succ b\]forb≠ab\\neq a, sora=m−∑b≠aXbr\_\{a\}=m\-\\sum\_\{b\\neq a\}X\_\{b\}andra−μa=−∑b≠a\(Xb−pa​b\)r\_\{a\}\-\\mu\_\{a\}=\-\\sum\_\{b\\neq a\}\(X\_\{b\}\-p\_\{ab\}\)\. SetB:=Bor⁡\(a\)B:=\\operatorname\{Bor\}\(a\)andg​\(X\):=\(∑b≠a\(Xb−pa​b\)\)kg\(X\):=\\bigl\(\\sum\_\{b\\neq a\}\(X\_\{b\}\-p\_\{ab\}\)\\bigr\)^\{k\}, givingMk​\(a\)=\(−1\)k​𝔼π​\[g​\(X\)\]M\_\{k\}\(a\)=\(\-1\)^\{k\}\\mathbb\{E\}\_\{\\pi\}\[g\(X\)\]\.

Since eachXb∈\{0,1\}X\_\{b\}\\in\\\{0,1\\\}andgghas total degree at mostkkin theXbX\_\{b\}’s \(it is thekk\-th power of a linear form\),ggreduces on\{0,1\}m−1\\\{0,1\\\}^\{m\-1\}to a multilinear polynomialg​\(X\)=∑\|T\|≤kγ​\(T\)​∏b∈TXbg\(X\)=\\sum\_\{\|T\|\\leq k\}\\gamma\(T\)\\prod\_\{b\\in T\}X\_\{b\}supported on subsetsT⊆𝒜∖\{a\}T\\subseteq\\mathcal\{A\}\\setminus\\\{a\\\}of size at mostkk\. Taking expectations,𝔼π​\[g​\(X\)\]=∑Tγ​\(T\)​pT∪\{a\}​\(a\)\\mathbb\{E\}\_\{\\pi\}\[g\(X\)\]=\\sum\_\{T\}\\gamma\(T\)\\,p\_\{T\\cup\\\{a\\\}\}\{\(a\)\}\(using[Lemma˜B\.2](https://arxiv.org/html/2605.19521#A2.Thmtheorem2)\)\.

By Möbius inversion on the subset lattice,γ​\(T\)=∑U⊆T\(−1\)\|T\|−\|U\|​g​\(eU\)\\gamma\(T\)=\\sum\_\{U\\subseteq T\}\(\-1\)^\{\|T\|\-\|U\|\}\\,g\(e\_\{U\}\), whereeU∈\{0,1\}m−1e\_\{U\}\\in\\\{0,1\\\}^\{m\-1\}is the indicator vector ofUU\. Evaluation atX=eUX=e\_\{U\}givesg​\(eU\)=\(\|U\|−B\)kg\(e\_\{U\}\)=\(\|U\|\-B\)^\{k\}, which depends onUUonly through\|U\|\|U\|, so the Möbius formula collapses toγ​\(T\)=∑j=0\|T\|\(−1\)\|T\|−j​\(\|T\|j\)​\(j−B\)k=c\|T\|​\(a\)\\gamma\(T\)=\\sum\_\{j=0\}^\{\|T\|\}\(\-1\)^\{\|T\|\-j\}\\binom\{\|T\|\}\{j\}\(j\-B\)^\{k\}=c\_\{\|T\|\}\(a\)withcs​\(a\)c\_\{s\}\(a\)as stated in the theorem\. Collecting bys=\|T\|s=\|T\|,0≤s≤k0\\leq s\\leq k, yields𝔼π​\[g​\(X\)\]=∑s=0kcs​\(a\)​Ps​\(a\)\\mathbb\{E\}\_\{\\pi\}\[g\(X\)\]=\\sum\_\{s=0\}^\{k\}c\_\{s\}\(a\)\\,P\_\{s\}\(a\), and multiplying by\(−1\)k\(\-1\)^\{k\}gives \([3\.6](https://arxiv.org/html/2605.19521#S3.Thmtheorem6)\)\. The right side depends onaaonly throughB=P1​\(a\)B=P\_\{1\}\(a\)and onπ\\pionly throughP0​\(a\),…,Pk​\(a\)P\_\{0\}\(a\),\\ldots,P\_\{k\}\(a\), hence on data of degree at mostk\+1k\+1\. ∎

###### Corollary B\.3\.

For everyk≥2k\\geq 2, thekk\-th central momentMk​\(a\)M\_\{k\}\(a\)has level exactlyk\+1k\+1\.

###### Proof\.

The upper bound is[Theorem˜3\.6](https://arxiv.org/html/2605.19521#S3.Thmtheorem6)\. For the lower bound, apply[Proposition˜3\.4](https://arxiv.org/html/2605.19521#S3.Thmtheorem4)withd=kd=k: the witness profilesπ,π′\\pi,\\pi^\{\\prime\}agree at every degree≤k\\leq k, soP0​\(a\),P1​\(a\),…,Pk−1​\(a\)P\_\{0\}\(a\),P\_\{1\}\(a\),\\ldots,P\_\{k\-1\}\(a\)coincide on the two profiles \(each is determined by degree\-≤k\\leq kdata\), and in particularBor⁡\(a\)=P1​\(a\)\\operatorname\{Bor\}\(a\)=P\_\{1\}\(a\)matches, makingc0​\(a\),…,ck​\(a\)c\_\{0\}\(a\),\\ldots,c\_\{k\}\(a\)identical on both profiles\. OnlyPk​\(a\)P\_\{k\}\(a\)differs \(it depends on degree\-\(k\+1\)\(k\+1\)data\)\. Sinceck​\(a\)=k\!≠0c\_\{k\}\(a\)=k\!\\neq 0\(thekk\-th forward difference of a monic degree\-kkpolynomial\), \([3\.6](https://arxiv.org/html/2605.19521#S3.Thmtheorem6)\) givesMk​\(a\)​\(π\)−Mk​\(a\)​\(π′\)=\(−1\)k​k\!⋅\(Pk​\(a\)​\(π\)−Pk​\(a\)​\(π′\)\)≠0M\_\{k\}\(a\)\(\\pi\)\-M\_\{k\}\(a\)\(\\pi^\{\\prime\}\)=\(\-1\)^\{k\}\\,k\!\\cdot\(P\_\{k\}\(a\)\(\\pi\)\-P\_\{k\}\(a\)\(\\pi^\{\\prime\}\)\)\\neq 0\. So no function of degree\-≤k\\leq kdata agrees withMkM\_\{k\}on these two profiles\. ∎

### B\.5Proof of[Proposition˜3\.7](https://arxiv.org/html/2605.19521#S3.Thmtheorem7)

See[3\.7](https://arxiv.org/html/2605.19521#S3.Thmtheorem7)

###### Proof\.

Under Plackett–Luce, the probability that a voter ranksaafirst amongSSis obtained by the sequential elimination rule: at each step, the next\-ranked alternative is drawn with probability proportional to its strenght\. Luce’s Choice Axiom givespS​\(a\)=va/∑x∈Svxp\_\{S\}\{\(a\)\}=v\_\{a\}/\\sum\_\{x\\in S\}v\_\{x\}directly\. Sincepa​b=va/\(va\+vb\)p\_\{ab\}=v\_\{a\}/\(v\_\{a\}\+v\_\{b\}\), the ratiova/vb=pa​b/\(1−pa​b\)v\_\{a\}/v\_\{b\}=p\_\{ab\}/\(1\-p\_\{ab\}\)is determined by pairwise data\. Fixing any reference alternativerr, we recoverva/vrv\_\{a\}/v\_\{r\}for allaa, and then

pS​\(a\)=va/vr∑x∈Svx/vr=pa​r/\(1−pa​r\)∑x∈Spx​r/\(1−px​r\),p\_\{S\}\{\(a\)\}=\\frac\{v\_\{a\}/v\_\{r\}\}\{\\sum\_\{x\\in S\}v\_\{x\}/v\_\{r\}\}=\\frac\{p\_\{ar\}/\(1\-p\_\{ar\}\)\}\{\\sum\_\{x\\in S\}p\_\{xr\}/\(1\-p\_\{xr\}\)\},which is a function of pairwise proportions alone\.

Regarding the formula for single\-peaked preferences, we prove it by induction on\|S\|\|S\|\.

*Base case \(\|S\|=2\|S\|=2\)\.*ForS=\{si,sj\}S=\\\{s\_\{i\},s\_\{j\}\\\}withi<ji<j:pS​\(si\)=psi​sjp\_\{S\}\{\(s\_\{i\}\)\}=p\_\{s\_\{i\}s\_\{j\}\}andpS​\(sj\)=1−psi​sjp\_\{S\}\{\(s\_\{j\}\)\}=1\-p\_\{s\_\{i\}s\_\{j\}\}, which matches \([3\.7](https://arxiv.org/html/2605.19521#S3.Thmtheorem7)\)\.

*Key lemma \(\|S\|=3\|S\|=3\)\.*Fora<b<ca<b<con the axis, single\-peakedness implies thatbbis never ranked last among\{a,b,c\}\\\{a,b,c\\\}: every voter’s peak is some elementxx, and ifx≤bx\\leq bthenb≻cb\\succ c\(closer to peak\), while ifx≥bx\\geq bthenb≻ab\\succ a\. In either casebbis not last\. Thereforeℙ​\(a≻b​and​c≻b\)=0\\mathbb\{P\}\(a\\succ b\\text\{ and \}c\\succ b\)=0\.

The three plurality scores sum to11and the “bbis last” event has probability zero, so:

p\{a,b,c\}​\(a\)\\displaystyle p\_\{\\\{a,b,c\\\}\}\{\(a\)\}=ℙ​\(a≻b​and​a≻c\)=ℙ​\(a≻b\)−ℙ​\(a≻b​and​c≻a\)\\displaystyle=\\mathbb\{P\}\(a\\succ b\\text\{ and \}a\\succ c\)=\\mathbb\{P\}\(a\\succ b\)\-\\mathbb\{P\}\(a\\succ b\\text\{ and \}c\\succ a\)=pa​b−ℙ​\(c≻a≻b\)=pa​b−\(pa​b−p\{a,b,c\}​\(a\)\)\.\\displaystyle=p\_\{ab\}\-\\mathbb\{P\}\(c\\succ a\\succ b\)=p\_\{ab\}\-\\bigl\(p\_\{ab\}\-p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\\bigr\)\.
Said differently: the events “aafirst”, “bbfirst”, “ccfirst” partition the probability space\. The event “bbfirst” decomposes as\{b≻a\}∩\{b≻c\}\\\{b\\succ a\\\}\\cap\\\{b\\succ c\\\}\. Since “bblast”=\{a≻b\}∩\{c≻b\}=\\\{a\\succ b\\\}\\cap\\\{c\\succ b\\\}has probability zero, we have :

p\{a,b,c\}​\(b\)\\displaystyle p\_\{\\\{a,b,c\\\}\}\{\(b\)\}=ℙ​\(b≻a​and​b≻c\)\\displaystyle=\\mathbb\{P\}\(b\\succ a\\text\{ and \}b\\succ c\)=1−ℙ​\(a≻b\)−ℙ​\(c≻b\)\+ℙ​\(a≻b​and​c≻b\)⏟=0\\displaystyle=1\-\\mathbb\{P\}\(a\\succ b\)\-\\mathbb\{P\}\(c\\succ b\)\+\\underbrace\{\\mathbb\{P\}\(a\\succ b\\text\{ and \}c\\succ b\)\}\_\{=\\,0\}=1−pa​b−\(1−pb​c\)=pb​c−pa​b\.\\displaystyle=1\-p\_\{ab\}\-\(1\-p\_\{bc\}\)=p\_\{bc\}\-p\_\{ab\}\.Thenp\{a,b,c\}​\(a\)=pa​bp\_\{\\\{a,b,c\\\}\}\{\(a\)\}=p\_\{ab\}andp\{a,b,c\}​\(c\)=1−pb​cp\_\{\\\{a,b,c\\\}\}\{\(c\)\}=1\-p\_\{bc\}follow fromp\{a,b,c\}​\(a\)\+p\{a,b,c\}​\(b\)\+p\{a,b,c\}​\(c\)=1p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\+p\_\{\\\{a,b,c\\\}\}\{\(b\)\}\+p\_\{\\\{a,b,c\\\}\}\{\(c\)\}=1andp\{a,b,c\}​\(a\)\+p\{a,b,c\}​\(b\)=pa​b\+\(pb​c−pa​b\)=pb​c=1−p\{a,b,c\}​\(c\)p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\+p\_\{\\\{a,b,c\\\}\}\{\(b\)\}=p\_\{ab\}\+\(p\_\{bc\}\-p\_\{ab\}\)=p\_\{bc\}=1\-p\_\{\\\{a,b,c\\\}\}\{\(c\)\}\.

*Inductive step\.*Suppose the formula holds for all subsets of sizek−1k\-1\. LetS=\{si1<⋯<sik\}S=\\\{s\_\{i\_\{1\}\}<\\cdots<s\_\{i\_\{k\}\}\\\}withk≥4k\\geq 4\. For the interior elementsijs\_\{i\_\{j\}\}with1<j<k1<j<k:

pS​\(sij\)=ℙ​\(sij≻sij−1​and​sij≻sij\+1​and​sij≻all others in​S\)\.p\_\{S\}\{\(s\_\{i\_\{j\}\}\)\}=\\mathbb\{P\}\\bigl\(s\_\{i\_\{j\}\}\\succ s\_\{i\_\{j\-1\}\}\\text\{ and \}s\_\{i\_\{j\}\}\\succ s\_\{i\_\{j\+1\}\}\\text\{ and \}s\_\{i\_\{j\}\}\\succ\\text\{all others in \}S\\bigr\)\.Single\-peakedness on the axis implies two monotonicity properties for any voter:

1. \(i\)ifa<b<ca<b<con the axis anda≻ba\\succ b, thena≻ca\\succ c;
2. \(ii\)ifa<b<ca<b<con the axis andc≻bc\\succ b, thenc≻ac\\succ a\.

By \(i\),sij≻sij\+1s\_\{i\_\{j\}\}\\succ s\_\{i\_\{j\+1\}\}impliessij≻siℓs\_\{i\_\{j\}\}\\succ s\_\{i\_\{\\ell\}\}for allℓ\>j\+1\\ell\>j\+1; by \(ii\),sij≻sij−1s\_\{i\_\{j\}\}\\succ s\_\{i\_\{j\-1\}\}impliessij≻siℓs\_\{i\_\{j\}\}\\succ s\_\{i\_\{\\ell\}\}for allℓ<j−1\\ell<j\-1\. Thereforesijs\_\{i\_\{j\}\}is first inSSif and only ifsijs\_\{i\_\{j\}\}is first in the three\-element subset\{sij−1,sij,sij\+1\}\\\{s\_\{i\_\{j\-1\}\},s\_\{i\_\{j\}\},s\_\{i\_\{j\+1\}\}\\\}\. By the base case, this probability ispsij​sij\+1−psij−1​sijp\_\{s\_\{i\_\{j\}\}s\_\{i\_\{j\+1\}\}\}\-p\_\{s\_\{i\_\{j\-1\}\}s\_\{i\_\{j\}\}\}\.

For the boundary elements:si1s\_\{i\_\{1\}\}is first inSSiffsi1≻si2s\_\{i\_\{1\}\}\\succ s\_\{i\_\{2\}\}\(by \(i\), this impliessi1≻siℓs\_\{i\_\{1\}\}\\succ s\_\{i\_\{\\ell\}\}for allℓ\>2\\ell\>2\), sopS​\(si1\)=psi1​si2p\_\{S\}\{\(s\_\{i\_\{1\}\}\)\}=p\_\{s\_\{i\_\{1\}\}s\_\{i\_\{2\}\}\}\. Similarly,siks\_\{i\_\{k\}\}is first iffsik≻sik−1s\_\{i\_\{k\}\}\\succ s\_\{i\_\{k\-1\}\}, givingpS​\(sik\)=1−psik−1​sikp\_\{S\}\{\(s\_\{i\_\{k\}\}\)\}=1\-p\_\{s\_\{i\_\{k\-1\}\}s\_\{i\_\{k\}\}\}\. ∎

### B\.6Proof of[Proposition˜4\.6](https://arxiv.org/html/2605.19521#S4.Thmtheorem6)

See[4\.6](https://arxiv.org/html/2605.19521#S4.Thmtheorem6)

###### Proof\.

Fix a subsetSSwith\|S\|=k\|S\|=kand an alternativea∈Sa\\in S\. Each pairwise comparison between elements ofSScreates an oriented link between two alternatives, and transitivity allows information to propagate along chains of such links\.

To determine whetheraais the top\-ranked element ofSS, all alternatives ofSSmust be reachable fromaathrough such a chain of links; otherwise, there exists someb∈S∖\{a\}b\\in S\\setminus\\\{a\\\}whose relation toaacan not be resolved\.

Any structure connecting allkkelements must contain at leastk−1k\-1links\. Therefore, any protocol must satisfyλ≥k−1\\lambda\\geq k\-1\. ∎

### B\.7Detailed derivation of[Theorem˜4\.5](https://arxiv.org/html/2605.19521#S4.Thmtheorem5)

###### Theorem B\.4\.

Fix a target degreeℓ≥2\\ell\\geq 2and anλ\\lambdabudgetλ\\lambdawithℓ−1≤λ≤m−1\\ell\-1\\leq\\lambda\\leq m\-1\. To estimate every degree\-ℓ\\ellentry of the plurality matrix to accuracyε\\varepsilonwith probability at least1−δ1\-\\delta:

1. *\(i\)**Chains\.*Setk=λ\+1k=\\lambda\+1\. Akk\-chain requiresNchain:=\(mℓ\)​TℓN\_\{\\mathrm\{chain\}\}:=\\binom\{m\}\{\\ell\}T\_\{\\ell\}queries, with total budgetBchain=Nchain⋅λB\_\{\\mathrm\{chain\}\}=N\_\{\\mathrm\{chain\}\}\\cdot\\lambda\.
2. *\(ii\)**Rankings\.*Ifλ≥⌈log2⁡\(ℓ\!\)⌉\\lambda\\geq\\lceil\\log\_\{2\}\(\\ell\!\)\\rceil, definek​\(λ\):=max⁡\{k∈\[ℓ,m\]:⌈log2⁡\(k\!\)⌉≤λ\}k\(\\lambda\):=\\max\\\{k\\in\[\\ell,m\]:\\lceil\\log\_\{2\}\(k\!\)\\rceil\\leq\\lambda\\\}\. Ak​\(λ\)k\(\\lambda\)\-ranking requiresNrank:=\(mℓ\)​Tℓ/\(k​\(λ\)ℓ\)N\_\{\\mathrm\{rank\}\}:=\\binom\{m\}\{\\ell\}T\_\{\\ell\}\\big/\\binom\{k\(\\lambda\)\}\{\\ell\}queries, with total budgetBrank=Nrank⋅⌈log2⁡\(k​\(λ\)\!\)⌉≤Nrank​λB\_\{\\mathrm\{rank\}\}=N\_\{\\mathrm\{rank\}\}\\cdot\\lceil\\log\_\{2\}\(k\(\\lambda\)\!\)\\rceil\\leq N\_\{\\mathrm\{rank\}\}\\lambda\. Ifλ<⌈log2⁡\(ℓ\!\)⌉\\lambda<\\lceil\\log\_\{2\}\(\\ell\!\)\\rceil, no ranking protocol is feasible\.

###### Proof\.

*Proof of \(i\): chain branch\.*The k\-chain protocol admits any schedule that assigns each size\-ℓ\\ellsubsetT⊆𝒜T\\subseteq\\mathcal\{A\}exactlyTℓT\_\{\\ell\}chain steps; we take the simplest such allocation, which usesNchain=\(mℓ\)​TℓN\_\{\\mathrm\{chain\}\}=\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\}steps\. ForN\>NchainN\>N\_\{\\mathrm\{chain\}\}, allocate the firstNchainN\_\{\\mathrm\{chain\}\}steps as below; the remainingN−NchainN\-N\_\{\\mathrm\{chain\}\}steps may be used arbitrarily without affecting the accuracy guarantee\.

For each step assigned toTT, choose a size\-kksupersetS⊇TS\\supseteq T\(e\.g\., by addingk−ℓk\-\\ellfiller alternatives\) and an orderingτ=\(a1,…,ak\)\\tau=\(a\_\{1\},\\ldots,a\_\{k\}\)ofSSin which the firstℓ\\ellpositions form a permutation ofTT\. Run theSS\-chain with orderingτ\\tauon a fresh voterσ∈𝒱\\sigma\\in\\mathcal\{V\}not previously queried and record the prefix\-ℓ\\ellwinnerwℓw\_\{\\ell\}\.

By induction on the chain rounds, the winner of the prefix\{a1,…,aj\}\\\{a\_\{1\},\\ldots,a\_\{j\}\\\}after roundj−1j\-1is the top of\{a1,…,aj\}\\\{a\_\{1\},\\ldots,a\_\{j\}\\\}inσ\\sigma’s restriction to that prefix; this is exactly transitivity ofσ\\sigma\. In particular,wℓw\_\{\\ell\}is the top ofTTinσ\|T\\sigma\|\_\{T\}, so for eacha∈Ta\\in T,

ℙσ​\[wℓ=a\]=pT​\(a\)\.\\mathbb\{P\}\_\{\\sigma\}\[w\_\{\\ell\}=a\]\\;=\\;p\_\{T\}\{\(a\)\}\.The single observationwℓw\_\{\\ell\}thus yieldsℓ\\ellcorrelated indicators\{𝟙​\[wℓ=a\]\}a∈T\\\{\\mathbbm\{1\}\[w\_\{\\ell\}=a\]\\\}\_\{a\\in T\}, each marginallyBer​\(pT​\(a\)\)\\text\{Ber\}\(p\_\{T\}\{\(a\)\}\)\. Across theTℓT\_\{\\ell\}steps assigned toTT, voters are drawn independently fromπ\\pi, so for each fixeda∈Ta\\in TtheTℓT\_\{\\ell\}indicators are i\.i\.d\. The pairwise correlation among indicators sharing a step is irrelevant: Hoeffding applies separately to each pair\(T,a\)\(T,a\), and the union bound overQℓQ\_\{\\ell\}pairs closes the argument\.

For the cost, eachkk\-chain step uses exactlyk−1=λk\-1=\\lambdapairwise comparisons, henceλ=λ\\lambda=\\lambdaandBchain=N⋅λB\_\{\\mathrm\{chain\}\}=N\\cdot\\lambda\.

*Proof of \(ii\): ranking branch\.*Setk:=k​\(λ\)k:=k\(\\lambda\)\. The k\-ranking protocol admits any schedule that produces a sequenceS1,…,SNS\_\{1\},\\ldots,S\_\{N\}of size\-kksubsets such that every size\-ℓ\\ellsubsetT⊆𝒜T\\subseteq\\mathcal\{A\}is contained in at leastTℓT\_\{\\ell\}of them\. Counting incidences in two ways, this requires

N​\(kℓ\)≥\(mℓ\)​Tℓ,N\\binom\{k\}\{\\ell\}\\;\\geq\\;\\binom\{m\}\{\\ell\}\\,T\_\{\\ell\},which is exactlyN≥NrankN\\geq N\_\{\\mathrm\{rank\}\}\. ForNNabove this bound by a\(1\+o​\(1\)\)\(1\+o\(1\)\)factor, uniform random sampling realizes the required covering count with high probability by a Chernoff bound\.

For each stepii, elicit akk\-ranking ofSiS\_\{i\}from a fresh voterσi∈𝒱\\sigma\_\{i\}\\in\\mathcal\{V\}not previously queried\. The ranking disclosesσi\\sigma\_\{i\}’s restriction toSiS\_\{i\}, and by transitivity this restriction determines the top of everyT⊆SiT\\subseteq S\_\{i\}\. For each pair\(T,a\)\(T,a\)withT⊆SiT\\subseteq S\_\{i\}anda∈Ta\\in T, the indicator𝟙​\[a​tops​T​in​σi\|T\]\\mathbbm\{1\}\[a\\text\{ tops \}T\\text\{ in \}\\sigma\_\{i\}\|\_\{T\}\]is therefore aBer​\(pT​\(a\)\)\\text\{Ber\}\(p\_\{T\}\{\(a\)\}\)sample\. Voters across steps are independent, so for any fixed pair\(T,a\)\(T,a\)the samples drawn from the \(at leastTℓT\_\{\\ell\}\) steps withT⊆SiT\\subseteq S\_\{i\}are i\.i\.d\. Hoeffding plus the union bound close the argument as in branch \(i\)\.

For the cost, each ranking step requires⌈log2⁡\(k\!\)⌉\\lceil\\log\_\{2\}\(k\!\)\\rceilpairwise comparisons\. The lower bound is information\-theoretic: sortingkkitems by binary comparisons demands at least⌈log2⁡\(k\!\)⌉\\lceil\\log\_\{2\}\(k\!\)\\rceilqueries, since each query reveals one bit andk\!k\!orderings must be distinguishable\. The upper bound is achieved up to lower\-order additive terms by Ford\-Johnson merge\-insertion sort, which lies withinlog2⁡\(k\!\)\+O​\(1\)\\log\_\{2\}\(k\!\)\+O\(1\)for smallkkand within\(1\+o​\(1\)\)​log2⁡\(k\!\)\(1\+o\(1\)\)\\log\_\{2\}\(k\!\)asymptotically\. By definition ofk​\(λ\)k\(\\lambda\),⌈log2⁡\(k​\(λ\)\!\)⌉≤λ\\lceil\\log\_\{2\}\(k\(\\lambda\)\!\)\\rceil\\leq\\lambda, so the per\-voter cost respects theλ\\lambdaconstraint, and

Brank=N⋅⌈log2⁡\(k​\(λ\)\!\)⌉≤N⋅λ\.B\_\{\\mathrm\{rank\}\}=N\\cdot\\lceil\\log\_\{2\}\(k\(\\lambda\)\!\)\\rceil\\leq N\\cdot\\lambda\.∎

## Appendix CAdditional Experiments

### C\.1Synthetic Data

We provide an informal explanation for the empirical observation in[Figure˜2](https://arxiv.org/html/2605.19521#S3.F2)that several structured preference models \(single\-peaked, Plackett–Luce and Euclidean\) yield unimodal rank distributions for most alternatives/

#### A common intuition

Across these models, a similar phenomenon is observed: alternatives that occupy “central” positions in the underlying structure are more likely to be ranked highly across voters, while “extreme” alternatives are less frequently top\-ranked\. This induces near\-unimodal distributions of ranks\. We will now specify how the notions of “central” and “extreme” translates under each of the structures\.

#### Single\-peaked preferences \(Walsh distribution\)\.

In the single\-peaked model, alternatives are ordered along an axisc1<c2<…<cmc\_\{1\}<c\_\{2\}<\\ldots<c\_\{m\}\. Each voter has their most preferred candidate \(peak\) somewhere on the axis, and their preference decrease as we move away from the peak towards each of the extremes\.

Given such an axes, there are two classical ways to sample rankings:

- \(i\)the Conitzer distribution, which samples the peak uniformly and then completes the ranking, and
- \(ii\)the Walsh distribution\(used in our experiments\), which samples uniformly from all rankings consistent with the axis\.

Under the Walsh distribution, the number of rankings compatible with a given peak depends strongly on its position: while there is a unique preference withc1c\_\{1\}\(resp\.cmc\_\{m\}\) as peak \(c1≻c2≻…≻cmc\_\{1\}\\succ c\_\{2\}\\succ\\ldots\\succ c\_\{m\}, resp\.cm≻cm−2≻…≻c1c\_\{m\}\\succ c\_\{m\-2\}\\succ\\ldots\\succ c\_\{1\}\), there are exponentially many compatible rankings with the peak corresponding to middle alternative of the axis\. As a result, peaks – and more generally high\-ranked alternatives– are overwhelmingly concentrated around the middle of the axis\. This induces unimodal rank distribution for most alternatives\.

#### Euclidean preferences\.

In thekk\-Euclidean model, both voters and alternatives are embedded inℝk\\mathbb\{R\}^\{k\}, and each voter ranks alternatives by increasing distance from their own position\. When both voters and alternatives are drawn from a roughly symmetric distribution \(e\.g\., uniformly over a bounded region\), alternatives near the geometric center of the space are, on average, closer to more voters\. Consequently, central alternatives are more likely to be top\-ranked, whereas peripheral alternatives tend to appear at lower positions\. This again creates a concentration of probability mass in the upper ranks, leading to unimodal rank distribution\.

#### Plackett–Luce model\.

In the Plackett–Luce model, each alternativeaais assigned a strength parametervav\_\{a\}, and rankings are generated sequentially: the top alternative is drawn with probability proportional to these strengths, then removed, and the process repeats on the remaining set\. When strengths are heterogeneous \(as in our experiments\), a small set of high\-strength alternatives dominates top positions in the ranking, while weaker alternatives are pushed toward lower ranks\. This induces a strong concentration of probability mass in high ranks for a few alternatives, again yielding unimodal rank distribution\.

### C\.2Experiment on election data

We now ask which regions of the moment plane are populated by real elections\. We use three datasets covering different scales and electoral settings, drawn from PrefLib\[[7](https://arxiv.org/html/2605.19521#bib.bib73)\]and from a French presidential election survey\[[5](https://arxiv.org/html/2605.19521#bib.bib20)\]\. For consistency with the synthetic experiment, each dataset is restricted to voters who provided complete rankings\.

![Refer to caption](https://arxiv.org/html/2605.19521v1/figs/fig_real.png)Figure 4:Pearson moment plane for three real\-election datasets: Glasgow STV city council elections \(208 alternatives\), New South Wales Legislative Assembly \(201 alternatives\), and the 2017 Voter Autrement online survey \(22 candidates\)\. Solid and dash\-dotted curves are the bounds from Figure[2](https://arxiv.org/html/2605.19521#S3.F2), with the upper envelope set for the largestmm\. Four highlighted candidates illustrate the four regions of the plane: Q1 \(Hamilton Ross, NSW\), Q2 \(Speakman Mark, NSW\), Q3 \(Marine Le Pen, Voter Autrement\), Q4 \(Jean\-Luc Mélenchon, Voter Autrement\)\. Inset histograms show the rank distribution of each highlighted candidate\.[Figure˜4](https://arxiv.org/html/2605.19521#A3.F4)shows that the moment plane is broadly populated\. Real elections do not concentrate near IC: alternatives appear throughout the feasible region, including positions deep in the asymmetric upper corners\. The four highlighted candidates illustrate the four regions identified in[Figure˜2](https://arxiv.org/html/2605.19521#S3.F2)\.

Le Pen and Mélenchon would both register as high\-disagreement alternatives under any measure based on rank variance alone\. The moment plane separates them\. The sign ofγ1\\gamma\_\{1\}tells which extreme of the rank scale concentrates the mass, and the magnitude ofγ2\\gamma\_\{2\}tells how heavy the tail toward the opposite extreme is\.

Speakman illustrates a different pattern\. His rank distribution is bimodal, and his position close to the lower parabola flags this directly\. Several other alternatives sit near the parabola in the NSW cloud\. Two\-camp polarization appears in real elections at non\-trivial frequency, which justify the use of a bimodality test to characterize disagreements\.

A caveat applies to all three datasets and most sharply to Voter Autrement: the figures use only voters who provided complete rankings\. Ranking 22 candidates fully is cognitively demanding, and voters who do so are likely highly engaged and politically informed\. Le Pen’s position should be read with this filter in mind: her vote share in 2017 French presidential first rounds has been near20%20\\%, considerably above what her moment\-plane position would suggest, consistent with a selection effect in which voters providing complete rankings underrepresent her actual base\.

## Appendix DInventory of measures and rules in theSS\-plurality hierarchy

In the main text we showed that the rank varianceVar⁡\(ra\)\\operatorname\{Var\}\(r\_\{a\}\), the Navarrete divisiveness, and the agreement indexA​\(π\)A\(\\pi\)admit closed forms inSS\-plurality coordinates, and that these forms place them at levels33,33, and22of the hierarchy respectively\. Beyond these three, a number of further disagreement measures, polarization indices, and aggregation rules from the social\-choice literature can be analyzed in the same way: each is either expressible as a function of\{pS​\(a\)\}S⊆𝒜,a∈S\\\{p\_\{S\}\{\(a\)\}\\\}\_\{S\\subseteq\\mathcal\{A\},\\,a\\in S\}at some finite levelℓ\\ell, or provably outside the hierarchy\. We collect the results of this analysis here\.

Table[3](https://arxiv.org/html/2605.19521#A4.T3)catalogs every measure and rule we have placed\. Subsec\.[D\.1](https://arxiv.org/html/2605.19521#A4.SS1)fixes the notation needed to read it\. Subsec\.[D\.1](https://arxiv.org/html/2605.19521#A4.SS1.SSS0.Px5)gives the long\-form expressions for the entries that the table abbreviates by equation number, with derivations where the closed form is new to this paper\.

Table 3:Aggregation rules and disagreement measures expressed inSS\-plurality form, grouped by purpose and sorted by informational level\. Long formulas are referenced by equation number; notations are in App\.[D\.1](https://arxiv.org/html/2605.19521#A4.SS1)\.LvlQuantitySS\-plurality formReferenceAggregation measuresLevel 2: pairwise, tournament\-family22BordaBor⁡\(a\)\\operatorname\{Bor\}\(a\)*\(score\)*∑b≠ap\{a,b\}​\(a\)\\sum\_\{b\\neq a\}p\_\{\\\{a,b\\\}\}\{\(a\)\}\[[20](https://arxiv.org/html/2605.19521#bib.bib1)\]22Copeland*\(rule\)*\#​\{b:pa​b\>12\}−\#​\{b:pa​b<12\}\\\#\\\{b:p\_\{ab\}\>\\tfrac\{1\}\{2\}\\\}\-\\\#\\\{b:p\_\{ab\}<\\tfrac\{1\}\{2\}\\\}\[[19](https://arxiv.org/html/2605.19521#bib.bib2)\]22Minimax*\(rule\)*minb≠a⁡p\{a,b\}​\(a\)\\min\_\{b\\neq a\}p\_\{\\\{a,b\\\}\}\{\(a\)\}\[[47](https://arxiv.org/html/2605.19521#bib.bib3),[36](https://arxiv.org/html/2605.19521#bib.bib4)\]22Kemeny*\(rule\)*arg⁡maxλ​∑a≻λbp\{a,b\}​\(a\)\\arg\\max\_\{\\lambda\}\\sum\_\{a\\succ\_\{\\lambda\}b\}p\_\{\\\{a,b\\\}\}\{\(a\)\}\[[34](https://arxiv.org/html/2605.19521#bib.bib5)\]22Slater, Ranked Pairs, Schulze*\(rule\)*computable from the tournament\{p\{a,b\}​\(a\)\}a,b\\\{p\_\{\\\{a,b\\\}\}\{\(a\)\}\\\}\_\{a,b\}\[[48](https://arxiv.org/html/2605.19521#bib.bib6),[55](https://arxiv.org/html/2605.19521#bib.bib7),[45](https://arxiv.org/html/2605.19521#bib.bib8)\]Levelkk\(parametric inkk\)kkkk\-wise Kemeny*\(rule\)*Eq\. \([7](https://arxiv.org/html/2605.19521#A4.E7)\)\[[29](https://arxiv.org/html/2605.19521#bib.bib9)\]Levelmm: positional, runoffmmPluralityℙ​\[ra=1\]\\mathbb\{P\}\[r\_\{a\}=1\]*\(rule\)*p𝒜​\(a\)p\_\{\\mathcal\{A\}\}\{\(a\)\}\[[20](https://arxiv.org/html/2605.19521#bib.bib1)\]mmAnti\-plurality1−ℙ​\[ra=m\]1\-\\mathbb\{P\}\[r\_\{a\}=m\]*\(rule\)*Eq\. \([9](https://arxiv.org/html/2605.19521#A4.E9)\)\[[40](https://arxiv.org/html/2605.19521#bib.bib10)\]mmkk\-approval,1<k<m−11<k<m\-1*\(rule\)*∑i≤kℙ​\[ra=i\]\\sum\_\{i\\leq k\}\\mathbb\{P\}\[r\_\{a\}=i\], partial sum of Eq\. \([8](https://arxiv.org/html/2605.19521#A4.E8)\)mmBucklin*\(rule\)*smallestkkwith∑i≤kℙ​\[ra=i\]≥12\\sum\_\{i\\leq k\}\\mathbb\{P\}\[r\_\{a\}=i\]\\geq\\tfrac\{1\}\{2\}\[[11](https://arxiv.org/html/2605.19521#bib.bib11)\]mmSTV / IRV*\(rule\)*recursivearg⁡mina∈S⁡pS​\(a\)\\arg\\min\_\{a\\in S\}p\_\{S\}\{\(a\)\}on shrinkingSS\[[54](https://arxiv.org/html/2605.19521#bib.bib48)\]Disagreement measuresLevel 2: pairwise22AgreementA​\(π\)A\(\\pi\), polarization1−A​\(π\)1\-A\(\\pi\)*\(profile\)*1\(m2\)​∑\{a,b\}\|2​p\{a,b\}​\(a\)−1\|\\tfrac\{1\}\{\\binom\{m\}\{2\}\}\\sum\_\{\\\{a,b\\\}\}\|2\\,p\_\{\\\{a,b\\\}\}\{\(a\)\}\-1\|\[[1](https://arxiv.org/html/2605.19521#bib.bib13),[12](https://arxiv.org/html/2605.19521#bib.bib32)\]22Generalized polarization family*\(profile\)*∑\{a,b\}f​\(p\{a,b\}​\(a\)\)\\sum\_\{\\\{a,b\\\}\}f\(p\_\{\\\{a,b\\\}\}\{\(a\)\}\)for a class offf\[[13](https://arxiv.org/html/2605.19521#bib.bib14)\]22DiversityΔKT​\(π\)\\Delta\_\{\\mathrm\{KT\}\}\(\\pi\)*\(profile\)*2​∑\{a,b\}p\{a,b\}​\(a\)​\(1−p\{a,b\}​\(a\)\)2\\sum\_\{\\\{a,b\\\}\}p\_\{\\\{a,b\\\}\}\{\(a\)\}\\,\(1\-p\_\{\\\{a,b\\\}\}\{\(a\)\}\)\[[32](https://arxiv.org/html/2605.19521#bib.bib19)\]22Partitioning ratioα​\(a,b\)\\alpha\(a,b\)*\(pair\)*2​min⁡\(pa​b,1−pa​b\)2\\min\(p\_\{ab\},\\,1\-p\_\{ab\}\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]Level 3: triple, divisiveness and conflict33Rank varianceVar⁡\(ra\)\\operatorname\{Var\}\(r\_\{a\}\)*\(per alt\.\)*Eq\. \([10](https://arxiv.org/html/2605.19521#A4.E10)\)\[[35](https://arxiv.org/html/2605.19521#bib.bib49)\]33Navarrete divisiveness*\(per alt\.\)*Eq\. \([11](https://arxiv.org/html/2605.19521#A4.E11)\)\[[41](https://arxiv.org/html/2605.19521#bib.bib62)\]33α\\alpha\-divisiveness,s=Bors=\\operatorname\{Bor\}*\(per alt\.\)*Eq\. \([12](https://arxiv.org/html/2605.19521#A4.E12)\)\[[16](https://arxiv.org/html/2605.19521#bib.bib17)\]33Discrepancyβ​\(a,b\)\\beta\(a,b\)*\(pair\)*Δ​\(a,b\)/\(m−1\)\\Delta\(a,b\)/\(m\-1\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]33Group imbalanceϕ​\(a,b\)\\phi\(a,b\)*\(pair\)*\|Bor⁡\(a\)−Bor⁡\(b\)\|/Δ​\(a,b\)\|\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)\|\\,/\\,\\Delta\(a,b\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]33Discrepancy balanceγ​\(a,b\)\\gamma\(a,b\)*\(pair\)*Eq\. \([16](https://arxiv.org/html/2605.19521#A4.E16)\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]33MaxSum \(most\-conflictual pair\)*\(rule\)*Eq\. \([17](https://arxiv.org/html/2605.19521#A4.E17)\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]33MaxNash*\(rule\)*Eq\. \([18](https://arxiv.org/html/2605.19521#A4.E18)\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]33MaxSwap*\(rule\)*Eq\. \([19](https://arxiv.org/html/2605.19521#A4.E19)\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]33pp\-MaxPolar,p\>0p\>0*\(rule\)*Eq\. \([20](https://arxiv.org/html/2605.19521#A4.E20)\)\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]Outside the hierarchyn/akk\-Kemeny distanceκk\\kappa\_\{k\}\(k≥2k\\geq 2\) and derivedP​\(E\)P\(E\),D​\(E\)D\(E\)*\(profile\)*inexpressible in\{pS​\(⋅\)\}\\\{p\_\{S\}\{\(\\cdot\)\}\\\}\[[24](https://arxiv.org/html/2605.19521#bib.bib16)\]n/aSpearman, Cayley distance\-based diversity*\(profile\)*inexpressible in\{pS​\(⋅\)\}\\\{p\_\{S\}\{\(\\cdot\)\}\\\}\[[32](https://arxiv.org/html/2605.19521#bib.bib19)\]n/aSupport\-based diversity \(\# distinct rankings\)*\(profile\)*inexpressible in\{pS​\(⋅\)\}\\\{p\_\{S\}\{\(\\cdot\)\}\\\}\[[32](https://arxiv.org/html/2605.19521#bib.bib19)\]n/aKarpov diversity orderings*\(profile\)*inexpressible in\{pS​\(⋅\)\}\\\{p\_\{S\}\{\(\\cdot\)\}\\\}\[[33](https://arxiv.org/html/2605.19521#bib.bib15)\]### D\.1Notation

We work overmmalternatives𝒜\\mathcal\{A\}and a profileπ\\pion𝒜\\mathcal\{A\}\.

#### SS\-plurality and pairwise\.

TheSS\-plurality ofaaonS∋aS\\ni ais

pS​\(a\)=ℙπ​\[a​ranked first in​S\],∑a∈SpS​\(a\)=1\.p\_\{S\}\{\(a\)\}=\\mathbb\{P\}\_\{\\pi\}\\bigl\[a\\text\{ ranked first in \}S\\bigr\],\\qquad\\sum\_\{a\\in S\}p\_\{S\}\{\(a\)\}=1\.Pairwise proportions are the level\-2 specialization,

pa​b=p\{a,b\}​\(a\)=ℙπ​\[a≻b\],pa​b\+pb​a=1\.p\_\{ab\}=p\_\{\\\{a,b\\\}\}\{\(a\)\}=\\mathbb\{P\}\_\{\\pi\}\[a\\succ b\],\\qquad p\_\{ab\}\+p\_\{ba\}=1\.

#### Borda and aggregateSS\-plurality\.

Bor⁡\(a\)\\displaystyle\\operatorname\{Bor\}\(a\)=∑b≠apa​b=𝔼π​\[m−ra\],\\displaystyle=\\sum\_\{b\\neq a\}p\_\{ab\}=\\mathbb\{E\}\_\{\\pi\}\[\\,m\-r\_\{a\}\\,\],Pk​\(a\)\\displaystyle P\_\{k\}\(a\)=∑T⊆𝒜∖\{a\},\|T\|=kpT∪\{a\}​\(a\),P0​\(a\)=1\.\\displaystyle=\\sum\_\{T\\subseteq\\mathcal\{A\}\\setminus\\\{a\\\},\\ \|T\|=k\}p\_\{T\\cup\\\{a\\\}\}\{\(a\)\},\\qquad P\_\{0\}\(a\)=1\.Pk​\(a\)P\_\{k\}\(a\)aggregates theSS\-plurality ofaaover allSSof sizek\+1k\+1containingaa\. NoteP1​\(a\)=Bor⁡\(a\)P\_\{1\}\(a\)=\\operatorname\{Bor\}\(a\)andPm−1​\(a\)=p𝒜​\(a\)P\_\{m\-1\}\(a\)=p\_\{\\mathcal\{A\}\}\{\(a\)\}\.

#### Expected rank\-distance\.

The expected absolute rank gap betweenaaandbb, used throughout the level\-3 disagreement entries, is

Δ​\(a,b\)=𝔼π​\[\|ra−rb\|\]\.\\Delta\(a,b\)=\\mathbb\{E\}\_\{\\pi\}\\bigl\[\\,\|r\_\{a\}\-r\_\{b\}\|\\,\\bigr\]\.Despite the shared symbol,Δ​\(a,b\)\\Delta\(a,b\)is unrelated to the profile\-level KT diversityΔKT​\(π\)\\Delta\_\{\\mathrm\{KT\}\}\(\\pi\)in Table[3](https://arxiv.org/html/2605.19521#A4.T3)\. Its closed form inSS\-plurality coordinates is given as Eq\. \([13](https://arxiv.org/html/2605.19521#A4.E13)\) below\.

#### Conditional rank\-distances\.

Δ\+​\(a,b\)=𝔼π​\[\|ra−rb\|\|a≻b\],Δ−​\(a,b\)=𝔼π​\[\|ra−rb\|\|b≻a\]\.\\Delta^\{\+\}\(a,b\)=\\mathbb\{E\}\_\{\\pi\}\\bigl\[\\,\|r\_\{a\}\-r\_\{b\}\|\\,\\big\|\\,a\\succ b\\,\\bigr\],\\qquad\\Delta^\{\-\}\(a,b\)=\\mathbb\{E\}\_\{\\pi\}\\bigl\[\\,\|r\_\{a\}\-r\_\{b\}\|\\,\\big\|\\,b\\succ a\\,\\bigr\]\.Closed forms are given as Eq\. \([14](https://arxiv.org/html/2605.19521#A4.E14)\)–\([15](https://arxiv.org/html/2605.19521#A4.E15)\)\.

#### Covariance kernel\.

Kb=∑c≠a,b\(p\{a,b,c\}​\(a\)−pa​b​pa​c\)=∑c≠a,bCovπ⁡\(𝟙​\[a≻b\],1​\[a≻c\]\)\.K\_\{b\}=\\sum\_\{c\\neq a,b\}\\bigl\(p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\-p\_\{ab\}\\,p\_\{ac\}\\bigr\)=\\sum\_\{c\\neq a,b\}\\operatorname\{Cov\}\_\{\\pi\}\\bigl\(\\mathbbm\{1\}\[a\\succ b\],\\,\\mathbbm\{1\}\[a\\succ c\]\\bigr\)\.
The expressions below correspond to the equation references in Table[3](https://arxiv.org/html/2605.19521#A4.T3)\.

### D\.2Aggregation rules\.

Withtopλ⁡\(S\)\\operatorname\{top\}\_\{\\lambda\}\(S\)denoting the alternative ranked first inSSby rankingλ\\lambda, thekk\-wise Kemeny rule of Gilbert et al\.\[[29](https://arxiv.org/html/2605.19521#bib.bib9)\]is

arg⁡minλ​∑ℓ=2k∑\|S\|=ℓ\(1−pS​\(topλ⁡\(S\)\)\)\.\\arg\\min\_\{\\lambda\}\\,\\sum\_\{\\ell=2\}^\{k\}\\sum\_\{\|S\|=\\ell\}\\bigl\(1\-p\_\{S\}\{\(\\operatorname\{top\}\_\{\\lambda\}\(S\)\)\}\\bigr\)\.\(7\)The level\-mminversion identity expresses the rank\-iifrequency in terms of\{Pk​\(a\)\}k\\\{P\_\{k\}\(a\)\\\}\_\{k\},

ℙπ​\[ra=i\]=∑k=m−im−1\(−1\)k−m\+i​\(km−i\)​Pk​\(a\),\\mathbb\{P\}\_\{\\pi\}\[r\_\{a\}=i\]=\\sum\_\{k=m\-i\}^\{m\-1\}\(\-1\)^\{k\-m\+i\}\\binom\{k\}\{m\-i\}\\,P\_\{k\}\(a\),\(8\)from which the anti\-plurality complement follows as thei=mi=mspecialization,

1−ℙπ​\[ra=m\]=1−∑k=0m−1\(−1\)k​Pk​\(a\)\.1\-\\mathbb\{P\}\_\{\\pi\}\[r\_\{a\}=m\]=1\-\\sum\_\{k=0\}^\{m\-1\}\(\-1\)^\{k\}\\,P\_\{k\}\(a\)\.\(9\)

### D\.3Rank variance\.

Varπ⁡\(ra\)=Bor⁡\(a\)​\(1−Bor⁡\(a\)\)\+2​∑\{b,c\}⊆𝒜∖\{a\}p\{a,b,c\}​\(a\)\.\\operatorname\{Var\}\_\{\\pi\}\(r\_\{a\}\)=\\operatorname\{Bor\}\(a\)\\bigl\(1\-\\operatorname\{Bor\}\(a\)\\bigr\)\+2\\sum\_\{\\\{b,c\\\}\\subseteq\\mathcal\{A\}\\setminus\\\{a\\\}\}p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\.\(10\)

### D\.4Navarrete et al\. Divisiveness\.

DivNav⁡\(a\)=1m−1​∑b≠a\|1\+Kbpa​b​\(1−pa​b\)\|\.\\operatorname\{Div\}\_\{\\mathrm\{Nav\}\}\(a\)=\\frac\{1\}\{m\-1\}\\sum\_\{b\\neq a\}\\biggl\|1\+\\frac\{K\_\{b\}\}\{p\_\{ab\}\\,\(1\-p\_\{ab\}\)\}\\biggr\|\.\(11\)

### D\.5α\\alpha\-Divisiveness\.

Theα\\alpha\-divisiveness\[[16](https://arxiv.org/html/2605.19521#bib.bib17)\]with Borda scoring is

DivαBor⁡\(a\)=1m−1​∑b≠a\(pa​b​\(1−pa​b\)\)α​\|Bor⁡\(a∣a≻b\)−Bor⁡\(a∣b≻a\)\|,\\operatorname\{Div\}\_\{\\alpha\}^\{\\operatorname\{Bor\}\}\(a\)=\\frac\{1\}\{m\-1\}\\sum\_\{b\\neq a\}\\bigl\(p\_\{ab\}\\,\(1\-p\_\{ab\}\)\\bigr\)^\{\\alpha\}\\,\\bigl\|\\operatorname\{Bor\}\(a\\mid a\\succ b\)\-\\operatorname\{Bor\}\(a\\mid b\\succ a\)\\bigr\|,\(12\)where the conditional Borda scores expand as

Bor⁡\(a∣a≻b\)\\displaystyle\\operatorname\{Bor\}\(a\\mid a\\succ b\)=1\+1pa​b​∑c≠a,bp\{a,b,c\}​\(a\),\\displaystyle=1\+\\frac\{1\}\{p\_\{ab\}\}\\sum\_\{c\\neq a,b\}p\_\{\\\{a,b,c\\\}\}\{\(a\)\},Bor⁡\(a∣b≻a\)\\displaystyle\\operatorname\{Bor\}\(a\\mid b\\succ a\)=11−pa​b​∑c≠a,b\(pa​c−p\{a,b,c\}​\(a\)\)\.\\displaystyle=\\frac\{1\}\{1\-p\_\{ab\}\}\\sum\_\{c\\neq a,b\}\\bigl\(p\_\{ac\}\-p\_\{\\\{a,b,c\\\}\}\{\(a\)\}\\bigr\)\.

### D\.6Expected rank\-distance\.

Δ​\(a,b\)\\displaystyle\\Delta\(a,b\)=2​\(m−1\)−Bor⁡\(a\)−Bor⁡\(b\)−2​∑c≠a,bp\{a,b,c\}​\(c\),\\displaystyle=2\(m\-1\)\-\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)\-2\\sum\_\{c\\neq a,b\}p\_\{\\\{a,b,c\\\}\}\{\(c\)\},\(13\)obtained from the triple\-ordering identity

ℙπ​\[c​between​a​and​b\]=2−2​p\{a,b,c\}​\(c\)−pa​c−pb​c,\\mathbb\{P\}\_\{\\pi\}\\bigl\[c\\text\{ between \}a\\text\{ and \}b\\bigr\]=2\-2\\,p\_\{\\\{a,b,c\\\}\}\{\(c\)\}\-p\_\{ac\}\-p\_\{bc\},summed overc≠a,bc\\neq a,b, together with∑c≠a,bpa​c=Bor⁡\(a\)−pa​b\\sum\_\{c\\neq a,b\}p\_\{ac\}=\\operatorname\{Bor\}\(a\)\-p\_\{ab\}\.

### D\.7Conditional rank\-distances\.

Δ\+​\(a,b\)\\displaystyle\\Delta^\{\+\}\(a,b\)=Δ​\(a,b\)\+Bor⁡\(a\)−Bor⁡\(b\)2​pa​b,\\displaystyle=\\frac\{\\Delta\(a,b\)\+\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)\}\{2\\,p\_\{ab\}\},\(14\)Δ−​\(a,b\)\\displaystyle\\Delta^\{\-\}\(a,b\)=Δ​\(a,b\)−Bor⁡\(a\)\+Bor⁡\(b\)2​\(1−pa​b\)\.\\displaystyle=\\frac\{\\Delta\(a,b\)\-\\operatorname\{Bor\}\(a\)\+\\operatorname\{Bor\}\(b\)\}\{2\\,\(1\-p\_\{ab\}\)\}\.\(15\)The first equality follows from total expectation,Δ​\(a,b\)=pa​b​Δ\+\+\(1−pa​b\)​Δ−\\Delta\(a,b\)=p\_\{ab\}\\,\\Delta^\{\+\}\+\(1\-p\_\{ab\}\)\\,\\Delta^\{\-\}; the closed form combines this with the signed identityBor⁡\(a\)−Bor⁡\(b\)=pa​b​Δ\+−\(1−pa​b\)​Δ−\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)=p\_\{ab\}\\,\\Delta^\{\+\}\-\(1\-p\_\{ab\}\)\\,\\Delta^\{\-\}\.

### D\.8Discrepancy balance\.

γ​\(a,b\)=min⁡\(Δ\+​\(a,b\)Δ−​\(a,b\),Δ−​\(a,b\)Δ\+​\(a,b\)\)\.\\gamma\(a,b\)=\\min\\\!\\left\(\\frac\{\\Delta^\{\+\}\(a,b\)\}\{\\Delta^\{\-\}\(a,b\)\},\\;\\frac\{\\Delta^\{\-\}\(a,b\)\}\{\\Delta^\{\+\}\(a,b\)\}\\right\)\.\(16\)

### D\.9Conflictual rule scores\.

Substituting \([13](https://arxiv.org/html/2605.19521#A4.E13)\)–\([15](https://arxiv.org/html/2605.19521#A4.E15)\) into the definitions of Delemazure et al\.\[[21](https://arxiv.org/html/2605.19521#bib.bib18)\]reduces each conflictual rule to a function ofΔ​\(a,b\)\\Delta\(a,b\),pa​bp\_\{ab\},Bor⁡\(a\)\\operatorname\{Bor\}\(a\), andBor⁡\(b\)\\operatorname\{Bor\}\(b\)\. Each rule selectsarg⁡max\{a,b\}\\arg\\max\_\{\\\{a,b\\\}\}of its score:

MaxSum​\(a,b\)\\displaystyle\\text\{MaxSum\}\(a,b\)=Δ​\(a,b\)\+\(1−2​pa​b\)​\(Bor⁡\(a\)−Bor⁡\(b\)\),\\displaystyle=\\Delta\(a,b\)\+\(1\-2\\,p\_\{ab\}\)\\bigl\(\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)\\bigr\),\(17\)MaxNash​\(a,b\)\\displaystyle\\text\{MaxNash\}\(a,b\)=Δ​\(a,b\)2−\(Bor⁡\(a\)−Bor⁡\(b\)\)2,\\displaystyle=\\Delta\(a,b\)^\{2\}\-\\bigl\(\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)\\bigr\)^\{2\},\(18\)MaxSwap​\(a,b\)\\displaystyle\\text\{MaxSwap\}\(a,b\)=Δ​\(a,b\)−\|Bor⁡\(a\)−Bor⁡\(b\)\|,\\displaystyle=\\Delta\(a,b\)\-\\bigl\|\\operatorname\{Bor\}\(a\)\-\\operatorname\{Bor\}\(b\)\\bigr\|,\(19\)p​\-MaxPolar​\(a,b\)\\displaystyle p\\text\{\-MaxPolar\}\(a,b\)=min⁡\(pa​b,1−pa​b\)⋅Δ​\(a,b\)p\.\\displaystyle=\\min\(p\_\{ab\},\\,1\-p\_\{ab\}\)\\cdot\\Delta\(a,b\)^\{p\}\.\(20\)All four scores depend on the level\-3 data\{p\{a,b,c\}​\(c\)\}c≠a,b\\\{p\_\{\\\{a,b,c\\\}\}\{\(c\)\}\\\}\_\{c\\neq a,b\}throughΔ​\(a,b\)\\Delta\(a,b\)in \([13](https://arxiv.org/html/2605.19521#A4.E13)\), together with the level\-2 data\{pa​b,Bor⁡\(⋅\)\}\\\{p\_\{ab\},\\operatorname\{Bor\}\(\\cdot\)\\\}\.