Méthode de Schulze

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

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.

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.

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 :

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

z est la 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.

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

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 :

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

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

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

à traduire par des spécialistes des critères

à traduire par des spécialistes des critères

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