Théorème de Gibbard-Satterthwaite

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

En théorie du choix social, le théorème de Gibbard-Satterthwaite est un résultat publié indépendamment par le philosophe Allan Gibbard en 1973[1] et l'économiste Mark Satterthwaite en 1975[2]. Il montre que toute règle de vote déterministe vérifie au moins l'une des propriétés suivantes :

  1. La règle est dictatoriale, c'est-à-dire qu'il y a un électeur privilégié qui peut choisir le vainqueur ; ou
  2. La règle ne permet d'élire que deux candidats différents ; ou
  3. La règle est sensible au vote tactique : il existe des situations où un bulletin sincère n'est pas celui qui défend au mieux les opinions d'un électeur.

Ce théorème est limité aux règles de vote ordinales : l'action d'un électeur consiste à fournir un ordre de préférence sur les options proposées. Le théorème de Gibbard, plus général, permet de considérer des mécanismes de choix collectif qui ne sont pas nécessairement ordinaux : par exemple, des modes de scrutin où les électeurs attribuent des notes aux candidats. D'autres théorèmes encore plus généraux, le théorème de Gibbard de 1978 et le théorème d'Hylland, étendent ces résultats aux mécanismes non-déterministes, c'est-à-dire où le résultat peut non seulement dépendre des actions des électeurs mais aussi comporter une part de hasard.

Présentation[modifier | modifier le code]

Considérons des électeurs , et qui souhaitent choisir ensemble une option parmi quatre candidats , , et . On suppose qu'ils utilisent la méthode Borda : chaque électeur communique un ordre de préférence sur les candidats. Pour chaque bulletin, on attribue 3 points au candidat en tête, 2 points au deuxième, 1 point au troisième et aucun point au dernier. Une fois tous les bulletins comptabilisés, le candidat avec le plus de points est élu.

Supposons que les préférences soient les suivantes.

Cette notation signifie que l'électeur préfère , suivi de , et  ; les électeurs et préfèrent chacun , suivi de , et . Si les électeurs votent sincèrement, alors les scores sont les suivants : . C'est donc qui est élu, avec 7 points.

Mais l'électeur peut s'apercevoir qu'un autre bulletin défend mieux ses opinions. Supposons qu'il modifie son bulletin pour aboutir à la situation suivante.

L'électeur a stratégiquement remonté le candidat et descendu le candidat . Les nouveaux scores sont : . C'est donc qui est élu. L'électeur est satisfait d'avoir soumis un bulletin différent de ses préférences sincères, puisqu'il préfère le nouveau résultat plutôt que , le résultat qu'il aurait obtenu en votant sincèrement.

On dit que la méthode de Borda est manipulable : il existe des situations où un bulletin sincère ne défend pas au mieux les préférences d'un électeur.

Malheureusement, le théorème de Gibbard-Satterthwaite montre qu'une règle de vote est nécessairement manipulable, sauf éventuellement dans deux cas : s'il y a un électeur privilégié qui dispose d'un pouvoir dictatorial, ou si la règle ne permet de choisir qu'entre deux décisions possibles.

Énoncé du théorème[modifier | modifier le code]

On note l'ensemble des alternatives (supposé fini), aussi appelées candidats, même s'il ne s'agit pas nécessairement de personnes : il peut aussi s'agir de différentes décisions possibles pour un sujet donné. On note l'ensemble des électeurs. On note l'ensemble des ordres stricts faibles (en) sur  : un élément de cet ensemble permet de représenter les préférences d'un électeur. Une règle de vote est une fonction . Elle prend pour argument un profil de préférences et renvoie un candidat vainqueur.

On dit que est manipulable si et seulement s'il existe un profil où un certain électeur , en changeant son bulletin pour un autre bulletin , peut obtenir un résultat qu'il préfère (au sens de ).

On note l'image de , c'est-à-dire l'ensemble des résultats possibles de l'élection. Ainsi, on dit que possède au moins trois résultats possibles si et seulement si possède au moins trois éléments.

On dit que est dictatoriale si et seulement s'il existe un électeur qui est un dictateur, c'est-à-dire que l'alternative gagnante est toujours sa préférée parmi les résultats possibles. Si le dictateur possède plusieurs alternatives préférées ex aequo parmi les résultats possibles, alors l'alternative gagnante est simplement l'une d'entre elles.

Théorème de Gibbard-Satterthwaite — Si une règle de vote possède au moins 3 résultats possibles et si elle est non-manipulable, alors elle est dictatoriale.

Exemples[modifier | modifier le code]

Dictature en série[modifier | modifier le code]

Le mécanisme de la dictature en série fonctionne de la façon suivante. Si l'électeur 1 préfère une seule alternative, alors celle-ci est élue. Sinon, on restreint les résultats possibles à ses candidats préférés ex aequo, et on s'intéresse au bulletin de l'électeur 2. Si ce dernier possède une seule alternative préférée parmi celles encore en lice, alors celle-ci est élue. Sinon, on restreint encore les résultats possibles, etc. S'il reste encore plusieurs candidats en lice après avoir consulté tous les bulletins, on départage les candidats selon un critère arbitraire.

Cette règle de vote n'est pas manipulable : un électeur a toujours intérêt à annoncer ses véritables préférences. Elle est également dictatoriale, et son dictateur est l'électeur 1 : l'alternative gagnante est toujours sa préférée ou, s'il en préfère plusieurs à égalité, choisie parmi celles-ci.

Vote majoritaire simple[modifier | modifier le code]

S'il y a seulement deux résultats possibles, une règle de vote peut être non-manipulable sans pour autant être dictatoriale. C'est le cas, par exemple, du vote majoritaire simple : chaque bulletin attribue 1 point à l'alternative incrite en tête et 0 points à l'autre. Cette règle n'est pas manipulable car un électeur a toujours intérêt à donner ses préférences sincères ; et elle n'est clairement pas dictatoriale. De nombreuses autres règles ne sont ni manipulables ni dictatoriales : par exemple, on peut imaginer que l'alternative gagne si elle reçoit deux tiers des voix et que gagne dans le cas contraire.

Un mécanisme qui montre que la réciproque n'est pas vraie[modifier | modifier le code]

Considérons la règle suivante. On élimine tous les candidats, à part le ou les candidats placés en première position sur le bulletin de l'électeur 1. On départage ensuite les candidats encore en lice selon la méthode Borda. La règle ainsi décrite est dictatoriale par définition. Cependant, elle est manipulable, pour les mêmes raisons que la méthode Borda. Ainsi, le théorème de Gibbard-Satterthwaite est bien une implication et non une équivalence.

Corollaire[modifier | modifier le code]

On s'intéresse maintenant au cas où on interdit par hypothèse qu'un électeur soit indifférent entre deux candidats. On note l'ensemble des ordres stricts totaux sur et on définit une règle de vote stricte comme une fonction . Les définitions de résultats possibles, manipulable, dictatoriale s'étendent naturellement dans ce cadre.

Pour une règle de vote stricte, la réciproque du théorème de Gibbard-Satterthwaite est vraie. En effet, une règle de vote stricte est dictatoriale si et seulement si elle choisit toujours le candidat préféré du dictateur parmi les résultats possibles ; en particulier, elle ne dépend pas du tout des bulletins des autres électeurs. Par conséquent, elle n'est pas manipulable : le dictateur est parfaitement défendu par son bulletin sincère, et les autres électeurs n'ont aucune influence sur le résultat, donc ils n'ont rien à perdre à voter sincèrement. On obtient donc le résultat d'équivalence suivant.

Corollaire — Si une règle de vote stricte possède au moins 3 résultats possibles, elle est non-manipulable si et seulement si elle est dictatoriale.

Aussi bien dans le théorème que dans le corollaire, on n'a pas besoin de supposer que toute alternative peut être élue. On suppose simplement qu'au moins trois d'entre elles peuvent l'être, c'est-à-dire sont des résultats possibles de la règle de vote. Il est parfaitement possible que d'autres alternatives ne puissent être élues en aucune circonstance : le théorème et le corollaire s'appliquent tout de même. Cependant, le corollaire est parfois présenté sous une forme moins générale[3] : au lieu de supposer que la règle possède au moins trois résultats possibles, on fait parfois l'hypothèse que contient au moins trois éléments et que la règle de vote est surjective, c'est-à-dire que toute alternative peut gagner[4]. La surjectivité est même parfois remplacée par l'hypothèse que la règle soit unanime, au sens où si tous les électeurs préfèrent le même candidat, alors celui-ci doit être élu [5],[6].

Historique[modifier | modifier le code]

L'aspect stratégique de l'acte de vote est déjà bien identifié en 1876 par Charles Dodgson, l'un des pionniers de la théorie du choix social, aussi connu sous le nom de Lewis Carroll. Sa citation (à propos d'un mode de scrutin particulier) a été rendue célèbre par Duncan Black[7] :

"Ce principe de vote fait d'une élection davantage un jeu d'habilité qu'un test réel des souhaits des électeurs."[8]

Au cours des années 1950, Robin Farquharson publie des articles influents sur la question du vote stratégique[9]. Dans un article écrit avec Michael Dummett[10], il conjecture que les règles de vote déterministes avec au moins trois résultats possibles sont confrontées à un problème intrinsèque de vote stratégique[11]. Cette conjecture de Farquharson-Dummett est prouvée indépendamment par Allan Gibbard et Mark Satterthwaite. Dans un article de 1973, Gibbard se base sur le théorème d'Arrow pour prouver le théorème qui porte désormais son nom et il en déduit ensuite le présent résultat, qui en est une conséquence immédiate[1]. Indépendamment, Satterthwaite prouve ce même résultat dans sa thèse de doctorat en 1973, puis la publie sous forme d'article en 1975[2]. Il se base également sur le théorème d'Arrow, mais sans exposer la version plus générale donnée par le théorème de Gibbard. Par la suite, divers auteurs développent des variantes de la preuve, généralement plus directes et plus courtes, soit pour le théorème lui-même, soit pour les corollaires et versions affaiblies mentionnés ci-dessus[4],[5],[6],[12],[13],[14],[15],[16],[17].

Résultats connexes[modifier | modifier le code]

Le théorème de Gibbard permet de considérer des mécanismes de choix collectif qui peuvent être non-ordinaux, c'est-à-dire où l'action d'un électeur ne consiste pas forcément à fournir un ordre de préférence sur les candidats. Le théorème de Gibbard de 1978 et le théorème d'Hylland étendent ces résultats aux mécanismes non-déterministes, c'est-à-dire où le résultat peut non seulement dépendre des bulletins mais aussi comporter une part de hasard.

Le théorème de Duggan-Schwartz[18] étend ce résultat dans une autre direction, en considérant des règles de votes déterministes, mais qui sélectionnent un sous-ensemble non vide des candidats au lieu d'un seul.

Postérité[modifier | modifier le code]

Le théorème de Gibbard-Satterthwaite est généralement présenté comme un résultat de théorie du choix social s'appliquant aux systèmes électoraux, mais il peut également être vu comme le résultat fondateur de la théorie des mécanismes d'incitation, qui s'intéresse à la conception de modalités de prise de décision collective, impliquant éventuellement des transferts monétaires. Noam Nisan présente cette relation ainsi[19] :

"Le théorème de Gibbard-Satterthwaite semble annihiler tout espoir de concevoir des fonctions de choix social qui incitent à révéler ses véritables préférences. Le champ disciplinaire entier de la théorie des mécanismes d'incitation tente d'échapper à ce théorème d'impossibilité en utilisant des modifications variées de ce modèle."[20]

L'idée principale de ces échappatoires est de se limiter à des classes restreintes de préférences, contrairement au théorème de Gibbard-Satterthwaite qui permet des préférences arbitraires. Ainsi, dans cette discipline, on suppose souvent que les agents ont des préférences quasi-linéaires, ce qui signifie que leur fonction d'utilité varie linéairement par rapport à la quantité d'argent. Dans ce cas, des transferts monétaires peuvent être utilisés pour les inciter à agir sincèrement. Cette idée est exploitée dans les enchères de Vickrey-Clarke-Groves.

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

  1. a et b (en) Allan Gibbard, « Manipulation of Voting Schemes : A General Result », Econometrica, vol. 41,‎ , p. 587-601
  2. a et b (en) Mark Allen Satterthwaite, « Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions », Journal of Economic Theory, vol. 10, no 2,‎ , p. 187–217 (DOI 10.1016/0022-0531(75)90050-2)
  3. (en) Tjark Weber, « Alternatives vs. Outcomes: A Note on the Gibbard-Satterthwaite Theorem », Technical report (University Library of Munich),‎ (lire en ligne)
  4. a et b (en) Philip Reny, « Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach », Economics Letters, vol. 70, no 1,‎ , p. 99–105 (lire en ligne)
  5. a et b (en) Jean-Pierre Benoît, « The Gibbard-Satterthwaite Theorem : A Simple Proof », Economics Letters, vol. 69, no 3,‎ , p. 319 –322 (ISSN 0165-1765, lire en ligne)
  6. a et b (en) Arunava Sen, « Another Direct Proof of the Gibbard-Satterthwaite Theorem », Economics Letters, vol. 70, no 3,‎ , p. 381 –385 (ISSN 0165-1765, lire en ligne)
  7. (en) Duncan Black, The theory of committees and elections, Cambridge, University Press,
  8. "This principle of voting makes an election more of a game of skill than a real test of the wishes of the electors."
  9. (en) Robin Farquharson, « Straightforwardness in voting procedures », Oxford Economic Papers, New Series, vol. 8, no 1,‎ , p. 80–89 (JSTOR 2662065)
  10. (en) Michael Dummett et Robin Farquharson, « Stability in voting », Econometrica, vol. 29, no 1,‎ , p. 33–43 (DOI 10.2307/1907685, JSTOR 1907685)
  11. (en) Michael Dummett, « The work and life of Robin Farquharson », Social Choice and Welfare, vol. 25, no 2,‎ , p. 475–483 (DOI 10.1007/s00355-005-0014-x, JSTOR 41106711)
  12. (en) Peter Gärdenfors, « A Concise Proof of Theorem on Manipulation of Social Choice Functions », Public Choice, vol. 32,‎ , p. 137–142 (ISSN 0048-5829, lire en ligne)
  13. (en) Salvador Barberá, « Strategy-Proofness and Pivotal Voters : A Direct Proof of the Gibbard-Satterthwaite Theorem », International Economic Review, vol. 24, no 2,‎ , p. 413–417 (ISSN 0020-6598, lire en ligne)
  14. (en) Michael Dummett, Voting Procedures, Oxford University Press, (ISBN 978-0198761884)
  15. (en) Rudolf Fara et Maurice Salles, « An interview with Michael Dummett: From analytical philosophy to voting analysis and beyond », Social Choice and Welfare, vol. 27, no 2,‎ , p. 347–364 (DOI 10.1007/s00355-006-0128-9, JSTOR 41106783)
  16. (en) Hervé Moulin, Axioms of Cooperative Decision Making, Cambridge University Press, (ISBN 9780521424585, lire en ligne)
  17. (en) Alan D. Taylor, « The manipulability of voting systems », The American Mathematical Monthly, vol. 109,‎ , p. 321–337 (DOI 10.2307/2695497, JSTOR 2695497)
  18. (en) John Duggan et Thomas Schwartz, « Strategic manipulability without resoluteness or shared beliefs : Gibbard-Satterthwaite generalized », Social Choice and Welfare, vol. 17, no 1,‎ , p. 85–93 (ISSN 0176-1714, lire en ligne)
  19. (en) Vijay Vazirani, Noam Nisan, Tim Roughgarden et Éva Tardos, Algorithmic Game Theory, Cambridge, UK, Cambridge University Press, (ISBN 0-521-87282-0), p. 215
  20. "The GS theorem seems to quash any hope of designing incentive-compatible social-choice functions. The whole field of Mechanism Design attempts escaping from this impossibility result using various modifications in the model."

Articles connexes[modifier | modifier le code]