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
[modifier | modifier le code]- 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, soit à cause de liens par paires[incompréhensible], 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
[modifier | modifier le code]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 | B | C | ré | E | F | g | |
|---|---|---|---|---|---|---|---|
| A | --- | Gagner | Perdre | Gagner | Gagner | Gagner | Gagner |
| B | Perdre | --- | Gagner | Gagner | Gagner | Gagner | Gagner |
| C | Gagner | Perdre | --- | Perdre | Gagner | Gagner | Gagner |
| ré | Perdre | Perdre | Gagner | --- | Également | Gagner | Gagner |
| E | Perdre | Perdre | Perdre | Également | --- | Gagner | Gagner |
| F | Perdre | Perdre | Perdre | Perdre | Perdre | --- | Gagner |
| g | Perdre | Perdre | Perdre | Perdre | Perdre | Perdre | --- |
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
[modifier | modifier le code]- Critère Condorcet
- Méthode Condorcet
- Ensemble de Landau
- Préordre
- Ordre partiel
Références
[modifier | modifier le code]- Ward, Benjamin, « Majority Rule and Allocation », Journal of Conflict Resolution, vol. 5, no 4, , p. 379–389 (DOI 10.1177/002200276100500405)
- Smith, J.H., « Aggregation of Preferences with Variable Electorates », Econometrica, The Econometric Society, vol. 41, no 6, , p. 1027–1041 (DOI 10.2307/1914033, JSTOR 1914033) 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.
- Fishburn, Peter C., « Condorcet Social Choice Functions », SIAM Journal on Applied Mathematics, vol. 33, no 3, , p. 469–489 (DOI 10.1137/0133030) Narrows Smith a généralisé le critère Condorcet au plus petit ensemble dominant et l'appelle le principe Condorcet de Smith.
- Thomas Schwartz, The Logic of Collective Choice, New York, Columbia University Press, Discute de l'ensemble Smith (nommé GETCHA) et de l'ensemble Schwartz (nommé GOTCHA) en tant que normes possibles pour un choix collectif optimal.
