Les mathématiques de la démocratie, II

Et le vainqueur du second tour est...

Le critère de Condorcet

Piste verte Le 10 mai 2012  - Ecrit par  Rémi Peyre Voir les commentaires (10)

Au XVIIIe siècle, le Marquis de Condorcet, cherchant à définir une théorie cohérente de la volonté du peuple, proposa le critère suivant pour déterminer le vainqueur “légitime” d’une élection de type présidentiel : « s’il existe un candidat qui, lorsqu’on le confronte à n’importe quel autre candidat, est préféré à cet autre candidat par une majorité d’électeurs, alors ce candidat est celui d’entre tous que le peuple préfère ». Dans ce texte, nous commencerons par expliquer quelles sont les justifications philosophiques et mathématiques de ce critère, puis nous regarderons dans quelles circonstances il y a ou pas un « vainqueur de Condorcet », avant de présenter une méthode qui généralise le critère de Condorcet lorsqu’aucun tel vainqueur n’existe. (Ce texte s’inscrit dans la continuité d’un article précédent du même auteur, et sera encore suivi par un troisième article).

Préambule : Retour sur l’élection présidentielle française

Le 6 mai dernier, François Hollande a été élu Président de la République Française. Pour nos lecteurs étrangers, rappelons d’abord comment fonctionne une élection présidentielle en France. Un nombre restreint de candidats (10 en l’occurrence) de bords politiques variés ayant été préalablement sélectionnés par les élus locaux, on procède entre eux à un scrutin uninominal à deux tours. Dans un tel scrutin, on organise d’abord un premier tour de vote dans lequel chaque électeur doit choisir un seul des candidats (ou s’abstenir). Si un des candidats reçoit la majorité absolue des suffrages exprimés (ce qui est rare en pratique), alors ce candidat est déclaré vainqueur. Sinon, on procède à un second tour de vote dans lequel les deux candidats ayant reçu le plus de suffrages au premier tour s’affrontent en face-à-face ; le candidat recevant le plus de voix au second tour est alors déclaré vainqueur.

Rappelons également quels ont été les résultats de l’élection de 2012. Pour simplifier la présentation, nous ne retiendrons ici que les cinq candidats principaux (que nous abrègerons parfois par leur initiale), à savoir François Bayrou (B), François Hollande (H), Marine Le Pen (L), Jean-Luc Mélenchon (M) et Nicolas Sarkozy (S). Les résultats du premier tour ont été les suivants [1] :

  1. Hollande (31 %)
  2. Sarkozy (28 %)
  3. Le Pen (19 %)
  4. Mélenchon (13 %)
  5. Bayrou (9 %)

Aucun des candidats n’ayant dépassé 50 % des voix, il y a donc eu un second tour opposant Hollande à Sarkozy, dont les résultats ont été les suivants :

  1. Hollande (52 %)
  2. Sarkozy (48 %)
JPEG - 32.4 ko
François Hollande
Hollande, le candidat élu par le peuple.

Au final, c’est donc Hollande qui a été élu président.

Soyons maintenant un peu plus curieux, et demandons-nous quels auraient pu être les résultats des autres faces-à-faces imaginables. Outre le second tour H – S qui a réellement eu lieu, il y aurait eu 9 autres possibilités : B – H, B – L, B – M, B – S, H – L, H – M, L – M, L – S et M – S. Évidemment nous ne saurons jamais avec certitude ce qu’auraient donné ces seconds tours fictifs ; toutefois, à en croire les instituts de sondage [2],
les résultats auraient été à peu près les suivants [3] :

  • Bayrou bat Hollande 51 – 49 ;
  • Bayrou bat Le Pen 74 – 26 ;
  • Bayrou bat Mélenchon 75 – 25 ;
  • Bayrou bat Sarkozy 55 – 45 ;
  • Hollande bat Le Pen 65 – 35 ;
  • Hollande bat Mélenchon 80 – 20 ;
  • Le Pen bat Mélenchon 53 – 47 ;
  • Le Pen est battue par Sarkozy 32 – 68 ;
  • Mélenchon est battu par Sarkozy 36 – 64.

Nous synthétisons tout cela sous la forme du « diagramme des préférences binaires » ci-dessous, où :

  • Chaque candidat est représenté par une position distincte ;
  • Entre chaque paire de candidats, il y a une flèche qui pointe vers celui des deux qui serait vainqueur en face-à-face (on néglige la possibilité d’un ex æquo) ;
  • Sur chaque flèche, on indique le score (en pourcentage) par lequel le vainqueur du face-à-face concerné gagne.

Diagramme des préférences binaires pour l’élection présidentielle

Ce qu’auraient pu donner les 10 seconds tours imaginables entre les cinq candidats principaux à l’élection présidentielle française de 2012 (les flèches pointent vers les vainqueurs).

JPEG - 28.4 ko
François Bayrou
Bayrou, le candidat voulu par le peuple ?

Une constatation frappe : François Bayrou aurait vaincu n’importe lequel de ses adversaires au second tour ! Comme, dans la situation historique, il n’y a pas été qualifié, il n’a évidemment pas été élu, mais plusieurs éditorialistes [voir par exemple ici ou ] ont souligné qu’il y avait là une forme de paradoxe... Ne serait-il pas logique, en effet, qu’un candidat globalement préféré à n’importe quel autre soit considéré comme le préféré de tous [4] ?

Philosophie du critère de Condorcet

Énoncé du critère

JPEG - 42.3 ko
Nicolas de Condorcet
Portrait de Nicolas de Condorcet par Jean-Baptiste Greuze.

C’était en tout cas l’opinion de Nicolas de Condorcet, savant français du XVIIIe siècle qui fut un des pionniers de l’étude mathématique de la démocratie. Il introduisit les définitions suivantes (que nous adaptons ici en langage moderne) :

Définitions (Vainqueur de Condorcet ; Critère de Condorcet)

Si, parmi les candidats à une élection, il en existe un qui, face à n’importe quel autre, lui est préféré par une majorité d’électeurs, alors ce candidat est appelé le vainqueur de Condorcet.

On dit qu’une méthode électorale satisfait le critère de Concorcet quand, lorsqu’il y a un vainqueur de Condorcet, c’est toujours lui que cette méthode déclare vainqueur (sous réserve que les électeurs aient voté selon leurs préférences véritables).

Avant toute chose, une vérification s’impose : nous parlons du vainqueur de Condorcet comme s’il était unique, mais est-ce bien le cas ? La réponse est « oui » :

Théorème (Unicité du vainqueur de Condorcet)

Il ne peut pas y avoir plus d’un vainqueur de Condorcet à une élection.

Démonstration

Imaginons une situation dans laquelle il y aurait deux vainqueurs de Condorcet (au moins), appelés X et Y. Puisque X est un vainqueur de Condorcet, il vainc n’importe lequel de ses concurrents en face-à-face, donc en particulier Y. Mais de même, puisque Y est un vainqueur de Condorcet, il doit vaincre X en face-à-face... Or le face-à-face entre X et Y ne peut évidemment avoir qu’un seul vainqueur : c’est donc qu’il est en fait impossible qu’il y ait plus d’un vainqueur de Condorcet.

La thèse de Condorcet était que, pour qu’une méthode électorale soit vraiment juste, il faut qu’elle satisfasse le critère éponyme. Citons le grand homme :

Il peut réſulter de la manière de voter employée dans les élections ordinaires une déciſion réellement contraire à la pluralité. Ainſi l’on devroit ſubſtituer à cette forme celle dans laquelle chaque Votant, exprimant l’ordre ſuivant lequel il place les Candidats, prononceroit à la fois ſur la préférence reſpective qu’il leur accorde. Lorſqu’on voudra choiſir le candidat le plus digne, il ſuffira que le ſyſtème n’implique point contradiction pour le candidat qui mérite la préférence ſur tous. [5]

Condorcet se serait donc opposé à notre méthode uninominale à deux tours, puisque l’exemple de Bayrou montre que celle-ci ne satisfait pas son critère ! Mais avant d’aller plus loin, il convient d’expliquer quelles sont les justifications théoriques à la thèse de Condorcet.

Justification mathématique du critère de Condorcet [6]

Si vous avez lu mon article précédent, vous vous souvenez sans doute qu’un grand problème de la théorie mathématique des élections est le suivant : les électeurs ont parfois intérêt à “voter stratégique” en exprimant une opinion mensongère qui amènerait le résultat du scrutin à être meilleur pour eux que celui qu’aurait donné un suffrage sincère ! Dans le cas du scrutin uninominal à deux tours dont nous parlions dans le préambule, un exemple typique est ce qu’on appelle le « vote utile ». Imaginons ainsi qu’à la veille du premier tour les sondages donnent Sarkozy loin en tête, suivi de Le Pen et Hollande au coude-à-coude, et nettement plus loin Mélenchon. Considérons un électeur fictif qui est grand supporteur de Mélenchon, est mitigé sur Hollande, n’aime pas Sarkozy et déteste Le Pen. Cet électeur se dit : « si je vote Mélenchon, cela ne suffira pas à le qualifier pour le second tour de toute façon ; par contre je cours le risque de voir un second tour entre les deux candidats que j’aime le moins. En revanche, en votant Hollande, je diminue les chances d’un second tour Sarkozy – Le Pen et je favorise l’élimination de ma candidate détestée ! J’ai donc intérêt à voter Hollande ».

Or, quand on prend en compte ce phénomène de vote stratégique, le vainqueur de Condorcet (s’il y en a un) peut s’arranger pour être élu à coup sûr ! (en tout cas dans la méthode uninominale à deux tours [7]).
En effet, imaginons qu’il y a un vainqueur de Condorcet appelé X, et supposons que les sondages prédisent la victoire d’un autre candidat Y. Comme X est un vainqueur de Condorcet, il y a une majorité d’électeurs qui le préfèrent à Y. Cette majorité peut alors se concerter et se dire « votons tous pour X dès le premier tour ; ainsi il aura une majorité de suffrages sur son nom et sera élu, ce qui plus intéressant pour nous ! ». Bien sûr, cela ne signifie par pour autant que tous les électeurs de cette majorité aient X pour candidat préféré. On peut même imaginer qu’un nombre conséquent d’eux préfèrent en fait un troisième candidat Z, et puissent être tentés de faire gagner Z avec l’aide d’anciens électeurs de Y qui préfèrent également Z à X... Mais c’est peine perdue, car X étant un vainqueur de Condorcet, il y a aussi une majorité (mais pas constituée des mêmes électeurs, bien sûr) qui préfère X à Z ; si Z devient trop dangereux dans les sondages, c’est cette majorité qui se liguera alors pour voter X afin d’éviter l’élection de Z ! [8]

Ainsi, une méthode satisfaisant le critère de Condorcet a ceci d’avantageux que les électeurs n’ont pas à se creuser la cervelle pour savoir si leur vote est bien calculé : avec une telle méthode en effet, s’il y a un vainqueur de Condorcet, il sera nécessairement élu !

Une autre qualité des méthodes satisfaisant le critère de Condorcet est la suivante : alors que les méthodes classiques (notamment les méthodes A, B, C, D et E de l’article précédent) sont sujettes à un phénomène d’“éparpillement des voix” quand le nombre de candidats devient grand, phénomène qui peut conduire à un résultat non pertinent, le résultat d’une méthode satisfaisant le critère de Condorcet ne change pas quand on retire ou qu’on ajoute des “petits” candidats :

Théorème (Indifférence aux petits candidats)
  1. Si on part d’une situation dans laquelle un des candidats est vainqueur de Condorcet, et qu’un ou plusieurs des autres candidats se retirent de l’élection, alors le vainqueur de Condorcet initial reste vainqueur de Condorcet après ce retrait.
  2. Inversement, si on part d’une situation dans laquelle un candidat est vainqueur de Condorcet, et qu’on introduit un ou plusieurs nouveaux candidats à chacun desquels le vainqueur initial est préféré en face-à-face, alors le vainqueur de Condorcet initial reste vainqueur de Condorcet après cet ajout.

Démonstration

Le retrait ou l’ajout d’un candidats ne change pas les préférences binaires des électeurs entre les autres candidats. Pour le point i, puisque notre vainqueur de Condorcet initial battait initialement tous ses adversaires en face-à-face, cela reste donc le cas si un ou plusieurs de ses adversaires se retirent. Pour le point ii, notre vainqueur de Condorcet initial continue de même à battre tous ses adversaires initiaux, et nous avons supposé qu’il battait également ses nouveaux adversaires, de sorte qu’il est bien toujours vainqueur de Condorcet dans la nouvelle situation.

Notons en revanche que, si le vainqueur de Condorcet éventuel est dans un sens un vainqueur inéluctable, ce n’est par contre pas nécessairement celui qui est réellement le préféré du peuple (au sens que nous avions évoqué dans l’article précédent, c’est-à-dire en mesurant le bonheur total que ce candidat apporterait à la population s’il était élu). Ainsi, s’il n’y a que deux candidats X et Y, et que 51 % des électeurs préfèrent légèrement X à Y et 49 % des électeurs préfèrent très largement Y à X, c’est X qui sera élu alors qu’on a envie de dire que c’est plutôt Y qui représente la volonté du peuple. Cela dit, ce phénomène de « dictature de la majorité » [9]
n’est pas directement lié au critère de Condorcet : c’est en fait un vice inhérent à la démocratie [10],
comme l’avait déjà compris Kant [11].

Pour l’instant, nous avons beaucoup parlé de philosophie et peu de mathématiques (et encore moins de recherche !). Mais cette introduction était nécessaire pour comprendre pourquoi le critère de Condorcet est un objet mathématique naturel et important. Dans la seconde partie de cet article, nous allons maintenant parler de recherches beaucoup plus récentes qui tournent autour de ce critère.

Le paradoxe de Condorcet existe-t-il vraiment ?

Le paradoxe de Condorcet

Le critère de Condorcet nous amène naturellement à parler du paradoxe de Condorcet, que nous avions déjà rencontré dans l’article précédent. Ce paradoxe énonce en substance qu’il n’y a pas nécessairement de vainqueur de Condorcet :

Paradoxe de Condorcet (1785)

Dès qu’il y a au moins 3 candidats, il existe des situations où il n’y a pas de vainqueur de Condorcet.

Démonstration

Supposons qu’il y ait au moins 3 candidats, et choisissons trois candidats particuliers parmi eux, appelés X, Y et Z. Nous imaginons que tous les électeurs préfèrent X, Y et Z à tous les autres candidats, de sorte qu’aucun de ces autres candidats ne peut être vainqueur de Condorcet. Maintenant, on peut imaginer en outre que 40 % d’électeurs ont l’ordre de préférence « X puis Y puis Z », 35 % « Y puis Z puis X » et 25 % « Z puis X puis Y ». Alors 65 % des électeurs préfèrent X à Y (donc Y n’est pas un vainqueur de Condorcet), 75 % préfèrent Y à Z (donc Z n’est pas un vainqueur de Condorcet), et 60 % préfèrent Z à X (donc X n’est pas un vainqueur de Condorcet) : aucun candidat n’est donc vainqueur de Condorcet.

Toutefois, nous avons vu dans le préambule un cas d’élection réelle avec pas moins de 5 candidats dans lequel il existait bel et bien un vainqueur de Condorcet [12] !
Cela suggère qu’il pourrait éventuellement exister un phénomène qui interdirait le paradoxe de Condorcet en pratique, parce que les situations politiques réalistes vérifieraient certaines hypothèses particulières sous lesquelles le paradoxe est impossible. Dans les paragraphes suivants, nous allons présenter différentes modélisations des préférences politiques, et voir si celles-ci permettent ou pas l’occurrence du paradoxe de Condorcet.

Paradoxe de Condorcet sur un échiquier politique

Nous allons introduire ici une modélisation assez réaliste des préférences politiques des électeurs que nous appellerons modélisation par échiquier politique, dont l’idée est simplement qu’en général, nous votons pour le candidat dont les positions s’éloignent le moins de nos opinions. On supposera ainsi qu’il existe un « échiquier politique » abstrait (qui permet de parler de « distance politique ») sur lequel on peut placer aussi bien les candidats que les électeurs, tel que les préférences de chaque électeur aillent du candidat qui lui est le plus proche vers celui qui lui est le plus éloigné.

On pourrait espérer qu’avec une telle modélisation, il n’y ait jamais de paradoxe de Condorcet... mais ce n’est pas le cas ! Supposons en effet que l’échiquier politique corresponde à un véritable échiquier (dont les cases mesurent, disons, 5 cm de côté), où l’on place un candidat X sur la case b7, un candidat Y sur la case f7, un candidat Z en e4 et un candidat W en c2. Nous imaginons que l’électorat est divisé en quatre groupes de tailles diverses dont chacun a exactement la même position qu’un des candidats [13] :
34 % des électeurs sont au niveau de X, 26 % au niveau de Y, 18 % de Z et 22 % de W. Les distances entre candidats sont alors celles qui sont indiquées sur le dessin ci-dessous, de sorte qu’on a les préférences suivantes pour les électeurs (« X>Y » signifiant « X est préféré à Y ») :

L’exemple de l’échiquier

Voici, à gauche, une configuration d’échiquier politique telle que, s’il y a 34 % des électeurs en X, 26 % en Y, 22 % en Z et 18 % en W, et que chaque électeur préfère les candidats dont il est le plus proche, alors aucun candidat n’est vainqueur de Condorcet : à droite, le diagramme de préférences binaires correspondant.

  • X > Y > Z > W pour 34 % des électeurs ;
  • Y > Z > X > W pour 26 % des électeurs ;
  • W > Z > X > Y pour 22 % des électeurs ;
  • Z > W > Y > X pour 18 % des électeurs.

Alors, dans cette configuration, X n’est pas un vainqueur de Condorcet (parce qu’il est battu par Z à 66 %), ni Y (battu par X à 56 %), ni Z (battu par Y à 60 %), ni W (battu par Z à 74 %) : on a donc bien paradoxe de Condorcet !

Les théorèmes de l’électeur médian

Dans l’exemple de l’échiquier, nous avons fabriqué un échiquier politique de dimension 2, c’est-à-dire avec 2 coordonnées (une pour les colonnes et une pour les lignes). Ce n’était pas un hasard ! Car si l’échiquier politique n’a qu’une seule dimension, on peut démontrer qu’il existe toujours un vainqueur de Condorcet :

Théorème (Premier théorème de l’électeur médian ; Black 1958)

Lorsque l’échiquier politique est un axe gradué (qu’on interprète généralement comme un positionnement politique du “plus à gauche” vers le “plus à droite”), il y a toujours un vainqueur de Condorcet.

Pour démontrer ce théorème, nous allons d’abord introduire une définition qui nous sera utile dans la preuve :

Définition (Profil de préférences en Λ)

On dit qu’un électeur a un profil de préférences en Λ (lire « lambda ») quand, lorsqu’on parcourt la liste des candidats du plus à gauche au plus à droite, la préférence de cet électeur monte jusqu’à atteindre son candidat préféré, puis redescend. (Éventuellement, le candidat préféré peut être le plus à gauche ou le plus à droite de tous ; l’important étant de ne jamais remonter après être descendu).

Par exemple, si nous supposons que les candidats de l’élection présidentielle se rangent de gauche à droite selon l’ordre « M, H, B, S, L », alors les préférences « B>H>S>L>M » ou « L>S>B>H>M » sont des profils en Λ, mais pas « H>M>S>B>L », puisqu’une telle préférence baisse entre H et B avant de remonter entre B et S.

Démonstration du premier théorème de l’électeur médian

Le premier point est de constater que, quand l’échiquier politique est un axe gradué, tous les électeurs ont un profil de préférence en Λ. En effet, considérons n’importe quel électeur. Quand on parcourt l’échiquier politique de gauche à droite, on commence par se rapprocher de cet électeur avant de s’en éloigner, de sorte que les préférences de l’électeur augmentent (tant qu’on est plus à gauche que cet électeur) avant de redescendre (une fois qu’on est plus à droite) : cela correspond bien à un profil de préférences en Λ. (Si aucun candidat n’est situé exactement à la même position que l’électeur, il faudra regarder les distances précises pour savoir si le candidat préféré de cet électeur est celui situé immédiatement à sa gauche ou immédiatement à sa droite, mais dans les deux cas on a bien un profil en Λ).

Nous prouvons maintenant le théorème. Pour éviter les problèmes d’ex æquo, supposons qu’il y a un nombre impair d’électeurs. Chacun de ces électeurs a un candidat préféré. Imaginons que nous demandions à chaque électeur d’écrire le nom de son candidat préféré sur un bulletin puis que nous classions les bulletins obtenus depuis le candidat le plus à gauche vers le candidat le plus à droite, et appelons X le candidat qui est sur le bulletin situé au milieu de ce classement. J’affirme alors que X est un vainqueur de Condorcet. En effet, considérons un candidat Y situé, par exemple, plus à droite que X (pour un candidat plus à gauche, il suffirait d’inverser « droite » et « gauche » dans la suite). Comme X est au milieu de notre classement des bulletins, il y a une majorité absolue de bulletins qui sont au nom soit de X, soit d’un candidat plus à gauche que X, ce qui signifie qu’il y a une majorité absolue d’électeurs dont le candidat préféré est soit X, soit un candidat situé plus à gauche que X. Considérons alors un tel électeur, dont nous appelons Z le candidat préféré (Z pouvant éventuellement être le même que X). Nous savons par le paragraphe ci-dessus que notre électeur a un profil de préférences en Λ, donc quand on s’éloigne de Z vers la droite, les préférences de l’électeur ne font que décroître. Or ici X est au moins aussi à droite que Z et Y est encore plus à droite que X, donc on croisera Y postérieurement à X au cours de cet éloignement ; par conséquent notre électeur préfère X à Y. Comme il en est de même pour une majorité absolue d’électeurs, cela signifie que X est majoritairement préféré à Y, et comme on peut faire le même raisonnement pour tous les Y possibles, cela prouve que X est un vainqueur de Condorcet.

Notez que cette démonstration montre que le théorème reste valable dès que tous les électeurs ont un profil de préférences en Λ.

Le défaut de ce premier théorème de l’électeur médian (et de la modélisation par échiquier politique en général) est qu’il considère que la seule qualité des candidats qui intéresserait les électeurs est leur positionnement politique. Or, à positionnement politique égal, il se peut que certains candidats soient “meilleurs” ou “moins bons”, par exemple à cause de leurs qualités intellectuelles ou charismatiques. Un modèle plus fin est donc le suivant : d’une part, il y a un axe gradué sur lequel sont placés les candidats et les électeurs, et d’autre part est aussi associée à chaque candidat une « valeur intrinsèque ». Chaque électeur calcule alors pour les différents candidats un « score » égal à la valeur intrinsèque du candidat moins la distance du candidat, et classe les candidats par score décroissant : un exemple est donné sur le dessin ci-dessous.

Axe politique avec valeurs intrinsèques

Voici un exemple tenant compte à la fois du placement des candidats sur l’axe politique « gauche – droite » et de la valeur intrinsèque des candidats. Dans cet exemple, il y a cinq candidats repérés par des points, la valeur intrinsèque de chacun d’eux étant indiquée entre parenthèses. Si nous considérons un électeur situé à la position « e », cet électeur donne alors à M un score égal à 9 (valeur) – 5 (distance) = 4, à H un score de 8 – 1 = 7, à B un score de 5 – 1 = 4, et de même à S et L des scores respectifs de 5 et 3. Par conséquent, l’ordre de préférences de cet électeur est « H > M > S > B > L » — qui n’est pas un profil en Λ.

Eh bien, dans ce modèle, on est encore assuré de l’existence d’un vainqueur de Condorcet :

Théorème (Second théorème de l’électeur médian ; Roberts 1977)

Si les candidats et les électeurs sont placés sur un même axe gradué d’une part, qu’à chaque candidat est associée une valeur intrinsèque d’autre part, et que les préférences de chaque électeur sont déterminées par la différence « valeur intrinsèque ­− distance du candidat », alors il y a toujours un vainqueur de Condorcet.

Pour démontrer ce théorème, nous commençons ici aussi par introduire une définition :

Définition (Préférences décroisées)

Étant donnés des candidats rangés de gauche à droite et des électeurs également rangés de gauche à droite, on dit que la configuration des préférences est décroisée s’il est impossible de trouver un candidat X plus à gauche qu’un autre candidat Y et un électeur A plus à gauche qu’un autre électeur B qui soient tels que A préfère Y à X mais que B préfère X à Y (autrement dit, qui soient tels que l’électeur de gauche préfère le candidat de droite et l’électeur de droite le candidat de gauche).

Démonstration du second théorème de l’électeur médian

Le premier point est de constater que, sous les hypothèses du théorème, la configuration des préférences est décroisée. Considérons en effet deux candidats X et Y, avec Y plus à droite que X. Dire que la configuration des préférences est décroisée signifie que, à mesure qu’un électeur fictif se déplace de gauche à droite sur l’axe politique, il ne peut pas passer d’une préférence « Y>X » à une préférence « X>Y » ; pour montrer cela, il suffit donc d’établir que la différence « score de Y − score de X » ne peut qu’augmenter quand on va de gauche à droite. Or, dans cette différence de scores, la seule chose qui change d’un électeur à l’autre est la partie du score qui dépend de la distance : celle qui dépend du score est la même ! Ainsi, il nous suffit en fait de montrer que la différence « distance de Y − distance de X » ne fait que diminuer quand on va de la gauche vers la droite. Or donc, que se passe-t-il quand on va de la gauche vers la droite ? Dans un premier temps, tant qu’on est encore à gauche de X, chaque pas vers la droite nous rapproche autant de X que de Y, et donc la différence « distance à Y − distance à X » ne varie pas. Puis, quand on se trouve entre X et Y, chaque pas vers la droite fait non seulement diminuer la distance à Y, mais aussi augmenter celle à X, de sorte que la différence « distance à Y − distance à X » diminue. Enfin, au-delà de Y, chaque pas vers la droite nous éloigne autant de X que de Y, et donc à nouveau la différence des distances reste constante. Ainsi on a bien une configuration de préférences décroisée.

Nous prouvons maintenant le théorème. Pour éviter les problèmes d’ex-æquo, supposons qu’il y a un nombre impair d’électeurs. Si nous classons ces électeurs de gauche à droite sur l’axe politique, il y en a alors un qui se retrouve au milieu de ce classement, que nous appellerons l’« électeur médian ». J’affirme que les préférences majoritaires sont exactement les mêmes que celles de cet électeur médian, et donc qu’en particulier le candidat préféré de l’électeur médian est un vainqueur de Condorcet [14].
En effet, supposons qu’entre deux candidats X et Y, l’électeur médian préfère X ; pour fixer les idées, disons que Y est plus à droite que X (sinon, inverser « droite » et « gauche »). Alors d’après le résultat intermédiaire ci-dessus, tous les électeurs plus à gauche que l’électeur médian préfèrent également X à Y, et donc il y a une majorité d’électeurs qui préfèrent X à Y, ce qu’on voulait démontrer.

Notez que cette démonstration montre que le théorème reste valable dès que la configuration des préférences est décroisée [15].

En plus de démontrer l’existence du vainqueur de Condorcet, la preuve ci-dessus nous dit à quoi ce vainqueur correspond : il s’agit du candidat préféré de l’électeur situé “au milieu” de tous sur l’axe des préférences (d’où le nom de « théorème de l’électeur médian »). Un phénomène similaire se produisait pour le premier théorème de l’électeur médian, où le résultat de l’élection correspondait au choix le plus central parmi les candidats favoris des différents électeurs. Une moralité qu’on peut en tirer est que le critère de Condorcet favorise les candidats “centristes” par rapport aux candidats plus orientés ou extrémistes. Est-ce un comportement souhaitable ? Les avis divergent sur cette question [16] :
pour certains, favoriser les centristes risque de dégoûter les électeurs non centristes qui auraient l’impression de ne jamais être pris en compte, et de favoriser la politique du consensus mou au détriment de projets plus ambitieux ; d’autres, au contraire, estiment qu’une politique centriste apaiserait le débat en permettant à chacun de s’y retrouver un peu, et qu’une grande stabilité politique serait plus propice à la mise en place de projets à long terme...

Et quand il n’y a pas de vainqueur de Condorcet ?

Les théorèmes de l’électeur médian tendent à indiquer que dans les situations concrètes, on aura la plupart du temps un vainqueur de Condorcet, ce que corrobore effectivement l’histoire des élections [17].
Cela dit, la modélisation purement unidimensionnelle sur laquelle reposent ces théorèmes est clairement trop réductrice, et l’exemple de l’échiquier nous montre qu’il suffit d’un cas à peine plus complexe pour voir réapparaître le paradoxe de Condorcet... Bref, si on souhaite appliquer une méthode électorale satisfaisant le critère de Condorcet, il faudra donner une règle pour désigner le candidat élu quand il n’y a pas de vainqueur de Condorcet. Mais laquelle ? Cette question n’a commencé à être étudiée qu’il y a quelques décennies [18],
notamment parce qu’avant l’invention de l’informatique il était pratiquement impossible de réaliser le dépouillement d’un vote où les électeurs indiquent leurs préférences entre tous les candidats. C’est des recherches sur ce sujet que nous allons maintenant parler.

La méthode minimax

Commençons par une approche très simple. On peut se dire : « à la base, un vainqueur de Condorcet est un candidat qui réalise plus de 50 % face à tous les autres. Si aucun des candidats n’y parvient, on peut baisser le seuil des 50 % pour dire : “s’il y a un seul des candidats qui parvient à atteindre, par exemple, 45 % face à n’importe quel autre, alors c’est ce candidat qui doit être élu” ». Autrement dit, le protocole est le suivant : pour chacun des candidats, on regarde le pire des scores qu’il ferait dans ses différents faces-à-faces, puis on déclare élu celui des candidats dont le pire des scores est le meilleur. Cette méthode est appelée méthode minimax, car elle regarde qui est le meilleur (« max ») dans la situation où il est le moins bon (« mini »).

Ainsi, pour l’exemple de l’échiquier présenté plus haut (où il n’y a pas de vainqueur de Condorcet), la pire défaite de X a lieu contre Z par 66 %, la pire défaite de Y contre X par 56 %, la pire défaite de Z contre Y par 60 % et la pire défaite de W contre Z par 78 %. La plus légère de ces pires défaites est celle de Y, qui est donc le vainqueur minimax.

Cela semble tout naturel ! Hélas, cette méthode ouvre la voie à une forme de “manipulation” (synonyme péjoratif de « vote stratégique ») particulièrement dangereuse. Supposons en effet que dans l’exemple de l’échiquier abordé précédemment, nous ayons en plus un groupe V composé d’“anarchistes” [19]. Ces anarchistes sont relativement nombreux puisqu’ils constituent 40 % de la population totale, de sorte qu’on a la distribution globale suivante : X 20 %, Y 16 %, Z 11 %, W 13 %, V 40 %. Cependant les anarchistes font l’unanimité contre eux en-dehors de leur groupe : aussi bien les partisans de X que de Y que de Z que de W classent V en dernière position dans leur ordre de préférences ! C’est là que les anarchistes ont une idée géniale pour prendre le pouvoir malgré cet important handicap. Ils se disent : « plutôt que de voter de façon équilibrée entre nos concurrents, nous allons nous arranger pour amplifier le plus possible les pires défaites de chacun d’eux ! ».

Pour ce faire, les électeurs du groupe V se divisent en trois sous-groupes (par contre, ils ne présentent toujours qu’un seul candidat) :

  • Le sous-groupe $V_1$ compte 18 % de tous les électeurs et vote « V > Z > Y > X > W » ;
  • Le sous-groupe $V_2$ compte 12 % des électeurs et vote « V > Y > X > Z > W » ;
  • Le sous-groupe $V_3$ compte 10 % des électeurs et vote « V > X > Z > Y > W ».

Avec cette stratégie, on a donc les votes suivants :

  • X > Y > Z > W > V pour 20 % des électeurs ;
  • V > X > Y > Z > W pour 18 % des électeurs ;
  • Y > Z > X > W > V pour 16 % des électeurs ;
  • W > Z > X > Y > V pour 13 % des électeurs ;
  • V > Z > X > Y > W pour 12 % des électeurs ;
  • Z > W > Y > X > V pour 11 % des électeurs ;
  • V > Y > Z > X > W pour 10 % des électeurs.

Cela conduit au diagramme de préférences binaires suivant (à droite) :

La manipulation des anarchistes

Voici les diagrammes correspondant à l’exemple de l’échiquier avec anarchistes, à gauche dans le cas où les anarchistes votent sincèrement (on suppose que les préférences des anarchistes entre X, Y et Z sont aléatoires et que W est toujours leur candidat détesté), et à droite avec la manipulation que nous avons expliquée (les changements sont indiqués en rouge). Dans le premier cas, le vainqueur minimax est Y ; dans le second, c’est V, à qui sont pourtant préférés tous les autres candidats !

Alors, les pires défaites de X, Y et Z sont respectivement de 62 %, 63 % et 64 % (respectivement contre Z, X et Y), la pire défaite de W est de 87 % (contre Z) et la pire défaite de V est de 60 % (contre n’importe lequel de ses adversaires) : c’est donc V qui devient le vainqueur minimax !

Évidemment, les partisans de X, Y , Z et W ont alors la possibilité de s’allier pour désigner Y comme candidat commun et faire échouer le plan de V, mais nous avons dit quelques paragraphes plus haut que la philosophie du critère de Condorcet était d’épargner autant que possible aux électeurs les tourments du vote stratégique ! Il semble donc, selon ce point de vue, que la méthode minimax ne soit pas pertinente quand il n’y a pas de vainqueur de Condorcet.

La méthode Schulze

Nous allons maintenant présenter une méthode conçue en 1997 par un étudiant en physique allemand du nom de Markus Schulze, qui ne présente pas le handicap qu’avait la méthode minimax. La philosophie derrière la méthode Schulze est la suivante : « au fond, une élection, ce n’est jamais qu’une astuce pour éviter les désagréments des révolutions : on consulte les électeurs afin de savoir qui finirait par gagner la révolution sans avoir à se battre ! ».

Ce qu’on appellera une « révolution », ici, c’est quand un grand nombre d’électeurs se mettent d’accord pour faire tomber le président et le remplacer par un autre, sur l’identité duquel ils se sont entendus préalablement. Dans ce sens-là, il est facile de comprendre le critère de Condorcet : si un candidat (appelons-le X) est vainqueur de Condorcet, n’importe quel autre candidat qui arriverait au pouvoir serait rapidement renversé par la majorité qui préfère X à ce candidat, alors qu’une fois que X sera au pouvoir il n’y aura jamais de majorité pour le renverser, ce qui rendra son assise beaucoup plus stable [20].
Au final, puisqu’on a rapidement des transitions de n’importe qui vers X et rarement des transitions de X vers n’importe qui, c’est bien X qui sera au pouvoir la plupart du temps. (Notez bien qu’ici nous ne prétendons pas qu’il est impossible de renverser un président sans avoir une majorité liguée contre lui : nous disons juste que cela est très nettement plus facile de le faire dès qu’on a un peu plus de personnes pour mener la révolution).

Regardons alors ce qui arriverait dans un tel cadre pour l’exemple de l’échiquier avec anarchistes. Les révolutions ont tendance à renverser les présidents dans le sens indiqué par les flèches, et beaucoup plus rarement en sens inverse. Par conséquent, au bout de quelques révolutions, le président est forcément X, Y ou Z, puisqu’une fois qu’on est arrivé à un de ces trois-là il n’y a aucun chemin suivant les flèches qui ramène en W ou V ! On voit donc déjà (comme cela nous paraissait naturel) que ce n’est pas V que les révolutions amèneront au pouvoir la plupart du temps.

Poursuivons. Nous savons que ce seront essentiellement X, Y et Z qui se partageront le pouvoir, mais dans quelles proportions ? Si nous regardons juste les flèches concernant ces trois candidats, nous avons le diagramme de gauche ci-dessous :

La méthode Schulze contre la manipulation des anarchistes

Ces diagrammes expliquent ce qui se passe quand on applique la méthode Schulze à la situation où les anarchistes tentent leur manipulation. Le groupe de tête du diagramme des préférences binaires dans cette situation [voir la figure précédente] est alors constitué des trois candidats {X, Y, Z} : en particulier V est éliminé puisqu’il était battu par tous les autres candidats ! Dans un second temps, on regarde le diagramme des préférences binaires entre ces trois candidats [à gauche]. Pour faire apparaître un groupe de tête plus petit, on supprime la flèche la plus faible [en rouge]. Le nouveau diagramme [à droite] a alors un groupe de tête constitué du seul candidat X : c’est donc lui qui est déclaré vainqueur par la méthode.

Maintenant, l’idée est que, de même qu’il était beaucoup plus difficile de faire une révolution avec moins de 50 % du peuple qu’avec plus de 50 %, il est beaucoup plus difficile de faire une révolution avec 62 % qu’avec 63 % ou 64 %... Du coup, on efface la flèche marquée « 62 % » pour signifier que cette révolution est rare, et on arrive au diagramme de droite ci-dessus. Au bout de quelques révolutions, c’est alors forcément X qui est président : l’idée de la méthode Schulze est donc de dire que c’est lui qui doit être proclamé vainqueur de l’élection [21] !

Maintenant que nous avons expliqué le principe de la méthode Schulze, nous allons pour finir en donner une définition rigoureuse et nous assurer que celle-ci donne bien un vainqueur unique dans tous les cas. Nous supposerons simplement qu’il n’y a jamais deux candidats exactement à égalité ni deux flèches ayant exactement la même force dans le diagramme des préférences binaires, ce qui est toujours le cas en pratique quand il y a beaucoup d’électeurs.

Notez que dans ce paragraphe, nous rencontrerons parfois des diagrammes de préférences binaires incomplets, c’est-à-dire où certains candidats ne sont pas reliés par des flèches.

Définition (Groupe de tête)

Dans un diagramme de préférences binaires (éventuellement incomplet), on dit qu’un candidat (appelé ici X) appartient au groupe de tête quand, en partant de n’importe quel autre candidat, il est possible de suivre un chemin selon les flèches qui part de ce candidat et aboutit en X.

Ici, il est important de remarquer que si le diagramme est complet, le groupe de tête n’est jamais vide :

Théorème

Dans un diagramme de préférences binaires complet, le groupe de tête n’est jamais vide.

Démonstration

Nous allons présenter une façon de construire le groupe de tête qui montre que celui-ci n’est jamais vide. J’appellerai ici « surgroupe de tête » tout groupe de candidats tel que, quand on part de n’importe quel candidat qui n’est pas dans ce groupe, on peut arriver à n’importe quel candidat du groupe en suivant les flèches.

J’observe d’abord que le groupe de tous les candidats est un surgroupe de tête, puisqu’il n’y a aucun candidat qui n’appartienne pas à ce groupe !

Maintenant, je dis la chose suivante : quand on a un surgroupe de tête,

  • Ou bien ce surgroupe de tête est le vrai groupe de tête ;
  • Ou bien, parmi ce surgroupe de tête, on peut sélectionner un certain nombre non nul de candidats qui forment un surgroupe de tête strictement plus petit.

En effet, supposons que notre surgroupe de tête ne soit pas le vrai groupe de tête. La seule façon que cela arrive est qu’il existe au moins un candidat X dans ce surgroupe de tête auquel il ne soit pas possible d’aboutir en partant d’un autre candidat Y, lequel est nécessairement dans le surgroupe de tête, puisqu’on sait qu’on peut aboutir à n’importe quel candidat du surgroupe de tête à partir de n’importe quel candidat hors du surgroupe de tête. Maintenant, je sélectionne les candidats du surgroupe de tête qui sont tels que, quand on part d’un de ces candidats, on ne peut pas arriver en X. Ce nouveau groupe n’est pas vide puisqu’il contient Y, et il est strictement plus petit que le surgroupe de tête initial puisqu’il ne contient pas X. J’affirme que ce nouveau groupe est encore un surgroupe de tête. En effet, considérons un candidat Z qui n’est pas dans ce nouveau groupe. Soit ce candidat n’était pas dans notre surgroupe de tête initial, et alors sait qu’on peut aller de Z à n’importe quel point de notre surgroupe de tête initial et donc en particulier à n’importe quel point de notre nouveau groupe. Soit ce candidat était dans notre surgroupe de tête initial mais pas dans le nouveau groupe. Alors, du candidat Z, on peut revenir au candidat X en suivant les flèches (par définition du nouveau groupe). Mais du candidat X, on peut aller vers n’importe quel candidat W du nouveau groupe : en effet, il existe une flèche entre X et W vu que notre diagramme est complet, et celle-ci pointe nécessairement de X vers W puisqu’il n’y a pas de chemin de W vers X ! Au final, on a montré que pour tout candidat Z qui n’est pas dans notre nouveau groupe, on peut aller de ce candidat à n’importe quel candidat du nouveau groupe en suivant les flèches, ce qui signifie bien que le nouveau groupe est un surgroupe de tête.

Partons maintenant du surgroupe de tête formé par tous les candidats, et tant qu’on n’a pas encore trouvé le vrai groupe de tête, appliquons la méthode ci-dessus pour former des surgroupes de tête de plus en plus petits, mais tous non vides. Forcément à un moment on sera obligé de s’arrêter, et à ce moment-là notre surgroupe de tête sera le vrai groupe de tête d’après l’alternative ci-dessus, et ce groupe de tête sera bien non vide, ce qui prouve le théorème.

Définition (Méthode Schulze)

À partir d’un diagramme de préférences binaires complet (où toutes les flèches portent des scores différents), on définit le vainqueur de Schulze par la méthode suivante :

  1. On part du diagramme des préférences binaires pour tous les candidats.
  2. S’il n’y a en fait qu’un seul candidat, celui-ci est proclamé vainqueur et on s’arrête.
  3. Sinon, on regarde le groupe de tête : s’il strictement plus petit que l’ensemble initial, on efface tous les candidats qui ne sont pas dans ce groupe de tête (ainsi que les flèches les concernant), et on recommence la méthode en faisant comme s’il n’y avait plus les candidats restants.
  4. Si, en revanche, le groupe de tête contient tous les candidats, on efface progressivement les flèches de plus petits scores, jusqu’à ce que le groupe de tête du diagramme obtenu en effaçant les flèches exclue au moins un des candidats (ce qui arrive forcément, car une fois que toutes les flèches seraient effacées il n’y aurait plus personne dans le groupe de tête). À ce moment-là, on efface tous les candidats qui ne sont pas dans ce nouveau groupe de tête (ainsi que les flèches les concernant), et on recommence la méthode en faisant comme s’il n’y avait plus que les candidats restants.

Pour s’assurer que la méthode conduit bien à la désignation d’un vainqueur, il reste à vérifier que, au cours de la procédure d’effacement des flèches, on ne risque pas de tomber sur un groupe de tête vide :

Théorème

Si on a un diagramme de préférences binaires pour plusieurs candidats (éventuellement incomplet) dans lequel le groupe de tête contient tous les candidats, alors effacer une seule des flèches ne peut pas amener à une situation où le nouveau groupe de tête serait vide. Par conséquent, quand on part d’un diagramme de préférences binaires dans lequel le groupe de tête contient tous les candidats et qu’on efface ses flèches une à une, le premier moment où le groupe de tête cesse de contenir tous les candidats donne un groupe de tête non vide.

Démonstration

Nous ne démontrons que le début de l’énoncé, la partie qui suit « par conséquent » en découlant immédiatement. Partons donc d’un diagramme de préférences binaires dans lequel le groupe de tête contient tous les candidats, et effaçons-en une flèche, dont nous appelons X le candidat duquel elle partait. Nous allons montrer que X est forcément dans le nouveau groupe de tête, qui sera donc non vide. Pour ce faire, considérons n’importe quel candidat Y, et montrons qu’on peut aller de Y à X en suivant les flèches malgré l’effacement effectué. Comme, avant l’effacement de la flèche, le groupe de tête contenait tous les candidats, on avait alors un chemin qui allait de Y à X. Mais forcément ce chemin n’empruntait pas la flèche effacée, puisque cette flèche part de X alors que dans notre chemin X est le point d’arrivée ! C’est donc que le chemin peut toujours être suivi une fois la flèche effacée, ce qu’on voulait.

Nous avions dit que l’intérêt de la méthode Schulze était d’éviter les manipulations comme celle des anarchistes dans l’exemple de l’échiquier. On peut effectivement prouver qu’une telle manipulation est impossible avec cette méthode :

Théorème (Robustesse à la manipulation)

Supposons qu’il y a deux types de candidats : les candidats « déraisonnables » et les candidats « raisonnables » (on suppose qu’il y a au moins un candidat raisonnable), et appelons « électeur raisonnable » un électeur qui classe tous les candidats déraisonnables à la fin de son ordre de préférences. Alors, s’il y a une majorité absolue d’électeurs raisonnables et que ces électeurs votent sincèrement, aucun candidat déraisonnable ne peut gagner avec la méthode Schulze.

Démonstration

D’après la définition de la méthode Schulze, il suffit de montrer qu’aucun candidat déraisonnable n’appartient au groupe de tête dans une telle situation. Or, quand on part d’un candidat raisonnable et qu’on suit une flèche du diagramme des préférences binaires, on aboutit forcément à un autre candidat raisonnable : en effet, la majorité d’électeurs raisonnables assure qu’aucune flèche ne peut pointer d’un candidat raisonnable vers un candidat déraisonnable. Par conséquent, il est impossible d’avoir un chemin qui parte d’un candidat raisonnable et aboutisse à un candidat déraisonnable, ce qu’on voulait.

Conclusion

Le critère de Condorcet pour une méthode électorale démocratique, qui énonce qu’un candidat préféré à n’importe quel autre en face-à-face doit toujours être élu, permet dans une certaine mesure d’éviter les problèmes du vote stratégique. Quand il n’y a pas de vainqueur de Condorcet, on peut imaginer plusieurs méthodes « de Condorcet » différentes : parmi elles, la méthode Schulze a l’avantage d’avoir à la fois une justification heuristique simple et d’être plus robuste à certaines formes de manipulation que, par exemple, la méthode minimax. C’est actuellement une des méthodes de vote les plus prisées par les théoriciens de la démocratie, et c’est elle qui est utilisée par exemple par les développeurs du système d’exploitation libre Debian — les geeks étant toujours à la pointe des progrès bizarres... ;-)

Dans un prochain article, nous présenterons d’autres méthodes originales, ne satisfaisant pas forcément le critère de Condorcet, mais qui ont également été préconisées par les théoriciens pour leurs propriétés mathématiques.

Références

Post-scriptum :

Je tiens à remercier chaleureusement la Rédaction du site, qui, afin que cet article puisse paraître en phase avec l’actualité, n’a pas hésité à prendre en charge elle-même la relecture du texte : merci donc aux relecteurs internes (notamment Julien Melleray et Clément Caubel) pour leurs conseils judicieux, et aux membres du Comité de Rédaction qui ont mis en place cette procédure exceptionnelle. Merci aussi à ma sœur « Ἀνεπώνυμη » qui a gentiment accepté de sous-traiter la réalisation du dessin de l’échiquier, ainsi qu’à mes collègues Aline K., Anne B. et Olivier G. pour leur assistance dans la traque aux coquilles !

Article édité par Étienne Ghys

Notes

[1L’auteur pris en compte les voix des “petits” candidats en reportant leurs voix sur les “gros” selon les proximités politiques généralement admises.

[2En fait, certains de ces faces-à-faces alternatifs ont réellement été testés par les sondeurs ; cependant la règlementation française interdit de publier un sondage de second tour dont l’affiche ne correspondrait pas à celle prédite par les sondages de premier tour [voir le site de la Commission des Sondages, paragraphe « Cohérence des questions »].

[3Ces chiffres ont été obtenus par l’auteur à l’aide d’un modèle mathématique pour reconstituer les données manquantes à partir des résultats de sondages dont il disposait. Ces “résultats” ne prétendent donc pas refléter fidèlement la réalité et sont à prendre comme une simple hypothèse de travail.

[4NOTA – L’auteur tient à préciser que la question est à prendre dans un sens strictement rhétorique : cet article n’a aucune visée partisane et le but de son introduction est purement pédagogique.

[5Compilation d’extraits du discours préliminaire de l’Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix.

[6La justification de Condorcet lui-même n’était en fait pas fondée sur la notion de volonté du peuple mais plutôt sur celle de vérité : Condorcet considérait les électeurs comme autant de juges devant évaluer quel est le meilleur candidat et interprétait les divergences d’opinions comme des erreurs d’appréciation malencontreuses de ces juges. Ici nous suivrons une approche foncièrement différente.

[7Cela est également valable dans un grand nombre de méthodes de vote, comme les méthodes A et F de notre article précédent. Par contre, ce n’est pas valable dans la méthode C (où les bulletins représentent le candidat contre lequel on vote et où c’est celui qui a le moins de voix qui gagne). Dans cette méthode en effet, si X est un candidat classé en tête par 60 % des électeurs (et donc en particulier vainqueur de Condorcet) et que Y et Z sont deux candidats de positions très proches classés en tête ensemble par 40 % des électeurs, il se passera la chose suivante : les partisans de Y et Z donneront 40 % de suffrages contre X, tandis que les partisans de X ne seront pas assez nombreux pour faire éliminer à la fois Y et Z, puisque cela demanderait que chacun de ces deux candidats reçoive 40 % de suffrages contre lui, soit 80 % en tout : X ne pourra donc pas être élu malgré la majorité d’électeurs en sa faveur !

[8Là, vous m’objecterez : « mais puisque, selon vous, le vainqueur de Condorcet peut toujours s’arranger pour gagner, comment se fait-il que Bayrou ait été éliminé au premier tour de l’élection présidentielle ? ». Eh oui, c’est là toute la différence entre la théorie et la pratique... On peut avancer trois explications pour ce phénomène, qui ont sans doute joué toutes les trois :

  • Première explication : les électeurs ont un haut sens moral et se refusent à voter de façon “stratégique”.
  • Seconde explication : le mécanisme de vote stratégique que nous avons présenté exige que les électeurs préférant Bayrou à Hollande (par exemple) se concertent pour changer leur vote tous ensemble, faute de quoi l’effet risque de ne pas être celui prévu ! Ce qui est irréalisable quand il s’agit d’une concertation entre des millions d’électeurs.
  • Troisième explication : le mécanisme de vote stratégique exige aussi, pour prendre en compte de façon pertinente les intentions de vote du reste de la population, que les électeurs disposent d’une information parfaitement fiable sur celles-ci. Or en pratique, nous savons bien que les chiffres des instituts de sondages souffrent d’une certaine erreur... En outre, les électeurs espèrent souvent que la dynamique de campagne changera les intentions de vote en faveur de leur candidat chéri, et peuvent donc préférer prendre le risque que gagne un candidat qu’ils détestent pour garder une chance que leur candidat favori l’emporte.

[9L’expression est due à Tocqueville.

[10Du moins à partir du moment où on suppose que les électeurs cherchent d’abord à servir leur intérêt personnel.

[11Le philosophe écrit ainsi dans l’article I de son opuscule Vers la paix perpétuelle : « La Démocratie est nécessairement un despotisme, puisqu’elle établit un pouvoir où tous peuvent décider contre un seul dont l’avis est différent ; la volonté de tous n’y est donc pas exactement celle de tous, ce qui est contradictoire et opposé à la liberté ».

[12Les chiffres que nous avons donnés sont incertains sur le résultat du face-à-face entre Hollande et Bayrou, mais même si Hollande battait en fait Bayrou, il existerait toujours un vainqueur de Condorcet qui serait alors Hollande lui-même.

[13On peut imaginer par exemple que les quatre groupes d’électeurs correspondent à des villes parmi lesquelles il faut choisir une capitale (comme dans le dilemme des Alliérins de l’article précédent), chaque électeur voulant que la capitale soit la plus proche possible de sa propre ville.

[14Noter qu’ici, on montre donc non seulement qu’il existe un vainqueur de Condorcet, mais même qu’il existe un classement global compatible avec les préférences binaires. En fait, un tel classement global existe aussi sous l’hypothèse de préférences en Λ, mais son interprétation n’est pas aussi simple.

[15À noter que, contrairement à ce qu’on pourrait penser, le fait que toutes les préférences soient en Λ n’entraîne pas que la configuration des préférences est décroisée. Par exemple, si quatre candidats s’appellent de gauche à droite W, X, Y, Z et que deux électeurs ont pour préférences respectives « X>Y>Z>W » et « Y>X>W>Z », la configuration des préférences ne peut pas être décroisée, car la comparaison de X et Y indiquerait que le premier électeur serait plus à gauche que le second tandis que la comparaison de W et Z indiquerait que c’est le second qui serait le plus à gauche.

[16Confer par exemple le passage de cette page Wikipédia commençant par « Opinions differ... ».

[17Cf. M. Balinski, Le Suffrage universel inachevé (Belin 2004), pp. 310-311.

[18Pour être tout-à-fait exact, Condorcet esquissait tout de même le problème dans son essai : il y préconisait apparemment une méthode qu’on appelle aujourd’hui « méthode Condorcet avec rangement des paires par ordre décroissant ».

[19Clin d’œil au célèbre personnage d’Alan Moore.

[20Bien sûr, tout cela est peu réaliste : dans la vraie vie, il faut que les citoyens soient extrêmement mécontents pour oser prendre les armes, et même ainsi les révolutions sont rares ; quant à leur résultat, il dépend de nombreux autres paramètres que le nombre de révolutionnaires ! Mais tout grossier qu’il soit, ce modèle demeure bien adapté au cadre de notre étude.

[21Vous aurez remarqué que la manipulation des anarchistes, si elle n’a pas permis de porter V au pouvoir, a tout de même changé le vainqueur de Y pour X... Mais on ne peut pas parler de « manipulation » en l’occurrence, vu que ce changement est dû à la modification de votes relatifs à X et à Y.

Partager cet article

Pour citer cet article :

Rémi Peyre — «Et le vainqueur du second tour est...» — Images des Mathématiques, CNRS, 2012

Crédits image :

Image à la une - Réalisation personnelle
Diagramme des préférences binaires pour l’élection présidentielle - Réalisation personnelle
L’exemple de l’échiquier - Réalisation personnelle
François Hollande - Affiche de campagne du candidat (détail)
Axe politique avec valeurs intrinsèques - Réalisation personnelle
La manipulation des anarchistes - Réalisation personnelle
La méthode Schulze contre la manipulation des anarchistes - Réalisation personnelle
François Bayrou - © Soazig de la Moissonnière
Nicolas de Condorcet - Domaine public

Commentaire sur l'article

  • Et le vainqueur du second tour est...

    le 11 mai 2012 à 00:55, par Vincent Beck

    Merci pour ces belles réflexions sur les systèmes de vote.

    Dans les commentaires de l’article précédent, il y avait une référence au site « vote au pluriel ». Une autre association « vote de valeur » a aussi effectué des expériences lors de cette élection.

    Une première analyse de leurs résultats est sortie aujourd’hui. On pourra y voir une forme de confirmation que Bayrou était bien un vainqueur de Condorcet pour cette élection.

    http://doc.votedevaleur.org/exp2012/compteRenduPreliminaire/web/co/resultats.html

    Répondre à ce message
  • Et le vainqueur du second tour est...

    le 12 mai 2012 à 11:38, par Jérôme Germoni

    Dans le même sens, Vote au pluriel a publié ses résultats : dans cette simulation, François Bayrou aurait gagné n’importe quel duel de second tour mais n’aurait pas atteint le second tour.

    (Quant au site Vote de valeur, il m’a semblé fort militant.)

    Répondre à ce message
  • Et le vainqueur du second tour est... A propos de transitivité

    le 12 mai 2012 à 12:06, par julesdesp

    Merci pour ce saisissant et fascinant exposé, dans sa globalité, d’une question taraudante : quels que soient les progrès acquis dans la liberté d’un choix, tout système d’élection reste dépendant d’un système de sélection. Le Saint-Esprit avait déclaré forfait pour ce qui est de choisir le successeur de Judas ... qui a été tiré au sort ! Hérodote préconisait de s’en remettre au hennissement des chevaux pour reconnaître l’empereur des Perses ... devant monter le cheval qui hennirait en premier à l’aube. Il a fallu attendre, jusqu’au milieu du XIVe siècle, la promulgation de la Bulle d’Or par Charles IV du Luxembourg pour régler les conditions de l’élection des empereurs germaniques.

    J’ai particulièrement bien-aimé la remarque portant sur l’intérêt qu’il peut y avoir à engranger des résultats mathématiques « négatifs » qui abondent, sans toutefois jouer le même rôle qu’une aporie usuelle - la réponse au 10e problème de Hilbert en est un exemple d’autant plus saisissant que cette question n’avait pas été soulevée oralement par Hilbert durant sa conférence mais ajoutée par écrit, dans le compte rendu de celle-ci ! - c’est Youri Matiiassevitch qui l’a raconté.

    Je suis reconnaissant à André Warusfel - si mon souvenir est exact ! d’avoir lié cette « application de l’analyse » à un jeu très ancien, avec trois figures de la main pour signifier Feuille, Pierre et Ciseaux, de sorte que F > P > C, mais aussi C > F car les Ciseaux coupent la Feuille, laquelle enferme la Pierre qui broie les Ciseaux ... avec une remarquable violation de la transitivité. Notons en passant que Cicéron disait de l’un de ses amis qu’il était tellement honnête qu’on pouvait jouer avec lui à ce jeu même la nuit ! Ceci me paraît amusant à comparer avec l’honnêteté entendue, notamment par Jean-Charles de Borda, elle, comme une sincérité, sans « brigue » et sans manipulation, hors stratégie.

    Peut-être extrapolé-je imprudemment : les dérivées partielles sont inhérentes à l’analyse ; cette grande conquête de Lagrange qui parlait de « caractère » (et non de symbole) pour désigner sa notation delta, ôtant toute ambiguïté à la transitivité qu’Euler n’avait pas distinguée d’une dérivée ordinaire, ce qui le poussait à réclamer (en latin) une méthode affranchie de toute considération géométrique, par laquelle il deviendrait patent, dans une telle recherche d’un maximum ou d’un minimum, qu’au lieu de Pdp, il faut écrire -pdP (avec l’inversion des termes et le renversement du signe). Comme l’a si bien dit je ne sais plus qui : « l’agrégation des préférences individuelles fait émerger un ordre de préférences qui ne vérifie plus la condition de transitivité » … dont je voulais seulement souligner qu’elle faisait problème parce qu’elle était essentielle.

    Répondre à ce message
    • Et le vainqueur du second tour est... À propos de transitivité

      le 12 mai 2012 à 17:08, par Jérôme Germoni

      À propos du jeu « Pierre–Feuille–Ciseaux », il y a un long article de Pierre Parlebas dans le numéro 196 de Mathématiques et sciences humaines. (J’avoue avec un peu de culpabilité le citer sans avoir eu le courage de le lire.)

      Répondre à ce message
    • Et le vainqueur du second tour est... A propos de transitivité

      le 17 mai 2012 à 16:16, par Rémi Peyre

      Bonjour « julesdesp »,

      Merci pour votre commentaire. Je suis ravi que mon article vous ait plu et qu’il ait éveillé en vous autant de réflexions !

      Répondre à ce message
  • Quelques remarques

    le 12 mai 2012 à 22:19, par François Sauvageot

    Bonjour,

    il ne me semble pas clair que de faire des redressements pour adapter le vote par internet (sur l’un ou l’autre site) soit pertinent.

    D’une part ça veut dire que l’élection telle qu’elle est pratiquée en France a plus de valeur. Or il me semble que cette proposition de systèmes alternatifs vise justement à faire réfléchir sur ce point.

    D’autre part, c’est la même erreur que celle qui pose problème avec la méthode des quotas. Peut-on prouver qu’une personne au hasard prise dans la case « a voté pour X lors de l’élection réelle » a autant de chance d’apparaître dans le vote par internet qu’une autre dans la même case. Autrement dit faire une simple règle de trois permet-elle d’obtenir une estimation fiable de ce qui se serait passé si tout le monde avait pu/dü voter par internet ?
    La réponse est certainement « non ». Maintenant, comment quantifier la pertinence de cette estimation ? Je crois bien que c’est impossible !

    Alors ? Je pose la question de savoir ce qu’on peut bien déduire de ces votes « pour de rire ». Que le mode de scrutin influe sur les résultats ? Oui. Mais on le savait déjà.
    A-t-on besoin d’une nouvelle preuve ? Oui, pourquoi pas ? Mais alors il faut la crédibiliser un peu plus et ne pas laisser paraître que les calculs effectués sont complètement justifiés.

    En fait on pourrait partir des résultats complets de systèmes différents, comme le système irlandais et voir ce qu’il donnerait dans un scrutin uninominal à deux tours. Le résultat serait sans doute différent de celui qui a lieu et ceci sur l’ensemble des électeurs.

    Maintenant, autre point, peut-on estimer le nombre de gens qui refusent d’aller voter à cause du système choisi et qui le ferait si on en changeait ? Et réciproquement ?

    Bref, autant je suis convaincu du résultat, autant la démonstration pourrait m’en faire douter à la lecture des sites cités ! Curieux, non ?!

    Sinon, dernier point, à propos de Shifumi, c’est un vieil exemple, qu’utilisait Nash par exemple (mais ça doit remonter encore plus loin, j’imagine). Personnellement, j’aime bien le mettre en scène avec un carré magique 3x3. On fait jouer chaque ligne contre une autre ligne, en comparant « colonne par colonne » la valeur des cases. Chaque ligne en bat une autre et est battue par la troisième.

    C’est joli, et c’est une situation assez courante dans les jeux individuels pratiqués par équipe, comme les échecs par exemple en tournoi intercercles. Situation exploitée quand on a la chance d’avoir des joueurs non-classés qui sont en fait d’un excellent niveau : on peut avoir intérêt à ne pas les faire jouer sur les échiquiers les plus forts.

    En fait je pense que Pierre/Feuille/Ciseaux a justement été inventé à cause de sa propriété. Elle remonte probablement aux débuts de l’humanité (la feuille n’est pas nécessairement en papier) et je me risquerais bien à penser que, comme la courte paille qui tire son origine des celtes tirant les bois, ce genre de « jugement divin » était utilisé par les druides des peuplades celtiques. Mais j’avoue ne pas en avoir de preuve ferme.

    François Sauvageot.

    Répondre à ce message
    • Quelques remarques

      le 17 mai 2012 à 16:13, par Rémi Peyre

      Bonjour,

      Concernant les limites à l’interprétation des expériences citées par Vincent Beck et Jérôme Germoni, j’ajouterais qu’il faut garder à l’esprit que les résultats d’une élection dépendent de façon sensible de la campagne que les candidats ont menée (la quatrième place de Mélenchon, ou le resserrement des scores entre Hollande et Sarkozy, en sont des illustrations) ; or cette campagne est pensée en fonction du système de vote retenu : ainsi, la stratégie de Hollande a clairement été conçue dans la perspective d’un second tour contre Sarkozy, et il y a fort à parier que son discours aurait été tourné différemment s’il s’était attendu à affronter, disons, Bayrou ! Ou encore, si notre méthode électorale avait vérifié le critère de Condorcet, Bayrou se serait sûrement retrouvé sous le feu des projecteurs pendant toute la campagne électorale, et cela aurait certainement eu un effet non négligeable sur les intentions de vote — quoique je ne me hasarderais pas à deviner lequel...

      Répondre à ce message
  • Et le vainqueur du second tour est...

    le 26 juillet 2013 à 17:18, par le-nguyen.hoang

    Bonjour,

    Merci beaucoup Monsieur Peyre pour cette superbe série d’articles ! Je travaille dans des problématiques proches (en conception de mécanisme) mais je ne connaissais pas la plupart des systèmes de vote que vous avez présentés !

    J’ai une question par rapport à la méthode Shulze. En voyant le graphe des préférences binaires, et surtout après avoir lu le principe de la méthode, j’ai eu tendance à imaginer un processus de Markov qui décrivait les révolutions successives. On pourrait alors calculer la probabilité stationnaire de la chaîne de Markov. Le vainqueur de l’élection serait alors celui dont la probabilité stationnaire est la plus élevée. Ceci serait-il équivalent à Shulze ?

    Répondre à ce message
  • Et le vainqueur du second tour est...

    le 27 juillet 2013 à 22:48, par Rémi Peyre

    Cher M. Lê-Nguyen,

    Je suis ravi que ces articles vous aient plu ! Concernant votre question, la réponse est essentiellement « oui » : la méthode Schulze peut effectivement s’interpréter en termes de probabilités stationnaires d’un processus markovien. J’ignore néanmoins si Markus Schulze avait cette interprétation en tête lorsqu’il conçut sa fameuse méthode...

    Je présume que votre message demandait aussi, en substance, quel serait le processus markovien en question ! À vrai dire, il ne faut pas considérer un processus à proprement parler, mais plus exactement une asymptotique, càd. qu’on va regarder une famille de processus dépendant d’un paramètre $\lambda$, ayant chacun sa mesure d’équilibre, et que ce n’est qu’à la limite pour $\lambda$ tendant vers l’infini que cette mesure convergera vers une loi de probabilité qui, comme souhaité, donnera le plus grand poids au vainqueur de Schulze — on aura même mieux : la loi limite associera en fait la totalité de son poids au vainqueur de Schulze !

    Mais revenons à la description de (la famille de) processus markoviens. Pour le processus d’indice $\lambda$, je note $q_\lambda(X,Y)$ la probabilité par unité de temps que notre processus a de sauter (autrement dit, de “subir une révolution”) du candidat X vers le candidat Y. Naturellement, on veut que $q_\lambda(X,Y)$ ne dépende en fait de X et Y qu’au travers de la proportion $m(X,Y)$ d’électeurs qui préfèrent Y à X, de sorte que $q_\lambda(X,Y)$ peut se réécrire (avec un léger abus de notation) $q_\lambda(m(X,Y))$. Je fais alors les hypothèses suivante sur les $q_\lambda(m)$ :

    • Les $q_\lambda(m)$ sont à valeurs dans $(0,\infty)$ ;
    • Pour tout $\lambda$, la fonction qui à $m\in[0,1]$ associe $q_\lambda(m)$ est croissante ;
    • Pour tous $m_1 < m_2$, le quotient $q(m_2)/q(m_1)$ tend vers l’infini quand $\lambda$ tend vers l’infini ;
    • En outre, le rapport \[\frac{\log\bigl(q_\lambda(m_2)/q_\lambda(m_1)\bigr)}{\log\bigl(q_\lambda(1)/q_\lambda(m_2)\bigr)}\] tend vers l’infini quand $\lambda$ tend vers l’infini.

    (Les conditions ci-dessous sont vérifiées par exemple pour $q_\lambda(m) = \exp[-(2-m)^\lambda]$). Sous ces conditions, on peut démontrer que, quand $\lambda \to \infty$, la mesure stationnaire de notre famille de processus convergera forcément vers la mesure attribuant une probabilité de 100 % au vainqueur de Schulze.

    Remarque : Une chose intéressante est qu’on peut s’amuser à fixer d’autres hypothèses sur l’asymptotique du processus markovien (en particulier concernant la dernière condition), et que cela peut alors conduire à des mesures d’équilibres qui elles aussi convergent vers une loi concentrée sur un seul point, mais... pas forcément le même ! Autrement dit, selon la façon dont on met en œuvre l’idée des processus markoviens, on peut (à priori) en déduire plusieurs méthodes de vote différentes ! (même si les hypothèses conduisant à la méthode Schulze me paraissent les plus pertinentes pour ma part). Par contre, je ne sais pas quelles seraient ces autres “méthodes markoviennes”...

    Note : En dépit de mon intérêt sur le sujet, je ne suis malheureusement nullement expert dans le domaine des méthodes de vote, et de ce fait une bonne partie de ce que je raconte ne provient pas de documents dument référencés mais aussi d’un peu de travail personnel ; c’est en particulier le cas pour le théorème que j’énonce ci-dessus. (Cela ne signifie pas pour autant que ce théorème n’existe pas dans la littérature ; au contraire, c’est hautement probable : je veux juste dire que je ne l’ai jamais rencontré explicitement au cours de ma documentation). Il convient donc de prendre deux précautions par rapport à ma réponse :

    • En dépit du soin dont j’ai essayé de faire preuve, il reste un risque que l’énoncé tel que je l’ai donné soit en fait faux (mais le cas échéant, soyez rassuré, il existe à coup sûr un énoncé similaire qui, lui, est juste !) ;
    • À contrario, les conditions que j’ai données sont peut-être beaucoup trop fortes par rapport à ce qui est réellement nécessaire.

    Cordialement,
    Rémi Peyre

    Répondre à ce message
  • Et le vainqueur du second tour est...

    le 3 août 2013 à 07:00, par le-nguyen.hoang

    J’ai fini par vous retrouver de Sciencetonnante à Image des maths ! Merci pour les explications. Elles sont excellentes !

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

registros

Cet article fait partie du dossier «Mathématiques de la planète Terre (2013)» voir le dossier

Suivre IDM