Mohamed Ouaguenouni1, Felipe Garrido-Lucero1, Umberto Grandi1, César Hidalgo2,3,4, Magdalena Tydrichova5
1. IRIT, Université Toulouse Capitole, Toulouse, France
2. Center for Collective Learning, IAST, Toulouse School of Economics, France
3. Center for Collective Learning, CIAS, Corvinus University of Budapest, Hungary
4. AMBS, University of Manchester, UK 5. Centrale Supélec, Paris Saclay, France
Théorie Algorithmique de la Décision et des Jeux (TADJ) · 21 June 2026
We have a set of alternatives \(\mathcal{A}\) (the candidates), and a set of voters.
Each voter ranks \(\mathcal{A}\) by a strict total order: complete and transitive.
Example: \(\mathcal{A} = \{a,b,c\}\), with its \(3! = 6\) orders.
order
\(\pi\)
\(a \succ b \succ c\)
0.22
\(a \succ c \succ b\)
0.08
\(b \succ a \succ c\)
0.15
\(b \succ c \succ a\)
0.30
\(c \succ a \succ b\)
0.05
\(c \succ b \succ a\)
0.20
A profile \(\pi\): the proportion of voters holding each order.
Objective
Understand how disagreement structures the population.
Sometimes that structure matters more than the consensus, and it guides the deliberation.
Voting in a digital democracy
People answer pairwise comparisons; across a population we observe only the proportions.
Pairwise answers
Voter 1\(a\succ b,\ \ a\succ c\)
Voter 2\(b\succ c,\ \ b\succ a\)
Voter 3\(a\succ b,\ \ b\succ c\)
\(\vdots\)
Pairwise proportions
\(p_{ab}=0.6\)
\(p_{ac}=0.5\)
\(p_{bc}=0.7\)
What's the difference?
\(p_{ab}\) and \(p_{ac}\) are marginals — they don't reveal the joint: the fraction of voters who prefer \(a\) to both \(b\) and \(c\) at once.
Why disagreement is harder to measure
Pairwise proportions power most voting rules — a tournament.
\(p_{ab} = \tfrac12\)
\(p_{ac} = \tfrac12\)
\(p_{bc} = \tfrac12\)
But the structure is harder — many populations share these proportions.
Rank distribution. \(\Pr[r_a{=}i]\): voters ranking \(a\) at position \(i\).
Antagonistic profile. two camps — half rank \(a\) first, half last.
1/31/31/3
123
Uniform
1/31/21/301/31/2
123
The same pairwise proportions fit both — one uniform, one split into two opposed camps. Pairwise data is blind to the structure of disagreement.
Collecting terms gives the formula above — degree 2 plus degree 3 entries.\(\quad\square\)
Proposition. The divisiveness is a measure of level 3:
\[ \mathrm{Div}(a) = \frac{1}{m-1}\sum_{b\neq a} \Big| 1 + \!\!\sum_{c\neq a,b}\!\! \Big[ p_{abc}(a)\Big(\tfrac{1}{1-p_{ab}} + \tfrac{1}{p_{ab}}\Big) - \tfrac{p_{ac}}{1-p_{ab}} \Big] \Big|. \]
Proof. Splitting voters by their verdict on \(\{a,b\}\), divisiveness is the gap in \(a\)'s mean rank between the two camps:
\[ \mathrm{Div}(a) = \frac{1}{m-1}\sum_{b\neq a} \big| \mathbb{E}[r_a \mid b\succ a] - \mathbb{E}[r_a \mid a\succ b] \big|. \]
Substituting both back gives the formula above — degree 2 and degree 3 entries.\(\quad\square\)
Common Thread
▸Why is the agreement index unable to distinguish the disagreement structure in \(\pi_{\mathrm{AN}}\)?
How to characterize the level of information used by a measure?
⇒Its level: the smallest degree of the plurality matrix it needs.
⇒Rank variance and divisiveness are level 3 — the degree-3 matrix, not the full profile.
⇒Most measures sit at level 2 (Borda, Copeland, agreement index) or level 3 (rank variance, divisiveness).
⇒Yet some structural disagreement stays invisible to every level-2 and level-3 measure.
Common Thread
▸Why is the agreement index unable to distinguish the disagreement structure in \(\pi_{\mathrm{AN}}\)?
▸How to characterize the level of information used by a measure?
⇒Its level: the smallest degree of the plurality matrix it needs.
⇒Rank variance and divisiveness are level 3 — the degree-3 matrix, not the full profile.
⇒Most measures sit at level 2 (Borda, Copeland, agreement index) or level 3 (rank variance, divisiveness).
⇒Yet some structural disagreement stays invisible to every level-2 and level-3 measure.
Can we find measures with a level higher than 3?
see →
Moments of the rank distribution
Central moment. For an alternative \(a\) with mean rank \(\mu_a = \mathbb{E}_\pi[r_a]\), the \(k\)-th central moment is \(\; M_k(a) := \mathbb{E}_\pi\big[(r_a - \mu_a)^k\big].\)
First moment. \(\;\mu_a = 1 + \sum_{b\neq a}(1 - p_{ab}) = m - \sum_{b\neq a} p_{ab} = m - \mathrm{Bor}(a)\)⇒proportional to the Borda score.
Second central moment. \(\; M_2(a) = \mathrm{Var}(a)\)⇒the rank variance (level 3).
Proposition. The \(k\)-th central moment is a measure of level \(k+1\):
\[ M_k(a) = (-1)^k \sum_{s=0}^{k} c_s(a) \!\!\sum_{\substack{S\subseteq\mathcal{A}\setminus\{a\}\\ |S|=s}}\!\! p_{S\cup\{a\}}(a), \]
where \(\;c_s(a) = \sum_{j=0}^{s} (-1)^{s-j}\binom{s}{j}\big(j - \mathrm{Bor}(a)\big)^{k}.\)
⇒skewness is level 4, excess kurtosis is level 5.
Common Thread
▸Why is the agreement index unable to distinguish the disagreement structure in \(\pi_{\mathrm{AN}}\)?
▸How to characterize the level of information used by a measure?
Can we find measures with a level higher than 3?
⇒Yes — the central moments of the rank distribution; the \(k\)-th is level \(k+1\).
⇒So skewness is level 4, and excess kurtosis is level 5.
⇒But are the moments above level 2 and 3 interpretable? see →
Sample a voter and a \(k\)-subset \(S=\{a,b,c,d\}\), \(k=|S|\).
Put it in a (random) query order.
Ask 1st vs 2nd; the winner faces the next, … — one sample per prefix.
a
b
c
d
→
→
→
\(\ell=2\)\(p_{\{b,d\}}(d)\)1
\(\ell=3\)\(p_{\{a,b,d\}}(a)\)1
\(\ell=4\)\(p_{\{a,b,c,d\}}(c)\)1
Which probe for a target degree?
\(k=|S|\) — the size of the queried subset (the \(k\) of a \(k\)-ranking / \(k\)-chain).
\(\ell\) — the degree of the plurality matrix we want to elicit.
A degree-\(\ell\) winner only appears in a subset of size \(\ge\ell\), so we need \(\;k\ge\ell\).
Proposition
To elicit degree \(\ell\), the minimum cognitive load is achieved by the \(\ell\)-chain \((k=\ell)\): \(\;\mathrm{MCL}=\ell-1\).
The two primitives, compared
\(k\)-Ranking
\(k\)-Chain
Cognitive loadper voter
\(\lceil\log_2 k!\rceil \approx k\log k\)
\(k-1\)
Independent samplesat degree \(\ell\)
\(\binom{k}{\ell}\)
\(1\)
Population vs cognitive load
For a fixed degree, the population and the per-voter load are tied by a precise law.
Theorem. Fix a degree \(k\). To estimate every degree-\(k\) entry of the plurality matrix to accuracy \(\varepsilon\) with probability \(1-\delta\):
a \(k\)-chain needs \(N = \binom{m}{k}\,T_k\) voters, at \(\mathrm{MCL} = k-1\);
a \(k\)-ranking needs \(N = \binom{m}{k}\,T_k \big/ (k\log k)\) voters, at \(\mathrm{MCL} = k\log k\).
where \(T_k = \ln(2Q_k/\delta)/(2\varepsilon^2)\) and \(Q_k = k\binom{m}{k}\) is the number of degree-\(k\) entries.
The ranking cuts the population by a factor \(k\log k\) — at a higher load per voter. More cognitive load per voter buys fewer voters.
↓ proof sketch — a worked case at degree 3
Proof sketch — degree \(\ell=3\)
Hoeffding. a cell \(p\) estimated from \(m\) independent samples obeys
\[ \Pr\!\big(|\hat p - p|\ge\varepsilon\big)\,\le\,2e^{-2m\varepsilon^{2}}
\;\Longrightarrow\; m \ge \frac{\ln(2/\delta)}{2\varepsilon^{2}} \approx 185
\;\;(\varepsilon=0.1,\ \delta=0.05). \]
Over all \(\binom{10}{3}=120\) degree-3 cells, \(\,M\approx 22{,}000\) samples. More samples per voter \(\Rightarrow\) fewer voters: \(\;N = M/(\text{samples/voter})\).
Probe
MCL
Samples / voter
Voters
3-chain
2
1
22,000
4-chain
3
1
22,000
5-chain
4
1
22,000
3-ranking
3
1
22,000
4-ranking
5
4
5,500
5-ranking
7
10
2,200
A chain yields one degree-3 sample for any \(k\) — the 3-chain is the cheapest probe (MCL 2); rankings buy fewer voters at a heavier load.
Population vs cognitive load — interactive
Fix any two of degree, population, cognitive load — the figure finds the third and the matching protocol.
