Théorème de Gibbard

Considérons des électeurs ${\displaystyle 1}$, ${\displaystyle 2}$ et ${\displaystyle 3}$ qui souhaitent choisir ensemble une option parmi trois possibilités ${\displaystyle a}$, ${\displaystyle b}$ et ${\displaystyle 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, ${\displaystyle (1,1,0)}$ est un bulletin autorisé : il signifie que l'électeur approuve les candidats ${\displaystyle a}$ et ${\displaystyle b}$ mais désapprouve le candidat ${\displaystyle 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 ${\displaystyle 1}$ préfère l'option ${\displaystyle a}$, suivie de ${\displaystyle b}$ et enfin ${\displaystyle 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 ${\displaystyle (0,1,1)}$ et ${\displaystyle (1,1,1)}$, alors l'électeur ${\displaystyle 1}$ ne dispose que d'un seul bulletin qui permette de faire élire son alternative préférée ${\displaystyle a}$ : il s'agit de ${\displaystyle (1,0,0)}$.
• Cependant, si on suppose maintenant que les deux autres électeurs votent respectivement ${\displaystyle (0,0,1)}$ et ${\displaystyle (0,1,1)}$, alors l'électeur ${\displaystyle 1}$ n'a pas intérêt à voter ${\displaystyle (1,0,0)}$ car cela conduit à l'élection de ${\displaystyle c}$ ; il devrait plutôt voter ${\displaystyle (1,1,0)}$, ce qui permet de faire élire ${\displaystyle b}$.

En résumé, l'électeur ${\displaystyle 1}$ est placé face à un dilemme de vote stratégique : selon ce que vont voter les autres électeurs, ${\displaystyle (1,0,0)}$ ou ${\displaystyle (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.

On note ${\displaystyle {\mathcal {A}}}$ l'ensemble des alternatives, qu'on pourra également appeler candidats dans un contexte de vote. On note ${\displaystyle {\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 ${\displaystyle i}$, on note ${\displaystyle {\mathcal {S}}_{i}}$ un ensemble qui représente les stratégies disponibles pour l'agent ${\displaystyle i}$ ; on suppose que ${\displaystyle {\mathcal {S}}_{i}}$ est fini. Soit ${\displaystyle g}$ une fonction qui, à tout ${\displaystyle n}$-uplet de stratégies ${\displaystyle (s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \ldots {\mathcal {S}}_{n}}$, associe une alternative. La fonction ${\displaystyle g}$ est ce qu'on appelle un mécanisme[2]. 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 ${\displaystyle g}$ est évident[3] si et seulement si pour tout agent ${\displaystyle i}$ et pour tout ordre strict faible (en) ${\displaystyle P_{i}}$ sur les alternatives, il existe une stratégie ${\displaystyle s_{i}^{*}(P_{i})}$ qui est dominante pour l'agent ${\displaystyle i}$ quand il est muni des préférences ${\displaystyle P_{i}}$ : il n'existe aucun profil de stratégies des autres agents tel qu'une stratégie ${\displaystyle s_{i}}$ différente de ${\displaystyle s_{i}^{*}(P_{i})}$ conduirait à un résultat strictement meilleur (au sens de ${\displaystyle 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 ${\displaystyle i}$ a identifié ses préférences ${\displaystyle P_{i}}$, il peut choisir une stratégie ${\displaystyle 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 ${\displaystyle g({\mathcal {S}})}$ l'image de ${\displaystyle g}$, c'est-à-dire l'ensemble des résultats possibles du mécanisme. Ainsi, on dit que ${\displaystyle g}$ possède au moins 3 résultats possibles si et seulement si ${\displaystyle g({\mathcal {S}})}$ possède au moins 3 éléments. Puisque les ensembles de stratégies sont finis, ${\displaystyle 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 ${\displaystyle g}$ est dictatorial si et seulement s'il existe un agent ${\displaystyle i}$ qui est un dictateur, c'est-à-dire que pour tout résultat possible ${\displaystyle a\in g({\mathcal {S}})}$, l'agent ${\displaystyle i}$ dispose d'une stratégie ${\displaystyle s_{i}^{*}(a)}$ qui assure que le résultat est ${\displaystyle a}$, quelles que soient les stratégies des autres agents.

• Théorème de Gibbard-Satterthwaite