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 .

Propriétés   
 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.

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

Exemple utilisant le classement Copeland :  

A perd à C, donc tous les candidats de A à C (A, B et C) sont confirmés pour être dans l'ensemble Smith. Il y a une comparaison où un candidat déjà confirmé être dans le set Smith perd ou a également avec quelqu'un qui n'a pas été confirmé être dans le set Smith: C perd contre D; il est donc confirmé que D fait partie de l'ensemble Smith. Maintenant, il y a une autre telle confrontation: D a également avec E, donc E est aussi dans l'ensemble Smith. Parce que tous les candidats de A à E ont battu tous les candidats qui n'ont pas été confirmés faire partie de l'ensemble Smith, l'ensemble Smith est désormais confirmé comme étant de les candidats de A à E.

Voir également 

 Critère Condorcet 
 Méthode Condorcet 
 Ensemble de Landau 
 Préordre 
 Ordre partiel

Références 

  
   Introduit une version d'un critère de Condorcet généralisé qui est satisfait lorsque les élections par paire sont basées sur un choix de majorité simple, et pour tout ensemble dominant, tout candidat de l'ensemble est collectivement préféré à tout candidat ne faisant pas partie de l'ensemble. Mais Smith ne discute pas de l'idée d'un plus petit ensemble dominant. 
   Narrows Smith a généralisé le critère Condorcet au plus petit ensemble dominant et l'appelle le principe Condorcet de Smith. 
   Discute de l'ensemble Smith (nommé GETCHA) et de l'ensemble Schwartz (nommé GOTCHA) en tant que normes possibles pour un choix collectif optimal.

Liens externes 
 Exemples d'algorithmes pour calculer l'ensemble de Smith

Algorithme