Méthode de 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 .

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

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 E, etc.) 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 $d[X,Y]$ 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 :

Matrice des duels entre candidats

	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

Le graphe des duels est le suivant :

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

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.

Ensemble de Schwartz

Pour un graphe des duels donné, l’ensemble de Schwartz 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 Z₁ tel que X bat Z₁ et Z₁ bat Y ;
• Il existe des candidats Z₁ et Z₂ tel que X bat Z₂, Z₂ bat Z₁ et Z₁ bat Y ;
• Il existe des candidats Z₁, Z₂ et Z₃ tels que X bat Z₃, Z₃ bat Z₂, Z₂ bat Z₁ et Z₁ bat Y ;
• Et ainsi de suite avec un nombre arbitrairement grand de candidats Z_i 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

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

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

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 :

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.

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 B ⟶ A, 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 D ⟶ C, 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

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

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 :

• $C(1)$ correspond à X
• $C(n)$ correspond à Y
• ∀ $i\in \lbrace 1...(n-1)\rbrace$ $d[C(i),C(i+1)]>d[C(i+1),C(i)]$
• ∀ $i\in \lbrace 1...(n-1)\rbrace$ $d[C(i),C(i+1)]\geqslant z$

z est la force du chemin.

Force du chemin

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

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

Matrice des duels entre candidats

	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

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

Chemins les plus forts

	... vers A	... vers B	... vers C	... vers D	... vers E
de A ...		A-(30)-D-(28)-C-(29)-B	A-(30)-D-(28)-C	A-(30)-D	A-(30)-D-(28)-C-(24)-E
de B ...	B-(25)-A		B-(33)-D-(28)-C	B-(33)-D	B-(33)-D-(28)-C-(24)-E
de C ...	C-(29)-B-(25)-A	C-(29)-B		C-(29)-B-(33)-D	C-(24)-E
de D ...	D-(28)-C-(29)-B-(25)-A	D-(28)-C-(29)-B	D-(28)-C		D-(28)-C-(24)-E
de E ...	E-(31)-D-(28)-C-(29)-B-(25)-A	E-(31)-D-(28)-C-(29)-B	E-(31)-D-(28)-C	E-(31)-D

La synthèse des résultats est alors :

Les plus grandes forces

	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

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

Exemple 2

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

Matrice des duels entre candidats

	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

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

Chemins les plus forts

	... vers A	... vers B	... vers C	... vers D
de A ...		A-(5)-B	A-(5)-C	A-(5)-B-(5)-D
de B ...	B-(5)-D-(6)-A		B-(7)-C	B-(5)-D
de C ...	C-(5)-D-(6)-A	C-(5)-D-(6)-A-(5)-B		C-(5)-D
de D ...	D-(6)-A	D-(6)-A-(5)-B	D-(6)-A-(5)-C

La synthèse des résultats est alors :

Les plus grandes forces

	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 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

Critères satisfaits

à traduire par des spécialistes des critères

Critères non satisfaits

à traduire par des spécialistes des critères

Adoptions et utilisations

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 :

• Le projet informatique Debian et l'ensemble des groupes d'utilisateurs Debian (DUG)
• La fondation Gentoo
• Expérience démocratique
• Groupe d'utilisateurs Linux
• Le comité directeur de Wikimédia
• Libre Entreprise
• L’association Ergodis (à l’origine du clavier bépo).

Ainsi que dans de nombreuses associations anglophones.

Programmes de dépouillement

• 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

Voir aussi

Articles connexes

• Méthode Condorcet
• Paradoxe de Condorcet
• Méthode Borda
• Théorème d'impossibilité d'Arrow