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, 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

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 :

Les pertes et les égalements sont en gras
A B C E F g
A --- Gagner Perdre Gagner Gagner Gagner Gagner
B Perdre --- Gagner Gagner Gagner Gagner Gagner
C Gagner Perdre --- Perdre Gagner Gagner Gagner
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

Références

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

Liens externes

Read other articles:

Esmé BiancoBianco pada 2014LahirEsmé Augusta Bianco25 Mei 1982 (umur 41)St. Albans, Hertfordshire, InggrisKebangsaanInggrisPekerjaanAktris, model, DJTahun aktif2007–sekarang Esmé Augusta Bianco (lahir 25 Mei 1982) adalah seorang aktris, model, pengisi suara dan DJ asal Inggris. Ia dikenal karena berperan sebagai Ros dalam Game of Thrones. Referensi Skin Two, Issue 43, Spring 2003 Daily Mirror, November 25, 2003 Liverpool Echo, December 17, 2003 Forum, Vol 38 No 11, 2004 The Ti...

 

 

Japanese band the GazettEThe Gazette performing at the PlayStation Theater on April 29, 2016Background informationAlso known asGazette (ガゼット)OriginKanagawa, JapanGenres Alternative metal[1] hard rock[2] nu metal[3] industrial metal[2] metalcore[4] punk rock[5] Years active2002–presentLabels Matina King PS Company CLJ Sony Music JPU Youkai MembersRukiUruhaAoiReitaKaiPast membersYuneWebsitethe-gazette.com The Gazette (stylized as the Gaz...

 

 

Radio station in Rhinelander, Wisconsin WRHNRhinelander, WisconsinFrequency100.1 MHzBranding100.1 Jack FMProgrammingFormatAdult hitsAffiliationsFox News RadioJack FM networkOwnershipOwnerNRG Media(NRG License Sub, LLC)Sister stationsWHDG, WLKD, WMQA-FM, WOBT, WRLO-FMHistoryFirst air date1966Call sign meaningW RHiNelanderTechnical informationFacility ID49800ClassC1ERP100,000 wattsHAAT89 meters (292 ft)Transmitter coordinates45°37′41.8″N 89°23′38.5″W / 45.628278°...

Pour les articles homonymes, voir Ramillies. Cet article est une ébauche concernant une localité brabançonne wallonne. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Ramillies Vue générale du village, avec l'église Saint-Martin Héraldique Administration Pays Belgique Région  Région wallonne Communauté  Communauté française Province  Province du Brabant wallon Arrondissement Nivelles B...

 

 

Defunct Philippine military-police force This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Philippine Constabulary – news · newspapers · books · scholar · JSTOR (June 2020) (Learn how and when to remove this template message) Philippine ConstabularyHukbóng Pamayapà ng Pilipinas Insignia of the Philippine Con...

 

 

Department in Provence-Alpes-Côte d'Azur, France Department of France in Provence-Alpes-Côte d'AzurAlpes-Maritimes Aups Maritims (Occitan)Department of FranceClockwise from top: a view on the Mediterranean from Roquebrune-Cap-Martin; Lérins Abbey on Île Saint-Honorat; Saint-Dalmas-le-Selvage; prefecture building in Nice; and Mercantour National Park FlagCoat of armsLocation of Alpes-Maritimes in FranceCoordinates: 43°50′N 7°10′E / 43.833°N 7.167°E / 43...

Oldest public outdoor swimming pool in England Cleveland PoolsLocationBath, Somerset, EnglandCoordinates51°23′27″N 2°20′50″W / 51.3908°N 2.3473°W / 51.3908; -2.3473Area180 square metres (1,900 sq ft)Built1815[1]ArchitectJohn Pinch the elderArchitectural style(s)Georgian Listed Building – Grade II*Designated5 August 1975[1]Reference no.1396146 Location of Cleveland Pools in Somerset Cleveland Pools located in Hampton Row, Bat...

 

 

2018–2020 North-South Korean building Inter-Korean Liaison Office남북공동연락사무소Unification flag of KoreaAgency overviewFormed14 September 2018Dissolved16 June 2020Jurisdiction Korea  North Korea  Republic of Korea HeadquartersKaesong Industrial Region, North Korea37°55′58.7″N 126°37′18.7″E / 37.932972°N 126.621861°E / 37.932972; 126.621861Agency executivesJon Jong-su, North Korea RepresentativeChun Hae-sung, South Korea Represe...

 

 

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl(英文)(波兰文)2020年夏季奥林匹克运动会(東京)2021年7月23日至8月8日(受2019冠状病毒病疫情影响推迟,但仍保留原定名称)運動員206參賽項目24个大项旗手开幕式:帕维尔·科热尼奥夫斯基(游泳)和马娅·沃什乔夫斯卡(自行车)[1]闭幕式:卡罗利娜·纳亚(皮划艇)&#...

Traditionally nomadic groups in Europe A showman's wagon, used for accommodation and transportation There are a number of traditionally itinerant or travelling groups in Europe who are known as Travellers or Gypsies (the latter being increasingly taken as derogatory). The origins of the indigenous itinerant groups are not always clear. The largest of these groups are the Romani people (also Roma or Rom), who have Indian roots and heritage; they left India around 1,500 years ago, entering Euro...

 

 

Conflict fought during the 1877-78 Russo-Turkish war Romanian War of Independence (1877–1878)Part of the Russo-Turkish War of 1877–78Romanian troops returning to Bucharest after the war, 8 October 1878.DateApril 24 [O.S. April 12] 1877 – 3 March 1878 (10 months, 1 week, 2 days)LocationBalkansResult Allied victory Treaty of San Stefano Treaty of BerlinTerritorialchanges Northern Dobruja passed from Ottoman Empire to RomaniaSouthern Bessarabia passed from Romania to Russ...

 

 

Узкоколейный тепловоз ТУ2-008 на Детской железной дороге в Оренбурге Детские железные дороги (ДЖД) — учреждения дополнительного образования детей, в формате которых выстроена уникальная система профориентации школьников на профессии железнодорожного транспорта с по...

Campionati europei di skeleton 2018 Competizione Campionati europei di skeleton Sport Skeleton Edizione XXIV Organizzatore IBSF Date 15 dicembre 2017 Luogo Igls Discipline 2 Impianto/i Olympia Eiskanal Innsbruck Vincitori Skeleton uomini M. Dukurs Skeleton donne E. Nikitina Medagliere Nazione Tot.  Russia 1 1 0 2  Lettonia 1 0 0 1  Germania 0 1 1 2 Cronologia della competizione Winterberg 2017 2019 Manuale I Campionati europei di skeleton 2018, ventiquattresima edizione della ...

 

 

Chương trình phối hợp của Liên Hợp Quốc về HIV và AIDSLoại hìnhNon-governmental organization, Joint ProgrammeTên gọi tắtUNAIDSLãnh đạoUNAIDS Executive Director, a.i. Gunilla CarlssonHiện trạngActiveThành lập26 tháng 7 năm 1994; 29 năm trước (1994-07-26)Trụ sởGeneva, Thụy SĩTrang webunaids.orgTrực thuộcUnited Nations Economic and Social Council Tòa nhà trụ sở UNAIDS tại Geneva, Thụy Sĩ. Chương trình phối h�...

 

 

This template does not require a rating on Wikipedia's content assessment scale.It is of interest to the following WikiProjects:Food and drink Food portalThis template is within the scope of WikiProject Food and drink, a collaborative effort to improve the coverage of food and drink related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Food and drinkWikipedia:WikiProject Food and drinkTemp...

H II region and open cluster in the constellation Centaurus IC 2944Emission nebulaopen clusterObservation data: J2000.0 epochRight ascension11h 36m 36.0sDeclination−63° 02′ 00″Distance6500[1] lyApparent magnitude (V)4.5Apparent dimensions (V)75'[2]ConstellationCentaurusPhysical characteristicsRadius71[1][2] lyNotable featuresopen cluster with nebulosity, Bok globulesDesignationsIC 2944, RCW 62 Running Chicken Nebula, Lambd...

 

 

порЧасБазові концепції Минуле Історія Глибокий час[en] Сьогодення Майбутнє Футурологія Далеке майбутнє Вічність Докази вічності[en] Вічне повернення Безсмертя Вимірювання та еталони[en]Хронометрія[en] Секунда Хвилина Година Доба Тиждень Місяць Рік Тропічний Зоряний Кален...

 

 

Ариабхатахинди आर्यभट्ट Заказчик Индийская организация космических исследований Производитель  Индия Оператор Индийская организация космических исследований[2] Задачи астрофизика Спутник Земли Стартовая площадка Капустин Яр Ракета-носитель Космос-3М Зап�...

Italian philosopher and activist Franco Bifo BerardiBerardi delivering a lecture in 2016.Born (1949-11-02) 2 November 1949 (age 74)Bologna, ItalyNotable workThe Soul at Work: From Alienation to Autonomy (2009)SchoolAutonomist MarxismContinental philosophy Part of a series onCommunism in Italy People Emilio Covelli Carlo Cafiero Errico Malatesta Costantino Lazzari Luigi Galleani Egidio Gennari Nicola Bombacci Amadeo Bordiga Antonio Gramsci Bruno Fortichiari Giuseppe Di Vittorio Palmiro T...

 

 

Valéry Giscard d'Estaing Jean-Bedel Bokassa L’affaire des diamants, ou affaire des diamants de Bokassa, est une affaire politique impliquant l'ancien président de la République française Valéry Giscard d'Estaing et l'ancien président puis empereur de Centrafrique Jean-Bedel Bokassa. L’affaire, emblématique du journalisme d'investigation et de la protection des sources d'information, débute en octobre 1979 à la suite de révélations du Canard enchaîné selon lesquelles le prés...