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 choisir un autre gagnant que le gagnant de Condorcet.

Beaucoup d'heuristiques de la méthode de Schulze 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 ne garantit pas un unique gagnant. Elle est utilisée entre autres dans le projet Debian.

Sommaire

1 L'heuristique du chemin gagnant
- 1.1 Principe
- 1.2 Exemples
  - 1.2.1 Exemple 1
  - 1.2.2 Exemple 2
2 L'heuristique de l'ensemble de Schwartz
3 Critères satisfaits et non satisfaits
- 3.1 Critères satisfaits
- 3.2 Critères non satisfaits
4 Adoptions et utilisations
5 Programmes de dépouillement
6 Notes et références
7 Voir aussi
- 7.1 Articles connexes

L'heuristique du chemin gagnant

Chaque bulletin comporte la liste complète de tous les candidats. Chaque électeur classe les 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.

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 tout $i \in \lbrace 1 ... (n-1) \rbrace$ on a $d [C (i), C (i + 1)] > d [C (i + 1), C (i)]$ .
Pour tout $i \in \lbrace 1 ... (n-1) \rbrace$ on a $d[C(i),C(i+1)] \geqslant 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 s'il n'existe pas de candidat E qui soit meilleur que lui.

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

Exemple 1

Exemple (45 votants; 5 candidats):

5 ACBED (c'est-à-dire, cinq votants ont choisi l'ordre de préférence A > C > B > E > D)

5 ADECB

8 BEDAC

3 CABED

7 CAEBD

2 CBADE

7 DCEBA

8 EBADC

On effectue les confrontations par paires (méthode Condorcet)

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

2 DABC

2 DBCA

2 CBDA

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

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

L'heuristique de l'ensemble de Schwartz

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.

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é par n - p.

La méthode de Schulze consiste alors à :

é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) ;
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 ;
sinon, supprimer du graphe le ou les arc(s) dont la pondération est minimale (c'est-à-dire le ou les arc(s) correspondant à la défaite la plus courte) puis retourner à l'étape 1.

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)

**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 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, tandis que la méthode Black aurait également conduit à l'élection de E.

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^[2]^,^[3]^,^[4]^,^[5]
Expérience démocratique^[6]
Groupe d'utilisateurs Linux
Le Comité directeur de Wikimédia
Wikipédia en Français^[7], Hébreux^[8], Hongrois^[9]
Libre Entreprise

ainsi que dans de nombreuses associations anglophones...

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

Notes et références

↑ Thomas Schwartz est professeur de sciences politiques à l'université de Californie
↑ Le processus électoral de la Fondation Gentoo
↑ Article Gentoo / Condorcet
↑ Article Gentoo / Condorcet / Schwartz
↑ Article Gentoo / Schulze
↑ Voir la section 40.6 de ce document(en))
↑ Prise de décision Wikipédia France
↑ Voir cet article sur Wikipédia en hébreux
↑ Un article sur Wikipédia Hongrie

Voir aussi

Regardez d'autres dictionnaires:

Methode Schulze — 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… … Wikipédia en Français
Methode Black — Méthode Black La méthode Black[1] est un système de vote utilisé pour lever un conflit lors d une méthode Condorcet. Sommaire 1 Principe 2 Exemple 3 Critique de la m … Wikipédia en Français
Methode Condorcet — Méthode Condorcet La méthode Condorcet (ou vote Condorcet) est un système de vote dans lequel l unique vainqueur est celui, s il existe, qui comparé tour à tour à tous les autres candidats, s avèrerait à chaque fois être le candidat préféré. Rien … Wikipédia en Français
Méthode condorcet — La méthode Condorcet (ou vote Condorcet) est un système de vote dans lequel l unique vainqueur est celui, s il existe, qui comparé tour à tour à tous les autres candidats, s avèrerait à chaque fois être le candidat préféré. Rien ne garantit la… … Wikipédia en Français
Méthode d'élection Condorcet — Méthode Condorcet La méthode Condorcet (ou vote Condorcet) est un système de vote dans lequel l unique vainqueur est celui, s il existe, qui comparé tour à tour à tous les autres candidats, s avèrerait à chaque fois être le candidat préféré. Rien … Wikipédia en Français
Methode Condorcet avec rangement des paires par ordre decroissant — Méthode Condorcet avec rangement des paires par ordre décroissant La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode… … Wikipédia en Français
Méthode Condorcet Avec Rangement Des Paires Par Ordre Décroissant — La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode initialement proposée par Condorcet est développée par Tideman[1]. Sommaire 1 … Wikipédia en Français
Méthode condorcet avec rangement des paires par ordre décroissant — La méthode Condorcet avec rangement des paires par ordre décroissant est un système de vote qui permet de résoudre certains conflits de la méthode Condorcet. La méthode initialement proposée par Condorcet est développée par Tideman[1]. Sommaire 1 … Wikipédia en Français
Schulze method — Part of the Politics series Electoral methods Single winner … Wikipedia
Méthode Black — La méthode Black[1] est un système de vote utilisé pour lever un conflit lors d une méthode Condorcet. Sommaire 1 Principe 2 Exemple 3 Critique de la méthode et … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Méthode Schulze

Sommaire