Smith stellte ein
In Abstimmungssystemen ist der Smith-Satz , benannt nach John H. Smith, aber auch als oberer Zyklus oder als GETCHA ( Generalized Top-Choice Assumption ) bekannt, der kleinste Satz, der bei einer bestimmten Wahl nicht frei von Kandidaten ist, so dass jedes Mitglied schlägt jeden Kandidaten außerhalb des Satzes bei einer Paarwahl. Das Smith-Set bietet einen optimalen Auswahlstandard für ein Wahlergebnis. Abstimmungssysteme, die immer einen Kandidaten aus dem Smith-Set auswählen, erfüllen das Smith-Kriterium und gelten als „Smith-effizient“.
Ein Kandidatensatz, bei dem jedes Mitglied des Satzes jedes Mitglied außerhalb des Satzes paarweise schlägt, wird als dominanter Satz bezeichnet .
Eigenschaften
- Das Smith-Set existiert noch und ist gut definiert. Es gibt nur eine kleinere dominante Menge, da die dominanten Mengen verschachtelt und nicht leer sind und die Menge der Kandidaten endlich ist.
- Die Smith-Menge kann mehr als einen Kandidaten haben, entweder aufgrund paarweiser Entzerrungen oder aufgrund von Zyklen, wie im Condorcet-Paradoxon .
- Der Condorcet-Gewinner , falls es einen gibt, ist das einzige Mitglied von Smiths Ensemble. Wenn es schwache Condorcet-Gewinner gibt , sind sie im Smith-Set.
- Die Smith-Menge ist immer eine Teilmenge der bevorzugten Kandidatenmenge mit gegenseitiger Mehrheit, falls vorhanden.
Algorithmen
Das Smith-Set kann mit dem Floyd-Warshall-Algorithmus über die Zeit berechnet werden Θ . Sie kann auch mit einer Version des Algorithmus des Kosaraju- oder Tarjan-Algorithmus in der Zeit Θ berechnet werden .
Sie können es auch finden, indem Sie eine paarweise Vergleichsmatrix mit Teilnehmern erstellen, die nach ihrer Anzahl von Paargewinnen minus Paarverlusten geordnet sind (ein Copeland-Methodenranking ), und dann nach dem kleinsten Quadrat von Zellen oben links suchen, das so abgedeckt werden kann, dass alle abgedeckt werden Zellen rechts von diesen Zellen zeigen Gewinne in Paaren. Alle links von diesen Zellen genannten Kandidaten befinden sich im Smith-Set.
Beispiel mit dem Copeland-Ranking:
| BEIM | B. | VS | Re | E. | F. | G | |
|---|---|---|---|---|---|---|---|
| BEIM | --- ---. | Gewinnen | Verlieren | Gewinnen | Gewinnen | Gewinnen | Gewinnen |
| B. | Verlieren | --- ---. | Gewinnen | Gewinnen | Gewinnen | Gewinnen | Gewinnen |
| VS | Gewinnen | Verlieren | --- ---. | Verlieren | Gewinnen | Gewinnen | Gewinnen |
| Re | Verlieren | Verlieren | Gewinnen | --- ---. | Ebenfalls | Gewinnen | Gewinnen |
| E. | Verlieren | Verlieren | Verlieren | Ebenfalls | --- ---. | Gewinnen | Gewinnen |
| F. | Verlieren | Verlieren | Verlieren | Verlieren | Verlieren | --- ---. | Gewinnen |
| G | Verlieren | Verlieren | Verlieren | Verlieren | Verlieren | Verlieren | --- ---. |
A verliert gegen C, daher wird bestätigt, dass alle Kandidaten von A bis C (A, B und C) die Smith-Menge sind. Es gibt einen Vergleich, bei dem ein Kandidat, der bereits bestätigt hat, dass er im Smith-Set ist, verliert oder auch mit jemandem hat, der nicht bestätigt wurde, dass er im Smith-Set ist: C verliert gegen D; es wird daher bestätigt, dass D Teil des Smith-Sets ist. Jetzt gibt es eine andere solche Konfrontation: D hat auch mit E, also ist E auch in der Smith-Menge. Da alle Kandidaten von A bis E alle Kandidaten besiegt haben, von denen nicht bestätigt wurde, dass sie Teil des Smith-Sets sind, wird nun bestätigt, dass das Smith-Set von den Kandidaten von A bis E stammt.
Siehe auch
- Condorcet-Kriterium
- Condorcet-Methode
- Kinderwagen eingestellt
- Vorbestellen
- Teilbestellung
Verweise
- Ward, Benjamin, " Mehrheitsregel und Zuteilung ", Journal of Conflict Resolution , vol. 5, n o 4,1961, p. 379–389 ( DOI 10.1177 / 002200276100500405 )
- Smith, JH, " Aggregation von Präferenzen mit variablen Kurfürsten ", Econometrica , The Econometric Society, vol. 41, n o 6,1973, p. 1027–1041 ( DOI 10.2307 / 1914033 , JSTOR 1914033 ) Führt eine Version eines verallgemeinerten Condorcet-Kriteriums ein, das erfüllt ist, wenn Paarwahlen auf einer einfachen Mehrheitswahl beruhen, und für jede dominante Gruppe wird jeder Kandidat in der Gruppe kollektiv allen Nichtkandidaten vorgezogen. Aber Smith diskutiert nicht die Idee einer kleineren dominanten Menge.
- Fishburn, Peter C., " Condorcet Social Choice Functions ", SIAM Journal on Applied Mathematics , vol. 33, n o 3,1977, p. 469–489 ( DOI 10.1137 / 0133030 ) Narrows Smith verallgemeinerte das Condorcet-Kriterium auf die kleinste dominante Menge und nennt es Smiths Condorcet-Prinzip.
- Thomas Schwartz , Die Logik der kollektiven Wahl , New York, Columbia University Press,1986 Erläutert das Smith-Set (mit dem Namen GETCHA) und das Schwartz-Set (mit dem Namen GOTCHA) als mögliche Normen für eine optimale kollektive Auswahl.