Les mathématiques de la démocratie, I

La démocratie, objet d’étude mathématique

Piste verte 16 avril 2012  - Rédigé par  Rémi Peyre Voir les commentaires (18)

Une démocratie est un régime politique dans lequel les décisions sont prises en fonction de la volonté du peuple. Mais qu’est-ce que la volonté du peuple ? En d’autres termes, quelle est la bonne façon de tenir compte des préférences de chaque individu pour en déduire la préférence collective ? Depuis quelques décennies, les mathématiciens se sont penchés sur ces questions, et sont arrivés à des conclusions... surprenantes ! (Ce texte est le premier d’une série de trois articles sur les problématiques mathématiques soulevées par l’étude du concept de démocratie : voir les liens suivants pour le second article, resp. pour le troisième article).

Introduction : La démocratie ? Quelle démocratie ?

Le dilemme des Alliérins

Suite à une révolution, le département de l’Allier est devenu indépendant ! La Constitution du nouvel État prévoit que des élections démocratiques soient organisées pour désigner sa capitale. Il se trouve que l’Allier présente la particularité d’avoir trois villes principales de tailles comparables, villes que nous noterons par leur dernière lettre : Montluçon (N), Moulins (S) et Vichy (Y). Chacune des ces villes a déposé une candidature pour devenir capitale, et chaque citoyen souhaite naturellement que la future capitale soit la plus proche possible de chez lui. Ainsi [voir la carte ci-dessous], les habitants de N, à défaut de voir leur ville choisie, préfèreraient S à Y, les habitants de S préfèreraient Y à N, et les habitants de Y préfèreraient S à N. (Nous négligerons ici les citoyens n’habitant aucune des trois villes).

L’Allier

Carte de l’Allier montrant les trois villes et les distances les séparant.

Si la Constitution dit bien que c’est par une élection démocratique que doit être désignée la capitale, elle ne précise en revanche pas quelle méthode électorale doit être suivie. Plusieurs méthodes concurrentes, toutes clairement démocratiques, ont été proposées :

  • Méthode A : Chaque électeur vote pour une ville ; la ville qui reçoit le plus de suffrages gagne.
  • Méthode B : Dans un premier tour, chaque électeur vote pour une ville, puis un second tour est organisé entre les deux villes ayant reçu le plus de suffrages au premier tour ; la ville qui reçoit le plus de suffrages au second tour gagne.
  • Méthode C : Chaque électeur vote contre une ville ; la ville qui reçoit le moins de suffrages gagne.
  • Méthode D : Dans un premier tour, chaque électeur vote contre une ville, puis un second tour est organisé entre les deux villes ayant reçu le moins de suffrages au premier tour ; la ville qui reçoit le moins de suffrages au second tour gagne.
  • Méthode E : Chaque électeur classe les villes par ordre de préférence ; sa ville préférée marque 2 points, la suivante 1 point et la dernière aucun. La ville qui obtient le meilleur total gagne.

Diantre, que de possibilités ! Mais bon, vu que ces méthodes sont toutes démocratiques, peut-être donnent-elles en fait la même vainqueuse... Hélas, non. Imaginons par exemple que 40 % des électeurs habitent N, 35 % habitent Y et 25 % habitent S. Alors :

  • Suivant la méthode A, N gagne par 40 % des suffrages contre 35 % pour Y et 25 % pour S.
  • Suivant la méthode B, Y gagne au second tour contre N par 60 % des suffrages contre 40 %, vu que les habitants de S se reportent sur Y au second tour.
  • Suivant la méthode C, S gagne par 0 % des suffrages contre 40 % pour Y et 60 % pour N, vu que les habitants de S et de Y votent contre N et que ceux de N votent contre Y.
  • Suivant la méthode D, S gagne au second tour contre Y par 35 % des suffrages contre 65 %, puisqu’après l’élimination de N les habitants de S votent contre Y et ceux de Y contre S.
  • Suivant la méthode E, S gagne avec une moyenne de 1,25 points par électeur (2 points de la part des habitants de S, et 1 point de ceux de N et de Y), suivi de Y avec 0,95 points (2 points de la part des habitants de Y, 1 point de ceux de S, et aucun de ceux de N), et de N avec 0,80 points (2 points de la part des habitants de N, et aucun de ceux de Y et de S).

Notez qu’ici les méthodes C, D et E donnent la même vainqueuse, mais qu’elles auraient pu aboutir à des vainqueuses contradictoires pour une autre répartition des électeurs entre les trois villes... Le tableau ci-dessous montre ainsi quelles seraient les vainqueuses suivant les différentes méthodes pour diverses répartitions des électeurs (le cas que nous venons de détailler est la ligne sur fond gris).

Les vainqueuses donnés par les différentes méthodes pour diverses répartitions des électeurs.
Proportion d’habitants de N Habitants de S Habitants de Y Vainqueuse selon la méthode A Selon B Selon C Selon D Selon E
60 % 15 % 25 % N NS N N
60 % 25 % 15 % N N S N S
40 % 25 % 35 % N Y S S S
40 % 35 % 25 % N S S S S
30 % 40 % 30 % S S S S S
25 % 35 % 40 % Y S S S S
35 % 25 % 40 % Y Y S S S
20 % 20 % 60 % Y Y S Y Y

La conclusion qu’on tire de cet exemple introductif, c’est que le concept de “volonté du peuple” se révèle ambigu, dans la mesure où plusieurs définitions a priori raisonnables de cette volonté sont en fait contradictoires... Par conséquent, le concept de démocratie, en tant que régime politique dans lequel les décisions sont prises en fonction de la volonté du peuple, est également ambigu ! Ainsi, derrière l’idée “naturelle” de démocratie, se pose le délicat problème suivant : comment déterminer la volonté du peuple à partir des préférences individuelles ? Y a-t-il des méthodes qui soient meilleures que d’autres, et si oui lesquelles ?

Or, dès lors qu’il s’agit de rendre rigoureuse l’étude d’un concept, on entre dans le terrain de jeu des mathématiciens... Il n’est donc pas surprenant que depuis la seconde moitié du XXe siècle, des dizaines de chercheurs se soient penchés sur les problèmes afférents à la théorie des élections démocratiques [1]. Leurs conclusions, nous le verrons, sont parfois très surprenantes...!

Cadre de cet article

L’objet de cet article (et de ceux à suivre) est d’analyser les différentes méthodes électorales démocratiques. Il y a différents contextes dans lesquels on peut vouloir recourir à un scrutin : choisir un président, composer une assemblée de représentants, ajuster les composantes d’un budget... Ces différents contextes peuvent conduire à des problématiques mathématiques différentes. Dans cette série d’articles, nous allons nous limiter à un cadre précis, mais malgré tout très général :

  • On s’intéresse aux situations où il s’agit de choisir une seule option parmi plusieurs. On peut en fait toujours se ramener à ce cadre : ainsi, choisir une entrée, puis un plat, puis un dessert est équivalent à choisir directement un menu ; de même, classer les candidats d’un concours équivaut à choisir un classement parmi tous ceux possibles...
  • On demande que l’élection se déroule en un seul tour. Là non plus ce n’est pas une vraie restriction, attendu qu’en revanche les bulletins de vote peuvent contenir des informations complexes. Une élection selon la méthode B ci-dessus, par exemple, peut très bien être organisée en un seul scrutin : dans cette organisation, chaque bulletin comportera, d’une part le choix de l’électeur au premier tour, d’autre part l’ensemble de ses choix au second tour pour tous les seconds tours possibles, ce qui donne bien une méthode équivalente au protocole à deux tours.
  • Les options proposées sont en nombre fini (mais peut-être très grand), de même que les types de suffrages possibles [2]. Il s’agit là d’une exigence essentiellement technique destinée à éviter certaines difficultés mathématiques ; en pratique ce n’est pas une restriction très importante.

Les hypothèses

Puisque nous parlons ici de mathématiques, il nous faut aussi donner un sens précis à ce que nous entendons par « méthode électorale démocratique ». Dans cette série d’articles, nous imposerons les hypothèses suivantes :

  • Tous les électeurs ont le même statut : aucun électeur n’est privilégié par rapport aux autres [3], et il n’y a pas non plus de système de “circonscriptions” qui établirait des relations particulières entre certains d’entre eux [4].
  • De même, toutes les options ont le même statut. En particulier, il n’y a aucune restriction sur les préférences que peut avoir un électeur : dans une élection réelle, cela signifierait par exemple qu’un électeur peut très bien avoir en premier choix le candidat “de droite”, en second choix le candidat “de gauche” et en troisième choix le candidat “du centre”, puisqu’ici les mots « gauche », « centre » et « droite » n’ont aucune signification...
  • Tous les électeurs votent, et il n’y a pas de bulletin nul (en revanche, la méthode peut très bien prévoir un type de suffrage « blanc »). Cela sert uniquement à simplifier la présentation, puisqu’on peut toujours décider qu’il y a des types de suffrages « abstention » et « nul » ayant le même effet qu’un suffrage « blanc ».
  • L’option vainqueur de l’élection dépend uniquement de la proportion d’électeurs ayant voté tel ou tel type de suffrage, pas de leur nombre absolu (par exemple, cela exclut que la méthode contienne une condition comme « seuls les types de suffrages ayant été votés par au moins 2 électeurs comptent »).
  • On suppose enfin que les cas “limites” où deux options sont rigoureusement à égalité, ou où tout le monde a voté blanc, etc., ne se produisent jamais [5] :
    c’est en effet ce qui se passe en pratique quand le nombre d’électeurs est très grand, donc autant ne pas s’ennuyer à préciser ce qu’on fait en cas d’ex-æquo.

Le paradoxe de Condorcet

Le référendum : jusqu’ici tout va bien...

La majorité a toujours raison !

Une pensée du célèbre Chat de Philippe Geluck.

La problématique de la démocratie est souvent résumée par la maxime « la majorité a toujours raison », ce qui paraît très simple à première vue. Ainsi, si le choix doit se faire entre 2 options seulement (ce que nous appellerons un référendum), les cinq méthodes que nous avons données dans le « dilemme des Alliérins » de l’introduction se confondent en une seule et même méthode : c’est l’option que la majorité des électeurs préfèrent à l’autre qui gagne ! Nous appellerons cette méthode (spécifique aux référendums) la méthode de la majorité. On peut montrer que la méthode de la majorité est (dans un certain sens) la seule méthode démocratique “convenable” dans les situations de référendum : voir le “théorème du référendum” quelques paragraphes plus loin.

♪ Sitôt qu’on est plus de deux... ♪

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

Toutefois, cette belle simplicité s’écroule dès qu’il y a au moins 3 options ! La découverte de ce phénomène est due au mathématicien français du XVIIIe siècle Nicolas de Condorcet, qui fut le plus important précurseur de l’étude mathématique de la démocratie avec son Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix écrit en 1785 [6]. Dans cet ouvrage, Condorcet démontre que la méthode de la majorité peut aboutir à des incohérences, et que donc il n’est pas raisonnable de poser que la majorité ait toujours raison :

Paradoxe de Condorcet (1785) : Il existe des situations où les préférences majoritaires des électeurs sont incohérentes, au sens où on peut trouver trois options X, Y et Z telles qu’une majorité d’électeurs préfèrent X à Y, une majorité d’électeurs préfèrent Y à Z, mais pourtant une majorité d’électeurs préfèrent Z à X.

Démonstration (piste verte)

On peut imaginer 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, 75 % préfèrent Y à Z, mais pourtant 60 % préfèrent Z à X.

Dans les situations concrètes, il semblerait que le paradoxe de Condorcet n’arrive en fait que rarement [7]. Mais du point de vue théorique, il s’agit quand même d’une belle épine dans notre pied : s’il est possible de se retrouver face à des situations aussi contraires à l’intuition, y a-t-il une chance qu’on puisse définir une théorie mathématique cohérente de la volonté du peuple ?

Le problème de la manipulation : élections, piège à cons ?

Une méthode parfaite... ou presque

En fait, la raison qui explique que le problème de déterminer la volonté du peuple soit si délicat n’est elle-même pas vraiment mathématique, mais plutôt... biologique. Pour comprendre pourquoi, nous allons présenter une méthode électorale “idéale” qui résoudrait tous nos problèmes dans un monde parfait, puis voir pourquoi celle-ci ne convient en fait pas dans la réalité. Dans cette méthode (que nous noterons « F »), chaque électeur vote en donnant une note entre 0 et 20 à chaque option, « 20 » signifiant qu’il adhère totalement à cette option et « 0 » qu’il la rejette totalement. Pour le dilemme des Alliérins, par exemple, on pourrait imaginer que les électeurs donnent une note de 20 à leur propre ville et que pour les autres villes ils enlèvent 1 point tous les 5 kilomètres de distance, de sorte que les notes données par les électeurs seraient celles du tableau ci-dessous.

Les notes que les différents électeurs donneraient sincèrement aux différentes villes.
Provenance de l’électeur Note de N Note de S Note de Y
N 20 5 1
S 5 20 8
Y 1 8 20

L’idée derrière cette méthode, c’est que la volonté du peuple doit être l’option qui optimise le bonheur total de la population, les notes servant à mesurer ce “bonheur”. Du point de vue philosophique, cette définition de la volonté du peuple (appelée utilitarisme) est certainement la plus raisonnable qu’on puisse donner ; et du point de vue mathématique, la méthode F permet de résoudre le paradoxe de Condorcet puisque l’ordre entre deux options est simplement l’ordre entre leurs notes moyennes et conduit donc à un classement sans ambiguïté [8]. Est-ce à dire que la méthode F est la méthode parfaite ? Hélas, non. Elle le serait... si Homo sapiens n’avait pas la capacité de mentir !
Voici en effet ce qui pourrait se passer dans la réalité, pour 40 % d’habitants de N, 35 % de Y et 25 % de S :

  1. Tout d’abord, si les électeurs votaient sincèrement, les notes seraient celles du tableau ci-dessus. S gagnerait alors par une moyenne de 9,80 points, suivi de N (9,60 points) et enfin Y (9,40 points).
  2. Mais comme les habitants de N sentent bien qu’ils risquent de finir seconds, ils peuvent décider de “mentir” en donnant à S une note de 0, bien que celle-ci ne corresponde pas à leur opinion véritable : dans ce cas en effet, la moyenne de S descend à 7,80 et c’est N qui gagne !
  3. Anticipant cette manœuvre, les habitants de Y se disent alors que c’est eux qui risquent de finir seconds... Du coup, ils décident de mentir à leur tour en donnant à N une note de 0 : cela fait descendre la moyenne de N à 9,25 et c’est maintenant Y qui gagne !
  4. Et, de stratagème en anticipation, on peut encore continuer longtemps comme cela...

Ce qui est sûr en tout cas, c’est que cette possibilité de voter un suffrage mensonger afin d’obtenir une vainqueuse qu’on préfère à celui que donnerait un suffrage sincère (ce que nous appellerons une manipulation) va complètement dévoyer la méthode en incitant les électeurs à donner des notes n’ayant que peu de rapport avec leur opinion véritable. Une anecdote raconte que le mathématicien français Jean-Charles de Borda, qui dans un ouvrage de 1770 avait défendu une méthode proche de la méthode F [9], répondit à Condorcet qui lui objectait la vulnérabilité de celle-ci à la manipulation : « ma méthode est faite pour des gens honnêtes ».

Si la maxime de Borda était pleine d’humanisme, force est malheureusement de constater qu’elle ne correspond guère à la réalité... Au contraire, il paraît plus réaliste de supposer que les électeurs n’hésiteront pas à utiliser dans leur intérêt personnel toute possibilité de manipulation permise par la méthode qui leur est proposée. Par conséquent, il paraît raisonnable d’exiger d’une méthode électorale, pour la qualifier de “bonne”, qu’elle soit robuste à la manipulation, c’est-à-dire que les électeurs aient toujours intérêt à voter selon leur opinion véritable. Est-ce possible ?

Le théorème de Gibbard & Satterthwaite

JPEG - 34.1 ko
Mark Satterthwaite
Photographie contemporaine de l’économiste Mark Satterthwaite.

Précisons la question que nous venons de poser. Il s’agit donc de savoir s’il existe une méthode démocratique pour laquelle les électeurs ont toujours intérêt à exprimer sincèrement leur opinion. Compte tenu que, comme nous venons de le voir, les méthodes de notation sont facilement vulnérables à la manipulation, il est clair que les seules questions qu’on pourra poser aux électeurs dans une méthode robuste à la manipulation devront concerner quelles options ils préfèrent à quelles autres, sans indication de nuance. Par conséquent, les types de suffrages possibles correspondront à un ordre de préférence entre les différentes options. Nous supposerons que les bulletins n’autorisent pas les ex-æquo, au motif qu’il y a toujours un chouïa qui fait basculer la préférence de l’électeur d’un côté ou de l’autre [10]. Ainsi, s’il y a 3 options X, Y et Z, il y aura 6 types de suffrages possibles qui sont « X puis Y puis Z », « X puis Z puis Y », « Y puis X puis Z », « Y puis Z puis X », « Z puis X puis Y » et « Z puis Y puis X ». Ce cadre étant précisé, la question de savoir s’il existe une méthode démocratique pour laquelle les électeurs ont toujours intérêt à voter sincèrement devient un problème mathématique parfaitement posé. Quelle est sa réponse ?

JPEG - 45.9 ko
Allan Gibbard
Photographie contemporaine du philosophe Allan Gibbard.

C’est en 1973 que deux chercheurs américains ont résolu indépendamment le problème... par la négative. Notez qu’aucun des deux n’appartenait au milieu des mathématiciens : Allan Gibbard était étiqueté comme philosophe et Mark Satterthwaite comme économiste... Mais c’est bien un théorème qu’ils ont démontré :

Théorème de Gibbard-Satterthwaite (1973) : Supposons que les types de suffrages possibles correspondent à classer par ordre de préférence les différentes options. Alors, quelle que soit la méthode démocratique pour déterminer l’option vainqueur à partir des votes des électeurs, dès qu’il y a au moins 3 options, on peut trouver une situation dans laquelle certains électeurs ont intérêt à voter un suffrage qui ne reflète pas leur opinion véritable.

Démonstration (piste noire) [11]

Supposons par l’absurde que nous ayons une méthode pour 3 options ou plus pour laquelle aucun électeur n’ait jamais intérêt à mentir. Nous considèrerons seulement le cas où il y a exactement trois options en lice X, Y et Z, vu qu’on peut toujours se ramener à ce cas en imaginant que ces trois options sont unanimement préférées à toutes les autres.

Imaginons que les proportions des différents types de suffrages sont telles que X soit déclarée vainqueuse, et considérons un électeur dont l’opinion véritable est « Y puis X puis Z ». Si cet électeur remplace son suffrage sincère par un suffrage mensonger « Y puis Z puis X », alors la vainqueuse après ce replacement ne doit pas pouvoir être Y, car sinon il serait avantageux pour l’électeur de mentir, ce qui est interdit par notre hypothèse. Ainsi, remplacer un suffrage « Y puis X puis Z » par un suffrage « Y puis Z puis X » ne peut pas faire changer la vainqueuse de X pour Y. Cela ne peut pas non plus faire changer la vainqueuse de Y pour X (ce qui serait bizarre, du reste), car sinon en faisant marche arrière on ferait changer la vainqueuse de X pour Y en remplaçant un suffrage « Y puis Z puis X » par un suffrage « Y puis X puis Z », ce qui est interdit par le même argument.

Avec le même raisonnement, on peut également montrer qu’on ne peut pas non plus faire changer la vainqueuse de X pour Y ni de Y pour X en remplaçant un suffrage « Z puis Y puis X » par un suffrage « Y puis Z puis X », ni en remplaçant « X puis Z puis Y » par « X puis Y puis Z », ni en remplaçant « X puis Z puis Y » par « Z puis X puis Y » (ou l’inverse). Au final, on se rend compte qu’aucune modification de suffrage ne peut faire changer la vainqueuse de X pour Y ni de Y pour X dès lors que cette modification ne change pas l’ordre relatif entre X et Y chez le suffrage concerné.

On a évidemment la même chose en permutant les rôles de X, Y et Z : aucune modification de suffrage ne peut faire changer la vainqueuse entre X et Z dès lors qu’elle ne change pas l’ordre relatif entre X et Z chez le suffrage concerné, et aucune modification de suffrage ne peut faire changer la vainqueuse entre Y et Z dès lors qu’elle ne change pas l’ordre relatif entre Y et Z chez le suffrage concerné. Par conséquent, la vainqueuse de l’élection dépend uniquement de la proportion de suffrages chez lesquels X est classée devant Y, de la proportion de suffrages où Y est classée devant Z et de la proportion de suffrages où Z est classée devant X, puisque si aucune de ces trois proportions n’est modifiée, la vainqueuse ne peut changer ni entre X et Y, ni entre X et Z, ni entre Y et Z.

Du coup, à toute valeur possible $(q_{XY},q_{YZ},q_{ZX}) \in [0,1]^3$ du triplet (« proportion de suffrages où X est classée devant Y », etc.), notre méthode associe une vainqueuse parmi $\{X,Y,Z\}$. On peut alors diviser l’espace tridimensionnel (ou plus précisément la partie de l’espace correpondant aux triplets possibles) en trois zones « X », « Y » et « Z », où la zone X est l’ensemble des points dont les coordonnées sont un triplet $(q_{XY},q_{YZ},q_{ZX})$ pour lequel X est déclarée vainqueuse, etc. : voir le dessin ci-dessous.

Représentation des préférences binaires entre X, Y et Z

L’ensemble des valeurs que peut prendre le triplet $(q_{XY},q_{YZ},q_{ZX})$ est un octaèdre irrégulier (en noir) obtenu en coupant deux coins opposés du cube $[0,1]^3$ (en gris). Les six sommets de cet octaèdre correpondent aux cas où tous les bulletins sont du même type : ainsi, le sommet « ZYX » correspond au cas où tous les bulletins sont du type « Z puis Y puis X », etc. Sur ce dessin, la coordonnée « arrière-avant » indique la proportion $q_{XY}$, la coordonnée « gauche-droite » indique $q_{YZ}$ et la coordonnée « bas-haut » indique $q_{ZX}$.

Puisque faire changer la vainqueuse de X pour Z impose de modifier $q_{ZX}$, cela signifie que la frontière entre les zones X et Z doit correspondre (localement) à une valeur constante de $q_{ZX}$, autrement dit que cette frontière est horizontale. Or, quand $q_{XY}$, $q_{YZ}$ et $q_{ZX}$ sont toutes les trois égales, les trois options jouent des rôles complètement symétriques, de sorte qu’on se situe nécessairement à la frontière entre les trois zones à la fois ; par conséquent, la droite « $q_{XY} = q_{YZ} = q_{ZX}$ » est en particulier contenue dans la frontière entre les zones X et Z, et donc est horizontale. Mais cela n’est pas vrai vu que $q_{ZX}$ varie le long de cette droite ! La seule manière d’éviter cette absurdité est de conclure que notre hypothèse de départ était fausse, autrement dit qu’aucune méthode électorale démocratique pour 3 options ou plus n’est robuste à la manipulation.

Notez que l’hypothèse qu’il y a au moins 3 options est cruciale, puisqu’en cas de référendum, la méthode de la majorité est robuste à la manipulation : c’est le “théorème du référendum”, dont l’origine se perd dans la nuit des temps :

Théorème du référendum : Supposons que nous sommes en présence d’un référendum (les options étant appelées « X » et « Y ») et qu’il y a deux types de suffrages possibles : « je préfère X » et « je préfère Y ». Alors :
  1. La méthode de la majorité est robuste à la manipulation, c’est-à-dire que les électeurs ont toujours intérêt à exprimer leur opinion véritable ;
  2. Cette méthode de la majorité est la seule méthode démocratique qui soit robuste à la manipulation.

Démonstration du premier point (piste verte)

Sous la méthode de la majorité, un électeur qui remplacerait son suffrage pour X par un suffrage pour Y ferait diminuer le score de X et augmenter celui de Y, de sorte qu’il pourrait éventuellement faire changer le résultat d’une victoire de X vers une victoire de Y, mais pas l’inverse. Par conséquent, si l’opinion véritable de cet électeur est en faveur de X, il n’a jamais intérêt à faire ce remplacement. De même, un électeur dont l’opinion véritable est en faveur de Y n’a jamais intérêt à voter pour X, ce qui prouve le point i.

Démonstration du second point (piste bleue)

Pour le point ii, supposons que nous avons une méthode démocratique robuste à la manipulation ; notre objectif est de montrer que cette méthode est nécessairement la méthode de la majorité. La robustesse à la manipulation implique que quand un électeur remplace un suffrage pour Y par un suffrage pour X, cela peut éventuellement faire gagner Y à la place de X, mais pas l’inverse (car sinon un électeur dont l’opinion véritable est en faveur de X aurait intérêt à voter un suffrage mensonger pour Y). En conséquence, si on passe progressivement de 0 % de suffrages pour Y (et 100 % pour X) à 100 % de suffrages pour Y (et 0 % pour X), il se peut qu’à un moment la vainqueuse passe de X à Y, mais pas l’inverse. Du coup, au cours de ce passage progessif de 0 % de suffrages pour Y à 100 %, ce qui se produit est forcément qu’il existe un seuil en deçà duquel c’est X qui gagne et au-delà duquel c’est Y qui gagne.

Notons S le pourcentage correspondant à ce seuil, c’est-à-dire que si Y reçoit plus de S % des suffrages, c’est Y qui gagne, et que sinon c’est X qui gagne. Comme les options X et Y jouent le même rôle, on a aussi que X gagne s’il reçoit plus de S % des suffrages et que Y gagne sinon. Le fait que Y reçoive plus de S % des suffrages doit donc être équivalent au fait que X reçoive moins de S % des suffrages ; par conséquent les deux options doivent se retrouver à exactement S % des suffrages au même moment. À ce moment-là, le total des suffrages sera alors de (2×S) %, et comme ce total des suffrages doit de toutes façons être de 100 %, c’est que nécessairement S est égal à 50 : on en conclut que notre méthode est bien la méthode de la majorité, ce qu’on voulait.

JPEG - 57 ko
Kenneth Arrow
Kenneth Arrow, “prix Nobel d’économie” 1972 (photographié en 2004).

Le théorème de Gibbard-Satterthwaite s’inscrit dans une lignée de grands résultats négatifs établis au cours de la seconde moitié du XXe siècle. La découverte de ces résultats fut une petite révolution théorique : ainsi, le premier des résultats de cette lignée, établi par l’économiste américain Kenneth Arrow en 1952, lui valut la quatrième édition du “prix Nobel d’économie” vingt ans plus tard !

Tout cela est tout de même assez déprimant : le seul intérêt de l’étude mathématique de la démocratie serait-il donc de gagner 240 000 couronnes [12] ? La théorie de la volonté du peuple serait-elle nécessairement absurde ? Restons optimistes : maintenant que nous avons touché le fond, nous ne pouvons plus que remonter... Et de fait, il y a aussi des résultats positifs dans la théorie de la volonté populaire ! Nous allons voir un tel résultat pas plus tard que tout de suite.

Le scrutin stochocratique, remède à tous nos maux ?

Attaquons ce paragraphe par une annonce fracassante : contrairement à ce que je vous ai laissé entendre, il existe bel et bien une méthode démocratique pour laquelle aucun électeur n’a jamais intérêt à voter de façon mensongère ! « Comment cela est-il possible sans contrevenir au théorème de Gibbard-Satterthwaite ? » me demanderez-vous. Eh bien, le fait est que j’ai passé sous silence une hypothèse implicite dans ce théorème... À savoir, j’ai supposé que l’option vainqueur de l’élection devait être déterminée uniquement par les votes des électeurs. Cette hypothèse paraît nécessaire à première vue, puisqu’on se dit que faire intervenir un paramètre extérieur romprait l’égalité entre les options ou entre les électeurs... Mais il y a tout de même un paramètre extérieur qui ne rompe pas cette égalité : le hasard ! En d’autres termes, on peut imaginer que vote des électeurs ne désigne pas directement l’option vainqueur de l’élection, mais que celle-ci soit désignée in fine par un tirage au sort — tirage dont, bien sûr, les règles dépendront des votes exprimés par les électeurs (ainsi, si par exemple tous les électeurs ont classé les deux mêmes options devant toutes les autres, il paraît raisonnable que dans ce cas le tirage ne permette la victoire que d’une de ces deux options-là).

On peut ainsi imaginer une méthode où chaque électeur écrit sur son bulletin son option préférée, puis où on mélange tous les bulletins avant d’en tirer un au hasard et de décider que celui-ci désigne l’option vainqueur de l’élection : nous appellerons cette méthode le scrutin stochocratique. Bien que cette méthode fasse appel au hasard, elle n’est pas complètement arbitraire non plus dans la mesure où, par exemple, une option n’a aucune chance de gagner si tous les électeurs lui préfèrent une même autre option : c’est ce qu’on appelle le critère d’unanimité. En outre, cette méthode est robuste à la manipulation :

Théorème : Dans un scrutin stochocratique, tous les électeurs ont toujours intérêt à exprimer leur opinion véritable.

Démonstration (piste verte)

Quand un électeur réfléchit au suffrage qu’il va voter, il doit prendre en compte deux éventualités, dont les probabilités ne dépendent pas du choix qu’il va faire :

  • Soit le bulletin tiré au sort est celui d’un autre électeur. Dans ce cas le suffrage de notre électeur n’est pas pris en compte, et il n’a donc aucun intérêt à mentir.
  • Soit le bulletin tiré au sort est le sien, et dans ce cas notre électeur a tout intérêt à exprimer son opinion véritable.

Dans tous les cas, il vaut donc mieux pour l’électeur exprimer son opinion véritable.

Le scrutin stochocratique est donc une méthode robuste à la manipulation. Cela dit, c’est tout de même une méthode assez “brutale”, car faisant courir le risque, bien que faible, que gagne une option qui déplaît à la grande majorité des électeurs ; en particulier, quand il n’y a que 2 options, cette méthode ne redonne pas la méthode de la majorité ! On aimerait donc bien disposer d’une autre méthode du même type qui soit plus “raisonnable” de ce point de vue... Mais il se trouve hélas que le scrutin stochocratique est la seule méthode qui satisfasse les critères que nous venons de voir :

Théorème “de la dictature aléatoire” (Gibbard, 1977) : Supposons que les types de suffrages possibles correspondent à classer par ordre de préférence les différentes options. Alors, dès qu’il y a au moins 3 options, la seule méthode démocratique avec tirage au sort éventuel qui satisfasse le critère d’unanimité (càd. pour laquelle une option unanimement classée derrière une même autre ne gagne jamais) et pour laquelle aucun électeur n’ait jamais intérêt à mentir est le scrutin stochocratique.

Démonstration (piste noire) [13]

Supposons que nous disposons d’une méthode robuste à la manipulation et satisfaisant le critère d’unanimité ; nous allons montrer que cette méthode est nécessairement le scrutin stochocratique. Pour simplifier la présentation, nous nous limitons au cas où seulement 3 options sont en lice, notées X, Y et Z ; sachant que le raisonnement que nous allons suivre s’adapte directement au cas d’un nombre arbitraire d’options [14]. Nous abrègerons les types de suffrages « X puis Y puis Z », « X puis Z puis Y », etc. en « XYZ », resp. « XZY », etc. Nous noterons $p_X$, $p_Y$ et $p_Z$ les probabilités que X, Y et Z gagnent à l’issue du tirage au sort, ces probabilités dépendant déterministiquement de la proportion de suffrages des différents types.

Commençons par observer que, quand un électeur remplace un suffrage XYZ par un suffrage XZY, cela ne peut pas faire varier $p_X$ (et de même, remplacer un suffrage YXZ par YZX ne pourra pas faire varier $p_Y$, ni remplacer ZXY par ZYX faire varier $p_Y$). En effet, imaginons un électeur aux yeux desquels Y et Z ont pratiquement la même valeur, mais qui estime que X leur est très supérieure. Pour cet électeur, la seule chose qui compte vraiment est de maximiser $p_X$ ; par conséquent, s’il arrivait à faire augmenter $p_X$ en remplaçant son suffrage XYZ par XZY, cela servirait son intérêt même si en réalité il préfère d’un chouïa Y à Z ; or cela est exclu par l’hypothèse de robustesse à la manipulation. C’est donc que remplacer un suffrage XYZ par XZY ne peut pas faire augmenter $p_X$ ; et cela ne peut pas le faire diminuer non plus puisque sinon c’est remplacer un suffrage XZY par XYZ qui ferait augmenter $p_X$, ce qu’on exclut de la même façon.

Nous venons ainsi d’établir que permuter les deux dernières options d’un suffrage ne peut pas faire varier la probabilité de victoire de l’option classée première sur ce suffrage. On montrerait de la même façon que permuter les deux premières options d’un suffrage ne peut pas faire varier la probabilité de victoire de l’option classée dernière sur ce suffrage : par exemple, remplacer XYZ par YXZ ne peut pas faire varier $p_Z$. [15]

Maintenant, imaginons la situation suivante. Dans un premier temps, un électeur votant XYZ change d’avis et décide de voter XZY : d’après ce que nous venons de voir, cela a pour seul effet éventuel d’augmenter $p_Z$ d’une probabilité $\varepsilon$ (qui pourrait être en fait négative sans perturber le raisonnement) et de diminuer $p_Y$ de la même quantité. Puis dans un second temps, une autre électrice change à son tour d’avis en remplaçant, pour sa part, son suffrage ZXY par ZYX : d’après ce que nous venons de voir, cela ne fait pas varier $p_Z$. L’effet combiné de ces deux changements sur $p_Z$ est donc une augmentation de $\varepsilon$. Regardons maintenant ce qui se passe quand on inverse l’ordre des changements d’avis, c’est-à-dire que la seconde électrice change d’avis en première : alors dans un premier temps $p_Z$ ne varie pas, et dans un second temps le remplacement du suffrage XYZ par XZY fait augmenter $p_Z$ de $\eta$ (et diminuer $p_Y$ de la même quantité). A priori $\varepsilon$ et $\eta$ pourraient être différents, vu que la répartition des suffrages au moment du changement d’avis de l’électeur de XYZ n’est pas la même dans la nouvelle situation que dans l’ancienne. Mais l’effet combiné des changements d’avis doit être le même dans les deux cas, de sorte qu’en fait $\varepsilon$ et $\eta$ sont nécessairement égaux. On a ainsi montré la chose suivante : l’effet du remplacement d’un suffrage XYZ par un suffrage XZY est le même quand, parmi les autres suffrages, on remplace un ZXY par un ZYX.

On peut montrer de la même façon que plus généralement, l’effet du remplacement d’un suffrage XYZ par un suffrage XZY est le même quand on permute sur un des autres suffrages deux options adjacentes qui ne sont pas collectivement Y et Z (c’est-à-dire qu’une des deux options permutées peut être Y ou Z, mais pas les deux). En répétant plusieurs fois cette opération, on peut considérablement changer la répartition des autres suffrages : la seule contrainte sur le changement de cette répartition est que le nombre des autres suffrages plaçant Y devant Z (ici, quand je dis « devant », cela signifie « devant “tout court” », pas « juste devant ») doit rester le même. Finalement, l’effet du remplacement d’un suffrage XYZ par un suffrage XZY ne dépend que de la proportion de suffrages chez lesquels Y est classée devant Z ; de même, l’effet du remplacement d’un suffrage YXZ par YZX ne dépend que de la proportion de suffrages classant X devant Z, etc.

On peut faire le même raisonnement en permutant non pas les deux dernières options, mais les deux premières options : on obtient alors que l’effet du remplacement d’un suffrage XYZ par un suffrage YXZ ne dépend que de la proportion de suffrages chez lesquels X est classée devant Y ; de même, l’effet du remplacement d’un suffrage XZY par ZXY ne dépend que de la proportion de suffrages classant X devant Z, etc.

Ayant exploré les conséquences du critère de robustesse à la manipulation, voyons maintenant une conséquence du critère d’unanimité : si tous les suffrages classent X en tête, alors X doit être élu avec une probabilité de 100 %. En effet, si tous les suffrages placent X en tête, cela signifie en particulier qu’ils placent tous X devant Y, et donc Y ne doit pas pouvoir être élu, ni Z d’après le même raisonnement, de sorte que c’est nécessairement X qui doit gagner.

Justement, regardons ce que donnent les conséquences du critère de robustesse quand tous les suffrages placent X en tête, c’est-à-dire que les seuls suffrages votés ont été XYZ et XZY. Dans ce cas, d’après le paragraphe précédent, remplacer un suffrage XYZ par XZY n’a aucun effet puisque c’est toujours X qui gagne à 100 % ! Or, de manière générale, nous savons que l’effet du remplacement d’un suffrage XYZ par XZY ne dépend que de la proportion de suffrages où Y est classée devant Z. Comme n’importe quelle proportion de suffrages où Y est classée devant Z peut être atteinte par une situation où tous les suffrages placent X en tête, on en déduit le résultat suivant : remplacer un suffrage XYZ par un suffrage XZY n’a jamais aucun effet ! Évidemment, X ne joue aucun rôle particulier dans ce raisonnement, donc on en déduit que permuter les deux dernières options sur un suffrage n’a jamais aucun effet ; autrement dit : $\boldsymbol{p_X}$, $\boldsymbol{p_Y}$ et $\boldsymbol{p_Z}$ ne dépendent que des options classées en tête par les suffrages.

Vu que seules les options classées en tête comptent, nous allons dorénavant parler de « suffrages pro-X » pour dire « suffrages où X est classée en tête », etc. La question que nous nous posons maintenant est la suivante : quel est l’effet du remplacement d’un suffrage pro-X par un suffrage pro-Y ? On peut imaginer que cela correspond en fait au remplacement d’un suffrage XYZ par un suffrage YXZ, de sorte que d’après ce que nous avons dit précédemment, l’effet que cela a sur $p_X$, $p_Y$ et $p_Z$ ne dépend que de la proportion de suffrages où X est classée devant Y. Mais nous savons aussi, d’après le paragraphe précédent, que cet effet ne dépend que des proportions des suffrages pro-X, pro-Y et pro-Z ! Or, il est possible de passer de n’importe quelle proportion de suffrages à n’importe quelle autre en ne procédant qu’aux deux opérations suivantes :

  • Soit modifier les préférences de chaque suffrage sans jamais changer le classement relatif de X et Y ;
  • Soit modifier les préférences de chaque suffrage sans jamais changer l’option classée en tête.

Au final, puisqu’aucune de ces deux opérations ne modifie l’effet du remplacement d’un suffrage pro-X par un suffrage pro-Y, on en déduit que l’effet du remplacement d’un suffrage pro-X par un suffrage pro-Y ne dépend absolument pas de la répartition des suffrages.

Nous y sommes presque ! Grâce à ce que nous venons d’établir, on a que quand on passe progressivement de 100 % de suffrages pro-X (où, d’après le critère d’unanimité, on a $p_X=\mathord\strut$100 %, $p_Y=\mathord\strut$0 % et $p_Z=\mathord\strut$0 %) à 100 % de suffrages pro-Y (où on a de même $p_X=\mathord\strut$0 %, $p_Y=\mathord\strut$100 % et $p_Z=\mathord\strut$0 %), chaque remplacement d’un suffrage pro-X par un suffrage pro-Y a le même effet ; donc, s’il y a $q_X$ % de suffrages pro-X, (100−$q_X$) % de suffrages pro-Y et 0 % de suffrages pro-Z, on a $p_X=\mathord\strut$$q_X$ %, $p_Y=\mathord\strut$(100−$q_X$) % et $p_Z=\mathord\strut$0 %. Si dans un second temps nous modifions la proportion de suffrages pro-Y et pro-Z, on peut imaginer que cela se fait en remplaçant des suffrages YZX par des suffrages ZYX, ce qui ne change pas $p_X$ comme nous l’avons établi plus haut : ainsi, après ce changement, la probabilité que X soit vainqueur est toujours exactement égale à la proportion $q_X$ de suffrages pro-X. Il en va évidemment de même pour Y et pour Z, donc au final la probabilité pour une option d’être vainqueur est exactement égale au nombre de suffrages classant cette option en tête, ce qui signifie bien que notre méthode est le scrutin stochocratique.

Les recherches continuent

Résumons. La problématique de déterminer la volonté du peuple à partir des préférences individuelles n’a pas de solution évidente a priori, en particulier à cause du fait que les électeurs ont la possibilité de manipuler le scrutin en exprimant une opinion mensongère afin de mieux faire triompher leur camp. Quand il n’y a que 2 options en lice, la méthode de la majorité surmonte cette difficulté et s’impose comme la méthode la plus convenable ; mais dès qu’il y a au moins 3 options, le paradoxe de Condorcet sur l’incohérence des préférences majoritaires empêche l’existence d’une telle méthode “parfaite”. La seule façon d’assurer que tous les électeurs votent sincèrement est le scrutin stochocratique, mais celui-ci peut parfois désigner une vainqueuse manifestement non satisfaisante !

Alors, que faire ? Faut-il préconiser le scrutin stochocratique malgré tout ? Cela ne semblerait vraiment pas raisonnable [16]... Faut-il abandonner la démocratie en raisons de ses paradoxes ? Cela serait tout de même excessif...

Les chercheurs n’ont pas baissé les bras. Ils se sont dits : « il n’existe pas de méthode électorale parfaite ? Eh bien, nous allons chercher une méthode “aussi parfaite que possible”, qui ne satisfasse peut-être pas tous les critères souhaitables mais qui en satisfait malgré tout un grand nombre ! Il n’existe pas de bonne règle générale pour déterminer le vainqueur dans toutes les situations ? Eh bien, nous allons chercher une règle “aussi générale que possible” qui donne un vainqueur incontestable dans la plupart des cas réalistes ! ». C’est sur ces passionnantes problématiques que nous nous pencherons dans la suite de cette série d’articles.

Références

Le lecteur désireux d’aller plus loin pourra consulter les références suivantes. Attention, celles-ci sont de difficulté « piste noire », voire hors piste !

  • Social Choice and the Mathematics of Manipulation, par Alan D. Taylor (2005) ; Cambridge University Press.
  • A geometric proof of Gibbard’s random dictatorship theorem, par John Duggan (1996) ; Ecomonic Theory no. 7, pp. 365−369 ; Springer-Verlag.
  • wiki.electorama.com : Un wiki créé par les membres du groupe de discussion « Election-Methods ».
Post-scriptum :

Je tiens à remercier les nombreuses personnes qui m’ont aidé dans la rédaction de cet article. J’ai grandement apprécié la cordialité des membres du groupe de discussion « Election-Methods » (trop nombreux pour être listés ici) qui m’ont aimablement indiqué des références pertinentes sur le sujet ou m’ont donné leur écho de spécialistes sur mon texte. Les commentaires des relecteurs désignés par Images des Mathématiques, notamment Frédéric Chardard et Jean Lécureux, ont conduit à des améliorations substantielles de l’article. Je remercie également mes parents Benoît et Odile qui m’ont servi de cobayes pour vérifier si le texte était compréhensible par les non-mathématiciens, et mon infographiste de sœur Laurence pour ses conseils avisés qui m’ont permis de mettre au point la carte de l’Allier et le logo !

Notes

[1Et le domaine est toujours bien vivant : ainsi, sur le groupe de discussion électronique « Election-Methods », les chercheurs s’échangent plus de 200 messages par mois !

[2Un « type de suffrage » n’est pas la même chose qu’une « option » : les options sont les possibilités parmi lesquelles il faut choisir, mais l’information que contient un bulletin de vote sera en général plus complexe qu’une seule option... Par exemple, dans le cas de la “méthode B synthétisée en un seul scrutin”, s’il y a 4 options, chaque électeur indique sur son bulletin, d’une part qui il choisit au premier tour, soit 5 possibilités (car il a aussi le droit de voter blanc), puis, pour chacun des 6 seconds tours possibles, qui il choisirait au second tour, soit 3 possibilités à chaque fois : il y a donc 5×3×3×3×3×3×3 = 3 645 types de suffrages possibles.

[3Dans certains scrutins, on peut cependant souhaiter que certains électeurs aient plus de poids que d’autres : par exemple, dans un concours de chant comme Nouvelle Star, on pourrait vouloir faire voter en même temps le public et le jury d’experts, mais en donnant plus de poids à un juré qu’à un spectateur anonyme... En fait, ce genre de situations peut se ramener à celle où tous les électeurs ont le même poids, en disant qu’un électeur “privilégié” (en l’occurrence, un juré) compte pour plusieurs personnes à lui tout seul.

[4Si nous étions en piste noire, nous dirions un peu pompeusement : « la méthode électorale est invariante par l’action de n’importe quelle permutation sur les électeurs ».

[5En piste noire, nous dirions que « nous demandons seulement que la vainqueuse de notre élection soit définie sur un ensemble de comesure nulle dans l’espace des dépouillements » — l’espace des dépouillements étant, s’il y a $k$ types de suffrages possibles, le $(k-1)$-simplexe formé par les $k$-uplets positifs de somme $1$ (chaque entrée d’un tel $k$-uplet correspondant à la proportion de suffrages d’un certain type), muni de la mesure de Lebesgue.

[6On s’est aperçu récemment que plusieurs des découvertes de Condorcet avaient en fait déjà été faites au... XIIIe siècle par le savant majorquin Raymond Lulle, dont le manuscrit Ars eleccionis, écrit en 1299, a été redécouvert en 2001 après sept siècles d’oubli !

[7Par exemple, dans le cas du dilemme des Alliérins de l’introduction, il n’y a jamais de paradoxe de Condorcet, quelle que soit la proportion d’habitants des différentes villes : nous verrons pourquoi dans le deuxième article de cette série.

[8L’idée nouvelle apportée par l’utilitarisme et qui permet de résoudre le paradoxe de Condorcet, c’est qu’une option préférée par la majorité peut ne pas correspondre à la volonté du peuple si la majorité n’est convaincue que de justesse par cette option alors que la minorité la trouve franchement mauvaise

[9En fait, la méthode que Borda proposait était exactement la méthode E.

[10Au pire, si l’électeur n’arrive vraiment pas à se décider, il peut toujours tirer au sort entre les deux manières de départager l’ex-æquo... Comme le nombre d’électeurs est très grand, cela revient en pratique au même que s’il votait un demi suffrage de chaque type.

[11Cette démonstration est sensiblement différente des preuves “classiques” qu’on peut trouver de ce résultat, parce qu’ici nous supposons que la proportion de suffrages de tel ou tel type est un paramètre continu, alors que d’habitude le théorème de Gibbard-Satterthwaite est énoncé pour un nombre fini d’électeurs ; en outre, nos hypothèses de symétrie entre électeurs et entre options sont nettement plus fortes ici que dans le “vrai” théorème de Gibbard-Satterthwaite.

[12Soit environ 180 000 euros d’aujourd’hui.

[13Cette démonstration est inspirée d’un article de John Duggan (cf. références).

[14Notez que par contre, contrairement à la démonstration du théorème de Gibbard-Satterthwaite, on ne peut pas arguer que démontrer le résultat pour 3 options suffit à montrer le cas général, attendu qu’il ne s’agit pas d’arriver à une contradiction mais de prouver qu’il n’y a qu’une seule méthode qui marche.

[15Dans le cas d’un nombre d’options quelconque, ce qu’on dit est que permuter deux options adjacentes ne peut pas faire varier la probabilité de victoire des autres options.

[16Il est à noter cependant que dans la démocratie athénienne, mère de toutes les démocraties, la plupart des magistrats étaient désignés par tirage au sort (comme le sont encore aujourd’hui, à bien moindre échelle, les jurés de cour d’assises), et que les élections étaient même considérées en Grèce antique comme un procédé non démocratique, au motif qu’elles favorisaient les citoyens les plus riches ou les plus célèbres ! Aristote écrivait ainsi dans sa Politique (livre VI, chap. VII) : « la voie du sort pour la désignation des magistrats est une institution démocratique ; le principe de l’élection, au contraire, est oligarchique ».

Partager cet article

Pour citer cet article :

Rémi Peyre — «La démocratie, objet d’étude mathématique» — Images des Mathématiques, CNRS, 2012

Crédits image :

Image à la une - Réalisation personnelle
L’Allier - Réalisation personnelle
La majorité a toujours raison ! - Philippe Geluck, Le Chat, éd. Casterman, 1986
Nicolas de Condorcet - Domaine public
Mark Satterthwaite - Evanston Photographic Studios Inc.
Allan Gibbard - Photographie aimablement fournie par le sujet
Kenneth Arrow - Linda A. Cicero / Stanford News Service
Représentation des préférences binaires entre X, Y et Z - Réalisation personnelle

Commentaire sur l'article

  • La démocratie, objet d’étude mathématique

    le 16 avril 2012 à 10:14, par Jonas Kahn

    Une petite remarque sur le fait d’écrire un bulletin de vote « robuste », avec juste des préférences plutôt que des valeurs.

    Une vertu qui n’en est pas mise en lumière est que les gens ne sont pas tous des machines identiques avec juste des préférences différentes. Ils pourront marquer leurs préferences différemment, quand bien même elles sont aussi fortes, s’ils ont des valeurs. Tandis que l’ordre (ou l’ordre des valeurs) est assez indépendant du « type » de la personne.

    Répondre à ce message
    • La démocratie, objet d’étude mathématique

      le 20 avril 2012 à 23:53, par Rémi Peyre

      Remarque très juste ; merci Jonas !

      Répondre à ce message
  • Théorème du référendum

    le 20 avril 2012 à 14:18, par xavier brochard

    Il me semble que le théorème du réferendum ne tient pas compte de deux autres choix possibles. C’est à dire qu’un référendum ne se limite pas à deux choix, mais quatre :
    on peut voter blanc et on peut s’abstenir.

    Choix qui me semblent tout à fait légitimes si on estime qu’aucun des choix proposé n’est satisfaisant. Comment alors tient-on compte de ces choix ?

    Peut-être que je me trompe, et que dans un référendum cette situation ne peut se produire ?

    Répondre à ce message
    • Théorème du référendum

      le 21 avril 2012 à 00:16, par Rémi Peyre

      Bonjour Xavier,

      En fait, j’avais précisé dans la section Cadre de cet article qu’on faisait l’hypothèse que « tous les électeurs votent, et [qu’]il n’y a pas de bulletin nul ». C’est une hypothèse idéale destinée à simplifier la présentation, et c’est dans ce cadre que le “théorème du référendum” était énoncé.

      Dans les vraies élections, il y a en fait toujours des abstentionnistes et des bulletins blancs ou nuls, mais on compte généralement les votes par rapport aux suffrages exprimés, ce qui ramène à la situation que j’ai décrite.

      Ne pas prendre en compte les bulletins blancs est souvent critiqué dans le monde politique. Du strict point de vue de la prise de décision, c’est pourtant assez logique : puisque de toutes façons il faut choisir une option parmi celles proposées, cela n’aide pas à se décider que de savoir que certains électeurs n’approuvent aucune des options proposées ! Après, la question de savoir si une élection doit uniquement servir à prendre une décision ou si elle est aussi destinée à connaître l’avis des gens est une question légitime, mais je n’ai pas voulu l’aborder dans mon article, où je me suis limité à la fonction décisionnelle.

      Maintenant, on peut aussi imaginer des solutions dans lesquelles le bulletin blanc a un véritable effet. Par exemple, pour une élection présidentielle, on pourrait imaginer la règle suivante : « s’il y a plus de 50 % de bulletins blancs, l’élection est annulée et le Congrès désigne un président parmi les non-candidats ». Dans un tel cas, le bulletin “blanc” n’est plus vraiment blanc puisqu’il revient à soutenir une certaine décision.

      Ainsi, pour en revenir à votre question, s’il est organisé un référendum pour la question « faut-il augmenter ou diminuer les impôts ? » et que les règles du scrutin prévoient qu’en cas de majorité de bulletins blancs les impôts resteront constants, le bulletin “blanc” est dans ce cas une véritable troisième option, et le théorème du référendum ne s’applique donc effectivement pas puisque le choix se fait entre plus de deux options !

      Répondre à ce message
  • La démocratie, objet d’étude mathématique

    le 20 avril 2012 à 18:54, par Jérôme Germoni

    Le site Vote au pluriel propose une expérimentation « grandeur nature » de plusieurs modes de scrutin à l’occasion de la présidentielle de 2012.

    Répondre à ce message
    • La démocratie, objet d’étude mathématique

      le 6 mai 2012 à 21:25, par Rémi Peyre

      Merci pour ce super lien ! J’encourage tous les lecteurs à participer à l’expérience pour faire avancer la recherche sur l’impact effectif des systèmes de vote : c’est peut-être grâce à de telles expérimentations que nous arriverons un jour à une démocratie de meilleure qualité qui reflètera plus fidèlement la volonté du peuple...!

      Répondre à ce message
  • La démocratie, objet d’étude mathématique

    le 30 avril 2012 à 10:48, par Christophe Boilley

    Bonjour et merci pour cet article très intéressant. J’ai un peu de mal à saisir la fin de la démonstration du théorème de Gibbard et Satterthwaite. En effet, les frontières des différentes zones de détermination de la méthode sont traitées comme des sous-variétés (transverses) or je n’ai pas vu d’argument topologique justifiant cette hypothèse. Rien n’interdit a priori que les différentes zones soient totalement disconnexes au voisinage de la diagonale, voire avec une frontière dense.

    Or le paradoxe de Condorcet permet de démontrer beaucoup plus facilement un résultat qui me semble plus général : si les suffrages sont des classements totalement ordonnés d’options et s’il y a au moins trois options, il n’existe pas de méthode démocratique robuste au sens de l’article qui aboutisse à la première option du classement majoritaire lorsqu’il existe.

    En effet, dès lors que trois classements cycliques (notés XYZ, YZX et ZXY) ont des probabilités strictement comprises entre 1/4 et 1/2, n’importe quel choix d’option (par exemple X) peut être amélioré par les électeurs les plus mécontents (en remplaçant leur suffrage YZX par ZXY, ce qui aboutit à l’élection de Z.)

    Par ailleurs, l’affirmation selon laquelle un scrutin à plusieurs tours est équivalent à un scrutin à un tour ne me semble pas facilement compatible avec l’hypothèse finitiste et le fait que les résultats dépendent de proportions continues.

    Répondre à ce message
    • La démocratie, objet d’étude mathématique

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

      Bonjour Christophe,

      Votre remarque sur le traitement injustifié des frontières comme des sous-variétés est tout-à-fait juste. Il s’agit en fait d’un choix de rédaction délibéré : j’avais opté pour cette preuve-ci car j’en trouvais l’idée générale particulièrement élégante, mais parler de la question de la régularité des frontières aurait requis un long développement peu éclairant alors que seuls les spécialistes verraient le problème ;-)

      Cela étant dit, il y a plusieurs options pour compléter la preuve, la plus simple étant... d’imposer la régularité des frontières dans la définition de ce qu’est une méthode électorale :-P On peut aussi commencer par montrer que les différentes zones de détermination sont nécessairement convexes, ou encore revenir à la nature discrète du véritable problème et donner la démonstration dans ce cadre-là (car à vrai dire, la rédaction que j’ai suivie ne définit pas rigoureusement ce qu’on entend par « possibilité de manipulation » dans le cadre continu). Enfin, la solution la plus confortable est sans doute de prendre comme démonstration de remplacement la preuve du théorème de Gibbard (qui emprunte un chemin différent), puisque le théorème de Gibbard–Satterthwaite n’en est qu’un cas particulier :-)

      Concernant votre argument fondé sur le paradoxe de Condorcet, il est effectivement très élégant, mais il requiert un lemme intermédiaire, à savoir qu’une option classée en tête par la majorité des électeurs doit nécessairement être gagnante. Or ce lemme n’est pas trivial... (d’ailleurs, j’avais écrit dans un premier temps une démonstration fondée sur cet argument, avant de l’abandonner car elle était trop compliquée !). Une autre objection moins grave est que la manipulation que vous suggérez est une manipulation collective, où de nombreux électeurs modifient leur suffrage en même temps, alors que les hypothèses du théorème tel que je l’ai écrit définissent le concept de manipulation à partir de la modification du suffrage d’un seul électeur — mais en fait, il est aisé de montrer que les deux définitions de la manipulabilité sont équivalentes.

      Je suis en revanche moins convaincu par votre objection sur les scrutins à plusieurs tours : la note [2] de l’article me semble déjà répondre en grande partie à cette question...

      Répondre à ce message
  • La démocratie, objet d’étude mathématique

    le 4 mai 2012 à 17:39, par g philip

    « Une démocratie est un régime politique dans lequel les décisions sont prises en fonction de la volonté du peuple ».

    Bonjour,
    Je pense plutot qu’une democratie est un regime dans lequel les decisions sont prises par le peuple.

    L’election ne devrait pas en etre le trait fondamental mais plutot le tirage au sort, ce qui laisse encore pas mal de grain a moudre pour les mathematiciens !

    Répondre à ce message
    • La démocratie, objet d’étude mathématique

      le 6 mai 2012 à 18:11, par Rémi Peyre

      Bonjour,

      Votre pensée se rapproche donc de celle d’Aristote (cf. la note [16] de l’article)... Pour ma part, je préfère ne pas prendre position sur la « bonne » définition de la démocratie. Disons que mon objectif se limitait à l’étude de la problématique des élections, et que celle-ci est généralement admise comme la marque de la démocratie. Après, « démocratie » n’est peut-être pas le mot juste, mais vu que le but de l’article est d’abord de parler de mathématiques, je botte en touche en arguant que ce n’est qu’un choix lexical arbitraire limité à ce texte ! :-)

      Répondre à ce message
  • La démocratie, objet d’étude mathématique

    le 15 mai 2012 à 11:59, par Hadrien

    Bonjour,

    Un scrutin stochocratique proche de celui présenté dans l’article, c’est-à-dire avec un vote précédant le tirage au sort, dont la probabilité d’obtenir une option quelconque serait pondérée proportionnellement au poids des suffrages accordés à cette option par le vote perd certainement un peu de la « resistance à la manipulation » que proposait le systeme stochocratique sans pondération, mais permet-il de compliquer assez les enjeux du vote en dissuadant l’électeur de se lancer dans des spéculations ardues, n’est-il pas un bon compromis entre la limitation du risque de choix stratégique et la limitation des chances de faire triompher une proposition majoritairement impopulaire ?

    Cette question rejoint une interrogation plus générale : Si d’une manière ou d’une autre, on parvient à masquer le fonctionnement interne d’un mode de scrutin aux votants, ou si on le complexifie assez pour que sa logique propre ne soit pas comprise par les votants (en supposant qu’il reste suffisamment simple dans la pratique du vote elle-même, et donc que cette complexité apparaissent plutôt dans les influences que peux avoir tel ou tel choix, la complexité occultant alors les effets pervers du vote, empêchant une utilisation biaisée de celui-ci.), atteint-on alors aussi une forme de « resistance à la manipulation » ?

    Le système stochocratique tel que vous le décrivez dans cet article dépend-il de ce cas général (le tirage au sort entraînant une ignorance des électeurs quand à la décision qui sera finalement choisie, et donc une forme d’incompréhension du fonctionnement du scrutin) ?

    Répondre à ce message
    • La démocratie, objet d’étude mathématique

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

      Bonjour Hadrien,

      Tout d’abord, merci pour vos questions que je trouve très judicieuses.

      Il me semble effectivement qu’un manque d’information (ignorance ou mauvaise compréhension) sur le fonctionnement interne du scrutin aurait pour effet d’inciter les électeurs à voter plus sincèrement, encore que je n’aie pas de référence précise sur le sujet. Cela dit, je crois qu’il y aurait un contrepoint très grave, qui est que les citoyens perdraient confiance en les institutions démocratiques s’ils n’avaient pas la conviction que les décisions prises par le système sont bien le reflet de leur vote !

      Le scrutin stochocratique n’entre pas dans ce cadre, car il est au contraire totalement transparent (du moins si les citoyens ont confiance en l’équité du tirage au sort). Cette méthode fait bien apparaître une forme d’ignorance, mais ce n’est pas cette ignorance qui rend le système robuste à la manipulation : au contraire, l’électeur sait que, quel que soit le bulletin tiré, il a toujours intérêt à voter sincèrement ! Une autre façon de le comprendre est de penser au scrutin stochocratique comme une « dictature aléatoire » : ce qui le rend robuste à la manipulation, ce n’est pas son aspect aléatoire (qui ne sert qu’à assurer l’équité entre les citoyens), mais uniquement son caractère dictatorial !

      Quant à la possibilité de déformer le scrutin stochocratique par une forme de pondération, je crois que même une faible pondération aurait un effet majeur : en effet, dès lors que les citoyens savent que leur vote a plus de chances d’être pris en compte s’ils votent pour une option plus prisée par les autres électeurs, il choisiront plus volontiers les options les plus populaires, ce qui accroîtra les différences d’intentions de vote entre les options, rendant encore plus intéressant de voter stratégique, etc. Par ailleurs, les options généralement considérées comme « intolérables » (extrêmistes) peuvent être partagées par une minorité relativement large (37 % pour le parti nazi en 1932 — désolé pour le point Goodwin...) : il n’est donc pas clair qu’une pondération changerait quoi que ce soit de ce côté-là !

      Enfin, il y a une grande question derrière tout cela sur laquelle un ami philosophe (merci Géhel) a attiré mon attention récemment : la manipulation n’est pas forcément dommageable en tant que telle : ce sont plutôt ses conséquence indirectes, comme la candidature unique d’un seul candidat par parti, la difficulté pour un « petit » candidat d’attirer les suffrages sur son nom, la difficulté d’interpréter les résultats, etc., qui font qu’il est préférable qu’un système ne soit pas manipulable ! Mais à partir du moment où on suppose que les citoyens sont suffisamment intelligents pour exploiter de manière également optimale les possibilités de manipulation qui leur sont offertes, il vaut certainement mieux un système qui reflète la volonté du peuple, même si celle-ci ne s’exprime alors qu’indirectement à travers les bulletins de vote (ceux-ci tenant alors compte non seulement de la préférence personnelle des électeurs mais aussi des calculs stratégiques qu’ils font), qu’un système aléatoire ou opaque.

      Répondre à ce message
      • La démocratie, objet d’étude mathématique

        le 20 mai 2012 à 13:45, par Hadrien

        Merci beaucoup pour cet excellent article et pour votre disponibilité vis-à-vis des lecteurs, merci de votre réponse !

        Répondre à ce message
  • Jugement Majoritaire

    le 28 octobre 2013 à 19:21, par Vitchy

    Vous indiquez « Compte tenu que, comme nous venons de le voir, les méthodes de notation sont facilement vulnérables à la manipulation ». Il semble cependant que votre « démonstration » ne repose que sur l’opérateur « moyenne ». N’est-ce pas un peu léger pour en déduire que toutes les méthodes de notation seraient facilement vulnérables à la manipulation ?
    Entre autres, que pensez-vous de l’opérateur « médiane » utilisé par exemple par balinski et laraki ?

    • https://1984f707-a-62cb3a1a-s-sites.googlegroups.com/site/ridalaraki/xfiles/PourLascience2012.pdf?attachauth=ANoY7cr_T8-YrdyH6jo4iSOTb9yaXheWFI6XNi1kf8eiWRI04bB-ErDgbQdVApNI4ungUx1U1IHsehR9xylxLbKZmjTCg5w-fPVLBr9yzhIYqR8XF2MYL485IHdYfb5DdxmSI4ULpixVw6ele33fJyacfCQNu1earOZz4IdVInO5yp5lR13pPc85Cw7mYW9CxmQBeLuzpmNSmUfHK5qIjtZd9UhaSnDss5Jd7eRc592amo-y7Jgsb3M%3D&attredirects=1
    • http://www.college-de-france.fr/site/pierre-rosanvallon/seminar-2012-02-29-10h00.htm#|q=../pierre-rosanvallon/seminar-2011-2012.htm|p=../pierre-rosanvallon/seminar-2012-02-29-10h00.htm|
    • ou https://mitpress.mit.edu/books/majority-judgment
    Répondre à ce message
    • Jugement Majoritaire

      le 31 octobre 2013 à 10:00, par Rémi Peyre

      Bonjour Vitchy,

      Votre remarque est tout-à-fait juste, et fait d’ailleurs l’objet d’une section dans le troisième article de cette série sur les mathématiques de la démocratie. J’avais ici forcé le trait pour des raisons pédagogiques...

      Répondre à ce message
  • La démocratie, objet d’étude mathématique

    le 14 mai 2014 à 13:45, par Sergejack

    Est-ce que vous pourriez me donner votre avis sur le système que je présente dans l’article suivant : http://www.les-mathematiques.net/phorum/read.php?15,935641

    Je ne suis pas mathématicien mais il me semble que cette méthode est robuste à la manipulation et devrait amener à des scrutins honnêtes.

    Répondre à ce message
    • La démocratie, objet d’étude mathématique

      le 14 mai 2014 à 18:44, par Rémi Peyre

      Bonjour Sergejack,

      J’ai répondu à votre question via les commentaires de votre article sur le forum du site “les-mathematiques.net”.

      Si vous avez des questions supplémentaires, vous pouvez me contacter par le biais de ma fiche sur Images des Mathématiques. (je compte sur vous pour vous auto-modérer ! ;-)).

      Bien cordialement,

      Répondre à ce message
  • La démocratie, objet d’étude mathématique

    le 15 mai 2014 à 11:44, par Sergejack

    Merci pour votre fantastique réponse (car j’ai tout compris ^^).

    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é ?

Dossiers

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

Suivre IDM