Théorème de Gibbard-Satterthwaite

Considérons des électeurs ${\displaystyle 1}$, ${\displaystyle 2}$ et ${\displaystyle 3}$ qui souhaitent choisir ensemble une option parmi quatre candidats ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$ et ${\displaystyle d}$. 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.

$${\displaystyle {\begin{array}{c|c|c}a&c&c\\b&b&b\\c&d&d\\d&a&a\end{array}}}$$

Cette notation signifie que l'électeur ${\displaystyle 1}$ préfère ${\displaystyle a}$, suivi de ${\displaystyle b}$, ${\displaystyle c}$ et ${\displaystyle d}$ ; les électeurs ${\displaystyle 2}$ et ${\displaystyle 3}$ préfèrent chacun ${\displaystyle c}$, suivi de ${\displaystyle b}$, ${\displaystyle d}$ et ${\displaystyle a}$. Si les électeurs votent sincèrement, alors les scores sont les suivants : ${\displaystyle (a:3,b:6,c:7,d:2)}$. C'est donc ${\displaystyle c}$ qui est élu, avec 7 points. Mais l'électeur ${\displaystyle 1}$ peut s'apercevoir qu'un autre bulletin défend mieux ses opinions. Supposons qu'il modifie son bulletin pour aboutir à la situation suivante.

$${\displaystyle {\begin{array}{c|c|c}b&c&c\\a&b&b\\d&d&d\\c&a&a\end{array}}}$$

L'électeur ${\displaystyle 1}$ a stratégiquement remonté le candidat ${\displaystyle b}$ et descendu le candidat ${\displaystyle c}$. Les nouveaux scores sont : ${\displaystyle (a:2,b:7,c:6,d:3)}$. C'est donc ${\displaystyle b}$ qui est élu. L'électeur ${\displaystyle 1}$ 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 ${\displaystyle b}$ plutôt que ${\displaystyle c}$, 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.

On note ${\displaystyle {\mathcal {A}}}$ 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 ${\displaystyle {\mathcal {N}}=\{1,\ldots ,n\}}$ l'ensemble des électeurs. On note ${\displaystyle {\mathcal {P}}}$ l'ensemble des ordres stricts faibles (en) sur ${\displaystyle {\mathcal {A}}}$ : 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 ${\displaystyle f:{\mathcal {P}}^{n}\to {\mathcal {A}}}$. Elle prend pour argument un profil de préférences ${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$ et renvoie un candidat vainqueur.

On dit que ${\displaystyle f}$ est manipulable si et seulement s'il existe un profil ${\displaystyle (P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}}$ où un certain électeur ${\displaystyle i}$, en changeant son bulletin ${\displaystyle P_{i}}$ pour un autre bulletin ${\displaystyle P_{i}'}$, peut obtenir un résultat qu'il préfère (au sens de ${\displaystyle P_{i}}$).

On note ${\displaystyle f({\mathcal {P}}^{n})}$ l'image de ${\displaystyle f}$, c'est-à-dire l'ensemble des résultats possibles de l'élection. Ainsi, on dit que ${\displaystyle f}$ possède au moins trois résultats possibles si et seulement si ${\displaystyle f({\mathcal {P}}^{n})}$ possède au moins trois éléments.

On dit que ${\displaystyle f}$ est dictatoriale si et seulement s'il existe un électeur ${\displaystyle i}$ 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.

On s'intéresse maintenant au cas où on interdit par hypothèse qu'un électeur soit indifférent entre deux candidats. On note ${\displaystyle {\mathcal {L}}}$ l'ensemble des ordres stricts totaux sur ${\displaystyle {\mathcal {A}}}$ et on définit une règle de vote stricte comme une fonction ${\displaystyle f:{\mathcal {L}}^{n}\to {\mathcal {A}}}$. 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.

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 ${\displaystyle {\mathcal {A}}}$ 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].

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'habileté 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].

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.

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.

• Théorème de Gibbard
• Théorème d'impossibilité d'Arrow

• Portail de l’économie
• Portail de la philosophie
• Portail de la politique