🔢 mathematics

Counting Votes with Multisets

Cet article démontre comment les propriétés catégoriques des multisets — plus précisément leur structure en tant que monoïde commutatif libre, foncteur et monade — peuvent être appliquées efficacement pour dériver et exprimer des résultats dans divers systèmes de vote, notamment le second tour à élimination instantanée, le système de De Borda et le vote à transfert unique.

Auteurs originaux : Bart Jacobs, Michael Johnson, Richard Buckland

Publié 2026-06-05

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Bart Jacobs, Michael Johnson, Richard Buckland

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous organisez un vote, mais au lieu de compter des bulletins de vote papier un par un, vous gérez un immense sac de billes colorées. C'est l'idée centrale de l'article : Les Multiensembles (Multisets).

Voici une décomposition simple de ce que les auteurs, Bart Jacobs, Michael Johnson et Richard Buckland proposent, en utilisant des analogies de la vie quotidienne.

1. Le sac magique (Qu'est-ce qu'un multiensemble ?)

D'habitude, en mathématiques, un « ensemble » est comme une liste d'éléments uniques. Si vous avez un ensemble de fruits, vous pouvez avoir une pomme et une banane, mais vous ne pouvez pas avoir « deux pommes » dans la définition de l'ensemble ; c'est juste « des pommes ».

Un Multiensemble est comme un sac de billes.

Si vous metvez 4 billes rouges, 3 billes bleues et 2 billes vertes dans un sac, l'ordre n'importe pas.
Ce qui compte, c'est le nombre.
Les auteurs écrivent cela ainsi : 4|R⟩ + 3|B⟩ + 2|G⟩.
Dans une élection, ce sac représente les votes. Peu importe qui a voté ou quand ils ont voté ; ce qui compte, c'est qu'il y a 4 votes pour Rouge, 3 pour Bleu et 2 pour Vert.

Pourquoi est-ce une bonne chose ?
Si vous conservez les votes sous forme de liste (comme un tableur), l'ordre de la liste pourrait accidentellement révéler qui a voté pour qui. Mais si vous jetez tout dans un « sac de multiensemble », l'ordre disparaît. Vous obtenez un décompte propre et anonyme, impossible à retracer jusqu'aux individus.

2. Les trois jeux de vote

L'article montre comment cette approche de « sac de billes » rend trois systèmes de vote complexes beaucoup plus faciles à comprendre et à calculer. Ils utilisent des termes mathématiques sophistiqués (comme « foncteurs » et « monades »), mais considérez-les comme des règles pour déplacer les billes.

Jeu A : Le vote à second tour instantané (Le jeu de l'« Élimination »)

Comment ça marche : Les électeurs classent les candidats (1er, 2e, 3e). Si personne n'obtient 50 % des voix, la personne qui a le moins de voix est éliminée. Ses voix sont alors attribuées au deuxième choix des électeurs.
L'astuce du multiensemble : Imaginez que votre sac de bulletins soit une pile de listes.
1. Vous regardez le haut de chaque liste (le 1er choix) et comptez les billes.
2. Vous trouvez le perdant (Candidat C).
3. Vous utilisez une « gomme magique » (appelée foncteur dans l'article) pour supprimer le Candidat C de chaque liste dans le sac.
4. Maintenant, les 2e choix deviennent les nouveaux 1ers choix. Vous comptez à nouveau le sac.
5. Vous répétez l'opération jusqu'à ce que quelqu'un ait une majorité.
Le bénéfice : Au lieu de rayer manuellement des noms sur des milliers de papiers, vous appliquez simplement la règle de « suppression » à l'ensemble du sac d'un seul coup.

Jeu B : Le décompte de Borda (Le jeu des « Points pondérés »)

Comment ça marche : Les électeurs classent les candidats. Le 1er choix reçoit 4 points, le 2e reçoit 3 points, le 3e reçoit 2 points, etc. Les points de chacun sont ensuite additionnés.
L'astuce du multiensemble :
1. Au lieu de simplement compter les votes, vous transformez chaque bulletin en un mini-sac de billes pondérées. Un bulletin disant « A, B, C, D » devient 4|A⟩ + 3|B⟩ + 2|C⟩ + 1|D⟩.
2. Vous jetez tous ces mini-sacs dans un seul grand super-sac.
3. Vous utilisez un outil d'« aplatissement » (appelé monade) pour écraser toutes les couches ensemble.
4. Le résultat est un seul grand décompte des points totaux pour chaque candidat.
Le bénéfice : Cela transforme un problème mathématique complexe en une simple opération d'« addition de tout ».

Jeu C : Le vote préférentiel à scrutin unique (Le jeu du « Partage du surplus »)

Comment ça marche : Ceci est utilisé pour élire plusieurs personnes (comme un conseil municipal). Il existe un « quota » (un nombre minimum de voix nécessaires pour gagner). Si un candidat obtient bien plus de voix que nécessaire, ses voix excédentaires ne devraient pas être gaspillées ; elles devraient être transférées au choix suivant des électeurs.
L'astuce du multiensemble :
1. Imaginez qu'un candidat gagne avec 93 voix, mais que le quota n'est que de 63. Il a 30 voix de « surplus ».
2. Au lieu de choisir 30 bulletins au hasard pour le transfert (ce qui serait injuste), les auteurs suggèrent une astuce mathématique : Dévaluer les votes.
3. Vous prenez toutes les 93 voix pour ce gagnant et vous les réduisez selon une fraction spécifique (comme le rétrécissement d'une photo).
4. Vous « supprimez » ensuite le gagnant des listes et transférez ces voix « réduites » aux candidats suivants.
5. Cela permet aux mathématiques de gérer parfaitement les fractions de votes, garantissant qu'aucun vote n'est gaspillé ou compté deux fois.

3. Pourquoi est-ce important ?

Les auteurs n'essaient pas d'inventer un nouveau type de mathématiques ; ils montrent que les mathématiques anciennes (la Théorie des Catégories) sont l'outil parfait pour le vote moderne.

Transparence : Parce que les multiensembles ignorent l'ordre des votes, le processus de comptage est mathématiquement garanti comme étant anonyme.
Simplicité : Des règles complexes (comme supprimer des perdants ou diviser les surplus de votes) deviennent de simples opérations sur un sac de billes.
Exactitude : Si vous écrivez un programme informatique pour compter les votes en utilisant ces règles de « sacs », il est beaucoup plus difficile de commettre une erreur que si vous essayez de trier des piles de papier.

En résumé : L'article soutient que si nous cessons de considérer les votes comme un tas désordonné de papiers et commençons à les considérer comme un sac de billes colorées, nous pouvons utiliser des règles mathématiques simples et puissantes pour les compter de manière équitable, rapide et sans erreur.

Résumé Technique : Comptage des Votes avec des Multiensembles

Énoncé du Problème
L'article traite du défi que représente la description, l'explication et l'implémentation d'algorithmes de comptage de votes pour des systèmes électoraux complexes, particulièrement ceux impliquant le vote préférentiel (préférences) et de multiples options pondérées. Alors que les élections simples (par exemple, deux candidats, un vote unique) peuvent être décrites via des listes ou des comptages simples, les mécanismes tels que le vote à élimination instantanée (IRV), le compte de De Borda et le vote à scrutin unique transférable (STV) impliquent le transfert de surplus de voix, l'élimination de candidats et la repondération des préférences. Les auteurs soutiennent que les types de données standards comme les listes sont sous-optimaux pour ces tâches car ils conservent l'ordre (ce qui est non pertinent pour le résultat) et peuvent divulguer des informations concernant la séquence de vote, compromettant potentiellement la confidentialité. De plus, l'implémentation de ces algorithmes avec des listes conduit souvent à un code complexe et ad hoc, difficile à vérifier en termes de correction et de transparence.

Méthodologie
L'article propose de modéliser les résultats électoraux et les processus de comptage de votes en utilisant des multiensembles (ensembles où les éléments peuvent apparaître plusieurs fois) plutôt que des listes. Les auteurs emploient des techniques élémentaires de la théorie des catégories pour formaliser les opérations sur ces multiensembles. La méthodologie centrale implique :

Sélection du Type de Donnée : Représenter une collection de votes comme un multiensemble $N(X)$ (ou $M(X)$ pour les votes fractionnaires), où les éléments sont les candidats et les multiplicités sont les comptes de votes. Cela fait abstraction de l'ordre des votes.
Structures Catégoriques : Les auteurs utilisent trois propriétés catégoriques spécifiques des multiensembles pour dériver et exprimer les algorithmes de vote :
- Monoïde Commutatif : Les multiensembles forment un monoïde commutatif libre, permettant l'addition des comptes de votes (union d'urnes) où l'ordre est non pertinent.
- Functorialité : La construction du multiensemble $N$ agit comme un foncteur. Cela permet aux fonctions définies sur les candidats (par exemple, "tête de liste" ou "supprimer candidat") d'être élevées à des fonctions sur des multiensembles de listes. Cette propriété est utilisée pour agréger les premières préférences et pour redistribuer les votes lorsqu'un candidat est éliminé.
- Structure de Monade : Les multiensembles forment une monade avec unit (création d'un multiensemble singleton) et flatten (effondrement d'un multiensemble de multiensembles). Cette structure est utilisée pour gérer les comptes pondérés où un vote unique (une liste de préférences) est décomposé en contributions pondérées à plusieurs candidats.

Contributions Clés et Résultats
L'article démontre l'application de ces structures catégoriques à travers trois mécanismes de vote spécifiques, utilisant de petits exemples (vérifiés via des scripts Python de la bibliothèque EfProb) pour illustrer l'abstraction :

Vote à Élimination Instantanée (IRV) :
- Mécanisme : Les candidats ayant le moins de premières préférences sont éliminés de manière itérative, et leurs votes sont transférés à la préférence suivante.
- Application : Les auteurs utilisent la functorialité des multiensembles. La fonction head (sélection de la première préférence) et la fonction delete (suppression d'un candidat éliminé) sont élevées pour opérer sur le multiensemble des listes de préférences. Cela permet l'agrégation des premières préférences et la redistribution subséquente des votes en s'exprimant par de simples compositions fonctionnelles ( $N(\text{hd})$ et $N(\text{del } c)$ ), évitant ainsi les processus itératifs complexes de listes.
Compte de De Borda :
- Mécanisme : Les électeurs classent les candidats et des points sont attribués selon le rang (par exemple, la 1ère place reçoit $n$ points, la 2ème reçoit $n-1$ , etc.).
- Application : La structure de monade est utilisée. Chaque liste de préférences est mappée vers un multiensemble de candidats pondérés (via unit et l'attribution de points). La collection de toutes ces listes pondérées forme un multiensemble de multiensembles. L'opération flatten effondre ensuite cette structure en un seul multiensemble de scores totaux, sommant efficacement les contributions pondérées.
Scrutin Unique Transférable (STV) :
- Mécanisme : Utilisé pour les circonscriptions plurinominales. Les candidats dépassant un quota (quota de Droop) sont élus, et leur surplus de voix est transféré à la préférence suivante.
- Application : Les auteurs étendent le type de donnée aux multiensembles fractionnaires ( $M(X)$ ) pour gérer la "valeur de transfert" (une fraction de vote). Ils utilisent la structure de monoïde pour la soustraction (dévaluation des votes utilisés pour élire un candidat) et la functorialité pour la redistribution. Le processus est modélisé comme une soustraction itérative des votes pondérés par le quota du candidat élu du multiensemble total, suivie de la suppression du candidat élu et du transfert des poids fractionnaires restants à la préférence suivante.

Signification et Revendications
L'article affirme modestement que sa contribution principale n'est pas la théorie des catégories profonde, mais la reconnaissance et l'exploitation de structures catégoriques existantes (foncteurs, monades, monoïdes) au sein du domaine des systèmes de vote. Les auteurs soutiennent que :

Abstraction : Décrire ces algorithmes en termes de multiensembles les rend "abstraits", permettant à des mécanismes complexes d'être décrits en quelques lignes de notation mathématique.
Correction et Transparence : L'approche par multiensemble garantit intrinsèquement la stabilité sous la permutation des votes (indépendance de l'ordre), une exigence fondamentale pour un comptage équitable. Elle sépare la logique du comptage de la représentation physique ou séquentielle des bulletins.
Implémentation : L'abstraction facilite la création d'implémentations prouvables de manière correcte dans des langages de programmation fonctionnelle (par exemple, Haskell) qui supportent les multiensembles.
Accessibilité : L'article vise à rendre ces techniques catégoriques accessibles aux non-experts, démontant qu'elles sont des outils pratiques pour assurer la transparence et l'exactitude des résultats électoraux, plutôt que des constructions purement théoriques.

L'article conclut que bien que des hypothèses simplificatrices aient été faites (par exemple, des longueurs de listes uniformes), l'approche par multiensemble offre un cadre robuste pour les futures implémentations de référence et l'analyse des algorithmes électoraux, allant au-delà de la dépendance historique au tri des bulletins de vote physiques.