In Wahlsystemen ist der Smith gesetzt, genannt nach John H. Smith, der kleinste nichtleere Satz von Kandidaten in einer besonderen solcher Wahl, dass jedes Mitglied jeden anderen Kandidaten außerhalb des Satzes in einer pairwise Wahl prügelt. Der Smith ist untergegangen stellt einen Standard der optimalen Wahl für ein Wahlergebnis zur Verfügung. Wahlsysteme, die immer einen Kandidaten vom Satz von Smith wählen, passieren das Kriterium von Smith und werden gesagt, "mit dem Schmied effizient" zu sein.

Eine Reihe von Kandidaten, wo jedes Mitglied des mit dem Paar klugen Satzes jedes Mitglied außerhalb des Satzes prügelt, ist auch bekannt als ein vorherrschender Satz.

Eigenschaften

• Der Schmied ist untergegangen immer besteht und ist bestimmt. Es gibt nur einen kleinsten vorherrschenden Satz seit dem Beherrschen von Sätzen werden verschachtelt, nichtleer, und der Satz von Kandidaten ist begrenzt.
• Der Schmied ist untergegangen kann mehr als einen Kandidaten, entweder wegen mit dem Paar kluger Bande oder wegen Zyklen, solcher als im Paradox von Condorcet haben.
• Der Condorcet Sieger, wenn man besteht, ist das alleinige Mitglied des Satzes von Smith. Wenn schwache Sieger von Condorcet bestehen, sind sie im Satz von Smith.

Schwartz hat Vergleich gesetzt

Der Schwartz ist untergegangen ist nah damit verbunden und ist immer eine Teilmenge des Satzes von Smith. Der Smith ist untergegangen ist größer, wenn, und nur wenn ein Kandidat im Satz von Schwartz ein mit dem Paar kluges Band mit einem Kandidaten hat, der nicht im Schwartz ist, untergeht.

Der Schmied ist untergegangen kann vom gesetzten Schwartz durch das wiederholte Hinzufügen von zwei Typen von Kandidaten gebaut werden, bis keine solche Kandidaten mehr außerhalb des Satzes bestehen:

• Kandidaten, die mit dem Paar kluge Bande mit Kandidaten im Satz, haben
• Kandidaten, die einen Kandidaten im Satz prügeln.

Bemerken Sie, dass Kandidaten des zweiten Typs nur bestehen können, nachdem Kandidaten des ersten Typs haben hinzugefügt werden.

Alternative Formulierung

Jede binäre Beziehung R auf einem Satz A kann eine natürliche teilweise Ordnung auf den R-Zyklus-Gleichwertigkeitsklassen des Satzes A erzeugen, so dass xRy [x]  [y] einbezieht.

Wenn R die Schlagen-oder-binden binäre Beziehung auf dem Satz von durch x Schlagen-oder-binden y definierten Kandidaten ist, wenn, und nur wenn x mit dem Paar klug schlägt oder y bindet, dann ist die resultierende teilweise Ordnung die schlagen-oder-binden Ordnung, die ein Gesamtbezug ist. Der Schmied ist untergegangen ist das maximale Element der schlagen-oder-binden Ordnung.

Algorithmen

Der Schmied ist untergegangen kann mit dem Algorithmus von Floyd-Warshall rechtzeitig Θ (n) berechnet werden. Es kann auch mit einer Version des Algorithmus von Kosaraju rechtzeitig Θ (n) berechnet werden.

Siehe auch

• Kriterium von Condorcet
• Methode von Condorcet
• Vorordnung
• Teilweise Ordnung

• In einer Analyse des auf der Mehrheitsregierung gestützten Serienentscheidungsbildens, beschreibt den Satz von Smith, und der Schwartz ist untergegangen.

• Führt eine Version eines verallgemeinerten Condorcet Kriteriums ein, das zufrieden ist, wenn pairwise Wahlen auf der einfachen Majoritätswahl, und für jeden vorherrschenden Satz basieren, wird jeder Kandidat im Satz jedem Kandidaten nicht im Satz insgesamt bevorzugt. Aber Schmied bespricht die Idee von einem kleinsten vorherrschenden Satz nicht.

• Wird schmäler Schmied hat Condorcet Kriterium zum kleinsten vorherrschenden Satz verallgemeinert und nennt es den Condorcet Grundsatz des Schmieds.

• Bespricht den Schmied-Satz (hat GETCHA genannt), und der Satz von Schwartz (hat GOTCHA genannt) als mögliche Standards für die optimale gesammelte Wahl.

Links

• Beispiel-Algorithmen, um den Smith zu berechnen, setzen