Théorème de Gibbard

En théorie des mécanismes d'incitation et en théorie du choix social, le théorème de Gibbard est un résultat prouvé par le philosophe Allan Gibbard en 1973. Il montre que tout mécanisme déterministe de choix collectif vérifie au moins l'une des propriétés suivantes :

1. Le mécanisme est dictatorial, c'est-à-dire qu'il y a un participant privilégié qui peut imposer le résultat ; ou
2. Le mécanisme ne permet de choisir qu'entre 2 options différentes ; ou
3. Le mécanisme oblige les agents à raisonner de manière stratégique : une fois qu'un participant a identifié ses préférences, il ne dispose pas d'une action qui défende au mieux ses opinions dans toutes les situations.

Ce théorème a pour corollaire le théorème de Gibbard-Satterthwaite sur les règles de vote. La principale différence entre les deux théorèmes est que celui de Gibbard-Satterthwaite 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.

Le théorème de Gibbard est lui-même généralisé par le théorème de Gibbard de 1978 et le théorème d'Hylland, qui é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 participants mais aussi comporter une part de hasard.

Présentation

Considérons des électeurs $1$, $2$ et $3$ qui souhaitent choisir ensemble une option parmi trois possibilités $a$, $b$ et $c$. Ils ont décidé d'utiliser le vote par approbation : chaque électeur attribue à chaque candidat la note 1 (approbation) ou 0 (désapprobation). Par exemple, $(1,1,0)$ est un bulletin autorisé : il signifie que l'électeur approuve les candidats $a$ et $b$ mais désapprouve le candidat $c$. Une fois les bulletins collectés, le candidat qui possède la plus grande note totale est élu. En cas d'égalité, on départage les candidats ex aequo en choisissant le premier dans l'ordre alphabétique.

Supposons que l'électeur $1$ préfère l'option $a$, suivie de $b$ et enfin $c$. Quel bulletin défend au mieux ses opinions ? À titre d'exemple, considérons les deux situations suivantes.

• Si les deux autres électeurs votent respectivement $(0,1,1)$ et $(1,1,1)$, alors l'électeur $1$ ne dispose que d'un seul bulletin qui permette de faire élire son alternative préférée $a$ : il s'agit de $(1,0,0)$.
• Cependant, si on suppose maintenant que les deux autres électeurs votent respectivement $(0,0,1)$ et $(0,1,1)$, alors l'électeur $1$ n'a pas intérêt à voter $(1,0,0)$ car cela conduit à l'élection de $c$ ; il devrait plutôt voter $(1,1,0)$, ce qui permet de faire élire $b$.

En résumé, l'électeur $1$ est placé face à un dilemme de vote stratégique : selon ce que vont voter les autres électeurs, $(1,0,0)$ ou $(1,1,0)$ peut s'avérer un bulletin qui défend mieux ses opinions. On dit alors que le vote par approbation n'est pas évident : une fois qu'un électeur a identifié ses propres préférences, il ne dispose pas d'un bulletin qui défende au mieux ses opinions dans toutes les situations.

Malheureusement, le théorème de Gibbard montre qu'un mécanisme ne peut pas être évident, sauf éventuellement dans deux cas : s'il y a un participant privilégié qui dispose d'un pouvoir dictatorial, ou si le mécanisme ne permet de choisir qu'entre deux décisions possibles.

Énoncé du théorème

On note ${\mathcal {A}}$ l'ensemble des alternatives, qu'on pourra également appeler candidats dans un contexte de vote. On note ${\mathcal {N}}=\{1,\ldots ,n\}$ l'ensemble des agents, qu'on pourra également appeler joueurs ou électeurs selon le contexte d'application. Pour chaque agent $i$, on note ${\mathcal {S}}_{i}$ un ensemble qui représente les stratégies disponibles pour l'agent $i$ ; on suppose que ${\mathcal {S}}_{i}$ est fini. Soit $g$ une fonction qui, à tout $n$-uplet de stratégies $(s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \ldots {\mathcal {S}}_{n}$, associe une alternative. La fonction $g$ est ce qu'on appelle un mécanisme. Autrement dit, un mécanisme est essentiellement défini comme un jeu, mais sans utilités associées aux résultats possibles : il décrit uniquement la procédure utilisée, sans spécifier a priori les gains des différents agents en fonction du résultat.

On dit que $g$ est évident si et seulement si pour tout agent $i$ et pour tout ordre strict faible (en) $P_{i}$ sur les alternatives, il existe une stratégie $s_{i}^{*}(P_{i})$ qui est dominante pour l'agent $i$ quand il est muni des préférences $P_{i}$ : il n'existe aucun profil de stratégies des autres agents tel qu'une stratégie $s_{i}$ différente de $s_{i}^{*}(P_{i})$ conduirait à un résultat strictement meilleur (au sens de $P_{i}$). Cette propriété est très souhaitable pour un processus de décision démocratique : elle signifie qu'une fois qu'un agent $i$ a identifié ses préférences $P_{i}$, il peut choisir une stratégie $s_{i}^{*}(P_{i})$ qui défend au mieux ses préférences, sans avoir besoin de connaître ou de deviner les stratégies choisies par les autres agents.

On note $g({\mathcal {S}})$ l'image de $g$, c'est-à-dire l'ensemble des résultats possibles du mécanisme. Ainsi, on dit que $g$ possède au moins 3 résultats possibles si et seulement si $g({\mathcal {S}})$ possède au moins 3 éléments. Puisque les ensembles de stratégies sont finis, $g({\mathcal {S}})$ l'est également ; ainsi, même si l'ensemble des alternatives n'est pas supposé fini, le sous-ensemble de celles qui peuvent effectivement être choisies l'est.

On dit que $g$ est dictatorial si et seulement s'il existe un agent $i$ qui est un dictateur, c'est-à-dire que pour tout résultat possible $a\in g({\mathcal {S}})$, l'agent $i$ dispose d'une stratégie $s_{i}^{*}(a)$ qui assure que le résultat est $a$, quelles que soient les stratégies des autres agents.

Théorème de Gibbard — Si un mécanisme est évident et s'il possède au moins 3 résultats possibles, alors il est dictatorial.

Exemples

Dictature en série

On suppose que chaque électeur fournit un ordre strict faible (en) sur les candidats. 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 possible, etc. S'il reste encore plusieurs candidats en lice après avoir consulté tous les bulletins, on utilise une règle de départage arbitraire.

Le mécanisme est évident : quelles que soient les préférences d'un électeur, il possède une stratégie dominante qui consiste à annoncer son ordre de préférence sincère. Il est également dictatorial, et son dictateur est l'électeur 1 : s'il souhaite faire gagner l'alternative $a$, il lui suffit de communiquer un ordre de préférence où $a$ est seul en tête.

Vote majoritaire simple

S'il y a seulement 2 résultats possibles, un mécanisme peut être évident sans pour autant être dictatorial. C'est le cas, par exemple, du vote majoritaire simple : chaque électeur vote pour son alternative préférée (parmi les deux résultats possibles), et l'alternative qui reçoit le plus de voix est élue. Ce mécanisme est évident car il est toujours optimal de voter pour son alternative préférée (quand on en a une). Cependant, il n'est clairement pas dictatorial. De nombreux autres mécanismes sont évidents et non dictatoriaux : 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 le mécanisme suivant. L'électeur 1 peut citer le nom d'un candidat ou s'abstenir. Dans le premier cas, le candidat concerné est automatiquement élu. Dans le cas contraire, les autres électeurs utilisent un système de vote usuel, par exemple la méthode Borda. Le mécanisme ainsi décrit est clairement dictatorial, puisque l'électeur 1 a la possibilité d'imposer le résultat. Cependant, il n'est pas évident : les autres électeurs sont confrontés aux mêmes questions de vote stratégique que dans la méthode Borda usuelle. Ainsi, le théorème de Gibbard est bien une implication et non une équivalence.

Article connexe

• Théorème de Gibbard-Satterthwaite