Méthode de Schulze

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Méthode Schulze)

La méthode de Schulze est un système de vote développé en 1997 par Markus Schulze qui choisit un gagnant simple dans un vote avec classement des candidats. La méthode peut également être employée pour créer une liste ordonnée de gagnants.

Si un candidat gagne tous ses duels lors des confrontations par paires avec les autres candidats (gagnant de Condorcet), la méthode de Schulze garantit que ce candidat gagnera. En raison de cette propriété, la méthode de Schulze est (par définition) une méthode de Condorcet. Cette propriété ne se rencontre pas toujours dans les votes à classement ou pondération. Les méthodes Borda et Vote alternatif de Ware, par exemple, peuvent désigner un autre gagnant que le gagnant de Condorcet [1].

Beaucoup d'heuristiques de la méthode de Schulze, c’est-à-dire de méthodes permettant un calcul effectif du gagnant, ont été proposées. Les heuristiques les plus importantes sont l'heuristique du chemin gagnant et l'heuristique de l'ensemble de Schwartz. Malgré leur aspect très différent, elles donnent toutes le même résultat.

La méthode de Schulze permet de résoudre la plupart des conflits générés par le paradoxe de Condorcet, mais elle ne garantit pas un unique gagnant. Elle est utilisée entre autres dans le projet Debian ou dans le projet BÉPO.

Contexte et notations[modifier | modifier le code]

La méthode de Schulze peut être exercée pour un scrutin dans lequel les électeurs classent les candidats par ordre de préférences strictes. Un électeur peut choisir de classer deux candidats à égalité. Si cinq candidats A, B, C, D et E sont proposés, un bulletin peut donc ressembler à B > D > E > A > C (l’électeur préfère strictement le candidat B au candidat D, lui-même strictement préféré au candidat Eetc.) ou à C = A > B = D = E (l’électeur ne manifeste pas de préférence entre les candidats C et A d’une part, ni entre les candidats B, D et E d’autre part, mais les deux premiers sont strictement préférés aux trois derniers).

Mathématiquement, la relation de préférence pour un électeur est donc un préordre total. C’est un postulat commun à l’ensemble des systèmes de vote de type Condorcet. L’intensité des préférences n’est pas prise en compte : un électeur ne peut par exemple pas voter A >>> D > B = C = E pour exprimer une large préférence pour A.

Par convention, lorsque certains candidats ne sont pas classés, le bulletin est normalisé : les candidats non-classés sont ajoutés, tous à égalité, en bas du classement. Dans l’exemple précédent, un bulletin invalide A > C serait normalisé en A > C > B = D = E.

La méthode de Schulze vise, à partir d’un nombre arbitrairement grand de tels votes, à déterminer un candidat élu correspondant le mieux possible à la volonté générale. Le dépouillement d’un tel vote commence par l’établissement d’un « tableau des duels » ou « matrice des duels », c’est-à-dire par la détermination, pour chaque paire de candidats (X, Y), du nombre de votants préférant strictement X à Y et réciproquement du nombre de votants préférant strictement Y à X.

Dans l’ensemble de l’article, on note le nombre de votants qui préfèrent strictement le candidat X au candidat Y.

À partir de la matrice des duels, on peut établir le graphe des duels associé. Ce graphe est un graphe orienté dont les sommets sont les candidats. Un arc (ou une flèche) est dirigé du candidat X vers le candidat Y lorsque X bat strictement Y. Il est pondéré : si le candidat X confronté au candidat Y gagne n confrontations (n électeurs préfèrent strictement X à Y) et en perd p (p électeurs préfèrent strictement Y à X) et si n > p, alors l’arc créé de X vers Y est pondéré par le nombre n - p.

Dans cette construction, les arcs sont nécessairement pondérés par un nombre entier strictement positif. En particulier, s’il y a égalité entre X et Y (il y a autant de candidats préférant strictement X à Y que de candidats ayant la préférence inverse), alors il n’y a ni flèche de X vers Y, ni flèche de Y vers X.

Exemple

On suppose qu’au cours d’un vote pour départager cinq candidats A, B, C, D et E, quarante-cinq électeurs ont voté. Les bulletins sont les suivants (on suppose pour simplifier qu’il n’y a pas eu de cas d’égalité) :

5 — A > C > B > E > D (cinq électeurs ont voté A > C > B > E > D)
5 — A > D > E > C > B
8 — B > E > D > A > C
3 — C > A > B > E > D
7 — C > A > E > B > D
2 — C > B > A > D > E
7 — D > C > E > B > A
8 — E > B > A > D > C

On effectue les confrontations par paires (méthode Condorcet) pour construire la matrice des duels :

d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31
Matrice des duels entre candidats

Le graphe des duels est le suivant :

Schulze0.svg

Pour un tel scrutin, il n’y a pas de vainqueur de Condorcet. Un rangement par paires décroissantes conduirait à l'élection de A, tandis que la méthode Black élirait E. La méthode de Schulze, présentée ci-après, conduit également à l’élection de E.

Heuristique de l'ensemble de Schwartz[modifier | modifier le code]

L’heuristique de l’ensemble de Schwartz est une méthode de détermination du vainqueur de Schulze fondée sur l’itération de deux étapes : détermination d’un ensemble de vainqueurs potentiels (dit ensemble de Schwartz), puis élimination du duel le plus serré (pour lequel l’écart de voix est le plus faible)

Cette heuristique, relativement simple, peut représenter le processus par lequel une série de « révolutions » (situation dans laquelle la majorité impose son choix à la minorité) aboutit à un choix stable ou, au moins, le moins instable possible[2].

Ensemble de Schwartz[modifier | modifier le code]

Pour un graphe des duels donné, l’ensemble de Schwartz[3] est défini formellement de la façon suivante :

  • Un groupe de tête est un ensemble non-vide E de candidats n’ayant perdu aucune confrontation avec un candidat hors de E ;
  • Un groupe de tête minimal est un groupe de tête qui ne contient pas de groupe de tête strictement plus petit ;
  • L'ensemble de Schwartz est constitué de tous les candidats appartenant à au moins un groupe de tête minimal.

De façon moins formelle, pour déterminer si un candidat appartient à l’ensemble de Schwartz, on s’intéresse aux candidats qui le « battent indirectement » et aux candidats qu’il « bat indirectement ». On dit que X « bat indirectement » Y si l’une des conditions suivantes est vérifiée :

  • X bat Y
  • Il existe un candidat Z1 tel que X bat Z1 et Z1 bat Y ;
  • Il existe des candidats Z1 et Z2 tel que X bat Z2, Z2 bat Z1 et Z1 bat Y ;
  • Il existe des candidats Z1, Z2 et Z3 tels que X bat Z3, Z3 bat Z2, Z2 bat Z1 et Z1 bat Y ;
  • Et ainsi de suite avec un nombre arbitrairement grand de candidats Zi intermédiaires.

Un candidat A appartient alors au groupe de tête si :

  1. Soit aucun candidat ne bat A ;
  2. Soit tout candidat qui « bat indirectement » A est aussi « battu indirectement » par A.

Sur le graphe des duels, les groupes de tête apparaissent comme les sous-ensembles non-vides du graphe vers lesquels aucune flèche n’est dirigée. À noter que l’ensemble constitué de tous les candidats est toujours un groupe de tête. Un paradoxe de Condorcet correspond à une situation dans laquelle il n’y a pas de groupe de tête minimal réduit à un singleton.

Algorithme[modifier | modifier le code]

Les électeurs remplissent leur bulletin en plaçant les différents candidats dans l'ordre de leur préférence comme dans toute méthode Condorcet. La matrice des duels, puis le graphe des duels sont établis.

L’algorithme consiste alors à :

  1. éliminer du graphe les sommets qui n'appartiennent pas à son ensemble de Schwartz (les arcs ayant pour origine ou extrémité un sommet supprimé sont supprimés également) ;
  2. si le graphe obtenu ne comporte plus aucun arc, alors les candidats correspondant aux sommets de ce graphe sont déclarés vainqueurs ex æquo (il y a un vainqueur unique s'il ne reste qu'un sommet) et la méthode est terminée ;
  3. dans le cas contraire, supprimer du graphe le ou les arcs dont la pondération est minimale, c'est-à-dire le ou les arcs correspondant à la défaite la plus courte, puis retourner à l'étape 1.

Exemple[modifier | modifier le code]

L’on reprend l’exemple précédent, dans lequel le graphe des duels est le suivant :

Schulze1.svg

Le seul groupe de tête est l’ensemble des candidats tout entier {A, B, C, D, E}. On ne peut en effet trouver aucun sous-ensemble non-vide vers lequel n’est dirigé aucune flèche. L'ensemble de Schwartz est donc également {A, B, C, D, E}. L’algorithme se poursuit.

La victoire la plus serrée est celle de E sur A (une voix d’avance seulement). L’arc correspondant, qui a la pondération la plus faible (1), est enlevé. Le graphe modifié est alors le suivant :

Schulze2.svg

Il n’y a toujours qu’un groupe de tête, l’ensemble tout entier. L'ensemble de Schwartz est encore constitué de l'ensemble tout entier {A, B, C, D, E}. Éliminer un arc n’a pas suffi à modifier l’ensemble de Schwartz.

On élimine à nouveau l’arc à la pondération la plus faible, qui part de C pour aller vers E.

Schulze3.svg

Il y a alors deux groupes de tête : celui constitué de l’ensemble des candidats {A, B, C, D, E}, et le singleton {E}. Seul le singleton {E} est minimal. L'ensemble de Schwartz est alors le singleton {E} . Le candidat E est donc le gagnant de l’élection.

À noter que l’on peut ensuite reproduire la méthode avec les quatre candidats non-élus pour aboutir à un classement de l’ensemble des candidats. Sur cet exemple, la passe suivante aboutit à un nouveau paradoxe de Condorcet, qui conduit à éliminer l’arc BA, et à retenir A comme second candidat. Puis à nouveau, un paradoxe de Condorcet subsiste entre les candidats B, C et D. L’élimination de l’arête DC, la plus faible, fait de C le troisième candidat de B le quatrième et de D le dernier. Le classement général résultant de cet exemple est E > A > C > B > D. En l’espèce, il n’y a aucun cas d’égalité entre deux candidats, mais une telle situation pourrait arriver.

L'heuristique du chemin gagnant[modifier | modifier le code]

L’heuristique du chemin gagnant permet de déterminer autrement le gagnant de Schulze. Elle est cependant plus complexe à mettre en œuvre.

Chemin de force[modifier | modifier le code]

On appelle chemin de force z du candidat X au candidat Y, une liste ordonnée de candidats C(1), ..., C(n) vérifiant les conditions suivantes :

  • correspond à X
  • correspond à Y

z est la force du chemin.

Force du chemin[modifier | modifier le code]

On appelle force du chemin la plus petite valeur des différents d[C(i),C(i+1)] le long du chemin. La force du chemin est donc égale à celle de son maillon le plus faible.

On note p[A,B] la force du plus fort chemin du candidat A vers le candidat B.

p[A,B] : = max { min { d[C(i),C(i+1)] | i = 1,...,(n-1) } | C(1),...,C(n) est un chemin de A vers B }

S'il n'existe pas de chemin de A vers B alors

p[A,B] : = 0

Si p[A,B] > p[B,A] on dit que le candidat A est meilleur que le candidat B.

Dans la méthode de Schulze on dit qu'un candidat D est un vainqueur potentiel si et seulement s'il n'existe pas de candidat E qui soit meilleur que lui.

Exemple 1[modifier | modifier le code]

L’on reprend l’exemple présenté ci-dessus. Les confrontations par paires (méthode Condorcet) aboutissent à la matrice des duels suivante :

d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31
Matrice des duels entre candidats

On détermine les chemins de plus grande force. Le maillon faible est souligné

  ... vers A ... vers B ... vers C ... vers D ... vers E
de A ...
Schulze method example1 AB.svg
A-(30)-D-(28)-C-(29)-B
Schulze method example1 AC.svg
A-(30)-D-(28)-C
Schulze method example1 AD.svg
A-(30)-D
Schulze method example1 AE.svg
A-(30)-D-(28)-C-(24)-E
de B ...
Schulze method example1 BA.svg
B-(25)-A
Schulze method example1 BC.svg
B-(33)-D-(28)-C
Schulze method example1 BD.svg
B-(33)-D
Schulze method example1 BE.svg
B-(33)-D-(28)-C-(24)-E
de C ...
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
de D ...
Schulze method example1 DA.svg
D-(28)-C-(29)-B-(25)-A
Schulze method example1 DB.svg
D-(28)-C-(29)-B
Schulze method example1 DC.svg
D-(28)-C
Schulze method example1 DE.svg
D-(28)-C-(24)-E
de E ...
Schulze method example1 EA.svg
E-(31)-D-(28)-C-(29)-B-(25)-A
Schulze method example1 EB.svg
E-(31)-D-(28)-C-(29)-B
Schulze method example1 EC.svg
E-(31)-D-(28)-C
Schulze method example1 ED.svg
E-(31)-D
Chemins les plus forts

La synthèse des résultats est alors :

  p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*]   28 28 30 24
p[B,*] 25   28 33 24
p[C,*] 25 29   29 24
p[D,*] 25 28 28   24
p[E,*] 25 28 28 31  
Les plus grandes forces

Le candidat E est un gagnant potentiel car p[E,X] ≥ p[X,E] pour tout autre candidat X

Exemple 2[modifier | modifier le code]

Exemple (9 votants ; 4 candidats):

3 — A > B > C > D
2 — D > A > B > C
2 — D > B > C > A
2 — C > B > D > A

On effectue les confrontations par paires

  d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*]   5 5 3
d[B,*] 4   7 5
d[C,*] 4 2   5
d[D,*] 6 4 4  
Matrice des duels entre candidats

On détermine les chemins de plus grande force. Le maillon faible est souligné .

... vers A ... vers B ... vers C ... vers D
de A ...
Schulze method example4 AB.svg
A-(5)-B
Schulze method example4 AC.svg
A-(5)-C
Schulze method example4 AD.svg
A-(5)-B-(5)-D
de B ...
Schulze method example4 BA.svg
B-(5)-D-(6)-A
Schulze method example4 BC.svg
B-(7)-C
Schulze method example4 BD.svg
B-(5)-D
de C ...
Schulze method example4 CA.svg
C-(5)-D-(6)-A
Schulze method example4 CB.svg
C-(5)-D-(6)-A-(5)-B
Schulze method example4 CD.svg
C-(5)-D
de D ...
Schulze method example4 DA.svg
D-(6)-A
Schulze method example4 DB.svg
D-(6)-A-(5)-B
Schulze method example4 DC.svg
D-(6)-A-(5)-C
Chemins les plus forts

La synthèse des résultats est alors :

  p[*,A] p[*,B] p[*,C] p[*,D]
p[A,*]   5 5 5
p[B,*] 5   7 5
p[C,*] 5 5   5
p[D,*] 6 5 5  
Les plus grandes forces

Les candidats B et D sont des gagnants potentiels car p[B,X] ≥ p[X,B] pour tout autre candidat X et p[D,Y] ≥ p[Y,D] pour tout autre candidat Y

Critères satisfaits et non satisfaits[modifier | modifier le code]

Critères satisfaits[modifier | modifier le code]

à traduire par des spécialistes des critères

Critères non satisfaits[modifier | modifier le code]

à traduire par des spécialistes des critères

Adoptions et utilisations[modifier | modifier le code]

La méthode de Schulze n'est pas encore employée dans des élections gouvernementales. Toutefois, elle a déjà été utilisée pour les primaires aux élections parlementaires par le Parti pirate (Suède). Par ailleurs, certaines organisations l'ont adoptée pour leurs besoins électoraux depuis de nombreuses années. Quelques organisations utilisatrices de la méthode de Schulze :

Ainsi que dans de nombreuses associations anglophones.

Programmes de dépouillement[modifier | modifier le code]

  • Condorcet PHP, application en ligne de commande et bibliothèque en langage PHP, permettant de manipuler des votes dans la quasi-totalité des méthodes respectant les critères de Condorcet dont celle de Schulze ; ou de trouver les gagnants / perdants idéaux de Condorcet s'ils existent. Distribué sous licence MIT.
  • Condorcet Internet Voting Service (CIVS), d'Andrew Myers

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]