Le théorème de Gibbard - Gibbard's theorem

Dans les domaines de la conception de mécanismes et de la théorie du choix social , le théorème de Gibbard est un résultat prouvé par le philosophe Allan Gibbard en 1973. Il stipule que pour tout processus déterministe de décision collective, au moins l'une des trois propriétés suivantes doit être vérifiée :

1. Le processus est dictatorial , c'est-à-dire qu'il existe un agent distingué qui peut imposer le résultat ;
2. Le processus limite les résultats possibles à deux options seulement ;
3. Le processus est ouvert au vote stratégique : une fois qu'un agent a identifié ses préférences, il est possible qu'il n'ait à sa disposition aucune action qui défende au mieux ces préférences indépendamment des actions des autres agents.

Un corollaire de ce théorème est le théorème de Gibbard-Satterthwaite sur les règles de vote. La principale différence entre les deux est que le théorème de Gibbard-Satterthwaite est limité aux règles de vote classées (ordinales) : l'action d'un électeur consiste à donner un classement de préférence sur les options disponibles. Le théorème de Gibbard est plus général et considère des processus de décision collective qui peuvent ne pas être ordinaux : par exemple, les systèmes de vote où les électeurs attribuent des notes aux candidats. Le théorème de Gibbard peut être prouvé en utilisant le théorème d'impossibilité d'Arrow .

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 de Hylland , qui étendent ces résultats aux processus non déterministes, c'est-à-dire où le résultat peut non seulement dépendre des actions des agents mais peut également impliquer un élément de hasard.

Aperçu

Considérons quelques électeurs , et qui souhaitent sélectionner une option parmi trois alternatives : , et . Supposons qu'ils utilisent le vote d'approbation : chaque votant attribue à chaque candidat la note 1 (approbation) ou 0 (refus d'approbation). Par exemple, est un scrutin autorisé : cela signifie que l'électeur approuve les candidats et mais n'approuve pas le candidat . Une fois les bulletins de vote recueillis, le candidat ayant obtenu la note totale la plus élevée est déclaré vainqueur. Les égalités entre les candidats sont rompues par ordre alphabétique : par exemple, s'il y a égalité entre les candidats et , alors l' emporte. ${\style d'affichage 1}$${\style d'affichage 2}$${\style d'affichage 3}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage c}$${\style d'affichage (1,1,0)}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage c}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage a}$

Supposons que l'électeur préfère l'alternative , alors et puis . Quel scrutin défendra le mieux ses opinions ? Par exemple, considérons les deux situations suivantes. ${\style d'affichage 1}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage c}$

• Si les deux autres votants votent respectivement et , alors l'électeur n'a qu'un seul bulletin qui conduit à l'élection de son alternative préférée  : .${\style d'affichage (0,1,1)}$${\style d'affichage (1,1,1)}$${\style d'affichage 1}$${\style d'affichage a}$${\style d'affichage (1,0,0)}$
• Cependant, si l'on suppose plutôt que les deux autres votants ont respectivement voté et , alors l'électeur ne devrait pas voter car il fait gagner ; elle devrait plutôt voter» , ce qui fait gagner.${\style d'affichage (0,0,1)}$${\style d'affichage (0,1,1)}$${\style d'affichage 1}$${\style d'affichage (1,0,0)}$${\style d'affichage c}$${\style d'affichage (1,1,0)}$${\style d'affichage b}$

Pour résumer, l'électeur fait face à un dilemme de vote stratégique : selon les bulletins que les autres électeurs vont voter, ou peut être un bulletin qui défend le mieux ses opinions. On dit alors que le vote par approbation n'est pas à l'épreuve des stratégies : une fois que l'é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 ; elle doit agir de manière stratégique, éventuellement en espionnant les autres électeurs pour déterminer comment ils ont l'intention de voter. ${\style d'affichage 1}$${\style d'affichage (1,0,0)}$${\style d'affichage (1,1,0)}$

Le théorème de Gibbard stipule qu'un processus déterministe de décision collective ne peut pas être à l'épreuve de la stratégie, sauf peut-être dans deux cas : s'il existe un agent distingué qui a un pouvoir dictatorial, ou si le processus limite le résultat à deux options possibles seulement.

Déclaration formelle

Soit l'ensemble des alternatives , que l'on peut aussi appeler candidats dans un contexte de vote. Soit l'ensemble des agents , qui peuvent aussi être appelés joueurs ou votants, selon le contexte d'application. Pour chaque agent , soit un ensemble qui représente les stratégies disponibles pour l' agent ; supposons que ce soit fini. Soit une fonction qui, à chaque -uplet de stratégies , mappe une alternative. La fonction est appelée une forme de jeu . En d'autres termes, une forme de jeu est essentiellement définie comme un jeu à n joueurs , mais sans utilités associées aux résultats possibles : elle décrit uniquement la procédure, sans préciser a priori le gain que chaque agent tirerait de chaque résultat. ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {N}}=\{1,\ldots ,n\}}$${\style d'affichage i}$${\displaystyle {\mathcal {S}}_{i}}$${\style d'affichage i}$${\displaystyle {\mathcal {S}}_{i}}$${\style d'affichage g}$${\style d'affichage n}$${\displaystyle (s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}}$${\style d'affichage g}$

On dit qu'il est à l' épreuve des stratégies (appelé à l'origine : simple ) si pour tout agent et pour tout ordre faible strict sur les alternatives, il existe une stratégie qui est dominante pour l'agent lorsqu'il a des préférences : il n'y a pas de profil de stratégies pour les autres agents tel qu'une autre stratégie , différente de , conduirait à un résultat strictement meilleur (au sens de ). Cette propriété est souhaitable pour un processus de décision démocratique : cela signifie qu'une fois que l'agent a identifié ses propres préférences , il peut choisir une stratégie 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. ${\style d'affichage g}$${\style d'affichage i}$ ${\style d'affichage P_{i}}$${\style d'affichage s_{i}^{*}(P_{i})}$${\style d'affichage i}$${\style d'affichage P_{i}}$${\style d'affichage s_{i}}$${\style d'affichage s_{i}^{*}(P_{i})}$${\style d'affichage P_{i}}$${\style d'affichage i}$${\style d'affichage P_{i}}$${\style d'affichage s_{i}^{*}(P_{i})}$

On note et on note par l'intervalle de , c'est-à-dire l'ensemble des issues possibles de la forme de jeu. Par exemple, nous disons que a au moins 3 résultats possibles si et seulement si la cardinalité de est 3 ou plus. Puisque les ensembles de stratégies sont finis, est fini aussi ; ainsi, même si l'ensemble des alternatives n'est pas supposé fini, le sous-ensemble des résultats possibles l' est nécessairement. ${\displaystyle {\mathcal {S}}={\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}}$${\displaystyle g({\mathcal {S}})}$${\style d'affichage g}$${\style d'affichage g}$${\displaystyle g({\mathcal {S}})}$${\displaystyle g({\mathcal {S}})}$${\displaystyle {\mathcal {A}}}$${\displaystyle g({\mathcal {S}})}$

On dit que c'est dictatorial s'il existe un agent qui est dictateur , en ce sens que pour toute issue possible , l'agent dispose d'une stratégie qui assure que le résultat est , quelles que soient les stratégies choisies par les autres agents. ${\style d'affichage g}$${\style d'affichage i}$${\displaystyle a\in g({\mathcal {S}})}$${\style d'affichage i}$${\style d'affichage a}$

Exemples

La dictature en série

Nous supposons que chaque électeur communique un ordre strict et faible sur les candidats. La dictature en série est définie comme suit. Si l'électeur 1 a un candidat unique le plus apprécié, alors ce candidat est élu. Sinon, les résultats possibles sont limités à ses candidats ex-aequo les plus appréciés et les autres candidats sont éliminés. Ensuite, le bulletin de vote de l'électeur 2 est examiné : s'il a un seul candidat le plus apprécié parmi les non-éliminés, alors ce candidat est élu. Sinon, la liste des résultats possibles est à nouveau réduite, etc. S'il y a encore plusieurs candidats non éliminés après examen de tous les bulletins de vote, alors une règle de départage arbitraire est utilisée.

Cette forme de jeu est à l'épreuve de la stratégie : quelles que soient les préférences d'un électeur, il a une stratégie dominante qui consiste à déclarer son ordre de préférence sincère. Il est aussi dictatorial, et son dictateur est électeur 1 : s'il souhaite voir son candidat élu, il lui suffit alors de communiquer un ordre de préférence où est l'unique candidat le plus apprécié. ${\style d'affichage a}$${\style d'affichage a}$

Vote à la majorité simple

S'il n'y a que 2 résultats possibles, une forme de jeu peut être à l'épreuve de la stratégie et non dictatoriale. Par exemple, c'est le cas du vote à la majorité simple : chaque votant vote pour son alternative la plus appréciée (parmi les deux issues possibles), et l'alternative ayant le plus de votes est déclarée gagnante. Cette forme de jeu est à l'épreuve des stratégies car il est toujours optimal de voter pour son alternative la plus appréciée (sauf si l'on est indifférent entre elles). Cependant, il n'est clairement pas dictatorial. De nombreuses autres formes de jeu sont à l'épreuve des stratégies et non dictatoriales : par exemple, supposons que l'alternative gagne si elle obtient les deux tiers des voix, et gagne autrement. ${\style d'affichage a}$${\style d'affichage b}$

Une forme de jeu montrant que l'inverse ne tient pas

Considérez la forme de jeu suivante. L'électeur 1 peut voter pour un candidat de son choix ou s'abstenir. Dans le premier cas, le candidat spécifié est automatiquement élu. Sinon, les autres votants utilisent une règle de vote classique, par exemple le dépouillement Borda . Cette forme de jeu est clairement dictatoriale, car l'électeur 1 peut imposer le résultat. Cependant, il n'est pas à l'épreuve de la stratégie : les autres électeurs sont confrontés au même problème de vote stratégique que dans le décompte habituel de Borda. Ainsi, le théorème de Gibbard est une implication et non une équivalence.

Notes et références

Voir également

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