Méthode Schulze
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 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. Il faut noter que cette propriété ne se rencontre pas toujours dans les votes à classement ou pondération. La méthode Borda et 'Instant-runoff', par exemple, peuvent choisir un autre gagnant que le gagnant de Condorcet.
Beaucoup d'heuristique de la méthode de Schulze ont été proposée. Les heuristiques les plus importantes sont l'heuristique du chemin gagnant et l'heuristique de Schwartz. Malgré leur aspect très différent, elles donnent toutes le même résultat.
La méthode Schulze permet de résoudre la plupart des conflits générés par le paradoxe de Condorcet mais ne garantit pas un unique gagnant. Elle est utilisée entre autres dans le projet Debian.
Sommaire |
[modifier] L'heuristique du chemin gagnant
Chaque bulletin comporte la liste complète de tous les candidats. Chaque électeur range ces candidats dans l'ordre de ses préférences. Un électeur peut, dans ses préférences, mettre à égalité plusieurs candidats. Il peut même présenter une liste incomplète. Les candidats non listés seront considérés comme placés après les autres et selon un même degré de préférence.
[modifier] Principe
On note d[V,W] le nombre de votants qui préfèrent strictement le candidat V au candidat W.
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
- Pour i = i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
- Pour i = 1,...,(n-1): d[C(i),C(i+1)] ≥ z.
S'il existe un entier p tel qu'un chemin de force p peut être créé de A vers B alors qu'il n'existe pas de chemin de force p de B vers A, on dit que le candidat A est meilleur que le candidat B.
On dit qu'un candidat D est un vainqueur potentiel si et seulement si il n'existe pas de candidat E qui soit meilleur que lui.
[modifier] Exemples
On appelle chemin du candidat X vers le candidat Y une liste ordonnées de candidats C(1),...,C(n) vérifiant les propriétés :
-
- C(1) correspond à X
- C(n) correspond à Y
- Pour i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
On appelle force du chemin la plus petite valeur de d[C(i),C(i+1)]. En gros c'est la force du 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
La méthode Schulze peut alors être interprétée de la manière suivante: le candidat A est un gagnant potentiel si et seulement si p[A,B] ≥ p[B,A] pour tout candidat B.
[modifier] Exemple 1
Exemple (45 votants; 5 candidats):
- 5 ACBED
- 5 ADECB
- 8 BEDAC
- 3 CABED
- 7 CAEBD
- 2 CBADE
- 7 DCEBA
- 8 EBADC
On effectue les confrontations par paires (méthode Condorcet)
| 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é
| ... 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 :
| 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
[modifier] Exemple 2
Exemple (9 votants; 4 candidats):
- 3 ABCD
- 2 DABC
- 2 DBCA
- 2 CBDA
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 |
On détermine les chemins de plus grande force. Le maillon faible est souligné .
| ... vers A | ... vers B | ... vers C | ... vers D | |
|---|---|---|---|---|
| de A ... | A-(5)-B | A-(5)-C | A-(5)-C-(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 :
| 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
[modifier] L'heuristique de Schwartz
[modifier] L'ensemble de Schwartz
L'ensemble de Schwartz[1] est constitué de la manière suivante
- Un groupe de tête est un groupe de candidats qui n'ont perdu aucune confrontation avec des candidats qui ne sont pas dans le groupe de tête
- Un groupe de tête minimal est un groupe de tête qui ne contient pas de groupe de tête plus petit
- L'ensemble de Schwartz est constitué de tous les candidats appartenant à au moins un groupe de tête minimal.
[modifier] Mise en œuvre
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
Les confrontations par paires sont alors organisées. On établit alors un graphe orienté pondéré : les sommets sont les candidats. Si le candidat X confronté au candidat Y gagne n confrontations et en perd p et si n > p, on crée un arc de X vers Y pondérée par n - p
La méthode Schulze consiste alors à
- Construire l'ensemble de Schwartz de l'élection
- S'il n'y aucune défaite dans ce groupe tous les candidats du groupe sont déclarés vainqueur (il peut exister plusieurs vainqueurs si ils sont tous ex-aequo)
- Sinon, supprime du graphe l'arête dont la pondération est minimale (ce qui correspond à ce qu'on appelle abusivement la plus faible défaite)
- On retourne à l'étape 1
[modifier] Exemple
Reprise de l'exemple 1 de l'heuristique du chemin : (45 votants; 5 candidats):
- 5 ACBED
- 5 ADECB
- 8 BEDAC
- 3 CABED
- 7 CAEBD
- 2 CBADE
- 7 DCEBA
- 8 EBADC
On effectue les confrontations par paires (méthode Condorcet)
| 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 constitue le graphe orienté des duels :
L'ensemble de Schwartz est constitué de l'ensemble tout entier {A, B, C, D, E}
On élimine la plus petite défaite/victoire de E vers A
L'ensemble de Schwartz est encore constitué de l'ensemble tout entier {A, B, C, D, E}
On élimine la plus petite défaite/victoire de C vers E
L'ensemble de Schwartz est alors constitué du singleton { E} . Le candidat E est alors le gagnant des élections.
Nota: Un rangement par paires décroissantes aurait conduit à l'élection de A
[modifier] Critères satisfaits et non satisfaits
[modifier] Critères satisfaits
à traduire pas des spécialistes des critères
[modifier] Critères non satisfaits
à traduire pas des spécialistes des critères
[modifier] Emploi de la méthode Schulze
La methode Schulze n'est pas encore employée dans des élections gouvernementales. Cependant elle commence à trouver des adeptes dans certaines organisations.
- Le projet Debian ainsi quand dans tous groupes d'utilisateurs Debian (DUG)
- Prise de décision sur la wikipedia francophone
- Fondation Gentoo (en)Site de la fondation [1] [2] [3] [4]
- Expérience démocratique (voir la section 30.6 de ce document(en))
- Groupes d'utilisateurs Linux
ainsi que dans de nombreuses associations anglophones...
[modifier] Programmes de dépouillement
- (en) Voting Software Project par Blake Cretney
- (en) Condorcet with Dual Dropping Perl Scripts par Mathew Goldstein
- (en) Condorcet Voting Calculator par Eric Gorr
- (en) Haskell Condorcet Module par Evan Martin
- (en) Condorcet Internet Voting Service (CIVS) par Andrew Myers
- (en) BetterPolls.com par Brian Olson
[modifier] Voir aussi
[modifier] Notes
- ↑ Thomas Schwartz est professeur de sciences politiques à l'université de Californie
[modifier] Sources
- (en) Cet article est partiellement ou en totalité issu d'une traduction de l'article en anglais : « Schulze method ».
