Scrutin de Condorcet randomisé

Le scrutin de Condorcet randomisé est un système de vote. Il s'agit d'une méthode de Condorcet, ce qui signifie qu'il élit les vainqueurs de Condorcet, lorsque ceux-ci existent. Dans le cas contraire, ce scrutin résout le paradoxe de Condorcet en choisissant l'élu selon une loi de probabilité parmi un sous-ensemble de candidats de tête.

Ce système est connu en anglais sous le nom de méthode du Bipartisan set à cause d'une analogie avec les plates-formes électorales sur lesquelles pourraient s'accorder des partis politiques cherchant à gagner le vote des électeurs.
Il est quelquefois appelé en Français méthode bipartiludique.

Ce système a plusieurs propriétés intéressantes du point de vue de la théorie du choix social en général  
et en particulier à propos de la question du vote stratégique des électeurs, 
qui en font une méthode particulièrement robuste au vote stratégique et un mode de scrutin « majoritaire » en ce qu'il désigne le vainqueur de Condorcet lorsqu'il y en a un.

Principe

Principe général des méthodes désignant le vainqueur de Condorcet 

Le principe de Condorcet, qui est un choix de critère possible pour déterminer le vainqueur d'une élection, affirme que  Autrement dit, lors d'une élection, si un candidat battait tout autre candidat en référendum, alors ce candidat est celui qui doit être désigné vainqueur du scrutin. On dit d'un tel candidat qu'il est vainqueur de Condorcet. En pratique, la grande majorité des modes de scrutin en vigueur dans les pays du monde violent ce principe. C'est le cas, par exemple, du scrutin uninominal majoritaire à deux tours utilisé pour désigner le président de la République en France sous la  République.

Cependant, rien ne garantit l'existence d'un vainqueur de Condorcet. Par exemple, pour trois candidats ,  et , il est possible que  soit préféré à ,  soit préféré à , et  soit préféré à . Il y a alors un paradoxe de Condorcet : aucun candidat n'est vainqueur de Condorcet. Cette difficulté est d'ailleurs au cœur des théorèmes d'impossibilité d'Arrow et de Gibbard-Satterthwaite. Pour résoudre le paradoxe de Condorcet, le scrutin de Condorcet randomisé propose d'élire le vainqueur selon une loi de probabilité. De façon cruciale, cette loi de probabilité n'a rien d'arbitraire.

Choix aléatoire dans le cas de paradoxe 

Le scrutin de Condorcet randomisé est l'un des moyens de résoudre le paradoxe. Le cas le plus simple du paradoxe est le suivant. Parmi l'ensemble des candidats, il existe un trio ,  et  tel que  est préféré à ,  est préféré à , et  est préféré à , et ce trio est préféré à tous les autres candidats. Dans ce cas, le scrutin de Condorcet randomisé  choisira le vainqueur au hasard parmi ,  et  avec les mêmes probabilités :.

On peut envisager des cas avec 5 candidats ou plus, où il n'y a ni vainqueur de Condorcet, ni trio vainqueur. Pour ces cas, le scrutin de Condorcet randomisé va choisir un « sous-groupe de tête » de candidats et va choisir au hasard dans ce sous-groupe (pas forcément avec les mêmes probabilités). La détermination du sous-groupe de tête ainsi que des probabilités dépend uniquement du graphe orienté des duels, ce qu'on appelle le tournoi majoritaire, et non des pourcentages de préférences (peu importe si  bat  avec un taux de préférence de  ou de , le seul paramètre pris en compte est que  est préféré à ).

Les loteries de Condorcet 
Pour concevoir la méthode, l'idée est d'ajouter à la liste des candidats des « loteries », qui sont définies comme étant des lois de probabilité pour choisir un candidat. Par exemple   avec une probabilité de ,  avec une probabilité de ,  avec une probabilité de  et  avec une probabilité de . Une telle loterie sera notée plus succinctement .

L'astuce du scrutin de Condorcet randomisé est d'ensuite généraliser les préférences de la majorité entre des alternatives à des préférences entre des loteries. Ainsi, on dira que la majorité préfère une loterie  à une loterie , si, lorsqu'un candidat  est tiré selon  et qu'un candidat  est tiré selon , la majorité préfère plus souvent  à  qu'elle ne préfère  à . Par exemple, si la majorité préfère  à , et  à  (noté ), alors on considère qu'elle préférera la loterie  à la loterie  qui tire tout le temps . En effet, dans  des cas,  tirera un meilleur choix (), alors que dans seulement  des cas, il s'agira un moins bon choix ().

Le théorème fondamental du scrutin de Condorcet randomisé, dû à Gilbert Laffond, Jean-François Laslier et Michel LeBreton; affirme alors qu'en dehors de cas pathologiques, il existe une unique loterie que la majorité préfère à toute autre loterie. Autrement dit, il existe une unique loterie qui, parmi les loteries, est vainqueur de Condorcet. On l'appelle loterie de Condorcet. Son unicité n'est violée que s'il existe deux candidats  et  à égalité en référendum, c'est-à-dire tels qu'exactement  du peuple préfèrent A à B, et  préfèrent B à A. En particulier, si le nombre d'électeurs est impair et si chaque électeur a une préférence totale, alors la loterie de Condorcet est unique.

Dans l'analyse de robustesse au vote stratégique que l'on fera plus loin, on considérera que les préférences des électeurs pour des loteries se déduisent de leurs préférences pour des alternatives, de la même manière que l'on a déduit les préférences de la majorité pour les loteries de ses préférences pour les alternatives. Il s'agit là d'une hypothèse réductrice : cette préférence sera en général différente de la préférence réelle de l'électeur. En effet, un électeur dont la préférence est  pourrait détester  plus que tout, et pourrait donc préférer abandonner les  de chance de  afin d'être certain que  ne soit pas élu. Toutefois, dans le cas plus général où une plus grande variété de préférences imaginables des électeurs est admise, le théorème d'Hylland prouve que le seul scrutin unanime et robuste à la manipulation est la dictature aléatoire.

Analogie avec le chifoumi (pierre-feuille-ciseaux) 
Pour trouver la loterie vainqueur, une analogie peut être faite avec le jeu Pierre-feuille-ciseaux et ses variantes avec plus d'objets (par exemple en ajoutant le puits). Ce jeu est bien connu mathématiquement et l'on sait déterminer l'unique stratégie minimax quelle que soit la variante du jeu (qui est aussi un équilibre de Nash). La stratégie minimax est définie comme la meilleure stratégie contre un adversaire qui s'y adapterait.

Par exemple, dans le jeu pierre-feuille-ciseau, la stratégie minimax consiste à jouer chacun des objets avec la même probabilité . En jouant cette stratégie, on est sûr de gagner aussi souvent qu'on perd, même si l'adversaire connaît notre stratégie. Par opposition, si on jouait plus souvent ciseaux que papier, l'adversaire pourrait s'adapter et jouer tout le temps pierre, et l'on perdrait alors plus souvent que l'on ne gagnerait.

Autre exemple : le jeu pierre-feuille-ciseaux-puits. Dans cet exemple, il n'y a jamais d’intérêt à jouer pierre par rapport à puits, car puits est gagnant dans tous les cas où pierre serait gagnant. On peut alors montrer que jouer puits, feuille et ciseaux avec la même probabilité est la stratégie minimax.

Dernier exemple : si l'on considère le jeu « pierre-ciseaux-puits », alors la stratégie optimale cette fois-ci serait de jouer tout le temps puits. En effet, puits bat tout autre objet.

Le scrutin de Condorcet randomisé consiste donc à construire un jeu de type pierre-feuille-ciseaux en utilisant le graphe des duels des candidats ; on détermine ensuite la stratégie minimax de ce jeu et l'on applique cette stratégie pour choisir le candidat.

Cette manière de concevoir la méthode est à l'origine du nom original de la méthode, à savoir la méthode du Bipartisan. En effet le jeu présenté plus haut est étudié en science politique formelle 
en tant que modèle de la compétition électorale entre deux partis qui cherchent uniquement la victoire. En l'absence d'une plate-forme politique vainqueur de Condorcet, le jeu de compétition électorale en stratégie mixte n'a pas d'équilibre pur, cependant les stratégies mixtes peuvent s'interpréter 
comme des plates-formes électorales partiellement floues, et l'ensemble Bipartisan décrit l'équilibre du jeu stratégique sur lequel convergent les deux partis. En français on a introduit le terme de méthode bipartiludique.

Algorithme de calcul de la loterie de Condorcet 

La loterie de Condorcet peut se calculer via la programmation linéaire. Son temps de calcul est polynomial en le nombre de candidats.

Détaillons le calcul. Définissons  si le candidat  bat ,  si le candidat  perd contre , et  s'il y a égalité entre  et  (par exemple si ). Déterminer la loterie de Condorcet correspond à assigner des probabilités  aux candidats , de sorte que pour toutes autres probabilités , on ait . Voilà qui revient à exiger .

Pour que  soit un vecteur de probabilité, il nous fait rajouter les contraintes linéaires  et , où  est le vecteur dont toutes les coordonnées sont égales à 1. L'ensemble des loteries de Condorcet est alors le polytope , où  est le nombre de candidats. L'algorithme du simplexe ou la méthode de l'ellipsoïde, entre autres, permettent alors de calculer un point de ce polytope.

Aspects évolutionnistes 
La méthode Condorcet aléatoire possédant de bonnes propriétés, il est légitime de se demander si elle constitue un bon modèle de la manière dont les systèmes naturels, fussent-ils biologiques ou socio-politiques, sélectionnent entre plusieurs alternatives. On a démontré que la méthode de Condorcet randomisée peut être imitée par des systèmes évolutionnistes, c'est-à-dire que certains modèles de sélection évolutionniste par renforcement convergent vers cette solution. Ce résultat peut effectivement être interprété en termes de biologie évolutionniste et fournit un des rares modèles permettant d'expliquer la persistance de la remarquable bio-diversité que la nature peut maintenir même très localement.

Propriétés remarquables

Indépendance aux alternatives non-pertinentes 
Une propriété remarquable du scrutin de Condorcet randomisé est son indépendance aux alternatives non-pertinentes. Plus précisément, si un candidat  n'est pas dans le support de la loterie de Condorcet, alors retirer  du scrutin ne modifie pas la loterie de Condorcet. De façon plus informelle, la présence d'un candidat mineur n'affecte pas l'issue du scrutin de Condorcet randomisé.

De façon contre-intuitive, la plupart des scrutins usuels violent l'indépendance aux alternatives non-pertinentes. Le cas du scrutin uninominal majoritaire à un tour est le plus frappant. Si  et  sont politiquement proches l'un de l'autre, et si l'opposition est un candidat  très distant, alors la co-existence de  et  dans l'élection a pour effet de diluer les votes, ce qui favorisera alors l'élection de . En particulier, si  est un candidat mineur, sa simple présence peut grandement affecter l'issue de l'élection, qui aurait pu avoir élu  en son absence.

Conséquences sociétales de la dépendance aux alternatives non-pertinentes 
En pratique, les conséquences de la dépendance aux alternatives non-pertinentes dans les scrutins usuels sont grandes. Par exemple, le premier tour de l'élection présidentielle de 2002 a été grandement affecté par la présence d'un grand nombre de candidats de gauche. En l'absence de ces candidats, il est très probable que le candidat socialiste Lionel Jospin serait passé au second tour, voire que Jacques Chirac ne soit pas redevenu Président de la République. Plus récemment, il n'est pas déraisonnable de penser que l'absence du candidat socialiste Benoît Hamon au premier tour de l'élection présidentielle de 2017 aurait permis au candidat Jean-Luc Mélenchon de la France Insoumise de passer au second tour de l'élection, ou vice-versa. Encore plus récemment, l'écart du nombre de voies entre Jean-Luc Mélenchon et Marine Le Pen au premier tour de l'élection présidentielle de 2022 étant faible, l'absence d'un seul des autres candidats de gauche aurait pu modifier l'issue du vote.

Robustesse à la manipulation stratégique 
Suivant la méthode de scrutin, il peut exister des cas où, en connaissant les votes des autres, un électeur ou un groupe d’électeur a intérêt à ne pas exprimer sa véritable opinion, afin d'obtenir une alternative qui lui conviendrait mieux. Il peut même arriver qu'il soit préférable d’exprimer un bulletin en complète opposition avec ces opinions. Prenons l'exemple du système du scrutin uninominal majoritaire à deux tours. Supposons qu'un électeur préfère  à  à  et que les sondages indiquent que, au deuxième tour,  battrait  et  battrait . Si les sondages annoncent aussi que  est certain de passer le premier tour, notre électeur aura alors tout intérêt à voter , son pire choix, pour éliminer . L'électeur y gagnerait en votant contrairement à ses préférences réelles. On dit qu'il aura effectué un vote stratégique (aussi appelé vote utile). Ces votes utiles peuvent remettre en cause la légitimité de l'élection.

Les méthodes de Condorcet sont connues pour être remarquablement robustes au vote stratégique. En effet, il suffit qu'une majorité d'électeurs préfèrent un candidat  à tout autre pour qu'aucun vote stratégique ne puisse être utile. En effet, dès lors,  est clairement vainqueur de Condorcet, et sera donc élu par les méthodes de Condorcet. Du coup, tous les électeurs dont  est le candidat préféré ont tout intérêt à affirmer cela, puisque cela garantit l'élection de leur candidat préféré. Par ailleurs, les autres électeurs ne pourront pas affecter l'issue de l'élection, et n'y gagneront donc pas en votant autre chose que leurs vraies préférences. Cependant, les méthodes de Condorcet ne sont en général pas entièrement robustes au vote stratégique, y compris lorsqu'un vainqueur de Condorcet déterministe des préférences existe.

Une propriété remarquable du scrutin de Condorcet randomisé est d'être robuste au vote stratégique dès que les préférences des électeurs admettent un vainqueur de Condorcet, si l'on considère que les préférences des électeurs pour les loteries correspondent à celles exprimées dans la section précédente . Mieux encore, on peut montrer que cette propriété est rare, dans le sens où, pour de nombreuses préférences des électeurs, tout autre scrutin avec cette propriété devra coïncider avec le scrutin de Condorcet randomisé .

Cas de manipulation stratégique 
Cependant, cette propriété n'est pas valable pour des préférences plus générales des électeurs, comme le montre l'exemple ci-dessous.

Si les électeurs votent suivant leurs préférences réelles,  est vainqueur de Condorcet et sera donc élu. Cependant, si l'électeur 3 adore , et est presque indifférent entre  et , alors il pourrait changer son vote en , provoquer une loterie uniforme et y gagner à voter ainsi. Dès lors, si l'électeur 1 ne veut absolument pas  et est assez indifférent entre  et , alors il peut changer son vote en  et ainsi élire . Si l'électeur 3 avait anticipé cette réaction, il aurait parfaitement manipulé puisque finalement  est élu à la place de .

Dans la pratique, il semble peu probable que ce type de stratégie soit utilisé à grande échelle, car assez complexe à mettre en œuvre pour des gains minimes. Cependant, il n'est pas complètement impossible, notamment si le système de dépouillement fait que, à tout instant, il est possible de connaître les résultats exacts de ceux qui ont déjà voté (ex. vote sous Chaîne de blocs). Il est possible d'imaginer que des communautés se coordonnent pour voter à la dernière minute et provoquer une loterie de Condorcet qui les favoriserait. On dit que le scrutin de Condorcet randomisé n'est pas robuste à la manipulation de groupe. Cependant, cette défaillance n'est nullement spécifique au scrutin de Condorcet randomisé. Toute méthode de Condorcet, même randomisée, est nécessairement vulnérable à la manipulation de groupe .

Avantages et inconvénients

Le non-déterminisme 

Le fait que la méthode puisse dans certains cas choisir le vainqueur de manière aléatoire peut paraître déroutant. Il faut noter toutefois que ces cas sont probablement rares, et que, dans ces cas, le tirage se fera uniquement parmi des candidats qui sont dans le « groupe de tête » : un candidat qui est détesté par la majorité (dans le sens où il n'est pas préféré, par une majorité, à au moins un autre candidat favori) n'a aucune chance d'être élu (contrairement à la méthode de la dictature aléatoire qui tire un bulletin des électeurs au hasard).

Enfin et surtout, en cas de paradoxe de Condorcet, aucun candidat n'est « complètement légitime ». En effet, quel que soit le candidat choisi, il existera au moins un autre candidat qui serait en mesure de demander un référendum pour être choisi à sa place ; et gagnerait.

Un cas extrême 

Si les électeurs votent  à 49 %,  à 2 % et  à 49 %, on est dans le cas d'un paradoxe et donc la loterie vainqueur est . A est premier pour 49 % des électeurs et dernier pour seulement 2 % des électeurs, B est premier pour 2 % des électeurs et dernier pour 49 %. Cependant le rapport de force entre les candidats ne semble pas proportionnel à leurs probabilités. A a notamment la même probabilité que B alors que A bat B avec 98%, B bat C avec 51%, et C bat A avec 51% également. Dès lors, on peut avoir l'intuition que A mérite une meilleure probabilité que B ou C.

La majorité mais pas la meilleure satisfaction 

La méthode étant une méthode majoritaire, elle ne tient pas compte de l'intensité des préférences et est donc soumise à la critique suivante, dite quelquefois la tyrannie de la majorité : si 51 % des élécteurs  préfèrent un peu A à B et 49 % perdent énormément en choisissant A plutot que B, la logique utilitariste indique que B est socialement meilleur que A car la "satisfaction totale" est plus grande avec B qu'avec A.

Possibilité de vote incomplet 

Dans le cas où le nombre de candidats est très important, (si l'on veut par exemple élire le meilleur film), il est parfaitement possible que des électeurs n'expriment pas leurs préférences sur ce qu'ils ne connaissent pas. Il est même possible que les électeurs ne s'expriment que sur une toute petite partie de l'ensemble des candidats. Il faut cependant que tous les candidats soient évalués par un assez grand nombre d'électeurs, pour que le graphe des duels alors construits soit au moins connecté.

Ceci n'est pas forcément vrai pour les systèmes d'élection fonctionnant par note, où l'hypothèse que les notes attribuées à un candidat ne dépendent pas des autres candidats notés est souvent difficile à vérifier.

Plus de nuances dans les décisions collectives 

Les scrutins peuvent être utilisés aussi bien pour élire un candidat que pour prendre des décisions collectives.

Par exemple, une association se demande si elle doit investir pour acheter un véhicule et si oui l'association doit choisir entre une voiture et une camionnette. 35 % des membres pensent qu'il ne faut pas acheter de véhicule pour faire des économies, 40 % sont plutôt dans le compromis et préfèrent acheter une voiture, et à défaut, préfèrent ne rien acheter, 25 % pensent qu'il faut acheter une camionnette mais qu'une voiture ne servirait à rien et qu'il vaut mieux ne rien acheter plutôt que d'acheter une voiture. Le tableau ci-dessous résume ces préférences :

Voici deux manières de voter cette décision : 
 les trois solutions sont présentées en même temps, et la solution avec le plus de voix est choisie (il s'agirait Scrutin uninominal majoritaire à un tour)
 un premier référendum est mis en place pour savoir si un véhicule est acheté et, si oui, un deuxième référendum est utilisé pour savoir quel type de véhicule choisir.

Dans ces deux situations, la voiture est choisie. Cependant, 60 % des membres auraient préféré ne rien acheter plutôt que d'acheter une voiture. Avec ces scrutins, ceux qui préfèrent la camionnette doivent se poser la question de ce qu'ils vont voter : soit ils supposent qu'ils sont suffisamment nombreux pour élire la camionnette et dans ce cas, ils peuvent voter suivant leur vrai préférence, soit ils supposent qu'ils n'ont aucune chance et dans ce cas, ils doivent voter « pas de véhicule ».

Utiliser un scrutin de Condorcet (notamment le randomisé) permettrait dans ce cas, de choisir l'alternative qui convient le mieux à tous. De manière générale, il n'y a plus d'intérêt à limiter les alternatives proposées et il n'est pas non plus nécessaire de choisir arbitrairement un « arbre de référendum ».

Variantes 

 La méthode de l'ensemble essentiel, a été introduite par Bhaskar Dutta et Jean-François Laslier. Elle est aussi dite méthode des  . Il s'agit d'une autre méthode Condorcet aléatoire, très similaire à la méthode du Bipartisan présentée dans cet article sous le nom de "Condorcet randomisé". Elle choisit bien le vainqueur de Condorcet lorsqu'il existe, la différence est que l'ensemble essentiel tient compte de la taille des majorités pour définir la force avec laquelle une alternative est "battue à la majorité par une autre".
Elle a également des propriétés intéressantes. Contrairement au scrutin de Condorcet randomisé, quand il y a un paradoxe de Condorcet à 3 candidats, les loteries maximales peuvent élire une loterie autre que . Cependant, il n'est pas clair que la loterie maximale soit plus « légitime » que la loterie de Condorcet. Par exemple, supposons : 2 électeurs votent  ; 2 électeurs votent  ; 1 électeur vote . La loterie maximale donne , , . On pourrait se demander en quoi  est plus légitime que les 2 autres.

 Il existe plusieurs variantes de scrutin de Condorcet qui ne sont pas aléatoires, comme la méthode Schulze et la méthode Condorcet avec rangement des paires par ordre décroissant. Ces méthodes ont l'avantage d'être entièrement déterministes (à certains rares cas d'égalité près) mais sont plus sensibles au vote stratégique, car il existe toujours des cas où un manipulateur pourra modifier son bulletin pour provoquer un paradoxe et avoir un meilleur choix sans être « sanctionné » par la possibilité d'élire un moins bon candidat à la place. De manière générale, la difficulté est que plus le choix du candidat à l'intérieur du paradoxe est attractif pour une majeure partie de la population, plus nombreux seront les électeurs qui auront intérêt à modifier leur votes pour provoquer ces paradoxes. Par ailleurs, des manipulations sont également possibles à l'intérieur des cas de paradoxes.

Liens externes 
 Vidéo de vulgarisation sur le fonctionnement du scrutin de Condorcet randomisé par la chaîne YouTube Science4All
 Deuxième vidéo, très détaillée, de la chaîne YouTube Science4All
 La quete du Graal electoral par Rémi Peyre sur Images des mathématiques(CNRS)
 votation.ovh une application en ligne qui permet d'organiser un vote suivant le scrutin de Condorcet randomisé à la manière d'un Doodle

Références 

Condorcet randomisé
Théorie du choix social
Nicolas de Condorcet