Méthodes - La Science du Choix Social

Méthodes Mathématiques

De la méthode de Borda à l'optimum de Kemeny-Young : s'approcher du consensus.

Pour redonner du pouvoir aux électeurs et, en particulier leur éviter la nécessité du vote utile, il faut au minimum leur demander une liste ordonnée de choix, éventuellement complétée par des notes. Le défi est ensuite de combiner tout cela en une fonction de satisfaction. Les méthodes les plus simples comme la distribution de points ou la méthode de Borda sont peu satisfaisantes.

La solution : L'indépendance des paires

Pour qu'un scrutin soit juste, le poids de l'électeur sur le choix entre deux candidats $a$ et $b$ doit être **indépendant** des autres candidats présents. Si l'électeur préfère $a$ à $b$, son vote doit autant peser sur ce duel que celui de tout autre électeur, et cela même si $a$ et $b$ sont mal classés dans ses propres préférences et même si des candidats mineurs sont intercalés.

C'est la force de la méthode de **Kemeny-Young** : elle n'additionne pas des rangs artificiels, mais cherche l'ordre global qui maximise la satisfaction de la population sur l'ensemble des duels croisés.

Kemeny-Young : La matrice des Duels $S$ et la fonction de satisfaction

Pour calculer le résultat, il faut d'abord compiler tous les bulletins dans une matrice globale $S[a,b]$ représentant le nombre de voix d'avance de $a$ sur $b$. On cherche ensuite la permutation de candidats (l'ordre final) qui obtient le meilleur score de satisfaction.

Trouver le classement des candidats donnant le meilleur score Kemeny-Young est un calcul lourd.

Propriétés remarquables de Kemeny-Young : En plus de ne pas décourager le vote pour ses vraies préférences, même si elles n'ont aucune chance, cette méthode garantit le respect absolu du Critère de Condorcet. Si un candidat gagne tous ses duels théoriques, il gagne l'élection. De plus, dans les cas courants elle rend sans efficacité les votes insincères.

Les défauts de la méthode de Borda

Dans la méthode de Borda on considère que, à défaut d'un candidat "Condorcet" qui bat tous les autres, le meilleur candidat est celui qui bat le maximum de personnes. Cela revient à considérer le classement moyen d'un candidat dans l'ensemble des votes.

Le défaut est le même que pour la distribution de points : si un électeur peuple le début de sa liste par des candidats hors-course, il lui restera moins d'amplitude de rang pour départager les autres. Il ne sera pas complètement spectateur mais pèsera moins que l'électeur moyen sur le résultat.

Et en plus cette méthode ne garantit même pas qu'un candidat ayant la propriété de Condorcet sera vainqueur. Il suffit en effet que quand dans un vote élémentaire le candidat Condorcet en bat un autre c'est avec peu d'avance alors que quand il est battu c'est avec une grande avance du concurrent.

Le problème :

Le score final dépend directement du nombre de candidats intercalés entre deux vainqueurs potentiels.

Il faut donc s'orienter plutôt sur des méthodes axées sur l'ensemble des paires de candidats et ne tenant compte que de leur ordre dans chaque vote, indépendamment des candidats qui s'intercalent entre eux.

Démonstration : L'inutilité de la triche

Supposons qu’il y a 3 candidats $\{a,b,c\}$, $c$ est le préféré d'un électeur tacticien mais n'a aucune chance, son deuxième choix est $b$. Les deux hypothèses vraisemblables de résultat sont $\{a,b,c\}$ ou $\{b,a,c\}$.

L'ordre sincère du tacticien est $\{c,b,a\}$ et comme $c$ n'a aucune chance, il peut être tenté de voter tactique en mettant $b$ en tête et $a$ en queue soit $\{b,c,a\}$. Comment cela fait-il varier les 2 hypothèses vraisemblables ?

En votant sincèrement $\{c, b, a\}$ :

Il fait varier de -3 le score KY de $\{a,b,c\}$
Et de -1 celui de $\{b,a,c\}$

En votant tactiquement $\{b, c, a\}$ :

Il fait varier de -1 le score KY de $\{a,b,c\}$
Et de 1 celui de $\{b,a,c\}$

Ainsi, tactique ou sincère font progresser le deuxième choix de la même façon. En revanche, le vote tactique fera perdre davantage de duels au premier choix. Même s'il n'avait aucune chance, son recul est mauvais pour sa crédibilité politique.

Dans des situations se jouant au % avec plus de candidats voisins dans le groupe de tête, la méthode KY n'est pas totalement invulnérable au vote tactique, mais comme celui-ci ne peut se baser que sur des sondages traditionnels imparfaits, l'électeur prendrait un gros risque à ce jeu.

Le vote tactique est un mauvais choix avec Kemeny-Young.

Le défi algorithmique

Ce problème est connu comme un problème NP-difficile (le temps de résolution exacte augmente plus vite que n'importe quelle puissance du nombre de candidats).

La première méthode est la force brute : on teste toutes les permutations possibles des $n$ candidats. On peut légèrement améliorer en élaguant l’arbre des possibilités par de la cuisine calculatoire.

Exemple basique : si dans une configuration testée un candidat $x$ est en moyenne avant un sous-ensemble contigu $\{a, b, c\dots\}$, c'est-à-dire si $S[x,a]+S[x,b]+\dots > 0$, alors ce candidat $x$ ne peut être placé à la fin du bloc. Cette règle permet d'éliminer énormément de branches.

Avec ces optimisations, le moteur actuel peut traiter jusqu'à 45 candidats avec un jeu de votes tirés au hasard. Pour cette taille, cela prend de l'ordre d'une heure de calcul sur un PC de bureau.

Sur le serveur de ce site, la taille est bridée à 25 candidats pour des raisons de sécurité du processeur, ce qui demande à peine 2 secondes.

Le calcul étant de complexité factorielle , la puissance brute n'aide que très peu. Compte tenu de l'élagage, le temps de calcul sur PC entre 20 et 45 choix évolue comme exp(n) ce qui laisse penser qu'avec un superordinateur un million de fois plus puissant qu'un PC de bureau, on pourrait gagner 50 choix supplémentaires. En tout état de cause la barrière des 100 candidats semble infranchissable avec une méthode exhaustive.

Pour les grands nombres, le site bascule sur une méthode heuristique de type "recuit simulé" : une marche déterministe jusqu'à un blocage (extremum local), puis un saut aléatoire contrôlé pour s'en dégager. En limitant le temps de calcul à une heure, l'optimum semble atteignable sur PC jusqu'à 200 candidats, ce qui semble être le plafond pratique pour des données réellement aléatoires. S'il y a la moindre structure sous-jacente cela va plus vite et, à la limite s'il y a un ordre total, cela devient quasi instantané.

Pour tester vos méthodes si vous avez d'autres idées :

Données pour test.

Pour en savoir plus

Fiches encyclopédiques (Wikipedia)

Méthode Kemeny-Young (Anglais, très complet) La Ruche des méthodes de Condorcet Histoire et calculs du scrutin de Borda Comparatif scientifique des critères de vote

Publications & Thèses universitaires

Pour une étude approfondie de la combinatoire, vous pouvez consulter la thèse de Robin Milosz (octobre 2018, Université de Montréal) intitulée : "Étude algorithmique et combinatoire de la méthode de Kemeny-Young et du consensus de classements".

Ouvrir le document PDF (UdeM)

Implémentations numériques rares

Les célèbres fiches de références algorithmiques proposent une analyse d'optimisation de la méthode :

Consulter l'implémentation KY

1. Agrégation de la matrice globale $S$

Pour chaque bulletin individuel $k$, si l'électeur préfère $a$ à $b$, la sous-contribution est $S_k[a,b] = 1$ et $S_k[b,a] = -1$. En cas d'ex-æquo sur cette paire ou de non-classement de l'un des deux candidats, la contribution est de $0$. La matrice générale est la somme de ces contributions :

$$S[a,b] = \sum_{k} S_k[a,b]$$

2. Calcul de la fonction de Satisfaction

Le score d'une hypothèse de classement (une permutation de candidats) est calculé en sommant les valeurs de la matrice $S$ pour toutes les paires dans l'ordre de la permutation testée :

$$Satisfaction = \sum_{a \prec b} S[a,b]$$

Où la notation $a \prec b$ signifie que le candidat $a$ devance le candidat $b$ dans le classement que l'algorithme est en train de tester.

3. La distance de Kendall-Tau

D'un point de vue géométrique, maximiser cette fonction de satisfaction revient exactement à chercher la permutation de candidats qui minimise la somme des désaccords (la distance mathématique de Kendall-Tau) entre cette permutation et chacun des votes. On extrait ainsi le véritable "centre de gravité" de l'opinion publique.