Choix, votes, élections : le théorème d’Arrow

Piste rouge Le 4 avril 2012  - Ecrit par  Jean-Yves Briend Voir les commentaires (2)

Le théorème d’Arrow est comme une flèche qui aurait
tué la démocratie : « toute démocratie est une dictature ! ».
Heureusement, la démocratie a la peau dure...

Platon écrit, dans La République, qu’à son avis, la « démocratie apparaît lorsque
les pauvres, ayant emporté la victoire sur les riches, massacrent les uns, bannissent
les autres, et partagent également avec ceux qui restent le gouvernement et les
charges publiques ; et le plus souvent ces charges sont tirées au sort. » Ainsi, voter
pour élire un président ou des représentants n’est pas, contrairement à ce que l’on
veut nous faire croire, une garantie de vie en démocratie. Cependant, même dans
la démocratie athénienne une assemblée peut être appelée à voter pour prendre une
décision
. Ainsi par exemple un comité
de sélection chargé du recrutement d’un maître de conférence à l’université vote-t-il pour classer les candidats à ce poste.

Le problème du vote a depuis longtemps intéressé les savants. Nombreux sont ceux qui ont entendu parler du paradoxe de Condorcet [1], énoncé par icelui au dix-huitième
siècle, moins nombreux sont ceux qui ont lu les articles d’arithmétique politique de
Gergonne au début du dix-neuvième. Nous allons ici nous entretenir brièvement d’un résultat de 1950 dû à Kenneth Arrow.

L’article d’Arrow

Son article s’intitule
A difficulty in the concept of social welfare et est paru au Journal of
political economics [2]. Kenneth Arrow a obtenu en 1972 le Prix de la banque de Suède
en sciences économiques à la mémoire d’Alfred Nobel [3] : dans la longue introduction
de son article il écrit que « la rationalité s’identifie avec une maximisation » et que
même si, devant les difficultés, la définition de rationalité doit être affaiblie, cela
ne doit être qu’un préliminaire à la « détermination d’un véritable maximum social
au sens plein et entier. » Plus loin il fait l’hypothèse que « les individus agissent
rationnellement ».

Les comités de sélection sont un exemple illustrant toute la validité d’une telle hypothèse d’action rationnelle puisque leurs membres sont soigneusement choisis pour être des parangons de rationalité. D’autre part, dans la nouvelle gouvernance universitaire [4] on cherche à maximiser une quantité numérique, grosso-modo le facteur d’impact d’un chercheur. On atteint ainsi, à n’en pas douter, un véritable optimum social.

Arrow formalise mathématiquement la notion d’action rationnelle dans ce qu’il
appelle une « carte d’indifférence » qui est, grossièrement, un classement des possibilités parmi lesquelles on doit choisir. Dit autrement, chaque votant doit être en mesure de classer les possibilités qui lui sont offertes sans ambiguïté : son vote est une liste ordonnée (premier : untel, deuxième : un-autretel etc...) des options proposées
(c’est-à-dire, dans le cas d’un comité de recrutement, des différents candidats).

Le théorème d’Arrow

Venons-en à l’énoncé du théorème d’Arrow. Un certain nombre $N$ d’individus
(une douzaine pour un comité de sélection) doit voter pour choisir un classement de $n$ options (« recruter Euclide, al-Khwarizmi,
Euler, Gauß ou Poincaré ? », par exemple). Le plus souvent les options sont numérotées, comme il se doit dans une démocratie moderne. Dans le cas du recrutement et afin de préserver l’anonymat des candidats, nous les numéroterions par numéro de sécurité sociale, mais nous garderons ici leur nom par commodité, d’autant qu’Euler a un numéro de sécurité sociale imaginaire pur tandis qu’al-Khwarizmi n’en a pas, étant entré illégalement sur le territoire français. Dans le cadre considéré par Arrow, le vote se déroule de la manière suivante : chaque individu $I_k$ choisit un classement des options proposées. Le premier membre du comité de sélection choisit donc par exemple le classement suivant : 

Poincaré 1, Gauß 2, Euclide 3, al-Khwarizmi 4 et Euler 5,

tandis que le second votant consulte un site de numérologie pour établir son classement qui est

Euler 1, Poincaré 2, Euclide 3, Gauß 4 et al-Khwarizmi 5.

Le vote du $k^e$ individu est donc une liste ordonnée $O_k$ de l’ensemble des options. Cette liste est sans ambiguïté sur l’ordre choisi ; dit autrement pour toute paire d’options $x,y$, le votant choisit une et une seule des possibilités : « je classe $x$ avant $y$ » ou « je classe $y$ avant $x$ ». D’autre part ce classement est tel que si le votant préfère $x$ à $y$ et $y$ à $z$ alors il préfère $x$ à $z$. En termes mathématiques, on dit que le votant propose une relation d’ordre totale sur l’ensemble des options.

Une fois que chaque votant a fait son choix, on entre la famille des listes ordonnées $(O_1, \ldots, O_N)$ dans une machine qui sort un classement $O^c$ qui est censé être le classement représentatif des désirs de la majorité.

Dans l’exemple du comité de sélection, on dispose des 12 classements proposés par les 12 membres du comité, dont les deux premiers peuvent s’écrire
Poincaré > Gauß > Euclide > al-Khwarizmi > Euler
et
Euler > Poincaré > Euclide > Gauß > al-Khwarizmi.

Le septième votant, lui, fournit la liste suivante :

Euclide > Gauß > al-Khwarizmi > Poincaré > Euler.

ll l’a discrètement tirée au sort, étant incapable d’ordonner complètement cette liste sans une discussion approfondie avec ses collègues qui permettrait de dégager, par exemple, que c’est al-Khwarizmi qui serait le plus approprié pour être un futur collègue dans son laboratoire. Le septième votant est connu pour son manque de rationalité.

Une fois les votes recueillis dans un grand chapeau, le président du comité rentre tous ces ordres dans son iPad et le programme fourni par la présidence de son université sort le classement qui sera proposé au conseil de l’université. Afin d’éviter toute protestation, celui-ci n’est pas transmis aux membres du comité, le suspense est insoutenable.

Pour résumer, le cœur de la machine électorale
est une application, dite fonction de choix social chez Arrow, qui à chaque vote représenté par un ensemble de $N$ classements $(O_1, \ldots, O_N)$ associe un unique classement $O^c$ que nous devrions plutôt noter $C(O_1, \ldots, O_N)$ afin de rappeler que ce classement, présumé représenter le classement socialement optimal, dépend bien évidemment du vote.

On demande à la fonction de choix social de satisfaire à un certain nombre de propriétés qui semblent des exigences assez naturelles pour que celle-ci fournisse un classement un tant soit peu représentatif des désirs des votants :

— le principe d’unanimité, qui énonce que si tous les individus préfèrent l’option $x$ à l’option $y$, alors le choix final préfère $x$ à $y$. Dit autrement,
si pour tout individu $k$ on a $x>y$ dans le classement $O_k$ choisi par $k$, alors $x>y$ dans le choix social $O^c$. Dans le comité de sélection, il est clair que si tout le monde préfère Poincaré à Euler, alors le vote final doit lui aussi classer Poincaré devant Euler ;

— l’absence de dictateur. Elle stipule que la fonction de choix social ne coïncide pas en permanence avec le choix d’un des individus (le dictateur), quels que soient les choix des autres votants. Dit autrement, il n’existe pas d’individu $I_k$ tel que quel que soit le vote $(O_1, \ldots, O_N)$, $O^c$ soit égal au choix $O_k$ de $I_k$. Dans l’exemple du comité de sélection, le programme entré dans l’Ipad du président ne doit pas sortir systématiquement le choix du président ;

— l’indépendance aux alternatives. Pour la comprendre, imaginons que le même comité de sélection vote deux fois de suite sur la même liste de candidats, parce que, par exemple, le chapeau dans lequel on récolte les bulletins s’est renversé. Quelques votants peuvent avoir changé d’avis entre les deux votes. Si cependant dans les deux votes les positions relatives d’Euler et de Poincaré sont les mêmes pour tous les votants, alors le principe d’indépendance aux alternatives stipule que pour les deux votes, le classement final donné par l’Ipad du président ordonnera Euler et Poincaré de la même manière. Voici un exemple : supposons que le comité de sélection n’ait que trois votants. Lors du premier vote, les choix des votants sont : 

V1 : Poincaré > Gauß > Euclide > al-Khwarizmi > Euler,

V2 : Euler > Poincaré > Euclide > Gauß > al-Khwarizmi

V3 : Euclide > Gauß > al-Khwarizmi > Poincaré > Euler.

Patatras, le chapeau se renverse et l’on demande aux membres du comité de voter à nouveau. Ayant quelques regrets, le second et le troisième membres changent légèrement leurs votes : 

V1 : Poincaré > Gauß > Euclide > al-Khwarizmi > Euler,

V2 : Euler > Poincaré > Gauß > Euclide > al-Khwarizmi

V3 : Euler > Euclide > Gauß > Poincaré > al-Khwarizmi.

Comme on le voit, dans les deux votes, aucun des votants n’a changé son choix quant aux positions relatives de Poincaré et d’Euclide. Dans les deux votes on a

V1 : Poincaré > Euclide

V2 : Poincaré > Euclide

V3 : Euclide > Poincaré.

Pour ces deux votes, la machine doit produire une liste finale $O^c$ dans laquelle Euclide et Poincaré ont les mêmes positions relatives. De manière générale, si l’on a deux votes $(O_1, \ldots, O_N)$ et $(O'_1,\ldots,O'_N)$ et deux options $x$ et $y$ telles que pour tout $k$ $x$ et $y$ soient ordonnés de la même manière dans $O_k$ et dans $O'_k$, alors la fonction de choix va ordonner de la même manière $x$ et $y$ pour les deux votes. Ainsi la fonction de choix ne doit pas
faire apparaitre, pour dire si $x$ est préféré à $y$, que les électeurs peuvent
avoir fait ce choix en connaissance des autres alternatives possibles. La condition d’indépendance aux alternatives est intéressante car, au premier abord, on pourrait croire qu’elle ne fait que paraphraser la règle de l’unanimité, mais il n’en est rien [5].

Nous pouvons maintenant énoncer :

Théorème d’Arrow : dès que le nombre de choix possibles est supérieur ou égal à 3, il n’existe pas de fonction de choix social qui simultanément satisfait au principe d’unanimité, est sans dictateur et est indépendante aux alternatives.

On le trouve souvent cité comme suit : une fonction de choix social
qui vérifie à la fois le principe d’unanimité et l’indépendance aux alternatives admet
un dictateur. Curieusement on ne le cite jamais sous la forme suivante : une fonction
de choix social qui satisfait au principe d’unanimité et n’admet pas de dictateur
ne peut être indépendante aux alternatives. Le principe d’indépendance est pourtant problématique puisqu’il suppose que l’on tienne compte dans le vote de « qui a voté quoi ». Ainsi viole-t-il un autre principe, celui de l’égalité des votants. Ne pourrait-on voir le théorème d’Arrow, cent quarante ans après Gergonne, comme une confirmation supplémentaire de la nocivité du scrutin censitaire [6] ?

Pour ma part, je préfère voir dans ce
théorème une démonstration de l’impossibilité de mécaniser la démocratie. Celle-ci
doit se nourrir de nombreux débats, de discussions et de palabres afin de pousser
au plus loin la recherche du consensus. Le vote ne devrait intervenir qu’en dernière
instance, pour valider un choix construit par la collectivité.

Voyons ce qui se passe dans le comité de sélection donné ci-dessus en exemple : même dans une université d’Excellence comme UT* ou A*MIDEX [7], le comité de sélection ne peut se soustraire au théorème d’Arrow. Le classement finalement retenu a été le suivant :

Euler > Euclide > Gauß > Poincaré > al-Khwarizmi.

Il se trouve que quoiqu’ait été le vote des membres du comité, c’est celui du membre numéro 3 qui aurait été choisi, celui-ci étant le représentant de l’Idex et ayant donc voix prépondérante. Il est le Primus Inter Pares et la machine de vote viole donc la seconde loi énoncée dans le théorème d’Arrow : l’absence de dictateur. C’est la garantie d’une gouvernance moderne et ambitieuse.

Post-scriptum :

6 mois après l’écriture de cet article j’ai appris qu’Euler n’avait pu être recruté, la préfecture ayant décrété que les nombres imaginaires n’existaient pas. Les autres candidats étant décédés entre-temps, le poste a été redéployé vers la recherche en management des établissements hospitaliers.

Un article de Rémi Peyre à paraître prochainement sur ce site vous permettra d’approfondir les questions soulevées ici sur le problème de la prise de décision grâce à un vote.

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Serma,
Nicolas Chatal,
Jérôme Poineau et
Laurent Bétermin.

Notes

[1Un article de Rémi Peyre le décrit sur ce site.

[2Voici un lien vers l’article original de K. Arrow.

[3Connu aussi sous le nom de « Prix Nobel d’Économie ».

[4Voir une analyse de L’IDEX toulousain UT* sur le site du Syndicat National des Chercheurs Scientifiques.

[5Ainsi peut-on imaginer faire jouer des étudiants (par exemple en première année à l’Université) avec les hypothèses du théorème d’Arrow afin de les familiariser avec des énoncés où l’ordre des quantificateurs a un rôle important.

[6Dans son article de 1820 aux Annales de Gergonne, on lit ceci : « Qu’on nous vante tant qu’on voudra les républiques de Sparte, d’Athènes et de Rome. Je n’aime pas moi cette liberté du petit nombre qui est fondée sur l’esclavage de tout le reste. » On trouve le texte complet ici.

[7Pour savoir ce que recouvrent ces doux acronymes, voir le site du SNCS ci-dessus, ou encore le texte plus concis que j’ai écrit pour mes collègues aixo-marseillais récemment. Les plus courageux peuvent lire le dossier complet de l’IDEX toulousain ici.

Partager cet article

Pour citer cet article :

Jean-Yves Briend — «Choix, votes, élections : le théorème d’Arrow» — Images des Mathématiques, CNRS, 2012

Commentaire sur l'article

  • Pour renouer avec le vote démocratique

    le 4 avril 2012 à 14:18, par le_cheveulu

    « Pour ma part, je préfère voir dans ce théorème une démonstration de l’impossibilité de mécaniser la démocratie. »

    Je vous conseille de lire la proposition de scrutin de Rida Laraki et Michel Balinski dans le dernier numéro de « Pour la sciences ». Ils proposent un vote basé uniquement sur l’appréciation de chaque candidat. Le candidat final étant choisi en prenant celui ou celle qui satisfasse plus de la moitié des votants. On se débarrasse ainsi de l’ordre total, on évite le paradoxe de Condorcet et on écarte les votes « stratégiques » (qu’on appelle plus volontiers vote utile !) qui nuisent à la démocratie.

    Répondre à ce message
  • Choix, votes, élections : le théorème d’Arrow

    le 4 avril 2012 à 19:14, par Gaston Rachlou

    Juste un mot pour dire que Kenneth Arrow, à 90 ans, se porte aussi bien que son théorème, qui n’en a que 61... Il y a quelques heures, il donnait un fort intéressant exposé à la Haute Ecole d’Economie de Moscou :
    http://conf.hse.ru/en/2012/announcements/49636677.html

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

registros

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

Suivre IDM