Théorème de Gibbard-Satterthwaite

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 et l'économiste Mark Satterthwaite en 1975. 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

Considérons des électeurs $1$, $2$ et $3$ qui souhaitent choisir ensemble une option parmi quatre candidats $a$, $b$, $c$ et $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.$${\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 $1$ préfère $a$, suivi de $b$, $c$ et $d$ ; les électeurs $2$ et $3$ préfèrent chacun $c$, suivi de $b$, $d$ et $a$. Si les électeurs votent sincèrement, alors les scores sont les suivants : $(a:3,b:6,c:7,d:2)$. C'est donc $c$ qui est élu, avec 7 points.

Mais l'électeur $1$ peut s'apercevoir qu'un autre bulletin défend mieux ses opinions. Supposons qu'il modifie son bulletin pour aboutir à la situation suivante.$${\begin{array}{c|c|c}b&c&c\\a&b&b\\d&d&d\\c&a&a\end{array}}$$L'électeur $1$ a stratégiquement remonté le candidat $b$ et descendu le candidat $c$. Les nouveaux scores sont : $(a:2,b:7,c:6,d:3)$. C'est donc $b$ qui est élu. L'électeur $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 $b$ plutôt que $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.

Énoncé du théorème

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

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

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

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

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

Dictature en série

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

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 inscrite 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 $a$ gagne si elle reçoit deux tiers des voix et que $b$ gagne dans le cas contraire.

Un mécanisme qui montre que la réciproque n'est pas vraie

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

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

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 : au lieu de supposer que la règle possède au moins trois résultats possibles, on fait parfois l'hypothèse que ${\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. 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 .

Historique

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 :

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

Au cours des années 1950, Robin Farquharson publie des articles influents sur la question du vote stratégique. Dans un article écrit avec Michael Dummett, 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. 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. 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. 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.

Résultats connexes

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

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 :

"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."

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.

Articles connexes

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