Aller au contenu
Condorcet.vote Alpha
← Le classement de Condorcet
Méthode d'appoint

La méthode Dodgson Quick

L'idée de Lewis Carroll : élire l'option qu'il faudrait le moins bousculer pour qu'elle batte tout le monde. Intuitive, mais sans garanties démontrées comparables à celles de Schulze.

Quand la choisir : si votre règlement la désigne, ou si cette lecture du résultat parle à vos votants.

Origine
Charles Dodgson (Lewis Carroll), 1876 ; approximation de McCabe-Dansted, Pritchard et Slinko, 2008
Variantes proposées
Dodgson Quick
Calcul
Polynomial, en n² pour n options (Dodgson exact : NP-difficile)
Le principe

Mesurer la distance au gagnant de Condorcet.

Dodgson élit l'option qui deviendrait gagnante de Condorcet avec le moins d'inversions sur les bulletins. Ce calcul exact est NP-difficile (Bartholdi, Tovey et Trick, 1989).

Dodgson Quick l'estime simplement : pour chaque duel perdu, il faut faire basculer au moins la moitié de l'écart. Le score additionne ces demi-écarts, arrondis au supérieur ; le plus petit gagne.

Pas à pas

Le même cycle, mesuré en inversions.

Les 100 bulletins de l'exemple
  • Camille , puis Adèle , puis Sophie 40 votants
  • Adèle , puis Sophie , puis Camille 35 votants
  • Sophie , puis Camille , puis Adèle 25 votants
  1. 1 Camille. Perd contre Sophie de 20 voix : score 10.
  2. 2 Adèle. Perd contre Camille de 30 voix : score 15.
  3. 3 Sophie. Perd contre Adèle de 50 voix : score 25.
Score (le plus petit gagne)
  1. Camille battue par Sophie, 20 voix d'écart 10
  2. Adèle battue par Camille, 30 voix d'écart 15
  3. Sophie battue par Adèle, 50 voix d'écart 25
Résultat : Camille › Adèle › Sophie, le même ordre que Schulze sur cet exemple.
Propriétés

Ce que la méthode garantit, face au scrutin à un tour.

Aucun tableau publié ne couvre Dodgson Quick : seules les cases établies par sa construction ou par un résultat général sont remplies.

Critère Dodgson Quick Scrutin à un tour
Majorité Une option placée en tête par plus de la moitié des votants gagne. Oui Note 1 Oui
Perdant majoritaire Une option placée en dernier par plus de la moitié des votants ne gagne jamais. Non établi Non
Majorité mutuelle Si une majorité place un groupe d'options devant toutes les autres, le gagnant en fait partie. Non établi Non
Gagnant de Condorcet L'option qui bat chacune des autres en duel est toujours élue. Oui Note 2 Non
Perdant de Condorcet L'option battue par chacune des autres en duel n'est jamais élue. Non établi Non
Critère de Smith Le gagnant appartient au plus petit groupe d'options qui battent toutes celles du dehors. Non établi Non
Indépendance des clones Ajouter une option très proche d'une autre ne change pas l'issue entre les autres. Non établi Non
Monotonie Mieux classer le gagnant ne peut jamais lui faire perdre. Non établi Oui
Indépendance locale Retirer l'option arrivée dernière (ou première) au résultat ne change pas l'ordre des autres. Non établi Non
Symétrie d'inversion Si tous les bulletins sont renversés, l'ancien gagnant ne gagne plus. Non établi Non
Participation Voter sincèrement ne peut jamais desservir le votant par rapport à l'abstention. Non Note 3 Oui
Cohérence Si une option gagne dans deux groupes séparés, elle gagne quand on les réunit. Non Note 3 Oui
Sans risque pour le premier choix Classer un choix supplémentaire ne peut jamais nuire à ceux déjà classés devant. Non Note 3 Oui Note 4
Résolvabilité Une égalité finale devient improbable quand le nombre de votants augmente. Non établi Oui
Calcul rapide Le résultat se calcule en temps polynomial, même avec beaucoup d'options. Oui Oui
  • ✓ toujours respecté
  • ✕ peut être violé dans certains votes
  • ? aucune source publiée ne l'établit
  1. 1 Conséquence directe du critère de Condorcet : une option placée en tête par la majorité bat toutes les autres en duel.
  2. 2 Garanti par construction : CondorcetPHP place toujours le gagnant de Condorcet en tête.
  3. 3 Aucune méthode qui respecte le critère de Condorcet ne peut satisfaire ce critère : c'est un résultat général.
  4. 4 Trivialement : le scrutin à un tour ne lit jamais au-delà du premier choix.
Toutes les méthodes, critère par critère
Dans Condorcet.Vote

Nos choix d'implémentation.

  • Le gagnant de Condorcet en tête. Quand il existe, CondorcetPHP le place toujours au premier rang.
  • Une approximation assumée. Dodgson exact n'est pas proposé : son calcul peut devenir impraticable.
  • Une limite à connaître. Le score ne regarde que les défaites : une option battue par toutes les autres peut se classer devant une option qui n'en perd qu'un.
Sources

Pour aller plus loin.

Encyclopédie Dodgson’s method Wikipedia
Documentation Voting Methods CondorcetPHP · docs.condorcet.io
Article Approximability of Dodgson’s rule John C. McCabe-Dansted, Geoffrey Pritchard, Arkadii Slinko (2008) · Social Choice and Welfare 31(2)

Les autres méthodes

Revenir au classement de Condorcet