Smith asetettu
Vuonna äänestysjärjestelmiä The Smith joukko , joka on nimetty John H. Smith, mutta tunnetaan myös ylemmät syklin , tai Getcha ( Generalized Top-Choice Olettamus ), on pienin joukko ei mitätön ehdokkaiden tietyllä vaaleissa niin, että kukin jäsen voittaa kaikki ehdokkaat ryhmän ulkopuolella parivalinnoissa. Smith-sarja tarjoaa optimaalisen valintastandardin vaalitulokselle. Äänestysjärjestelmät, jotka valitsevat aina ehdokkaan Smith-joukosta, täyttävät Smith-kriteerin ja sanotaan "Smith-tehokkaiksi".
Ehdokasjoukko, jossa joukon kukin jäsen lyö pareittain jokaista joukon ulkopuolista jäsentä, tunnetaan hallitsevana joukkona .
Ominaisuudet
- Smith-joukko on edelleen olemassa ja hyvin määritelty. On vain yksi pienempi hallitseva joukko, koska hallitsevat joukot ovat sisäkkäisiä eikä tyhjiä ja ehdokasjoukko on rajallinen.
- Smith-joukolla voi olla useampi kuin yksi ehdokas joko pareittain tapahtuvien tasausten tai jaksojen takia, kuten Condorcetin paradoksissa .
- Condorcet voittaja , jos sellainen on olemassa, on ainoa jäsen Smithin ensemble. Jos on heikkoja Condorcetin voittajia , he ovat Smith-sarjassa.
- Smith-joukko on aina osajoukko keskinäisen enemmistön ensisijaisesta ehdokasjoukosta, jos sellainen on olemassa.
Algoritmit
Smith-joukko voidaan laskea Floyd - Warshall -algoritmilla ajan myötä Θ . Se voidaan myös laskea käyttämällä versiota algoritmi on Kosaraju tai Tarjan algoritmin ajan Θ .
Se löytyy myös luomalla parikohtainen vertailumatriisi kilpailijoiden kanssa, jotka on järjestetty parien voittojen lukumäärällä miinus parihäviöt ( Copeland-menetelmän sijoitus ) ja etsimällä sitten ylhäältä vasemmalle pienintä solujen neliötä, joka voidaan peittää siten, että kaikilla solujen oikealla puolella olevilla soluilla on voittoja pareittain. Kaikki näiden solujen vasemmalla puolella nimetyt ehdokkaat ovat Smith-joukossa.
Esimerkki Copeland-sijoituksen käytöstä:
| AT | B | VS | re | E | F | g | |
|---|---|---|---|---|---|---|---|
| AT | --- | Voittaa | Menettää | Voittaa | Voittaa | Voittaa | Voittaa |
| B | Menettää | --- | Voittaa | Voittaa | Voittaa | Voittaa | Voittaa |
| VS | Voittaa | Menettää | --- | Menettää | Voittaa | Voittaa | Voittaa |
| re | Menettää | Menettää | Voittaa | --- | Myös | Voittaa | Voittaa |
| E | Menettää | Menettää | Menettää | Myös | --- | Voittaa | Voittaa |
| F | Menettää | Menettää | Menettää | Menettää | Menettää | --- | Voittaa |
| g | Menettää | Menettää | Menettää | Menettää | Menettää | Menettää | --- |
A häviää C: lle, joten kaikki ehdokkaat A: sta C: hen (A, B ja C) vahvistetaan olevan Smith-joukko. On vertailu, jossa ehdokas, joka on jo vahvistettu olevan Smith-joukossa, menettää tai on myös jonkun kanssa, jonka ei ole vahvistettu olevan Smith-joukossa: C häviää D: lle; sen vuoksi vahvistetaan, että D on osa Smith-sarjaa. Nyt on toinen tällainen vastakkainasettelu: D on myös E: n kanssa, joten E on myös Smith-sarjassa. Koska kaikki ehdokkaat A: sta E: hen kukistivat kaikki ehdokkaat, joiden ei vahvistettu olevan osa Smith-sarjaa, Smith-joukko on nyt vahvistettu ehdokkaista A: sta E: hen.
Katso myös
- Condorcet-kriteeri
- Condorcet-menetelmä
- Lastenvaunusetti
- Ennakkotilaus
- Osittainen järjestys
Viitteet
- Ward, Benjamin, ” enemmistösääntö ja allokaatio ”, Journal of Conflict Resolution , voi. 5, n o 4,1961, s. 379–389 ( DOI 10.1177 / 002200276100500405 )
- Smith, JH, ” Aggregation of Preferences with Variable Electorates ”, Econometrica , The Econometric Society, voi. 41, n ° 6,1973, s. 1027–1041 ( DOI 10.2307 / 1914033 , JSTOR 1914033 ) Esittää version yleistetystä Condorcet-kriteeristä, joka täyttyy, kun parivalinnat perustuvat yksinkertaiseen enemmistövalintaan, ja minkä tahansa hallitsevan joukon kohdalla joukko-ehdokkaita suositaan yhdessä muiden kuin ehdokkaiden kanssa. Mutta Smith ei keskustele ajatuksesta pienemmästä hallitsevasta joukosta.
- Fishburn, Peter C., " Condorcet Social Choice Functions ", SIAM Journal of Applied Mathematics , voi. 33, n ° 3,1977, s. 469–489 ( DOI 10.1137 / 0133030 ) Narrows Smith yleisti Condorcet-kriteerin pienimmälle hallitsevalle joukolle ja kutsuu sitä Smithin Condorcet-periaatteeksi.
- Thomas Schwartz , Kollektiivisen valinnan logiikka , New York, Columbia University Press,1986 Tarkastellaan Smith-sarjaa (nimeltään GETCHA) ja Schwartz-sarjaa (nimeltään GOTCHA) mahdollisina normeina optimaaliselle kollektiiviselle valinnalle.