{"author":{"id":"boris","title":"Ex-Stagiaire et ambianceur","name":"Boris","excerpt":"Reste souple","cover":"/authors/boris/cover.jpg"},"articles":[{"id":"hello-democracy","title":"Élections, théorie du choix social et Go","author":"Boris","date":"2022-07-08","tags":["dev","golang"],"excerpt":"Let's vote kids!","content":"\nGRRR BAW ici Boris, et aujourd’hui on va parler CÉ-FRAN. Oui ça fait des mois qu’on vous gave avec les élections, mais calmez-vous, ~~ça va bien se passer~~ il ne sera ici question que d’un peu de sciences et d’informatique. Désolé pour le retard, l’article était censé être publié pendant l’entre-deux tours, puis a été repoussé aux législatives, puis à maintenant… mais les croisés tu connais.\n\nDISCLAIMER : Aucune notion d’informatique n’est nécessaire à la compréhension de l’article, il vous suffit donc d’ignorer les solutions en Go si ces dernières ne vous intéressent pas.\n\n## Un peu de théorie du choix social…\n\nHein, c’est un blog de tech ou de socio ?! Pas si vite, on va voir que les deux thématiques peuvent être beaucoup plus proches qu’on ne le pense, et que mêler politique et choix computationnel n’est finalement pas si aberrant.\n\nOn peut définir la **théorie du choix social** comme l’étude du processus menant les préférences individuelles à la préférence collective d’une société. Cette préférence peut être un classement des choix possibles (appelé fonction de _bien-être social_) ou une décision unique (appelée fonction de _choix social_). Attention voyageur fortuit !!! Posons les bases : les votants seront supposés tous égaux et présenteront leur choix sous forme d’ordre total. Si vos cours de maternelle semblent trop lointains, retenez que les ordres totaux permettent de toujours discriminer deux éléments.\n\n## 17\n\nComme le nombre de titres des Boston Celtics, ou encore le nombre de systèmes électoraux existants à travers le monde. Oui, ça en fait un paquet, et oui gaulois, il n’y a pas que le scrutin uninominal majoritaire à deux tours ! Mais que mène un État à choisir un mode de scrutin plutôt qu’un autre ? Comment faire pour séparer les bonnes fonctions de choix social des moins bonnes ? C’est ici qu’on va faire appel à la Dream Team des bonnes propriétés :\n\n - Universalité : l’élection doit toujours aboutir à un résultat, peu importe les candidats et votants\n - Unanimité : si tous les votants préfèrent Jonathan Cohen à Emmanuel Macron, alors Jonathan Cohen doit devenir Président de la République\n - IAND (Indépendance des Alternatives Non-Disponibles) : si les votants préfèrent un candidat à un autre, alors l’entrée d’un nouveau candidat dans la course ne devrait pas altérer cette préférence (ce qui est en principe assez difficile à vérifier)\n - Absence de Dictateur : la règle de choix social n’obéit à aucun individu\n\nIl suffit donc de trouver la méthode capable de satisfaire cet ensemble non ? Pas si vite, car selon le [théorème d’impossibilité d’Arrow](https://www.economie.gouv.fr/facileco/kenneth-arrow) (1951), aucune fonction de choix social n’est en mesure de satisfaire simultanément toutes ces propriétés _cries in democrat._\n\nDésolé de briser vos rêves, mais devons-nous pour autant en conclure que la démocratie n’est qu’une utopie ? Bof, et l’une des méthodes pour contourner ce théorème pourrait être de pondérer l’importance de chaque propriété dans la construction d’une démocratie : respecter la dernière propriété (Absence de Dictateur) serait par exemple une condition _sine qua non_, et si vous n’êtes pas d’accord qu’est-ce que vous foutez à lire un article pareil ??\n\nComme chez Coddity on n’enfile pas des _Perl_, cette petite étude sera servie sur son lit d’implémentations en Go, histoire de rendre tout cela (un peu) sophistiqué et faire semblant de faire du choix social computationnel.\nOn va donc se munir des structures suivantes, qui nous seront utiles pour toutes les méthodes de vote :\n\n```golang\ntype Candidate struct {\n Id int\n Name string\n}\n\ntype Voter struct {\n Id int\n Name string\n Vote ScrutinIndiv\n}\n\ntype Result struct {\n DuelsWon int\n TotalPoints int\n WonAgainst []Candidate\n}\n\ntype ResultPerCandidate struct {\n Cand Candidate\n Res Result\n}\n\ntype Pair struct {\n L Candidate\n R Candidate\n}\n\ntype ScrutinIndiv []Candidate\n```\n\nAinsi, quels sont les avantages et inconvénients des différentes méthodes ? Est-il possible de les comparer ? Pourquoi notre système actuel n'est-il pas optimal ? Ce sont les questions auxquelles nous allons tenter de répondre dans cet article.\n\nAllez, on respire… c’est parti !\n\n## Le scrutin uninominal majoritaire à deux tours 🇫🇷\n\nCette méthode est naturelle pour nous, et certains peuvent voir d’un œil étranger les pays où les élections se déroulent différemment. Elle a certes l’avantage d’être facile à mettre en place, permet un dépouillement très rapide, mais ce chauvinisme est-il justifié ? Spoiler alert : elle présente en réalité de nombreux défauts, le premier étant la manipulabilité, où il peut être profitable à un électeur de mentir sur ses préférences. Supposons que pour les candidats A, B, C, D on ait :\n\n - 20 votants ayant la préférence C > A > D > B\n - 12 votants ayant B > A > C > D\n - 10 votants ayant A > D > B > C\n\nEn l’état, C serait élu. Cependant, si les 12 votants préférant B forment une coalition et décident de voter ensemble pour A, alors ce dernier serait élu, malgré le fait qu’ils préfèrent B. Manipulabilité vous avez dit ?\n\nDe plus, elle permet la dictature de la majorité au travers du _vote utile_, n’incitant donc pas vraiment à la participation (\"Que je vote ou pas, ça ne changera rien\"). Par conséquent, ceci favorise une division bipartite du paysage politique, désavantageant par la même occasion les candidats les moins influents. Enfin, il n’est ici pas possible de vérifier l’IAND, puisqu’au premier tour, on risque d’éliminer un candidat pourtant préféré aux autres (voir _critère de Condorcet_ plus bas).\n\nLorsqu’on voit que l’abstention concerne 1⁄4 des inscrits, on peut se demander si l’élection désigne réellement le candidat que les Français souhaitent en majorité. Bref, arrêtons le massacre, et passons à l’implémentation pour y voir un peu plus clair (ou pas) :\n\n```golang\nfunc TwoRoundSystem(voters []model.Voter, c []model.Candidate) model.ResultList {\n count := make(map[model.Candidate]int)\n\n secondRoundList := make([]model.Candidate, 0)\n // Appel à une fonction de service qui va simuler le scrutin\n // en suivant ses règles\n firstRoundResult := majorityProcedure(voters, c, count)\n\n if len(firstRoundResult) == 1 {\n return firstRoundResult\n } else {\n for i := range firstRoundResult {\n secondRoundList = append(secondRoundList, firstRoundResult[i].Cand)\n // Appel recursif avec les candidats qualifiés au\n // second tour\n finalRes := TwoRoundSystem(voters, secondRoundList)\n return finalRes\n }\n }\n return model.ResultList{}\n}\n\nfunc majorityProcedure(voters []model.Voter, candidates []model.Candidate, res map[model.Candidate]int) model.ResultList {\n resultList := make(model.ResultList, len(res))\n resPair := make(model.ResultList, 0)\n total := 0\n\n for _, v := range voters {\n for i, alternative := range candidates {\n // On parcourt les choix de chaque votant\n if v.Vote.IndexOf(candidates[i]) == alternative.Id {\n res[alternative] += 1\n total++\n }\n }\n }\n for k, v := range res {\n // On affecte à chaque candidat le nombre de voix récoltées\n resultList = append(resultList, model.ResultPerCandidate{\n Cand: k,\n Res: model.Result{\n TotalPoints: v,\n },\n })\n }\n\n sort.Sort(sort.Reverse(resultList))\n // Ballot est une fonction dont le comportement dépend de la méthode\n // choisie (implémentation détaillée sur le repository GitHub)\n resPair, shouldReturn, returnValue := model.Ballot(\"majority\", resultList, total, resPair, candidates)\n if shouldReturn {\n return returnValue\n }\n return resPair\n}\n```\n\n## Le vote par approbation\n\nCe scrutin en deux tours est assez particulier, car permet aux électeurs de voter pour **plusieurs** candidats au premier tour, ce qui règle le problème de dispersion des votes. Mais encore une fois, le vote stratégique reste possible, puisqu’on est naturellement tenté de ne pas voter pour un candidat pouvant potentiellement battre notre champion. De plus, il n'y a pas d'échelle de valeurs entre les votes : un vote en faveur d'un candidat populaire et un vote pour un candidat dont la victoire est peu crédible serait traité de la même façon (ce qui peut être aussi bien positif que négatif, selon le point de vue).\n\nEn 2002, une expérience^[1] a été menée sur 5 bureaux de vote à Orsay, avec un échantillon de 2597 votants. Voici le nombre d’assentiments (nombre de candidats qu’un électeur choisit) par bulletin :\n\n![](./assentiments.png)\n\nVoyons les résultats à partir de jolis graphiques :\n\n![](./majority.png)\n\n![](./approval.png)\n\nOui les candidats passant au deuxième tour sont les mêmes. Cependant, on observe que le vote par approbation apporte un résultat plus serré, avec une qualification au second tour beaucoup moins confortable pour Lionel Jospin et Jacques Chirac. On a par exemple Noël Mamère qui se trouve à seulement 1,8% du second tour, malgré sa sixième place. De plus, si l’on compare les médianes des deux scrutins (pour flex : [test statistique de Mood](https://fr.wikipedia.org/wiki/Test_de_Mood)), on peut parvenir à la conclusion que l’assentiment permet une meilleure distribution des votes, et donc une meilleure considération des souhaits des électeurs.\n\nVoyons ce que ça donne en Go :\n\n```golang\n// La différence avec le vote majoritaire réside ici, dans la fonction Ballot\nfunc Ballot(votingMethod string, resultList ResultList, total int, resPair ResultList, candidates []Candidate) (ResultList, bool, ResultList) {\n for cand := range resultList {\n percentage := (resultList[cand].Res.TotalPoints * 100) / total\n if percentage > 50 {\n resPair = append(resPair, ResultPerCandidate{\n Cand: resultList[0].Cand,\n Res: Result{\n TotalPoints: resultList[0].Res.TotalPoints,\n },\n })\n return nil, true, resPair\n } else {\n for i := 0; i < len(candidates)-1; i++ {\n // Disjonction de cas entre l’approbation et le vote majoritaire\n if votingMethod == \"approval\" {\n resPair = append(resPair, resultList[i])\n } else if votingMethod == \"majority\" {\n resPair = append(resPair, resultList[0], resultList[1])\n }\n return nil, true, resPair\n }\n }\n }\n return resPair, false, nil\n}\n```\n\n## La méthode de Condorcet\n\nRemontons à 1785, où fut défini le **vainqueur de Condorcet**. On peut le définir comme le candidat préféré à tous les autres, pris un par un. Autrement dit, c’est comme si on avait pleins de tournois en cage 1v1 entre tous les candidats, et s’il existe un candidat mettant KO tous les autres pendant la majorité des combats, alors c’est le vainqueur de Condorcet.\n\nOn pourrait illustrer cela à l’aide d’un graphe de majorité **non-transitif**, où un arc reliant le candidat A au candidat B signifie qu’une majorité stricte de votants préfèrent A à B : _el ganador de Condorceto_ serait donc le candidat pointant vers tous les nœuds.\n\n![](./condorcet.jpg)\n\nCette méthode paraît très séduisante, puisqu’elle annihile la notion de vote utile et donc supprime les inégalités entre \"petits\" et \"grands\" candidats : pratique ! Pour l’anecdote, Nicolas Sarkozy fut élu président de la République à l’issue de l’élection de 2007, tandis que les sondages indiquaient une préférence des Français pour François Bayrou par rapport à Sarkozy (et à chaque autre candidat) wtf la démocractie ???\n\nPauvre François, validé par les Français mais même pas foutu de se qualifier au second tour…\n\nGoGoGo :\n\n```golang\nfunc CondorcetVoteRound(votes []model.Voter, candidates []model.Candidate) (model.Candidate, model.Result) {\n now := time.Now()\n\n possiblePairDiff, resultList := model.GeneratePossiblePairDiffsAndResultList(candidates)\n // On récupère le score de chaque duel pour chacun des votants\n fmt.Println(\"---- before setPossiblePairDiffValue\", time.Since(now))\n model.SetPossiblePairDiffValue(possiblePairDiff, votes)\n fmt.Println(\"--- after setPossiblePairDiffValue\", time.Since(now))\n now = time.Now()\n // Liste des résultats\n model.SetResultListValue(possiblePairDiff, resultList)\n now = time.Now()\n // On récupère un gagnant\n var result model.Result = model.Result{}\n var candidat model.Candidate = model.Candidate{}\n for r, v := range resultList {\n if result.DuelsWon < v.DuelsWon {\n result = *v\n candidat = r\n }\n }\n return candidat, result\n}\n```\n\nCependant, ce système peut être victime d’un phénomène assez embêtant : le _paradoxe de Condorcet_. Tah un Pierre-Feuille-Ciseau où A serait préféré à B, B à C, et C à A. Pour y remédier, une règle de _tie-break_ doit être définie afin de déterminer le gagnant selon une loi de probabilité. Mais c’est relou à faire, puis allez expliquer à René 85 ans ou Mathilde 15 ans que non, ça ne signifie pas que le président va être tiré au sort.\n\nAinsi, pour s’affranchir de cette peine, des pays comme l’Australie ou l’Irlande ont adopté une méthode dérivée, où chaque électeur classe les candidats par ordre de préférence : le vote alternatif.\n\n![](./alternatif.jpg)\n\nOn ne rentrera pas plus en détail de cette méthode dérivée de Condorcet, mais la chose à retenir est que l'obligation d’obtenir une majorité absolue augmente fortement la légitimité de l’élu, mais ne permet pas toutefois d’élir forcément un gagnant de Condorcet, dommage... Heureusement, il existe un moyen d’y remédier.\n\n## La méthode de Copeland\n\nCet article peut donner l’impression que l’on se dirige petit-à-petit vers la quintessence de la démocratie, mais rappelez-vous d’une chose : il n’existe pas de méthode de vote parfaite, juste des moins pires que d’autres. L’objectif est de maximiser le nombre d’électeurs dont le vote suivrait strictement leurs préférences, et en ce sens, la **règle de Copeland** ne paraît pas trop déconnante.\n\nEn bref, Copeland est un mix de Condorcet et du vote alternatif, modulo les défauts, ce qui signifie qu’à la fin d’une procédure de Copeland, on est censé avoir élu un vainqueur de Condorcet. Notons que cette méthode de vote reste sujette aux manipulations, où l’on peut voir apparaître par exemple des coalitions pour nuire à un adversaire. Mais dans cet article nous vivons dans un monde idéal , alors pas de risque à ce niveau-là.\n\nConcrètement, pour le candidat i, on va établir une [matrice antisymétrique](https://fr.wikipedia.org/wiki/Matrice_antisymétrique) de taille n×n (avec n ≥ 2 le nombre de candidats), construite telle qu’une cellule vaut :\n\n - (+1) si i est strictement préféré au candidat j pour l’ensemble des électeurs\n - (-1) si j est strictement préféré à i\n\nOn définit alors le **score de Copeland** de i comme la somme sur j des cellules concernées. Si le candidat i obtient un score de n - 1, jackpot : il est alors vainqueur de Copeland ET de Condorcet. Rien que ça.\n\nVoyons un exemple très simple, avec la combinaison de préférences individuelles ci-dessous pour les candidats A, B, C et D obtenues après dépouillement :\n\n![](./example_copeland.png)\n\nOn obtient alors la matrice suivante :\n\n![](./matrix_copeland.png)\n\nAinsi, B est élu puisqu’il est l’unique candidat capable de satisfaire le critère de Condorcet, ce qu’on peut illustrer encore une fois par le graphe complet suivant :\n\n![](./copeland.jpg)\n\nPlace à l’implémentation en Go, pour notre plus grand plaisir (ou détresse) :\n\n```golang\n// Petit tricks : Calculer le score de Copeland à partir d’un vote\n// de Condorcet pour s’affranchir de la manipulation matricielle\nfunc Copeland(voters []model.Voter, candidates []model.Candidate) (model.Candidate, int) {\n numberOfDuels := len(candidates) - 1\n candidat, result := CondorcetVoteRound(voters, candidates)\n duelLost := numberOfDuels - result.DuelsWon\n\n // result.DuelsWon - duelLost correspond au score de Copeland\n return candidat, result.DuelsWon - duelLost\n\n}\n```\n\n## Vers un changement du mode de scrutin en France ?\n\nAlors finalement, le changement c’est maintenant ? Dans les faits, très peu. Les considérations politiques^[2] représentent d’importants obstacles à une éventuelle évolution, et plus le temps passe, plus les perspectives de changement s’éloignent au vu du conservatisme dont fait preuve le droit électoral français^[3].\n\nCependant, on observe sur les réseaux sociaux de plus en plus de personnes pointant du doigt notre système actuel, avec un vote utile ayant été plus que jamais au cœur des débats. Plus que de simples articles hypothétiques de revues, de vrais travaux sont en cours, initiés par une expérience menée en 2017 par des chercheurs du CNRS, en partenariat avec l’Université de Paris-Dauphine et l’Ecole Polytechnique. L’objet de leur étude fut de voir quel serait le résultat du scrutin présidentiel de 2017 en procédant au Jugement Majoritaire, méthode étudiée par ailleurs par l’un de nos [lauréats de la bourse Coddity](https://www.youtube.com/watch?v=gdsr5Qq83xM) en 2017 ! Ils ont pu mettre en place cette méthode à partir d’un échantillon de 52 000 personnes, et bien que les résultats ne soient pas parfaits, il est bon de voir que certains s’emploient à étudier les alternatives pouvant être réellement mises en place ! Vous pourrez trouver toutes les infos la concernant sur [leur site](http://www.jugementmajoritaire2017.com/).\n\nJ’espère que cet article vous a plu, et si vous souhaitez voir en détail l’implémentation vous trouverez tout sur [ce repo](https://github.com/cazicbor/hello-democracy) GitHub. (n’hésitez pas à ajouter une petite _star_ la famille ça fait toujours plaisir)\n\nNB : N’étant que stagiaire, je remercie Charles pour la _code review_ et le super _mocks generator_, et me dédouane donc de toute responsabilité vis-à-vis d’éventuelles non-optimalités.\n\nA BIENTOT LA MIF\n\nSources :\n\n[1] Jean-François Laslier, Karine van der Straeten. Élection présidentielle : Une expérience pour un autre mode de scrutin. 2003. hal-00242952\n\n[2] Quinault-Maupoil, T. (2021, 2 mars). Proportionnelle : l’option parlementaire se corse. Le Figaro. https://www.lefigaro.fr/politique/proportionnelle-l-option-parlementaire-se-corse-20210302\n\n[3] Rambaud, A. R. (2021, 4 mars). Est-il encore possible de changer les règles des élections de 2022 ? Blog du droit électoral. https://blogdudroitelectoral.fr/2021/03/est-il-encore-possible-de-changer-les-regles-des-elections-de-2022-r-rambaud/\n","authorData":{"id":"boris","title":"Ex-Stagiaire et ambianceur","name":"Boris","excerpt":"Reste souple","cover":"/authors/boris/cover.jpg"},"cover":"/articles/hello-democracy/./cover.png"}]}

Boris

Ex-Stagiaire et ambianceur

Articles écrits par Boris :

Élections, théorie du choix social et Go