On a régulièrement l’impression que chaque système électoral a ses aberrations. On a souvent vu le système parlementaire élire un gouvernement majoritaire, alors que le parti au gouvernement n’a pas remporté 50% du vote populaire. Le système à deux tours peut aussi forcer à un vote stratégique dès le premier tour si l’on veut se retrouver avec un choix « acceptable » au second tour. Dans un système proportionnel à la pluralité des voix, on pourrait voir élu un candidat avec une très faible majorité, alors que le deuxième sur la liste serait le premier ou deuxième choix de la majorité des électeurs. Les mathématiques peuvent-elles nous aider à concevoir un système de vote qui reflète la volonté des électeurs?
Un système de vote idéal
On pourrait imaginer que dans un système de vote idéal, chaque électeur donne la liste ordonnée de ses préférences parmi les candidats.
Prenons un exemple à cinq candidats, que chaque électeur ordonne sur son bulletin de vote. Le premier reçoit 4 points, le deuxième, 3 points, le troisième, 2 points, le quatrième, 1 point, et le cinquième, aucun point. C’est la méthode de Borda. Le premier tableau à gauche est un exemple de profil (ou ensemble des préférences des électeurs), où la notation \(A \succ B\) signifie « A est préféré à B ». Le second tableau présente la compilation de ces votes.
D’où le choix social
\[ A \succ E \succ C \succ D \succ B.\]
Supposons maintenant que C se retire du vote. Il ne reste que quatre candidats. Le premier reçoit 3 points, le deuxième, 2 points, le troisième, 1 point, et le quatrième, aucun point. La nouvelle compilation est donnée dans le troisième tableau et le nouveau choix social est
\[E \succ A \succ D \succ B.\]
Que s’est-il passé ? L’ordre social relatif de A et E a changé lors du retrait de C, alors que les électeurs n’ont pas changé leur ordre relatif de A et E. La méthode de vote a donc une aberration. Cette aberration porte un nom:
La méthode Borda ne respecte pas l’indépendance des alternatives non pertinentes.
Le mathématicien Condorcet a proposé comme parade le système suivant: pour qu’un candidat gagne, il doit gagner en duel contre chaque autre candidat. En effet, un vainqueur de Condorcet est vraiment un vainqueur hors de tout doute. Mais existe-t-il toujours? Regardons le profil à droite et la compilation pour les trois duels A et B, B et C et A et C (trois tableaux suivants).
Le premier tableau de duel indique que A est vainqueur du duel A – B.
Le second tableau de duel indique que B est vainqueur du duel B – C.
Le troisième tableau de duel indique que C est vainqueur du duel A – C.
Donc, le choix social donne:
\[A \succ B \succ C \succ A.\]
La méthode de Condorcet ne respecte pas la transitivité.
On voit qu’il n’est pas si facile de construire un système électoral qui n’ait pas d’aberrations! On va procéder autrement. On va se donner un système d’axiomes auxquels doit obéir un système électoral démocratique, c’est-à- dire qui respecte la volonté populaire. Pour cela, comme pour la méthode Borda, on va demander à chaque électeur de donner sa liste ordonnée des candidats. Le système électoral doit déduire de ce profil (soit l’ensemble des choix ordonnés des électeurs) le choix social. Le premier axiome est l’axiome d’unanimité:
Axiome 1 (unanimité):
Si chaque électeur préfère A à B, alors le choix social doit placer A avant B.
Les deux autres axiomes sont ceux qu’on a déjà rencontrés:
Axiome 2 (transitivité):
Si le choix social donne \(A \succ B\) et \(B \succ C,\) alors il doit donner \(A \succ C.\)
Axiome 3 (indépendance des alternatives non pertinentes):
Si les électeurs changent leur ordre des candidats sans changer l’ordre relatif de A et B, alors l’ordre de A et B dans le nouveau choix social, doit être le même que dans le choix social initial.
Les propriétés troublantes de la dictature.
Lorsqu’il existe un électeur X tel que le choix social est toujours le choix de l’électeur X, on dit que cet électeur est un dictateur, puisqu’il impose ses choix. On peut montrer que la dictature obéit aux trois axiomes (voir section problèmes).
Le célèbre théorème d’Arrow (1951) affirme avec fracas que la dictature est le seul système de vote qui satisfait aux trois axiomes! L’encadré à la fin de cet article donne les grandes idées de la preuve.
Kenneth Joseph Arrow (1921-2017)
Kenneth Arrow est né à New-York de parents roumains d’origine juive et a fait la plus grande partie de sa carrière aux États-Unis. On le présente comme un économiste mais, signe de l’importance des sciences mathématiques en économie dont la statistique et la recherche opérationnelle, 69 de ses publications sont référencées en sciences mathématiques.
Son célèbre théorème d’impossibilité date de sa thèse en 1951. Et l’ensemble de ses travaux sera récompensé par le prix Nobel d’économie en 1972. Fait absolument remarquable: quatre de ses étudiants recevront aussi le prix Nobel d’économie et tous ont des publications référencées en sciences mathématiques. Il s’agit de John Harsanyi (1994), Michael Spence (2001), Eric Maskin et Roger Myerson (2007).
Ceci signifie qu’un système de vote idéal n’existe pas. Il y aura toujours des aberrations. On peut seulement espérer qu’il y en ait le moins possible. Le mathématicien américain, Donald Saari, a longtemps médité sur la question. Examinons un exemple qu’il a donné.
L’exemple de Saari
Le tableau Profil de Saari présente un profil de population dans une élection avec cinq candidats.
On va regarder cinq systèmes de vote qui peuvent, chacun, sembler légitimes, et montrer que les vainqueurs identifiés par ces cinq systèmes sont tous différents.
Le premier système de vote qui ne considère que les premiers choix est celui de la pluralité des voix. C’est A qui est vainqueur car il a plus de premiers choix (soit six) que les autres candidats.
Dans le deuxième système de vote, on compte les premiers et deuxièmes choix. C’est B qui est ici vainqueur avec dix premiers et deuxièmes choix.
Dans le troisième système de vote, on compte les premiers, deuxièmes et troisièmes choix. C’est C qui gagne ici avec 13 premiers, deuxièmes et troisièmes choix.
Dans le quatrième système de vote on compte les premiers, deuxièmes, troisièmes ou quatrièmes choix. C’est D qui est ici vainqueur avec 16 premiers, deuxièmes, troisièmes ou quatrièmes choix. Remarquez qu’avec cinq candidats ce système de vote revient à demander aux électeurs quel est le candidat dont ils ne veulent pas. Et dans notre exemple, aucun électeur ne place D en cinquième position.
Finalement, le cinquième système de vote est la méthode Borda qui donne E vainqueur avec 34 points.
Donald Saari montre qu’on peut généraliser cet exemple à N candidats et trouver un profil pour lequel chaque candidat a un système de vote qui le déclare premier. Bien sûr cette propriété n’est pas vraie pour TOUT profil de votes, mais seulement pour un sous-ensemble de profils.
Dites moi quel parti vous voulez voir gagner aux élections et je vous dessinerai le système de vote en conséquence.
Le découpage de la carte électorale
Un autre système électoral important est le système parlementaire. Ce système est utilisé dans beaucoup de pays anglo-saxons ou encore lors d’élections législatives. Au Canada, le pays est divisé en circonscriptions électorales. Les électeurs votent pour élire le député de leur circonscription. Le parti qui gouverne est (sauf exception) celui qui a le plus de députés. Ce système a ses aberrations: un parti peut avoir la majorité au parlement sans avoir, ni la majorité des votes (soit 50 % des votes), ni même la pluralité des votes (soit plus de votes que les autres partis). Dans un tel système le découpage de la carte électorale est alors très important.
Faire un découpage électoral partisan pour favoriser un parti s’appelle le Gerrymandering. En 1811, juste avant l’élection présidentielle, Elbridge Gerry, alors gouverneur du Massachusetts, fut accusé d’avoir redécoupé une circonscription pour favoriser son parti. La circonscription avait une forme tellement bizarre évoquant vaguement une salamandre que cela a éveillé les soupçons: on a accusé le gouverneur Gerry d’avoir annexé à la circonscription des régions favorables à son parti et, pour garder le même nombre d’électeurs, d’en avoir enlevé d’autres qui lui étaient défavorables. Le nom gerrymandering, qui vient de la contraction de Gerry avec salamander, est utilisé aujourd’hui pour désigner un découpage électoral partisan, pensé pour favoriser un parti.
Jusqu’où peut-on tricher dans le découpage de la carte électorale sans éveiller les soupçons?
Nous allons nous pencher sur le cas de deux partis, comme c’est le cas par exemple aux États-Unis. Il y a deux manières de tricher:
- Si on veut favoriser le parti qui a peu d’intentions de votes, alors on s’arrange pour découper des circonscriptions où le parti majoritaire gagne par une très large majorité. Il gaspille alors ses votes. On découpe aussi des circonscriptions où le parti minoritaire gagne par quelques voix seulement.
- Si on veut favoriser le parti majoritaire, on privilégie un découpage dans lequel il gagne beaucoup de circonscriptions par une petite majorité.
Regardons les deux cartes électorales pour les mêmes électeurs, le parti Bleu ayant 63,6% du vote.
Dans la première, le parti Bleu rafle tous les comtés. Dans la deuxième, le parti Rouge est majoritaire avec seulement 36,4% des votes.
Des mathématiciens se sont penchés sur la manière de favoriser le parti majoritaire.
Il est possible de faire gagner le parti majoritaire dans toutes les circonscriptions tout en découpant des circonscriptions en forme de polygones convexes!
Pour expliquer ce résultat, on va faire l’hypothèse qu’on divise les électeurs en circonscriptions contenant chacune exactement b sympathisants du parti Bleu et r sympathisants du parti Rouge. (Donc, \(N = n(b + r).)\) On posera aussi la petite hypothèse technique que trois électeurs ne sont jamais alignés.
Prenons le cas \(n = 2.\) Il suffit de trouver une droite qui sépare le territoire en deux régions contenant chacune la moitié des sympathisants de chaque parti. ll s’agit en fait d’une application du théorème du sandwich au jambon1.
En effet, prenons une droite orientée quelconque (la droite horizontale sur la figure) et déplaçons-là parallèlement à elle-même jusqu’à ce qu’il y ait la moitié des sympathisants du parti Rouge de chaque côté. S’il y a un nombre inégal de sympathisants du parti Bleu de chaque côté, elle ne convient pas. Tournons-là continûment tout en la déplaçant pour qu’à presque chaque instant (sauf quand elle passe par deux électeurs) il y ait la moitié des sympathisants du parti Rouge de chaque côté. Lorsqu’on aura fait un demi-tour, on sera revenu à la droite initiale mais on aura échangé son côté droit avec son côté gauche. Du côté droit où il y avait moins de sympathisants du parti Bleu, il y en maintenant plus. Donc, entre les deux situations on est passé par une situation où on avait un nombre égal de sympathisants du parti Bleu de chaque côté. (Bien sûr, on a un peu triché car la droite ayant une direction donnée n’est pas unique, mais la grande idée est là.)
On a maintenant tous les ingrédients pour traiter le cas où le nombre de circonscriptions est une puissance de \(2: n = 2^m\). On itère simplement le processus: on divise la région en deux domaines, puis chaque domaine en deux sous-domaines, etc.
Si maintenant \(n = 2^ms\) où \(s\) est impair, on commence par diviser la région en 2 domaines, puis chaque domaine en 2 sous-domaines, etc., jusqu’à se ramener à devoir diviser des sous-domaines en \(s\) circonscriptions contenant chacune exactement b sympathisants du parti Bleu et \(r\) sympathisants du parti Rouge.
Ici il n’est pas toujours possible d’utiliser des droites pour diviser le domaine. Dans la configuration ci-contre des électeurs, il n’existe aucune droite divisant le plan en deux demi-plans contenant chacun trois fois plus de sympathisants du parti Bleu que de sympathisants du parti Rouge. Mais on peut diviser ce domaine en trois sous-domaines contenant chacun le tiers des sympathisants de chaque parti.
Le cas général
Il a été traité par trois mathématiciens professeurs à l’époque au département d’informatique de l’Université de la Colombie-Britannique: Sergei Bespamyatnikh, David Kirkpatrick et Jack Snoeyink. Sous des petites hypothèses techniques, ils ont montré que
– soit on peut, par une variante du théorème du sandwich au jambon, faire une 2-partition de la région, c’est-à-dire une partition en deux demi-plans, le premier contenant \(n_1b\) sympathisants du parti Bleu et \(n_1r\) sympathisants du parti Rouge, et le second contenant \(n_2b\) sympathisants du parti Bleu et \(n_2r\) sympathisants du parti Rouge, où \(n_1 + n_2 = n;\)
– ou encore on peut faire, comme dans la figure ci-contre, une 3-partition convexe de la région, donnée par trois demi-droites concurrentes dont une verticale, où chacune des régions contient une proportion égale de sympathisants du parti Bleu et de sympathisants du parti Rouge. On a donc \(n_1 +n_2 +n_3=n.\)
On itère ensuite la construction sur chacun des sous-domaines. L’encadré donne quelques détails sur la construction de la 3-partition.
Construire une 3-partition
On fait l’hypothèse que deux électeurs ne sont jamais alignés verticalement. Sinon, on commence par faire une rotation de la carte.
En chaque point P du plan, on peut construire une 3-partition pour les sympathisants du parti Rouge, et une autre pour ceux du parti Bleu.
On cherche un point P en lequel les deux 3-partitions coïncident et donnent des régions convexes. Les 3-partitions sont de quatre types donnés ci-dessous. Les droites verticales et les droites joignant deux électeurs divisent le plan en régions dans lesquelles le type des 3-partitions associées à P est constant. On aura gagné si on montre qu’on a une frontière entre deux régions de types respectifs 1 et 3, ou encore de types respectifs 2 et 4. Sous l’hypothèse qu’une 2-partition n’existe pas, Sergei Bespamyatnikh, David Kirkpatrick et Jack Snoeyink montrent qu’une telle frontière existe toujours, mais les détails sont un peu techniques.
Préserver l’équité du système démocratique
Peut-on encore organiser des élections équitables dans un régime démocratique? Bien sûr, au vu du théorème d’Arrow, il va falloir laisser tomber un axiome. Donald Saari dans son livre « Chaotic elections » fait une analyse exhaustive de la question. Il montre que des systèmes de vote comme voter pour le nombre de candidats de votre choix, ou encore partager un total de 10 points entre les candidats permettent de manipuler significativement le vote.
Il montre aussi que, dans beaucoup de systèmes de vote, un très petit changement dans les votes de quelques électeurs peut avoir un effet très grand sur le résultat du vote, d’où le terme d’élections chaotiques.
Il conclut que la méthode Borda est celle qui a le moins d’effets pervers et qui constitue le meilleur compromis. Mais, elle reste un compromis…
Les grandes idées de la preuve du théorème d’Arrow
Considérons un système de vote satisfaisant aux axiomes 1, 2, et 3, et montrons que c’est une dictature. Dans un premier temps, il faut identifier le dictateur X. Ensuite, il faut montrer que cet électeur est bien un dictateur. La preuve utilise des petits jeux où les électeurs changent leur vote plusieurs fois: on suit alors l’évolution du choix social.
Étape 1: identifier le dictateur
Prenons un candidat B, et ordonnons les électeurs, premier électeur, deuxième électeur, etc. .
Si tous les électeurs mettent B en bas de leur liste de préférence, alors B sera en bas du choix social par l’axiome 1 (unanimité).
Si tous les électeurs mettent B en haut de leur liste de préférence, alors B sera en haut du choix social par l’axiome 1.
Si tous les électeurs mettent B, soit en bas, soit en haut de leur liste de préférence, alors B sera, soit en bas, soit en haut du choix social. Cette affirmation est absolument contre-intuitive. Pourtant, elle découle des trois axiomes. Au départ, chacun met B en bas de sa liste de préférence. Un à un, les électeurs modifient leur liste en déplaçant B du bas de leur liste au haut de leur liste, sans changer leurs autres choix. Il existe un premier électeur X pour lequel B va basculer du bas de la liste du choix social vers une position supérieure. Sans surprise, cet électeur X sera notre dictateur.
Mais, il reste du travail pour le montrer. Appelons profil 1, l’ensemble des bulletins de vote, alors que X plaçait B en bas, et profil 2, l’ensemble des bulletins de vote, quand X a déplacé B en haut de son bulletin de vote.
Nous affirmons que lorsque X déplace B du bas vers le haut de sa liste, alors B bascule au haut de la liste du choix social.
Supposons que dans le choix social B ait basculé quelque part au milieu. Alors, il existe des candidats A et C tels que dans le nouveau choix social on ait \(A \succ B\) et \(B \succ C.\) Dérivons une contradiction.
Rappelons que tous les électeurs placent B en bas ou en haut de leur liste. Maintenant, dans le profil 1, permettons que tous les électeurs changent leur bulletin de vote en mettant C au-dessus de A, mais en gardant B à la même place en bas ou en haut: ceci donne le nouveau profil 3. Les nouveaux bulletins ont le même ordre relatif pour A et B que le profil 1, puisque B est toujours en bas ou en haut. Le profil 1 donnait un choix social avec B en bas. Donc,
\[A \succ B\]
pour le choix social du profil 3, par l’axiome 3 (indépendance des alternatives non pertinentes). De même, les nouveaux bulletins ont le même ordre relatif pour B et C que le profil 2, toujours puisque B est toujours en bas ou en haut. Le profil 2 donnait un choix social avec C en dessous de B. Donc,
\[B \succ C\]
pour le choix social du profil 3, par l’axiome 3.
Par l’axiome 2 (transitivité), le choix social du profil 3 montrera
\[A \succ C\]
Mais, tous les électeurs ont placé C au-dessus de A. Donc, par l’axiome 1, le choix social doit donner
\[C \succ A\]
et nous obtenons notre contradiction.
Remarquons qu’on a absolument eu besoin des trois axiomes pour dériver le résultat contre-intuitif que, lorsque X a déplacé B du bas de sa liste au haut de sa liste, alors B a basculé du bas de la liste au haut de la liste dans le choix social. Il en sera de même des autres arguments de la preuve.
Étape 2: l’électeur X est un dictateur pour toute paire de candidats A et C différents de B.
Ceci signifie que l’ordre relatif de A et C dans le choix social est le même que celui de l’électeur X.
Les arguments sont du même type et utilisent encore les trois axiomes.
Étape 3: l’électeur X est un dictateur pour toute paire de candidats D et B.
Ici aussi, les arguments sont du même type et utilisent les trois axiomes.
- Voir Partage équitable, Accromath 12. été-automne 2017. ↩
