Les Newsletters Interstices
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    La minorité l’emporte

    Culture & Société
    Algorithmes
    Le Dr Jacob Ecco, le détective qui utilise des méthodes mathématiques et informatiques pour résoudre des énigmes, se trouve une fois encore mis à l'épreuve par un client haut placé. Parviendra-t-il à résoudre ce nouveau problème ? Et vous, pourquoi n'essayez-vous pas ?
    « Il faut voter tôt et souvent »
    (Anonyme.)

     

    C’était par un de ces dimanches clairs et glacials de février où, même à New York, personne ne s’aventure dehors. Ecco me fit entrer et m’invita à me servir une tasse de thé.

    Image : Vivian Fayard

    « Vous avez vu la presse à propos du scandale du vote au Congrès patagonien ?
    — Je l’ai parcourue. Cette assemblée de savants, de fonctionnaires et de dirigeants d’entreprise du monde entier qui conseille les Nations Unies ne me passionne guère.
    — Mais enfin, cher professeur, répondit Ecco, c’était pourtant un remarquable exemple de l’illogisme de la presse : elle a parlé de scandale alors qu’il n’y en avait pas.
    — Comment le savez-vous ? m’exclamai-je, surpris qu’Ecco ait des contacts dans le monde politique.
    — Simple déduction. Regardez ce que dit le New York Times. Il y avait trois candidats en lice pour la présidence du Congrès : Guarez, Swenson et Libretti. Avant l’élection, Guarez et Swenson, son ennemi juré, étaient assurés du soutien d’au moins 40 % des membres du Congrès. Il n’en restait donc plus que 20 % derrière Libretti, vraisemblablement parce qu’il avait la réputation d’être un peu naïf et de manquer d’envergure politique. Cela n’a pas empêché Libretti de remporter l’élection. Les observateurs extérieurs parlent de manipulation, mais les membres du Congrès se refusent à tout commentaire.

    Là-dessus, d’autres journaux ont repris l’information en laissant entendre qu’il y avait bien eu trucage. Mais d’après les statuts du Congrès patagonien que j’ai ici, je pense pour ma part que l’élection s’est déroulée selon les règles. Selon les statuts, les élections pour la présidence ont lieu en plusieurs tours, chacun opposant deux candidats. Le premier tour pouvait donc opposer Guarez et Swenson, et le second, le vainqueur final du premier et Libretti. Ou encore, le premier tour pouvait opposer Swenson et Libretti, et le second, le vainqueur du premier et Guarez. Ou enfin, Libretti et Guarez pouvaient s’opposer au premier tour. Quoi qu’il en soit, il ne peut y avoir que deux tours opposant chacun deux candidats. »

    Avant d’aller plus loin, avez-vous une idée de la manière dont Libretti aurait pu emporter la présidence sans tricher ?

    « Les statuts changent tout, poursuivit Ecco. Du fait de l’hostilité entre Guarez et Swenson, quel que soit l’ordre dans lequel on procède, Libretti gagne. Les partisans de Swenson le préfèrent à Guarez, et ceux de Guarez, à Swenson. »

    Quelques jours plus tard, le courrier des lecteurs du New York Times publiait une lettre signée K. Arrow qui reprenait le même raisonnement. Je reconnus le style d’Ecco, mais ce dernier se contenta de me dire : « Pas du tout, le mérite en revient entièrement à Arrow.
    — Votre démenti sent l’aveu.
    — Peut-être, dit Ecco en souriant. Vous vous rappelez la commotion que Kenneth Arrow a provoquée dans le monde des sciences humaines avec son fameux théorème des possibilités ? Ce théorème démontre, entre autres choses, que les préférences de la majorité peuvent être subverties par des élections opposant plus de deux candidats.

    Arrow a démontré, par exemple, que, selon certains modes d’élections, un candidat capable de battre n’importe qui dans une élection n’opposant que deux personnes — on l’appelle parfois le candidat Condorcet — peut encore perdre. Supposons qu’il y ait trois candidats A, B et C ; A est très à droite, C très à gauche, et B au milieu. Si on utilise un scrutin majoritaire, les deux candidats qui ont obtenu le plus de voix au premier tour se retrouvent au second. Si l’électorat est très polarisé, comme c’était le cas au Congrès patagonien, B sera éliminé au premier tour. Toutefois, il battrait A ou C dans une élection opposant seulement deux candidats.

    Le protocole des élections au Congrès patagonien prévoit que le candidat Condorcet, si tant est qu’il y en ait un, gagne quoi qu’il arrive. À condition toutefois que les votants soient fidèles à leurs convictions à chaque tour. La presse est partie du principe que les statuts prévoyaient des élections opposant plusieurs candidats. C’est pour cette raison, qu’à ses yeux, Libretti était battu d’avance. »

    On frappa alors à la porte.

    Antonio Libretti, le nouveau président du Congrès patagonien, ne ressemblait pas du tout à un homme dénué d’envergure politique. Au contraire, il paraissait avoir des objectifs bien définis et solidement étayés.

    « Ainsi, messieurs, conclut-il quelques minutes plus tard, l’enjeu est l’avenir de l’Amazone, voire de notre planète. La proposition de loi que je défends et souhaite voir le Congrès adopter signerait l’arrêt de tout aménagement supplémentaire, alors que les propositions concurrentes provoqueraient une destruction de la jungle impossible à juguler. »

    Ecco acquiesça sans enthousiasme.

    « Monsieur Libretti, vos objectifs sont très louables et je les soutiens entièrement, mais vous avez dit que votre problème requérait mes services. Je n’appartiens pas à un groupe de pression.
    — Je le sais, docteur Ecco. Je ne suis pas venu vous demander de faire pression mais de résoudre un problème logique. Commençons par représenter toutes les propositions concernant l’Amazone par des lettres : A, B, C et D. La mienne est la C. Parmi les autres, je préfère A à D et D à B.
    « Le Congrès patagonien compte 100 membres, dont 17 partagent exactement mes vues. 32 membres préfèrent A à B, B à D et D à C ; 34, D à B, B à C et C à A. 17 autres préfèrent B à A, A à C et C à D.
    — Si vous me permettez de résumer, monsieur Libretti, dit Ecco, les préférences sont les suivantes :

    (C, A, D, B) : 17 partisans
    (A, B, D, C) : 32 partisans
    (D, B, C, A) : 34 partisans
    (B, A, C, D) : 17 partisans

    « Le premier groupe représente vos 17 partisans et vous-même qui préférez C à A, A à D et D à B, et ainsi de suite pour les autres groupes.

    — Exactement, dit Libretti. Mais, comme vous pouvez le voir, ma position ne remporte guère de suffrages auprès de la plupart des membres du Congrès. En outre, je n’ai pas le droit de prendre part au vote. Mais je dispose d’un privilège que j’espère bien utiliser à mon avantage.

    « Notre système stipule que l’on doit procéder au vote en plusieurs tours opposant deux propositions. Par exemple, le premier tour pourrait opposer A à B. Le deuxième, le vainqueur à C ou C à D, etc. Bien sûr, seul le vainqueur d’un tour a le droit de participer aux tours suivants — le vainqueur final est celui qui reste quand tous les autres ont été éliminés. Toutefois, le mode de scrutin peut avoir une influence sur le résultat, comme vous l’avez déjà observé dans votre analyse de mon élection. »

    Ecco sursauta. Comment Libretti pouvait-il savoir qu’il était l’auteur de l’analyse de son élection ?
    « En tant que président, continua Libretti, ma prérogative est de choisir les candidats des différents tours.
    — Et vous pensez que votre proposition va gagner de cette manière ? demandai-je. Si vous représentiez B, je comprendrais que vous ayez un espoir. Mais C ? Dans une élection opposant B et C, B remporterait 83 voix. C n’a certainement rien d’un candidat Condorcet.
    — Si le Dr Ecco et vous-même y réfléchissez, me dit Libretti en fronçant les sourcils, je suis sûr que vous trouverez un moyen d’expliquer cela. »

    (1) En supposant que chacun vote chaque fois selon ses préférences, existe-t-il une succession de tours opposant chacun deux candidats qui permettrait à C de sortir vainqueur ? Si tel est le cas, quelle est-elle ?

    La stratégie consiste à commencer par faire s’affronter les deux propositions les plus populaires. C gagnera si les élections ont lieu dans cet ordre : D contre B (D gagne par 51 à 49), A contre D (A gagne par 66 à 34), A contre C (C gagnera par 51 à 49).

    « Voici votre réponse, Monsieur Libretti, dit Ecco. Vous pouvez faire adopter la proposition qui sauvera l’Amazone. C’est possible parce qu’il n’y a pas de candidat Condorcet, si bien que l’ordre peut tout changer.

    — Parfait, dit Libretti. Un dernier point : la tradition dans ce type d’élections veut que le président désigne les deux candidats au premier tour, mais que l’opposition choisisse ceux du deuxième tour. Dans ce cas précis, l’opposition rassemble ceux dont le premier choix est B ou D. La question est la suivante : si je choisis les candidats du premier tour, et l’opposition, ceux du deuxième, puis-je être sûr que l’une de mes deux propositions, C ou A, l’emportera ? »

    (2) Pouvez-vous garantir que C ou A gagnera si vous choisissez le premier couple de propositions et que l’opposition choisit le deuxième ? Rappelez-vous que les tours suivants ne peuvent opposer que les vainqueurs des précédents. Si oui, dites quelles propositions devraient se présenter au premier tour. Vous devez démontrer que C ou A sera vainqueur, quel que soit le couple choisi pour le deuxième tour. Sinon, pourquoi ?

    Non. Si l’opposition choisit les propositions en lice au deuxième tour, alors B ou D gagnera. Notez que B gagne contre toutes les propositions sauf D. Donc, si D perd au premier tour, B gagnera. Si D survit au premier tour et que A et C sont encore en course, alors l’opposition opposera A à C au deuxième tour. C gagnera, mais perdra alors contre D au troisième tour.

    La dernière possibilité est que D survive et que seul A ou C survive au premier tour. Cela signifie que B doit survivre aussi. Au deuxième tour, l’opposition opposera donc B à A ou C. Cela ne laisse que B et D pour le troisième tour.

    « La tradition a vraiment du bon », s’exclama Libretti après avoir entendu la réponse d’Ecco. L’air radieux, il nous serra la main et prit congé.

    « Alors, professeur, dit Ecco après le départ de notre visiteur, la fin justifie-t-elle les moyens ? Nous avons fait gagner Libretti et sa minuscule minorité, pervertissant ainsi ce qui devrait être un processus démocratique. Mais peut-être la règle bizarre des élections opposant deux candidats est-elle la cause de tout cela. »

    (3) Montrez que A, B, C ou D peut gagner selon un ordre prédéterminé.

    Nous avons démontré comment faire gagner C. A gagne si l’élection procède dans l’ordre suivant : B contre C, D contre B et A contre D. D gagne si l’ordre choisi est A contre B, B contre C et B contre D. B gagne si l’ordre choisi est A contre D, A contre B et B contre C.

    « On sous-estime certainement Libretti en le traitant de naïf, dis-je. Il est prêt à tirer toutes les ficelles pour obtenir ce qu’il veut, aussi louables ses intentions soient-elles.

    — Ou peut-être emploie-t-on le mot naïf dans un sens plus profond. Pensez aux répercussions quand on se rendra compte que Libretti a encore su exploiter le système de scrutin à son avantage. Il risque bien de perdre le peu de partisans qu’il a. » Ecco s’interrompit, le menton sur la main, les yeux fixés par terre. « D’un autre côté, les gens peuvent également se dire qu’il représente une force écrasante et prendre le train en marche. » Ecco sourit et soupira. « Si seulement la politique était aussi facile à comprendre que les mathématiques. »

    Cette énigme a été publiée dans le livre Les Aventures extraordinaires du Docteur Ecco, Éditions Odile Jacob, nouvelle édition juin 2006.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Dennis Shasha

    Chercheur en informatique et en intelligence artificielle à l'institut de mathématiques de l'Université de New York.
    Voir le profil

    Ces articles peuvent vous intéresser

    ArticleCulture & Société
    Algorithmes

    Comment désigner le vainqueur d’une élection ?

    Jérôme Lang

    Niveau intermédiaire
    Niveau 2 : Intermédiaire