18 janvier 2013

1 commentaire — commenter cet article

Les mathématiques de la démocratie, III

La quête du Graal électoral

À la recherche de la méthode électorale optimale

Rémi Peyre

Maitre de conférences à l'École des Mines de Nancy (page web)

Au cours de deux articles précédents (ici et ), j’ai présenté les questions mathématiques que soulève la problématique de la démocratie, en particulier de savoir s’il est possible de trouver une méthode électorale qui donne une image fidèle de la préférence collective à partir des préférences individuelles, et ce même quand les électeurs sont prêts à élaborer des stratégies de vote mensongères pour faire triompher chacun son chouchou personnel. Nous avons démontré dans le premier article qu’il ne peut exister aucune méthode qui soit idéale à tous points de vue, puis dans le deuxième article nous avons essayé de proposer malgré tout un critère pour distinguer des méthodes meilleures que d’autres.

Toutefois, nous n’avons toujours pas vraiment répondu à la question fondamentale : quelle est la méthode électorale qui, à défaut d’être parfaite, est la meilleure de toutes — du moins selon tel ou tel critère — ? C’est à cette question que ce texte se propose de répondre, en clôture de notre série d’articles.

Nous allons présenter trois méthodes électorales particulières inventées par les mathématiciens au cours des dernières décennies, chacune d’elles ayant été conçue pour être optimale selon une certaine approche. Après un paragraphe d’introduction ré-expliquant la problématique générale de cette série sur les mathématiques de la démocratie, trois parties indépendantes seront consacrées respectivement aux différentes méthodes qui sont l’objet de cet article : le vote par assentiment, le jugement majoritaire, et le très surprenant scrutin bipartiludique.

Introduction

Problématique : « La volonté du peuple », quésaco ?

(Ce paragraphe revient succinctement sur certaines questions traitées dans le premier article de la série, auquel le lecteur curieux pourra se référer pour plus de détails).

Des « moi » au « nous »

Allégorie de la volonté du peuple.

Nous présentons ici la problématique dans laquelle s’inscrit cet article. Le principe fondamental de la démocratie est que l’État doit suivre la volonté du peuple. Mais les différents individus qui composent ce peuple, évidemment, ne sont en général pas d’accord entre eux... Pour connaitre la volonté populaire, on doit donc consulter les citoyens par le biais d’un scrutin électoral, dans lequel chacun indique ses préférences entre les différentes options parmi lesquelles il s’agit de choisir (par exemple la validation ou non d’une loi, le choix d’un président, la peine infligée à un accusé, ...). Mais même ainsi, ce que signifie au juste l’expression « volonté du peuple » n’est pas clair : quelle est la bonne façon d’agréger les préférences individuelles de chaque électeur pour en faire émerger une préférence collective ? On entend fréquemment que « c’est la majorité qui doit l’emporter », mais cette règle de la majorité présente trois écueils :

  • Déjà, il n’est pas si clair que cette règle soit vraiment équitable : quand 51 % des citoyens sont “plutôt pour” une loi et que 49 % sont “carrément contre”, la volonté du peuple est-elle vraiment en faveur de la loi ? (voir aussi ici).
  • D’autre part, ce principe ne peut bien fonctionner que dans le cas d’un référendum, car dès qu’il y a au moins trois options en lice, il est évidemment possible qu’aucune des trois ne recueille la préférence de 50 % des électeurs...
  • Pire encore, ce principe aboutit parfois à des décisions contradictoires : il se peut ainsi qu’une option X soit majoritairement préférée à une autre option Y, elle-même majoritairement préférée à une troisième option Z, et que pourtant Z soit majoritairement préférée à X ! (C’est ce qu’on appelle le « paradoxe de Condorcet » ; voir aussi ici).

À vrai dire, de solides arguments philosophiques et mathématiques suggèrent que la meilleure définition de la volonté du peuple serait sans doute de choisir l’option qui maximise le “bonheur total” apporté à la population. Cela correspondrait à une méthode électorale où chaque électeur attribue aux différentes options des “notes” évaluant la “quantité de bonheur” respective que ces options apporteraient pour lui, et où est déclarée vainqueuse l’option qui obtient le meilleur total (voir aussi ici). Nous appellerons cette méthode électorale scrutin utilitariste [1].

Le gros écueil du scrutin utilitariste est cependant qu’il y est facile aux électeurs de “tricher” en déclarant des notes qui ne correspondent pas à leur opinion véritable afin d’amplifier l’impact de leur suffrage personnel. Imaginons ainsi une situation très simple où deux électeurs A et B doivent chacun donner une note entre 0 et 20 à deux options X et Y. L’électrice A, qui aime bien X mais pas du tout Y, donne une note de 15 à X et de 2 à Y. L’électeur B, pour sa part, préfère Y à X mais tolèrerait quand même cette dernière option : s’il mettait ses notes sincèrement, il donnerait ainsi 11 à X et 17 à Y. « Toutefois, se dit B (qui connait les préférences de A), du coup c’est X qui sera élu par 26 à 19... J’ai plutôt intérêt à tricher en exagérant mes préférences : si je donne 0 à X et 20 à Y, le score total deviendra de 15 à 22, et c’est mon choix Y qui gagnera ! ». C’est ce qu’on appelle le problème de la manipulabilité (voir aussi ici), et c’est un sérieux problème, car il n’y a guère de doute que bon nombre d’électeurs n’hésiteront pas à dévoyer le système en leur faveur s’ils le peuvent !

Une faille dans le système...

Allégorie de la manipulation d’une méthode électorale.

But de cet article

Une bonne méthode électorale doit donc non seulement donner une image fidèle de la préférence collective, mais aussi être faite de sorte qu’elle soit difficile à manipuler. Il a été montré dans le premier article qu’il est mathématiquement impossible de trouver une méthode qui soit parfaite de ces deux points de vue à la fois (voir ici). Toutefois, existe-t-il un compromis optimal, une méthode qui serait la seule à présenter une certaine liste de propriétés souhaitables ?

De nombreux exemples de méthodes électorales ont déjà été présentés dans les deux articles précédents ; et certaines d’entre elles semblent particulièrement judicieuses, comme la méthode Schulze (voir ici). Notre but ici ne sera pas de critiquer ces méthodes, mais simplement d’en présenter de nouvelles, auxquelles on n’aurait pas forcément songé à première vue mais qui pourtant jouissent de solides atouts mathématiques. Nous diviserons cet article en trois parties indépendantes, chacune étant consacrée à une telle méthode : respectivement le vote par assentiment, le jugement majoritaire et le « scrutin bipartiludique ». Notez que ces méthodes sont toutes les trois d’invention (ou du moins de mise en exergue) récente, puisqu’ aucune n’a plus de quarante ans !

Le vote par assentiment

Préambule : Manipulation du scrutin utilitariste

Nous avons dit dans l’introduction que, si tous les électeurs étaient parfaitement honnêtes, la méthode électorale idéale serait le scrutin utilitariste, dans lequel chaque électeur donne une note aux différentes options (par exemple entre 0 et 20) et où l’option vainqueuse est alors celle qui obtient le meilleur total. Mais nous avons aussi dit qu’il serait facile à un électeur malhonnête de manipuler un tel scrutin en amplifiant ses préférences véritables... L’idée que nous allons suivre dans cette partie est de regarder, justement, ce qui se passerait avec le scrutin utilitariste si tout le monde votait stratégiquement !

J’affirme que pour maximiser l’impact de son vote dans un tel scrutin, un électeur manipulateur a intérêt à écarter ses notes à l’extrême en ne donnant que des notes de 0 et de 20 aux différentes options. C’est évident quand il n’y a que deux options en lice ; et s’il y a plus de deux options, on peut en fait toujours se ramener plus ou moins au cas binaire : car si le nombre d’électeurs est très grand, la voix d’un électeur individuel ne peut en général rien changer au résultat de l’élection ; à la rigueur, si les deux options arrivées en tête se tiennent dans un mouchoir de poche, la voix d’un électeur peut faire basculer le résultat de l’une à l’autre — auquel cas on est ramené au cas de deux options — ; mais pour avoir réellement trois options ou plus à prendre en compte, il faudrait carrément que ce soient les trois options arrivées en tête qui se tiennent dans un mouchoir de poche, ce qui devient tellement improbable qu’on peut considérer que cela n’arrive jamais ! L’argument donné ci-dessus n’est pas tout à fait rigoureux, mais on peut tout de même démontrer le théorème suivant :

Théorème

Si tous les électeurs ont déjà voté et qu’il ne reste plus qu’au dernier électeur à mettre ses notes, alors le meilleur résultat (à ses yeux) que cet électeur puisse espérer peut toujours être obtenu en ne donnant que des notes de 0 et de 20.

Démonstration

Je ne démontrerai pas ce théorème ici, car sa preuve est la même que celle du théorème de robustesse au mensonge du vote par assentiment que nous verrons un peu plus loin : il faudrait montrer que lorsque les notes sont libres entre 0 et 20, la stratégie optimale du dernier électeur consiste à donner la note de 20 à l’option qu’il préfère parmi celles qui ont encore une possibilité de gagner, à donner également 20 à toutes les options qu’il aime encore mieux, et à donner 0 à toutes les autres options.

Le système de vote par assentiment

L’idée derrière la méthode du vote par assentiment est maintenant simplissime : pour éviter le développement de stratégies mensongères chez les électeurs, n’autorisons à tout le monde que les notes de 0 et de 20, ce qui coupera l’herbe sous le pied des manipulateurs ! Comme il n’y a alors plus que deux notes, il est plus logique de les renommer en « contre » et « pour », ce qui donne la méthode électorale suivante :

Définition (Vote par assentiment)

Dans la méthode du vote par assentiment, chaque électeur vote « pour » ou « contre » chaque option, indépendamment pour chaque option (c’est-à-dire que l’électeur peut aussi bien donner « pour » à une seule option et « contre » à toutes les autres, que « contre » à une seule option et « pour » à toutes les autres, moitié « pour » et moitié « contre », etc. [2]). Est déclarée vainqueuse l’option qui a reçu le plus grand nombre de « pour ».

La méthode du vote par assentiment est apparue indépendamment dans les travaux de divers chercheurs aux environs de l’année 1977 [3].

PNG - 42 ko
Bulletin de vote par assentiment
Un bulletin de vote pour un scrutin par assentiment avec 5 options en lice, rempli (en bleu) par un électeur.
PNG - 73.2 ko
Dépouillement d’un scrutin par assentiment
Tableau de dépouillement du scrutin par assentiment dont nous avons présenté un bulletin ci-contre (les bâtons bleus sont ceux qui proviennent du bulletin en question).

Avec le système de vote par assentiment, la notion de « vote stratégique » est ambigüe, car c’est à l’électeur d’apprécier si une opinion mitigée doit être traduite en pour ou en contre, ce qui fait qu’il y a plusieurs possibilités de vote sincère ! Par exemple, une électrice classant trois options X, Y et Z dans cet ordre peut aussi bien choisir de voter « pour X, contre Y, contre Z » que « pour X, pour Y, contre Z » sans qu’aucun de ces suffrages ne puisse être qualifié de mensonger. Dans ce contexte, il faut donc distinguer « manipulation du scrutin » et « vote stratégique » : même quand on vote sincèrement, il peut y avoir une part de stratégie pour choisir entre les différents votes sincères possibles...

Définition (Suffrage sincère)

Dans le vote par assentiment, on dira que le suffrage d’un électeur est sincère quand cet électeur ne préfère aucune des options qu’il a votées « contre » à aucune des options qu’il a votées « pour », c’est-à-dire quand ses votes « pour » et « contre » correspondent respectivement aux options qu’il classe en deçà et au-delà d’un certain seuil dans sa liste de préférences. Un suffrage non sincère sera dit mensonger.

Cette définition posée, nous allons énoncer une propriété remarquable du vote par assentiment, à savoir qu’il ne permet le développement d’essentiellement aucune stratégie mensongère ! En outre, c’est dans un sens la seule méthode qui présente cet avantage, car nous avons vu dans le premier article qu’il n’est pas possible d’éviter les manipulations dès lors qu’on peut classer les options sur trois niveaux ou plus. L’énoncé précis de cette propriété est le suivant :

Théorème (Robustesse au mensonge du vote par assentiment)

Dans le cadre d’un vote par assentiment, aucun électeur n’a jamais intérêt à voter un suffrage mensonger, dans le sens suivant : quels que soient les suffrages des autres électeurs, la meilleure stratégie possible pour notre électeur consiste en un certain suffrage sincère.

Démonstration

Nous allons commencer par éliminer une difficulté purement technique, à savoir la possibilité d’ex-æquo (auquel cas la détermination de la vainqueuse serait équivoque) : pour éviter cela, nous allons faire comme si le nombre d’assentiments reçus par chaque option était un nombre à virgule, et supposer que tous ces scores ont des valeurs après la virgule différentes (par exemple, s’il y a 4 options en lice, on peut imaginer qu’elles ont reçu respectivement 13,5, 11,6, 14,2 et 13,9 « pour » de la part des autres électeurs).

Pour simplifier la présentation, nous ferons comme si notre électeur votait en dernier. Appelons $X_1$, $X_2$, ... et $X_m$ les options en lice, et supposons qu’avant le vote de notre électeur elles ont reçu respectivement $S_1$, $S_2$, ... et $S_m$ « pour ». Notons $S_\spadesuit$ la plus grande valeur des $S_i$ et désignons par $X_\spadesuit$ l’option correspondante. J’affirme alors que le vote de notre électeur peut conduire à la victoire d’une option $X_i$ si et seulement si $S_i>S_\spadesuit-1$. En effet, si $S_i>S_\spadesuit-1$, en votant pour l’option $X_i$ et aucune autre notre électeur amènera la victoire de $X_i$, puisque après son vote $X_i$ aura $S_i+1$ « pour », ce qui est strictement supérieur à $S_\spadesuit$, tandis que toutes les autres options auront au plus $S_\spadesuit$ « pour », leur score n’ayant pas bougé. Réciproquement, si $S_i< S_\spadesuit-1$ [4], quel que soit le vote de notre électeur l’option $X_i$ aura au plus $S_i+1$ « pour » au total, soit moins de $S_\spadesuit$, tandis que l’option $X_\spadesuit$ aura toujours au moins les $S_\spadesuit$ « pour » qu’elle avait au départ : étant dépassée par $X_\spadesuit$, l’option $X_i$ ne pourra donc pas être vainqueuse.

Nous savons ainsi quelles sont les options dont le vote de notre électeur peut amener la victoire. Parmi toutes ces options-là, notons $X_\heartsuit$ celle qu’il préfère. J’affirme alors que le suffrage sincère pour notre électeur consistant à voter pour $X_\heartsuit$ et pour toutes les options qu’il préfère à $X_\heartsuit$, et contre toutes les options qu’il aime moins que $X_\heartsuit$, conduit bien à l’élection de $X_\heartsuit$ — ce qui était la meilleure possibilité à ses yeux. En effet, si $X_i$ est une option que notre électeur aime moins que $X_\heartsuit$, avec ce suffrage il votera pour $X_\heartsuit$ et contre $X_i$, de sorte que le score total de $X_\heartsuit$ sera $S_\heartsuit+1$ et que celui de $X_i$ sera $S_i$ ; mais nous savons que $X_\heartsuit$ est une option qui peut gagner, donc $S_\heartsuit>S_\spadesuit-1$, et par conséquent $S_\heartsuit+1>S_\spadesuit\geqslant S_i$ : ainsi $X_\heartsuit$ obtient un meilleur score que $X_i$, qui n’est donc pas la vainqueuse. La vainqueuse est donc soit $X_\heartsuit$, soit une option que notre électeur préfère à $X_\heartsuit$ ; mais comme de toutes façons les options que notre électeur préfère à $X_\heartsuit$ ne peuvent pas gagner, c’est forcément que la vainqueuse est bien $X_\heartsuit$.

Le jugement majoritaire

JPEG - 16.1 ko
Les inventeurs du jugement majoritaire
Photographies contemporaines de Michel Balinski (à g.) et Rida Laraki (à d.), concepteurs du scrutin au jugement majoritaire.

La méthode électorale que nous allons présenter dans cette partie est elle aussi dérivée du scrutin utilitariste, mais cette fois-ci, au lieu de supposer que tout le monde vote stratégiquement et d’en tirer les conséquences, on va plutôt supposer que quelques personnes votent stratégiquement et chercher comment corriger le scrutin utilitariste afin que le résultat soit le moins possible impacté par ces électeurs manipulateurs.

Imaginons ainsi un scrutin utilitariste auquel 9 électeurs ont participé, et que les électeurs ont mis les notes suivantes à l’option X : 14, 14, 14, 14, 14, 14, 0, 14 et 14. Là, on se dit : « Ouh là ! Il y a consensus à une voix près pour dire que X vaudrait 14 ; c’est sans doute que X vaut réellement 14 et que le vote de la septième électrice est un vote manipulatoire, donc ne méritant pas d’être pris en compte ! », de sorte qu’on a envie de décréter que la moyenne “authentique” de X est 14 [5]. On peut pousser ce principe un peu plus loin, en disant que s’il y a une majorité stricte d’électeurs qui ont mis exactement la même note, celle-ci doit correspondre à la note globale. Par ailleurs, il semble évident de requérir que, si l’un des électeurs modifie la note qu’il a mise à une option X pour la remplacer par une note plus élevée, cela ne pourra faire qu’augmenter la note globale de X (éventuellement cette note globale pourra rester la même si on estime que notre électeur est en train de faire usage de stratégie, mais en aucun cas elle ne devra baisser !).

Il se trouve que, dès lors qu’on a retenu ces deux principes, il n’y a en fait qu’une seule façon possible de déterminer la note globale en fonction des notes individuelles ! Imaginons par exemple que les notes mises par nos 9 électeurs pour une option Y soient, par ordre décroissant, 20, 11, 8, 8, 6, 5, 3, 0 et 0 ; et essayons de voir quelle pourrait être la note globale N correspondante. Si les quatre premiers électeurs diminuaient leur note pour tous la remplacer par « 6 », la distribution des notes deviendrait « 6, 6, 6, 6, 6, 5, 3, 0, 0 », et la note globale serait alors de 6 vu qu’il y aurait une majorité stricte pour cette note. Mais comme, au cours de cette modification de notes, il n’y aurait eu que des diminutions, la note globale ne pourrait qu’avoir diminué, de sorte que N était nécessairement supérieur ou égal à 6. Inversement, si les quatre derniers électeurs montaient leur note à « 6 », la distribution devenant alors « 20, 11, 8, 8, 6, 6, 6, 6, 6 » avec une majorité de « 6 », la nouvelle note globale serait de 6, ce qui implique que N était initialement inférieur ou égal à 6. Au bout du compte, il n’y a qu’une seule possibilité : N est forcément égal à 6. On peut immédiatement généraliser ce raisonnement pour obtenir le

Théorème (Robustesse à la manipulation et note médiane)

Lorsqu’on veut agréger un nombre impair de notes en une seule, la seule méthode qui vérifie les conditions suivantes :

  • Majorité : Si une majorité stricte d’électeurs sont d’accord pour mettre une même note, alors celle-ci correspond à la note globale ;
  • Croissance : Si un ou plusieurs électeurs modifient leur note individuelle à la hausse (resp. à la baisse), cela ne peut faire qu’augmenter (resp. diminuer) la note globale ;

est la « règle de la médiane », consistant à ordonner les notes des différents électeurs par ordre décroissant et à retenir celle du milieu.

Cela nous amène à la méthode électorale qui fait l’objet de cette partie :

Définition (Scrutin au jugement majoritaire)

Le scrutin au jugement majoritaire est la méthode consistant à demander à chaque électeur de noter les différentes options et à retenir pour chaque option la note médiane. Notez que dans cette méthode, les « notes » ne sont pas obligées d’être des nombres : cela peut très bien être des mentions (comme « excellent », « très bien », « bien », etc.), la seule chose qui compte étant que ces mentions soient ordonnées selon une hiérarchie stricte.

Le scrutin au jugement majoritaire a été mis au point en 1996 par deux chercheurs du CNRS : l’américain Michel Balinski et le marocain Rika Laraki.

PNG - 43.5 ko
Bulletin de vote à la préférence majoritaire
Un bulletin de vote pour un scrutin à la préférence majoritaire avec 5 options en lice, rempli (en bleu) par un électeur.
PNG - 171.3 ko
Dépouillement d’un scrutin à la préférence majoritaire
Tableau de dépouillement du scrutin à la préférence majoritaire dont nous avons présenté un bulletin ci-contre (les notes bleues sont celles qui proviennent du bulletin en question).

Avant de clore ce paragraphe, signalons enfin que l’idée d’attribuer à chaque option sa note médiane est aussi liée au critère de Condorcet qui faisait l’objet de notre second article : en effet, si un vote est organisé pour choisir la note attribuée à une option donnée, la note médiane est alors la vainqueuse de Condorcet parmi toutes les notes possibles, en vertu du premier théorème de l’électeur médian.

Le scrutin bipartiludique (piste rouge)

La méthode que nous allons présenter dans cette partie est un peu plus compliquée, mais c’est une curiosité mathématique qu’il m’aurait semblé dommage de ne pas mentionner.

Nous savons que la question de l’expression démocratique est très simple à résoudre dans le cas où il n’y a que deux options en lice (par exemple pour un référendum), puisqu’il n’y a alors qu’à choisir l’option qui remporte le plus de suffrages — c’est là une règle clairement démocratique, et qui ne prête le flanc à aucune stratégie manipulatoire de la part des électeurs (voir aussi ici). C’est d’ailleurs l’idée qui sous-tend le scrutin uninominal majoritaire à deux tours (dans lequel un second tour décisif est organisé entre les deux candidats arrivés en tête à l’issue du premier — méthode utilisée notamment pour les élections présidentielles françaises) : autant on peut ergoter sur la pertinence des résultats du premier tour, autant le second ne prête à aucune contestation de par sa nature binaire !

Dans nombre de démocraties, le système de scrutin est fait de sorte que cette situation binaire peut se retrouver jusque dans la composition des partis politiques, deux partis hégémoniques écrasant tous les autres [6] — l’exemple archétypique d’un tel phénomène étant les États-Unis. Imaginons maintenant un pays dans lequel n’existent que deux partis, que par allusion nous appellerons respectivement « Démocrate » et « Républicain ». Nous faisons l’hypothèse que ces deux partis n’ont aucune ligne politique déterminée a priori : leur seul objectif est la conquête du pouvoir, et ils sont prêts pour cela à suivre aveuglément le vent de l’opinion publique. Justement, une élection présidentielle approche, et les partis doivent publier leurs programmes, programmes en fonction desquels les électeurs voteront pour l’un ou pour l’autre. Nous imaginons qu’il n’y a que trois programmes politiques envisageables (les mêmes pour les deux partis) : un programme appelé « pierre », un programme appelé « feuille » et un programme appelé « ciseaux ». On suppose que les préférences des électeurs au sujet de ces programmes sont les suivantes :

  • Dans le cas d’une confrontation pierre contre feuille, feuille l’emporterait ;
  • Dans le cas d’une confrontation pierre contre ciseaux, pierre l’emporterait ;
  • Dans le cas d’une confrontation feuille contre ciseaux, ciseaux l’emporterait. [7]

La question est alors : que va-t-il se passer ?

Remarquons d’abord que les états-majors des partis se moquent complètement de savoir par quels scores auraient lieu les victoires de feuille sur pierre, de pierre sur ciseaux ou de ciseaux sur feuille. Remarquons aussi que dans la situation que nous avons décrite, si l’un des deux partis (mettons le parti Démocrate) doit présenter son programme avant l’autre, il est certain de perdre : il suffira en effet aux Républicains de proposer feuille si les Démocrates ont proposé pierre, de proposer ciseaux s’ils ont proposé feuille, et de proposer pierre s’ils ont proposé ciseaux. La situation n’est donc intéressante que si les deux partis doivent présenter leurs programmes en même temps. Mais alors, qu’avons-nous là ? Eh oui, vous l’avez compris : c’est exactement comme si les deux partis jouaient à chifoumi ! De façon générale, les programmes politiques envisageables peuvent être en nombre quelconque, et les électeurs peuvent avoir n’importe quelles préférences entre ces programmes ; mais l’idée reste la même, c’est pourquoi nous appellerons également « chifoumi » les variantes suivantes :

Définition

Un jeu de chifoumi est un jeu dans lequel deux joueurs s’affrontent en proposant simultanément chacun un « coup » au sein d’une liste finie (la même liste pour les deux joueurs). Au début du jeu, on a précisé pour chaque paire de coups différents lequel battrait l’autre en cas de duel. Une fois que les deux joueurs ont dévoilé leurs coups, c’est celui qui a proposé le coup qui bat l’autre en duel qui gagne le jeu. Dans le cas où les deux joueurs ont proposé le même coup, le gagnant est tiré au sort.

On appelle chifoumi standard le jeu de chifoumi dans lequel les coups possibles sont « pierre », « feuille » et « ciseaux », et où les résultats des duels sont ceux expliqués quelques paragraphes plus haut.

Jeu de chifoumi standard

La pierre est battue par la feuille (qui l’enveloppe) ; la feuille est battue par les ciseaux (qui la découpent) ; et les ciseaux sont battus par la pierre (qui les émousse).

Il se trouve que la théorie mathématique des jeux de chifoumi a été étudiée de longue date et est aujourd’hui parfaitement comprise ; en particulier, on sait déterminer la stratégie optimale pour ces jeux. Ce qui est fascinant ­— mais ne surprendra guère ceux d’entre vous y ayant déjà joué —, c’est que cette stratégie optimale consiste à jouer d’une certaine façon... aléatoire ! [8] Nous n’avons malheureusement pas la place ici de présenter en détail ce domaine passionnant des mathématiques qu’est la « théorie des jeux » ; nous nous contenterons donc d’énoncer les définitions et les résultats indispensables pour cet article :

Définitions (Stratégie ; Stratégie optimale)
  1. Dans un jeu de chifoumi, ce qu’on appelle une stratégie pour un joueur consiste à attribuer à chacun des coups une certaine probabilité de jouer effectivement celui-ci (le total des probabilités devant bien entendu valoir 100 %) : par exemple, une stratégie pour le jeu de chifoumi standard peut consister à jouer aléatoirement « pierre » dans 30 % des cas, « feuille » dans 20 % des cas et « ciseaux » dans 50 % des cas.
  2. Si chacun des deux joueurs a choisi une stratégie, on peut parler pour chaque joueur de sa probabilité de victoire, qui est évidemment la probabilité que ce joueur gagne. (Un exemple est donné dans le bloc dépliable ci-dessous).
  3. On dit qu’une stratégie est optimale quand, quelle que soit la stratégie adoptée en face par l’adversaire, la probabilité de victoire en utilisant cette stratégie est d’au moins 50 % [9].

Exemple de calcul de probabilité de victoire

On considère ici le jeu de chifoumi standard. On considère la stratégie pour le premier joueur consistant à jouer « pierre » dans 60 % des cas, « feuille » dans 40 % des cas et « ciseaux » dans 0 % des cas ; tandis que le second joueur suit la stratégie dans laquelle il joue « pierre » à 0 %, « feuille » à 70 % et « ciseaux » à 30 %. Quelle est alors la probabilité que le premier joueur gagne ? Il y a deux possibilités qui conduisent à cette éventualité. Soit le premier joueur a choisi « pierre » et le second « ciseaux » : cela se produit dans 30 % de 60 % des cas, soit 18 %. Soit les deux joueurs ont joué « feuille » (ce qui se produit dans 70 % de 40 % des cas, soit 28 %) et ensuite le premier joueur a gagné le tirage au sort : cela arrive avec une probabilité de 28÷2 = 14 %. La probabilité totale de victoire du premier joueur est donc de 32 % (le second joueur ayant quant à lui 68 % de chances de gagner).

Le grand théorème sur les jeux de chifoumi est alors le suivant :

Théorème

Dans un jeu de chifoumi :

  1. Il existe toujours une stratégie optimale ;
  2. En outre, cette stratégie optimale est unique.

Le bloc dépliable suivant présente quelques exemples de stratégies optimales :

Exemples de stratégies optimales

Vainqueurs des duels pour notre jeu à six coups
vs ABCDEF
A AACAEF
B ABBBEB
C CBCCEC
D ABCDDD
E EEEDEF
F FBCDFF
  • Dans le cas du chifoumi standard, la stratégie optimale consiste à jouer chacun des trois coups avec une probabilité d’un tiers, ce qui n’est pas surprenant vu que ces trois coups jouent des rôles similaires.
  • Dans le jeu de chifoumi où les coups sont « fort », « moyen » et « faible », « fort » battant « moyen » et « faible » et « moyen » battant « faible », la stratégie optimale consiste évidemment à jouer « fort » dans 100 % des cas. (c’est donc une stratégie “aléatoire”... qui ne l’est pas vraiment !).
  • Dans le jeu où les six coups sont « A », « B », « C », « D », « E » et « F » et où les résultats des duels sont ceux présentés dans le tableau ci-contre, la stratégie optimale consiste à jouer respectivement « A », « B » et « C » avec une probabilité de 1 neuvième, « D » et « E » avec une probabilité de 3 neuvièmes, et « F » avec une probabilité nulle : on vérifie qu’aucun coup ne gagne plus d’une fois sur deux face à une telle stratégie.

Maintenant que nous avons ce vocabulaire en main, nous pouvons présenter le « scrutin bipartiludique » [10] :

Définition (scrutin bipartiludique)

Le scrutin bipartiludique est la méthode électorale définie de la façon suivante. Sur son bulletin, chaque électeur classe les différentes options selon son ordre de préférence. Après dépouillement, on regarde pour chaque paire d’options différentes laquelle est majoritairement préférée à l’autre par les électeurs. Puis on considère le jeu de chifoumi dans lequel les coups que peuvent jouer les deux joueurs correspondent aux différentes options en lice, le coup vainqueur d’un duel étant l’option qui est majoritairement préférée à l’autre. Ce jeu possède sa stratégie optimale ; notons S cette stratégie. Le principe du scrutin bipartiludique consiste alors à tirer au sort l’option vainqueuse de l’élection selon la loi de probabilité S.

L’origine du scrutin bipartiludique semble remonter à une publication de Laffond, Laslier & Le Breton en 1993. Je me suis appuyé pour écrire le présent texte sur la présentation qu’en fait Myerson dans son article cité parmi les références.

PNG - 47.7 ko
Bulletin de vote bipartiludique
Bulletin de vote pour un scrutin bipartiludique avec 5 options en lice, rempli (en bleu) par un électeur.
PNG - 210.2 ko
Dépouillement d’un scrutin bipartiludique
Tableau de dépouillement du scrutin bipartiludique dont nous avons présenté un bulletin ci-contre (les bâtons bleus sont ceux qui proviennent du bulletin en question). Les duels se concluant par une victoire ont été entourés en blanc.

Ainsi le scrutin bipartiludique donne, de manière générale, une vainqueuse aléatoire ! Cela rappelle le « scrutin stochocratique » évoqué dans le premier article. Toutefois, la vainqueuse d’après le scrutin bipartiludique est beaucoup moins arbitraire qu’avec le scrutin stochocratique ; dans de nombreux cas, elle n’est même pas aléatoire du tout :

Théorème

S’il existe une option X qui est « vainqueuse de Condorcet », c’est-à-dire telle que pour toute autre option Y, X est préférée à Y par une majorité d’électeurs (les électeurs constituant cette majorité pouvant dépendre de Y), alors le scrutin bipartiludique désignera X vainqueuse avec une probabilité de 100 %. Autrement dit, le scrutin bipartiludique est une méthode « de Condorcet » (confer le deuxième article).

Démonstration

Supposons qu’il existe une vainqueuse de Condorcet X. Dans le jeu de chifoumi associé à ce scrutin, le coup « X » bat alors n’importe quel autre. Par conséquent, si le joueur Démocrate choisit la stratégie consistant à jouer systématiquement « X », il gagnera une fois sur deux quand le Républicain jouera le même coup, et à chaque fois que le Républicain jouera un autre coup ; ainsi, quelle que soit la stratégie utilisée par le Républicain, le Démocrate gagnera au moins une fois sur deux. Or cela signifie précisément que la stratégie consistant à jouer systématiquement « X » est une stratégie optimale (et donc la stratégie optimale) ; par conséquent, le résultat du scrutin bipartiludique dans ce cas consistera à déclarer X vainqueuse systématiquement.

Notez que dans les situations de la vraie vie, il existe quasiment toujours une vainqueuse de Condorcet [11] ; ainsi, le caractère aléatoire du scrutin bipartiludique a beau en être une propriété théorique essentielle, en pratique il apparaît comme un détail !

Digression : Le scrutin biparticulique DOIT être aléatoire

Il est tentant de vouloir éliminer le caractère aléatoire du scrutin bipartiludique en imaginant un « scrutin bipartiludique déterminisé » dans lequel l’option vainqueuse serait celle, non aléatoire, correspondant au coup joué le plus souvent dans le jeu de chifoumi associé (ce qui poserait incidemment des difficultés pour résoudre les cas d’ex-æquo, mais passons). Outre que la justification d’un tel système par analogie avec la situation des Démocrates et des Républicains ne serait plus valable, cette méthode perdrait en fait toutes les propriétés sympathiques du véritable scrutin bipartiludique :

  • D’abord, comme cela sera expliqué plus loin, le véritable scrutin bipartiludique est la seule méthode qui soit « robuste à la manipulation contre une vainqueuse de Condorcet » ; en particulier, le scrutin bipartiludique déterminisé ne possède pas cette propriété importante.
  • Encore plus grave, une telle méthode ne vérifierait pas une propriété théoriquement essentielle appelée « critère des clones » (dont nous avons déjà parlé dans la note [6]) : concrètement, cela signifie que si un parti décide de présenter deux candidats (aux lignes politiques extrêmement proches) au lieu d’un seul, il se peut que ce parti perde dans la configuration avec deux candidats alors qu’il aurait gagné avec un seul candidat ! C’est là une situation considérée comme inadmissible par presque tous les théoriciens, car elle incite les partis politiques à ne présenter qu’un nombre restreint de candidats, ce qui réduit injustement le choix offert aux électeurs.

Dans le deuxième article, nous avons dit que le fait d’être une méthode de Condorcet était une forme de robustesse à la manipulation (voir ici). Le scrutin bipartiludique est même particulièrement robuste à la manipulation :

Théorème (Robustesse à la manipulation du scrutin bipartiludique)

Le scrutin bipartiludique est « robuste à la manipulation contre une vainqueuse de Condorcet », dans le sens suivant : s’il existe une vainqueuse de Condorcet X (c’est-à-dire une option qui est majoritairement préférée à toute autre) [12], alors il n’est pas possible à un électeur ou un groupe d’électeurs de mettre au point une stratégie de vote mensongère qui changerait le résultat du scrutin sincère (lequel donne systématiquement X vainqueuse d’après le théorème précédent) dans un sens qui les arrangerait. J’entends par là que si ce groupe d’électeurs tente une manipulation, le nouveau résultat aura au moins autant de risques de désigner vainqueuse une option que ces manipulateurs aimaient moins que X que de chances de désigner vainqueuse une option qu’ils préféraient à X.

Démonstration

Supposons qu’il existerait une vainqueuse de Condorcet X si tout le monde votait sincèrement, et qu’en votant stratégiquement, un groupe d’électeurs a fait en sorte que le scrutin bipartiludique ne déclare plus systématiquement X vainqueuse, c’est-à-dire que le jeu de chifoumi associé au scrutin manipulé ait une stratégie optimale S dans laquelle le coup « X » ne soit plus systématiquement choisi. Appelons $p$ la probabilité que S choisisse un coup qui bat « X » (pour le scrutin manipulé s’entend), et $q$ la probabilité qu’elle choisisse un coup battu par « X » (la probabilité que S choisisse « X » lui-même étant donc de $1-p-q$). Quelle est alors la probabilité que, dans le jeu de chifoumi associé au scrutin manipulé, un joueur jouant systématiquement « X » gagne contre S ? Il y a une probabilité $q$ pour les cas où la stratégie S choisit un coup battu par « X », plus une probabilité $({1-p-q})/2$ pour les cas où S choisit « X » lui-même, soit au total une probabilité de $1/2 + ({q-p})/2$. Mais comme S est une stratégie optimale, nous savons que cette probabilité ne peut excéder $1/2$, de sorte que $p$ est forcément au moins aussi grand que $q$. Ainsi, quand le scrutin bipartiludique déclare vainqueuse une option autre que X (c’est-à-dire quand S choisit un coup autre que « X »), c’est plus souvent une option qui bat X (pour le scrutin manipulé) que l’inverse.

Maintenant, j’affirme qu’une option Y qui bat X dans le scrutin manipulé est forcément une option que nos électeurs manipulateurs aimaient moins que X ! En effet, dans la situation sincère X était une vainqueuse de Condorcet et battait donc Y. Mais si nos électeurs manipulateurs avaient préféré Y à X, leur vote stratégique n’aurait rien pu changer au fait que X batte Y, puisqu’alors ils auraient déjà donné leur préférence à Y sur X dans le suffrage sincère... Ainsi, les options battant X, que nous avons dit être le plus souvent désignées vainqueuses, sont des résultats qui vont contre l’intérêt de nos manipulateurs, ce qui est le théorème annoncé.

Le théorème ci-dessus ne semble guère impressionnant... Pourtant, le scrutin bipartiludique est la seule méthode de Condorcet qui le vérifie ! Nous ne démontrerons pas ce point ici ; cependant nous allons montrer comment, par exemple, la « méthode Schulze » que nous avions présentée dans le second article pourrait se prêter à la manipulation :

Proposition

La méthode Schulze ne vérifie pas le théorème ci-dessus.

Démonstration

Supposons qu’il y a 3 options X, Y et Z en lice, et que les préférences sincères des électeurs sont les suivantes :

  • X puis Y puis Z : 23 %
  • X puis Z puis Y : 19 %
  • Y puis X puis Z : 21 %
  • Y puis Z puis X : 15 %
  • Z puis X puis Y : 12 %
  • Z puis Y puis X : 10 %.

Dans ce cas, X bat Y (par 54 % à 46 %) et Z (63 % à 37 %) ; X est donc vainqueuse de Condorcet. Mais imaginons maintenant que les 21 % d’électeurs qui pensent « Y puis X puis Z » se mettent à voter « Y puis Z puis X ». On obtient alors une situation où X bat toujours Y par 54 %, Y bat Z par 59 %, mais cette fois-ci Z bat X par 58 % : il n’y a plus de vainqueuse de Condorcet, et c’est Y que la méthode Schulze désigne comme vainqueuse... Ainsi les électeurs manipulateurs ont bien gagné au change, puisqu’ils préféraient Y à X !

Références

  • Sur le vote par assentiment : Approval Voting, 2e édition, par S. Brams & P. Fishburn ; Springer éd. (2007). Niveau piste rouge (en anglais).
  • Sur le jugement majoritaire : Ne votez pas, jugez !, par M. Balinski & R. Laraki ; Pour la Science no 414, pp. 22–28 (2012). Niveau piste bleue.
  • Sur le « scrutin bipartiludique » : Fundamentals of Social Choice Theory, par Roger B. Myerson ; texte librement disponible sur l’internet (1996). Niveau hors-piste (en anglais).
  • Sur l’utilisation pratique des différentes méthodes électorales : Le suffrage universel inachevé, par M. Balinski ; Belin éd. (2004). Niveau piste verte.
P.S. :

Cette série d’articles, et ce dernier article en particulier, trouve son origine dans une conversation informelle avec Yann Ollivier : celui-ci, en m’expliquant le principe du scrutin bipartiludique, a le premier aiguisé ma curiosité pour les mathématiques de la démocratie... Qu’il soit remercié d’avoir su m’intéresser à un sujet aussi joli, riche et profond !

Concernant ce dernier article, l’élégance des illustrations doit un peu, une fois de plus, à mes sous-traitantes de sœurs... Merci en particulier à Mathilde d’avoir accepté de consacrer son temps et son talent au dessin de « Une Faille dans le système ».

Merci enfin aux relecteurs (Damien Gayet, TheBarber, Antoine Chambert-Loir) pour leurs commentaires et leurs suggestions, et plus particulièrement au premier cité dont la méticulosité de la relecture n’eut d’égale que la pertinence !

Notes

[1L’adjectif « utilitariste » vient de ce que la valeur d’une option aux yeux d’un électeur est appelée « utilité » par les mathématiciens.

[2Éventuellement l’électeur peut même choisir de n’attribuer que des pour ou que des contre, mais un tel vote sera évidemment sans effet sur la détermination de la vainqueuse.

[3Oui, vous avez bien lu : 1977... Qu’une méthode aussi naturelle et aussi simple ait mis aussi longtemps à émerger est pour le moins étonnant ! Signalons cependant que le vote par assentiment avait déjà été utilisé occasionnellement (notamment dans la République de Venise), mais fort peu, et surtout sans jamais qu’il apparût comme un moyen de représenter plus fidèlement la volonté collective.

[4On ne peut pas avoir $S_i=S_\spadesuit-1$, à cause de l’hypothèse que tous les scores ont des valeurs après la virgule différentes.

[5Dans l’introduction nous avions défini la vainqueuse du scrutin utilitariste comme l’option ayant le meilleur total ; dans cette partie il sera plus commode de parler en termes de moyenne, ce qui évidemment revient au même.

[6Il est important de réaliser que le système de scrutin employé dans un pays impacte notoirement la vie politique de celui-ci. Par exemple, le scrutin uninominal majoritaire à un tour a tendance à favoriser l’émergence du bipartisme (c’est la loi de Duverger) : en effet, si deux partis majeurs sont en place, une électrice tentée de voter pour un petit parti se dira que sa voix a peu de chances de faire gagner ce parti tiers, mais que par contre cette voix pourrait manquer à celui des deux grands partis qu’elle préfère et amener de ce fait la victoire de l’autre grand parti, de sorte qu’elle préfèrera finalement voter pour un des deux grands partis même si ce n’était pas son préféré dans l’absolu — c’est le fameux “vote utile”. Un système uninominal à deux tours est à peine meilleur de ce point de vue, ne permettant guère la coexistence de plus de trois grands partis. À l’inverse, les méthodes électorales que nous présentons dans cet article ne présentent pas cet effet de vote utile et permettent à un électeur d’exprimer sa préférence pour un “petit” candidat sans risque — c’est ce qu’on appelle le « critère des clones » —, de sorte qu’il n’y a alors aucun intérêt pour les partis politiques à s’agréger en “mastodontes” tentant tant bien que mal de concilier des points de vue hétéroclites.

[7Une telle situation peut paraitre incohérente à première vue, mais elle est néanmoins possible en vertu du « paradoxe de Condorcet » (voir ici).

[8Qu’on doive jouer de façon aléatoire ne signifie pas pour autant qu’on puisse jouer n’importe comment : il faut certes utiliser le hasard pour choisir son coup, mais on doit l’utiliser d’une certaine manière bien précise !

[9Notez qu’aucune stratégie ne peut garantir une probabilité de victoire strictement supérieure à 50 % : en effet, si l’adversaire a choisi la même stratégie que vous, il est évident que chacun des deux aura 50 % de chances de gagner.

[10L’adjectif « bipartiludique », inventé par l’auteur, signifie étymologiquement « relatif au jeu des deux partis ».

[11Cf. M. Balinski, Le suffrage universel inachevé, pp. 310-311. L’exemple de la présidentielle française de 2012 traité dans le second article corrobore également cette observation.

[12C’est presque toujours le cas en pratique, comme nous l’avons dit plus haut.

Crédits images

Image à la une — Réalisation personnelle
Bulletin de vote par assentiment — Réalisation personnelle
Dépouillement d’un scrutin par assentiment — Réalisation personnelle
Bulletin de vote à la préférence majoritaire — Réalisation personnelle
Dépouillement d’un scrutin à la préférence majoritaire — Réalisation personnelle
Bulletin de vote bipartiludique — Réalisation personnelle
Dépouillement d’un scrutin bipartiludique — Réalisation personnelle
Des « moi » au « nous » — D’après une affiche de l’INSEE promouvant le recensement de la population française
Jeu de chifoumi standard — Réalisé par Ἀνεπώνυμη
Les inventeurs du jugement majoritaire — © Institute for Operations Research and the Management Sciences (photo de gauche) / Rida Laraki (photo de droite)
Une faille dans le système... — Dessiné par Mathilde Peyre

Affiliation de l'auteur

Rémi Peyre : Institut Élie Cartan (Université de Lorraine) / CNRS

Commentaires sur l'article

Pour citer cet article : Rémi Peyre, « La quête du Graal électoral »Images des Mathématiques, CNRS, 2013.

En ligne, URL : http://images.math.cnrs.fr/La-quete-du-Graal-electoral.html

Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :