Théorème d'impossibilité d'Arrow

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le théorème d'impossibilité d'Arrow, également appelé « paradoxe d'Arrow », est une confirmation mathématique dans certaines conditions précises du paradoxe évoqué dès 1785 par Nicolas de Condorcet selon lequel il n'existe pas de fonction de choix social indiscutable, permettant d'agréger des préférences individuelles en préférences sociales. Pour Condorcet, il n'existe pas de système simple assurant cette cohérence. Arrow tente de démontrer, sous réserve d'acceptation de ses hypothèses, qu'il n'existe pas du tout de système assurant la cohérence, hormis celui où la fonction de choix social coïncide avec les choix d'un seul individu, parfois surnommé dictateur, indépendamment du reste de la population.

Origine[modifier | modifier le code]

Le précurseur : Nicolas de Condorcet[modifier | modifier le code]

Nicolas de Condorcet énonce en 1785 dans son ouvrage Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, le paradoxe de Condorcet : soit l'idée selon laquelle la définition d'une position commune à plusieurs votants se heurte à des difficultés logiques. Notamment le non-respect de la règle de l’intransitivité.

L'auteur[modifier | modifier le code]

Ce théorème est dû à Kenneth Arrow, lauréat 1972 du Prix de la Banque de Suède en sciences économiques en mémoire d'Alfred Nobel, communément désigné par Prix Nobel d'économie, lequel l'a exposé dans sa thèse et l'a publié en 1951 dans son livre Choix social et valeurs individuelles (Social Choice and Individual Values).

Préférences[modifier | modifier le code]

Notion

Si un individu ayant des préférences classe une option A devant une option B, la présence d'une troisième option C toutes choses égales par ailleurs ne doit pas en principe intervertir cette préférence. On dit que cela manifeste la cohérence de son choix.

Formalisation

Pour les mathématiciens, ce que les économistes appellent « préférences » correspond à un pré-ordre total. En particulier, ce peut être un ordre total (on parle alors de « préférences strictes » ).

De façon similaire, les « préférences » d'un individu correspondent à l'ordre qu'un individu établit entre des options qui s'offrent à lui. Ces préférences sont dites strictes lorsque l'individu ne classe jamais deux options ex-æquo. Pour que la description de cette notion soit complète, on suppose que l'ordre qu'un individu établit entre les différentes options existantes n'est pas modifié par l'ajout d'options supplémentaires.

Un profil de préférences est le nom donné à un « groupe » de préférences individuelles. On nomme préférences sociales des préférences qui valent au niveau social.

Les problèmes[modifier | modifier le code]

Il s'agit d'agréger un ensemble de préférences individuelles en un ensemble de préférences sociales, autrement dit un ensemble d'ordres individuels en un ordre social.

Quelques exemples:

  • élection : Différents candidats se présentent à une élection. Les électeurs ont des préférences quant aux candidats. À partir de ces préférences, on veut classer les candidats.
  • championnat de formule 1 : Différentes écuries sont présentes. On dispose de classements par écurie pour chaque grand-prix. À partir de ces classements par grand-prix, on veut un classement définitif.
  • choix entre projets d'infrastructure : Différents projets d'infrastructure sont présentés. Ces projets peuvent être classés selon différents critères (prix, durée des travaux et différents critères de qualité). À partir de ces classements par critères, on veut un classement global des différents projets.

On nomme fonction de choix social l'opération de passage des préférences individuelles vers une préférence collective.

Énoncé simplifié[modifier | modifier le code]

Le théorème d'Arrow est connu sous la forme suivante.

Pour au moins trois options de choix et deux individus, il n'existe pas de fonction de choix social satisfaisant les propriétés suivantes :

  1. Universalité, ou domaine non restreint (en) : la fonction de choix social doit être définie dans tous les cas de figure, c'est-à-dire déterminer toujours un choix collectif, quel que soit le profil de préférences de chaque individu.
  2. Non-dictature : il n'existe aucun individu pour lequel la liste de ses choix personnels coïncide avec la fonction de choix social, indépendamment des préférences des autres ;
  3. Unanimité (Optimum de Pareto): lorsque tous les individus préfèrent une certaine option à une certaine autre, la fonction de choix social doit associer cette même préférence à la société.
  4. Indifférence des Options Non-Pertinentes : le classement relatif de deux options ne doit dépendre que de leur position relative pour les individus et non du classement d'options tierces ; si l'on ne considère qu'un sous-ensemble d'options, la fonction ne doit pas aboutir à un autre classement de ce sous-ensemble.

Dans une autre version du théorème, l'unanimité peut être remplacée par les deux hypothèses suivantes :

  1. Monotonie : un individu ne doit pas pouvoir faire diminuer le classement global d'une option en la classant plus haut.
  2. Souveraineté : aucun choix social ne doit être impossible a priori.

Principe de la démonstration et interprétation[modifier | modifier le code]

La démonstration est très technique et repose sur plusieurs lemmes que l'on déduit de cas particuliers. Le plus souvent, on suppose l'existence d'une procédure de choix social vérifiant les conditions d'universalité, d'unanimité, et d'indifférence aux options non pertinentes, et l'on montre que cette procédure coïncide avec les choix d'un individu donné.

Plus précisément, désignons par X l'ensemble de la population. Une partie F de cette population est dite décisive, si la fonction de choix social donne comme résultat la liste des préférences des individus de la partie F, lorsque ceux-ci ont les mêmes préférences individuelles. On montre alors que l'ensemble de ces parties décisives F forme un ultrafiltre sur X. Lorsque X est fini, l'ultrafiltre est trivial, ce qui signifie qu'il existe parmi les éléments de l'ultrafiltre une partie décisive formée d'un seul individu x, et que toute partie F est décisive si et seulement si cette partie contient cet individu x. On montre enfin que la fonction de choix social coïncide avec les choix de x[1].

Ce théorème n'est pas un résultat positif : il ne permet pas d'illustration systématique, mais constate que pour des choix non-binaires, il y aura toujours des situations problématiques. Ainsi, une fonction de choix social qui présente les propriétés élémentaires énoncées plus haut sera souvent sensible aux options non-pertinentes. Remarquons néanmoins que nos propres choix sont parfois influencés eux aussi par des options non-pertinentes et que cela n'affecte pas dans le cas général notre efficacité.

Relaxation des conditions[modifier | modifier le code]

Si ce théorème ne gêne pas les partisans de régimes dictatoriaux (qui sont prêts à faire confiance à un « homme fort » pour mener raisonnablement le peuple) et gêne peu les libéraux (qui récusent l'idée de transformer des préférences individuelles en préférence collective), il est en revanche une épine dans le pied des partisans de la démocratie.

Le théorème a suscité en conséquence une abondante réflexion sur les procédures envisageables et les conditions moins fortes qui restent compatibles entre elles.

En travaillant par élimination, on conçoit ne pas pouvoir admettre qu'une procédure de vote puisse

  • rester indéfiniment indécise,
  • être dictatoriale,
  • être non monotone,
  • avoir un résultat prédéterminé (IONP)

Les propriétés d'universalité et d'IONP sont-elles raisonnables? Oui, au sens qu'il serait raisonnable de les accepter. Non, au sens qu'il serait déraisonnable de les exiger : Ces deux propriétés ne sont ni basiques, ni élémentaires. En ce qui concerne le fait d'avoir un résultat prédéterminé, on peut concevoir que le résultat soit partiellement prédéterminé : par exemple, on peut ne pas admettre l'élimination d'un parti politique même si un vote en décidait. On fait alors intervenir des choix d'un niveau différent de celui du choix d'un système de vote : le théorème n'envisage pas le côté moral ou admissible des options; il traite juste de la procédure transformant les options de départ en décision finale. Il reste donc non admissible qu'une procédure de vote puisse exclure a priori des options.

Seule l'indifférence aux options non pertinentes (IONP) pouvait raisonnablement être affaiblie. Nous ne la pratiquons d'ailleurs en général pas nous-mêmes dans nos choix individuels, faiblesse connue des vendeurs et exploitée par eux (méthodes dite du bait and switch - on appâte le chaland avec des produits à bas prix... puis on propose un autre article de 'meilleure' qualité à marge plus importante)

Elle revient à dire, dans le cas du choix d'un projet selon plusieurs critères, que proposer un projet nouveau ne doit pas intervenir dans le classement existant des autres projets. Dans le cas d'une élection, elle revient à dire que l'apparition ou le désistement d'un candidat ne doit pas intervenir sur ce que nous pensons des autres. Nous sommes habitués à des systèmes électoraux qui violent cette condition, sans que cela choque trop. L'électeur est parfois poussé au « vote utile », ce qui implique qu'il doit lui-même deviner quelles sont les options pertinentes, et éliminer celles qui ne le sont pas.

En fait, cette condition IONP se traduit par le fait que, seule, l'option finalement retenue est pertinente, l'introduction ou la suppression de toutes les autres étant sans effet sur le résultat final. Cela parait un peu fort.

Il est apparu qu'on pouvait envisager de remplacer cette condition par une condition moins forte : l'indifférence aux options les moins pertinentes (IOMP). On retient comme options pertinentes les membres du plus petit ensemble qui battent, dans les matchs deux à deux, toutes les options hors de l'ensemble (ensemble de Smith). Ainsi et par exemple, Si A bat B, B bat C et C bat A, mais que A, B et C battent toutes les autres options, l'ensemble de Smith est constitué de A, B et C, et représente les options qui ont une chance de l'emporter. Les autres options constituent les options les moins pertinentes.

Avec cette définition plus lâche, certaines méthodes de Condorcet vérifient le critère.

Variante : le théorème de Gibbard-Satterthwaite[modifier | modifier le code]

Alors que le théorème d'Arrow s'intéresse à la question de déterminer une fonction de choix social visant à dresser une liste de préférences collectives à partir des listes des préférences individuelles, une question plus fréquente consiste à choisir collectivement un unique élu à partir des préférences individuelles entre plusieurs candidats. Tel est l'objet du théorème de Gibbard-Satterthwaite (en). Celui-ci énonce le résultat suivant relatif à une procédure de désignation du gagnant à une élection :

  • Chaque individu de la population classe des candidats à une élection selon un ordre de préférence personnelle.
  • On suppose que chaque candidat peut se trouver élu si la population choisit de façon adéquate son ordre de préférence. Autrement dit, la procédure de désignation n'élimine aucun candidat
  • On suppose qu'il y a au moins trois candidats.
  • La procédure de désignation est dite manipulable s'il existe un votant i dont la liste de préférence est R et telle que, s'il décide de changer son choix en R' qui ne correspond pas à ses préférences, alors l'élu choisi après son nouveau choix sera mieux placé dans ses préférences que l'élu choisi avec ses préférences initiales.

Alors la procédure de désignation est non manipulable si et seulement si elle est dictatoriale.

Dans la pratique, les procédures de désignation sont manipulables, et il est fréquent qu'un votant ayant les préférences A > B > C vote pour B afin d'être sûr de ne pas voir C élu.

Exemples d'application[modifier | modifier le code]

Système par points cumulés[modifier | modifier le code]

Dans le cas des courses automobiles, chaque voiture remporte des points à chaque épreuve selon son ordre d'arrivée. Le plus grand total remporte la compétition. Ce dispositif passe d'un classement à un classement ; il est universel, souverain, monotone, mais il n'est pas indifférent aux alternatives non-pertinentes.

Deux écuries (A et B) de deux voitures chacune (A1, A2 et B1, B2) sont à la fin d'une compétition, la dernière course est sur le point de s'achever. Le meneur A1 mène B1 de deux points au classement général, mais il est derrière lui et n'espère plus le rattraper. Loin devant eux, A2 et B2 sont seuls. Les points à l'arrivée sont attribués comme suit :

1er 10

2nd 9

3e 6

4e 5

...

A1 devrait gagner la compétition, puisque B1 n'aura qu'un point de mieux. Mais, à ce moment-là, le directeur de l'écurie B peut demander à B2 d'abandonner la course : B1 sera alors deuxième à cette course, et à trois points de mieux que A, gagnera la compétition ! S'il fait ça, on peut même imaginer que A2 soit tenté d'abandonner pour permettre à A1 de n'arriver qu'à un point de B1, respectivement en deuxième et première position.

Cette situation montre bien qu'un système par points cumulés n'est pas indifférent aux alternatives non-pertinentes, ou encore que la procédure de désignation du vainqueur est manipulable, au sens Gibbard-Satterthwaite.

Appel d'offres pour les marchés publics[modifier | modifier le code]

De même, on peut espérer que les comités d'expertise qui retiennent un projet selon plusieurs critères sont monotones et souverains, indifférents aux options non-pertinentes :

Au besoin, le code des marchés a prévu que les critères de choix doivent être pondérés et non pas seulement hiérarchisés.

Articles connexes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Peter Komjath, Vilmos Totok, Ultrafilters, Amer. Math. Monthly, 115, n°1, (Janvier 2008), p.33-44