Résumé Technique : Géométrie Métrique pour le Vote par Classement

1. Problématique

La théorie du choix social computationnel étudie souvent les préférences métriques, où candidats et électeurs sont plongés dans un espace métrique commun. Cependant, la littérature classique se concentre principalement sur les classements complets (permutations). Dans les élections réelles (comme celles en Écosse), les bulletins sont souvent partiels (les électeurs ne classent que quelques candidats).

Le problème central est de construire un cadre géométrique rigoureux qui étende les deux distances de classement les plus importantes — la distance de Kendall tau ($\tau$) et la distance de Spearman (footrule) — aux classements partiels, afin de permettre l'analyse de la polarisation, de la proportionnalité et de la diversité sans perdre la structure mathématique des permutations complètes.

2. Méthodologie

Les auteurs développent deux approches complémentaires pour représenter les bulletins de vote dans un espace géométrique :

A. Plongements de coordonnées (Coordinate Embeddings)

Ils définissent deux fonctions de plongement pour transformer un bulletin $\sigma$ en un vecteur dans un espace euclidien $\mathbb{R}^m$ ou $\mathbb{R}^{\binom{m}{2}}$ :

• Plongement de Borda ($b$) : Chaque candidat reçoit un score basé sur sa position. Les auteurs utilisent une convention pessimiste pour les classements partiels (les candidats non mentionnés reçoivent 0 point), ce qui permet de gérer les bulletins incomplets de manière cohérente. La distance de Spearman est alors dérivée de la distance $L_1$ entre ces vecteurs.
• Plongement tête-à-tête ($h$) : Chaque paire de candidats est enregistrée comme un duel ($\pm 1$ ou $0$). La distance de Kendall tau est dérivée de la distance $L_1$ entre ces vecteurs de comparaisons par paires.

B. Réalisations par graphes (Ballot Graphs)

Pour éviter les limites des coordonnées, ils introduisent des structures de graphes :

• Le graphe de bulletin ($G_m$) : Un graphe où les nœuds sont des classements partiels et les arêtes représentent des échanges de voisins (swaps) ou des extensions/troncations de bulletins. La métrique de chemin dans ce graphe correspond à la distance de Kendall tau.
• Le graphe de bulletin raccourci ($G^+_m$) : Ajoute des arêtes de "swaps généraux" (échanges de candidats non adjacents), dont la métrique de chemin correspond à la distance de Spearman.
• Graphes généralisés : Ils étendent ces concepts aux classements avec ex-æquo (slates), permettant de modéliser des préférences entre des groupes de candidats.

3. Contributions Clés

1. Extension mathématique : Preuve que les distances de Kendall tau et de Spearman s'étendent naturellement aux classements partiels via des graphes et des coordonnées, tout en préservant les propriétés métriques.
2. Stabilité de la classification : Ils prouvent que dans une élection suffisamment polarisée, le partitionnement des électeurs (en blocs) est stable et reste identique même si l'on change de métrique (entre Kendall et Spearman), grâce à une propriété de bi-Lipschitz équivalence.
3. Algorithmes de clustering : Développement de méthodes pour regrouper les électeurs (blocs) et les candidats (slates) en utilisant des algorithmes de type $k$-medoids (PAM) et l'agglomération hiérarchique.

4. Résultats et Validation

Les auteurs testent leurs méthodes sur deux types de données :

• Élections synthétiques : En utilisant des modèles de Mallows, ils démontrent que leurs algorithmes de clustering identifient avec précision les centres de polarisation et les groupes de candidats, même avec des tailles de clusters déséquilibrées.
• Élections écossaises réelles (2012-2022) :
  • Ils appliquent la méthode sur l'élection de Pentland Hills.
  • Résultats sur les blocs : Les méthodes de clustering identifient des groupes d'électeurs qui correspondent de manière frappante aux affiliations partisanes (SNP, Labour, Conservative), même sans utiliser les étiquettes de partis.
  • Résultats sur les slates : Le clustering des candidats regroupe naturellement les membres d'un même parti. Ils notent également que la méthode est "agnostique aux partis", permettant de découvrir des alliances inter-partis (ex: la proximité entre le SNP et les Verts).
  • Robustesse : Ils constatent que 73,5 % des élections présentent des centres de clustering identiques pour les deux métriques (Borda et Kendall).

5. Signification

Ce travail fournit un cadre unificateur pour la science politique computationnelle. En transformant des classements qualitatifs en objets géométriques, il devient possible de :

• Mesurer mathématiquement la polarisation (distance entre les centres des blocs).
• Évaluer la proportionnalité (si les "slates" de candidats élus reflètent la taille des blocs d'électeurs).
• Appliquer des outils d'apprentissage non supervisé (machine learning) à des données électorales réelles et incomplètes, offrant une analyse plus fine que la simple analyse par étiquettes de partis.