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 - p22. 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 loteriesG. Kreweras. "Aggregation of preference orderings". In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962), pages 73–79, 1965.. 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