Ensemble de Smith

Dans les systèmes de vote, l'ensemble de Smith, nommé d'après John H. Smith, mais également connu sous le nom de cycle supérieur, ou comme GETCHA (Generalized Top-Choice Assumption en anglais), est le plus petit ensemble non vide de candidats dans une élection particulière de telle sorte que chaque membre bat chaque candidat en dehors de l'ensemble lors d'une élection par paires. L'ensemble de Smith fournit une norme de choix optimal pour un résultat électoral. Les systèmes de vote qui élisent toujours un candidat de l'ensemble Smith satisfont au critère de Smith et sont dits «Smith-efficient». Un ensemble de candidats où chaque membre de l'ensemble bat par paire chaque membre en dehors de l'ensemble est connu comme un ensemble dominant . L'ensemble de Smith existe toujours et est bien défini. Il n'y a qu'un plus petit ensemble dominant car les ensembles dominants sont imbriqués et non vides et l'ensemble des candidats est fini. L'ensemble Smith peut avoir plus d'un candidat, , ou à cause de cycles, comme dans le paradoxe de Condorcet. Le vainqueur de Condorcet, s'il en existe un, est le seul membre de l'ensemble de Smith. S'il existe de faibles gagnants Condorcet, ils font partie de l'ensemble de Smith. L'ensemble Smith est toujours un sous-ensemble de l'ensemble de candidats préféré par la majorité mutuelle, s'il en existe un. L'ensemble Smith peut être calculé avec l'algorithme Floyd – Warshall dans le temps Θ . Il peut également être calculé en utilisant une version de l'algorithme de Kosaraju ou de l'algorithme de Tarjan dans le temps Θ . Il peut également être trouvé en créant une matrice de comparaison par paires avec les candidats classés par leur nombre de victoires par paire moins les défaites par paire (un classement selon la méthode Copeland ), puis en recherchant le plus petit carré de cellules en haut à gauche qui peut être couvert tel que toutes les cellules à droite de ces cellules affichent des victoires par paires. Tous les candidats nommés à gauche de ces cellules sont dans l'ensemble Smith.