Smith satt
I stemmesystemer er Smith-settet , oppkalt etter John H. Smith, men også kjent som den øvre syklusen , eller som GETCHA ( Generalized Top-Choice Assumption ), det minste settet som ikke er ugyldig for kandidater i et bestemt valg, slik at hvert medlem slår hver kandidat utenfor settet i et parvalg. Smith-settet gir en optimal valgstandard for et valgresultat. Stemmesystemer som alltid velger en kandidat fra Smith-settet oppfyller Smith-kriteriet og sies å være "Smith-effektive".
Et kandidatsett der hvert medlem av settet slår parvis hvert medlem utenfor settet er kjent som et dominerende sett .
Eiendommer
- Smith-settet eksisterer fortsatt og er veldefinert. Det er bare ett mindre dominerende sett fordi de dominerende settene er nestede og ikke tomme, og settet med kandidater er endelig.
- Smith-settet kan ha mer enn en kandidat, enten på grunn av parvise utjevninger, eller på grunn av sykluser, som i Condorcet-paradokset .
- Den Condorcet vinner , hvis det er en, er det eneste medlemmet av Smiths ensemble. Hvis det er svake Condorcet-vinnere , er de i Smith-settet.
- Smith-settet er alltid en delmengde av det gjensidige flertalls foretrukne kandidatsettet, hvis det finnes.
Algoritmer
Smith-settet kan beregnes med Floyd - Warshall-algoritmen over tid Θ . Det kan også beregnes ved hjelp av en versjon av algoritmen til Kosaraju eller Tarjan-algoritmen i tid Θ .
Det kan også bli funnet ved å lage en parvis sammenligningsmatrise med deltakere rangert etter antall parvinninger minus partap (en Copeland-metode- rangering ), og deretter se etter det minste kvadratet av celler øverst til venstre som kan dekkes slik at alle celler til høyre for disse cellene viser seire i par. Alle kandidatene navngitt til venstre for disse cellene er i Smith-settet.
Eksempel på bruk av Copeland-rangering:
| PÅ | B | VS | re | E | F | g | |
|---|---|---|---|---|---|---|---|
| PÅ | --- | Å vinne | Å tape | Å vinne | Å vinne | Å vinne | Å vinne |
| B | Å tape | --- | Å vinne | Å vinne | Å vinne | Å vinne | Å vinne |
| VS | Å vinne | Å tape | --- | Å tape | Å vinne | Å vinne | Å vinne |
| re | Å tape | Å tape | Å vinne | --- | Også | Å vinne | Å vinne |
| E | Å tape | Å tape | Å tape | Også | --- | Å vinne | Å vinne |
| F | Å tape | Å tape | Å tape | Å tape | Å tape | --- | Å vinne |
| g | Å tape | Å tape | Å tape | Å tape | Å tape | Å tape | --- |
A taper mot C, så alle kandidater fra A til C (A, B og C) bekreftes å være Smith-settet. Det er en sammenligning der en kandidat som allerede er bekreftet å være i Smith-settet taper eller også har med noen som ikke er bekreftet å være i Smith-settet: C taper til D; det bekreftes derfor at D er en del av Smith-settet. Nå er det nok en slik konfrontasjon: D har også med E, så E er også i Smith-settet. Fordi alle kandidatene fra A til E beseiret alle kandidatene som ikke ble bekreftet å være en del av Smith-settet, er Smith-settet nå bekreftet å være fra kandidatene fra A til E.
Se også
- Condorcet-kriterium
- Condorcet-metoden
- Barnevogn sett
- Forhåndsbestille
- Delvis rekkefølge
Referanser
- Ward, Benjamin, " Majority Rule and Allocation ", Journal of Conflict Resolution , vol. 5, n o 4,1961, s. 379–389 ( DOI 10.1177 / 002200276100500405 )
- Smith, JH, " Aggregation of Preferences with Variable Electorates ", Econometrica , The Econometric Society, vol. 41, n o 6,1973, s. 1027–1041 ( DOI 10.2307 / 1914033 , JSTOR 1914033 ) Introduserer en versjon av et generalisert Condorcet-kriterium som oppfylles når parvalg er basert på et enkelt flertallsvalg, og for ethvert dominerende sett foretrekkes enhver kandidat i settet kollektivt fremfor ikke-kandidat. Men Smith diskuterer ikke ideen om et mindre dominerende sett.
- Fishburn, Peter C., “ Condorcet Social Choice Functions, ” SIAM Journal on Applied Mathematics , vol. 33, n o 3,1977, s. 469–489 ( DOI 10.1137 / 0133030 ) Narrows Smith generaliserte Condorcet-kriteriet til det minste dominerende settet og kaller det Smiths Condorcet-prinsipp.
- Thomas Schwartz , The Logic of Collective Choice , New York, Columbia University Press,1986 Diskuterer Smith-settet (kalt GETCHA) og Schwartz-settet (kalt GOTCHA) som mulige normer for optimalt kollektivt valg.