Die Smith -Menge [ Anmerkung 1 ] , auch als oberster Zyklus bezeichnet, verallgemeinert das Konzept des Condorcet-Gewinners auf Fälle, in denen kein solcher Gewinner existiert . Dies geschieht, indem Zyklen von Kandidaten gemeinsam behandelt werden, als wären sie ein einziger Condorcet-Gewinner. [ 1 ] Wahlsysteme, die stets einen Kandidaten aus der Smith-Menge wählen, erfüllen das Smith-Kriterium . Sowohl die Smith-Menge als auch das Smith-Kriterium sind nach dem Mathematiker John H. Smith benannt .

Die Smith-Menge liefert einen Standard für die optimale Wahl eines Wahlergebnisses. Ein alternatives, strengeres Kriterium stellt die Landau-Menge dar .

Definition

Die Smith-Menge ist formal definiert als die kleinste Menge, sodass jeder Kandidat innerhalb der Menge S paarweise jeden Kandidaten außerhalb von S besiegt .

Alternativ kann es auch als die Menge aller Kandidaten definiert werden, die über einen (nicht strikten) Pfad zu jedem Kandidaten führen, der sie besiegt.

Eine Menge von Kandidaten, deren Mitglieder jeweils paarweise jeden Kandidaten außerhalb der Menge besiegen, wird als dominierende Menge bezeichnet . Daher wird die Smith-Menge auch als kleinste dominierende Menge bezeichnet .

Strikter Top-Zyklus (Schwartz-Menge)

Die Schwartz-Menge ist äquivalent zur Smith-Menge, außer dass sie Stimmengleichstände ignoriert. Formal ist die Schwartz-Menge diejenige Menge, in der jeder Kandidat genau einen direkten Weg zu jedem Kandidaten hat, der ihn besiegt.

Die Smith-Menge kann aus der Schwartz-Menge konstruiert werden, indem man wiederholt zwei Arten von Kandidaten hinzufügt, bis keine solchen Kandidaten mehr außerhalb der Menge existieren:

  • Kandidaten, die paarweise mit Kandidaten im Set gleichauf liegen,
  • Kandidaten, die einen Kandidaten im Set besiegen.

Beachten Sie, dass Kandidaten des zweiten Typs erst existieren können, nachdem Kandidaten des ersten Typs hinzugefügt wurden.

Eigenschaften

  • Die Smith-Menge existiert stets und ist nicht leer. Sie ist außerdem wohldefiniert (siehe nächster Abschnitt).
  • Die Smith-Menge kann mehr als einen Kandidaten haben, entweder aufgrund paarweiser Bindungen oder aufgrund von Zyklen, wie beispielsweise beim Condorcet-Paradoxon .
  • Der Condorcet-Gewinner , sofern er existiert, ist das einzige Element der Smith-Menge. Falls schwache Condorcet-Gewinner existieren, gehören auch sie zur Smith-Menge.
  • Die Smith-Menge ist stets eine Teilmenge der kleinsten, von der gemeinsamen Mehrheit bevorzugten Kandidatenmenge. [ 2 ]

Eigenschaften von dominierenden Mengen

Satz: Dominierende Mengen sind verschachtelt ; das heißt, von je zwei dominierenden Mengen in einer Wahl ist die eine eine Teilmenge der anderen.

Beweis: Angenommen, es gäbe im Gegenteil zwei dominierende Mengen D und E , von denen keine eine Teilmenge der anderen ist. Dann müssten Kandidaten d ∈ D und e ∈ E existieren, sodass d ∉ E und e ∉ D. Nach Voraussetzung schlägt d jedoch jeden Kandidaten, der nicht in D liegt (einschließlich e ) , während e jeden Kandidaten, der nicht in E liegt (einschließlich d ), schlägt – ein Widerspruch. ∎

Folgerung: Daraus folgt, dass die Smith-Menge die kleinste nichtleere dominierende Menge ist und dass sie wohldefiniert ist.

Satz: Wenn D eine dominierende Menge ist, dann gibt es einen Schwellenwert θ D, so dass die Elemente von D genau die Kandidaten sind, deren Copeland-Score mindestens θ D beträgt . (Der Copeland-Score eines Kandidaten ist die Anzahl der anderen Kandidaten, die er besiegt, plus die Hälfte der Anzahl der anderen Kandidaten, mit denen er gleichauf liegt.)

Beweis: Wähle d als Element von D mit minimalem Copeland-Score und identifiziere diesen Score mit θ<sub> D </sub> . Angenommen, ein Kandidat e ∉ D hat einen Copeland-Score von mindestens θ<sub> D </sub> . Da d zu D gehörtund e nicht, folgt daraus, dass d e besiegt. Damit der Copeland-Score von e mindestens so groß ist wie der von d , muss es einen dritten Kandidaten f geben , gegen den e einen besseren Score erzielt als d . Wenn f ∈ D , dann gibt es ein Element von D , das e nicht besiegt, und wenn f ∉ D, dann gibt es einen Kandidaten außerhalb von D , gegen den d nicht besiegt, was in beiden Fällen zu einem Widerspruch führt. ∎

Das Smith-Kriterium

Das Smith-Kriterium ist ein Kriterium für Wahlsysteme , das eine strengere Vorstellung von Mehrheitsprinzip formalisiert als das Condorcet-Kriterium . Ein Wahlsystem erfüllt das Smith-Kriterium, wenn es stets einen Kandidaten aus der Smith-Menge auswählt.

Weniger gebräuchlich ist jedoch der Begriff Smith-effizient, der auch für Methoden verwendet wird, die aus der Smith-Menge auswählen. [ 3 ]

Hier ein Beispiel für eine Wählerschaft ohne Condorcet-Sieger: Es gibt vier Kandidaten: A, B, C und D. 40 % der Wähler ordnen D > A > B > C. 35 % der Wähler ordnen B > C > A > D. 25 % der Wähler ordnen C > A > B > D. Die Smith-Menge ist {A, B, C}. Alle drei Kandidaten der Smith-Menge werden von der Mehrheit gegenüber D bevorzugt (da 60 % jeden von ihnen vor D einstufen). Die Smith-Menge ist nicht {A, B, C, D}, da die Definition die kleinste Teilmenge verlangt, die die übrigen Bedingungen erfüllt. Die Smith-Menge ist nicht {B, C}, da B nicht von der Mehrheit gegenüber A bevorzugt wird; 65 % stufen A vor B ein. (Usw.)

con
Profi
A B C D
A — 65 40 60
B 35 — 75 60
C 60 25 — 60
D 40 40 40 —
maximale Chancen 60 65 75 60
Minimax 60 60

In diesem Beispiel gibt es unter Minimax ein Unentschieden zwischen A und D; unter Smith//Minimax gewinnt A.

Im obigen Beispiel befinden sich die drei Kandidaten im Smith-Set in einem Mehrheitszyklus nach dem Prinzip „Stein/Papier/Schere“ : A liegt mit einer 65%igen Mehrheit vor B, B liegt mit einer 75%igen Mehrheit vor C und C liegt mit einer 60%igen Mehrheit vor A.

Weitere Kriterien

Jedes Wahlverfahren, das dem Smith-Kriterium genügt, erfüllt auch das Condorcet-Gewinnerkriterium , da ein Condorcet-Gewinner der einzige Kandidat in der Smith-Menge ist. Smith-Verfahren erfüllen zudem das Condorcet-Verliererkriterium , da ein Condorcet-Verlierer niemals in der Smith-Menge enthalten sein kann. Daraus folgt auch das Kriterium der gegenseitigen Mehrheit , da die Smith-Menge eine Teilmenge der MMC-Menge ist. [ 2 ] Umgekehrt erfüllt jedes Verfahren, das eines dieser drei Mehrheitskriterien (gegenseitige Mehrheit, Condorcet-Verlierer oder Condorcet-Gewinner) nicht erfüllt, auch nicht das Smith-Kriterium.

Einhaltung der Methoden

Das Smith-Kriterium wird von Rangpaaren , dem Schulze-Verfahren , dem Nanson-Verfahren und einigen anderen Verfahren erfüllt. Darüber hinaus kann jedes Abstimmungsverfahren so modifiziert werden, dass es das Smith-Kriterium erfüllt, indem die Smith-Menge ermittelt und alle Kandidaten außerhalb dieser Menge ausgeschlossen werden.

Das Wahlverfahren Smith//Minimax wendet beispielsweise die Minimax-Funktion auf die Kandidaten der Smith-Menge an. Ein anderes Beispiel ist das alternative Tideman -Verfahren, das abwechselnd Kandidaten außerhalb der Smith-Menge und den Kandidaten mit den wenigsten Stimmen (ähnlich dem Instant-Runoff-Verfahren ) ausschließt, bis ein Condorcet-Sieger feststeht. Ein weiterer Ansatz besteht darin, das Mitglied der Smith-Menge zu wählen, das in der Reihenfolge des Wahlergebnisses des jeweiligen Verfahrens am höchsten steht.

Methoden, die das Condorcet-Kriterium nicht erfüllen, erfüllen auch nicht das Smith-Kriterium. Allerdings können einige Condorcet-Methoden (wie z. B. Minimax ) das Smith-Kriterium nicht erfüllen.

Bezug zu anderen Turniersätzen

Die Smith-Menge enthält die Copeland-Menge und die Landau-Menge als Teilmengen.

Sie enthält außerdem die Banks-Menge und die Bipartisan-Menge . Darüber hinaus wurden eine Reihe weiterer Teilmengen der Smith-Menge definiert. [ 4 ]

Berechnung der Smith-Menge

Die Smith-Menge kann mit dem Floyd-Warshall-Algorithmus in der Zeit Θ ( n 3 ) oder mit dem Kosaraju-Algorithmus in der Zeit Θ ( n 2 ) berechnet werden.

Detaillierter Algorithmus

Der Algorithmus lässt sich anhand eines Beispiels detailliert darstellen. Angenommen, die Ergebnismatrix sieht wie folgt aus:

2.
1.
A B C D E F G Punktzahl
A – 1 1 1 1 1 0 5
B 0 – 0 0 1 0 0 1
C 0 1 – 0 1 ⁠1/2⁠1 3 ⁠1/2⁠
D 0 1 1 – 1 1 1 5
E 0 0 0 0 – 0 0 0
F 0 1 ⁠1/2⁠0 1 – 0 2 ⁠1/2⁠
G 1 1 0 0 1 1 – 4

Ein Eintrag in der Haupttabelle ist hier 1, wenn der erste Kandidat von mehr Wählern dem zweiten vorgezogen wurde als umgekehrt; 0, wenn das Gegenteil der Fall ist; und1/2Bei Punktgleichheit gibt die letzte Spalte die Copeland-Punktzahl des ersten Kandidaten an.

Der Algorithmus zur Berechnung der Smith-Menge ist agglomerativ: Er beginnt mit der Copeland-Menge, die garantiert eine Teilmenge der Smith-Menge ist, aber oft kleiner ist, und fügt Elemente hinzu, bis keine weiteren mehr benötigt werden. Der erste Schritt besteht darin, die Kandidaten nach ihrer Punktzahl zu sortieren:

2.
1.
A D G C F B E Punktzahl
A – 1 0 1 1 1 1 5
D 0 – 1 1 1 1 1 5
G 1 0 – 0 1 1 1 4
C 0 0 1 – ⁠1/2⁠1 1 3 ⁠1/2⁠
F 0 0 0 ⁠1/2⁠– 1 1 2 ⁠1/2⁠
B 0 0 0 0 0 – 1 1
E 0 0 0 0 0 0 – 0

Wir betrachten die höchste Punktzahl (5) und berücksichtigen die Kandidaten (Copeland-Gewinner), deren Punktzahl mindestens so hoch ist, also {A, D}. Diese gehören mit Sicherheit zur Smith-Menge, und alle Kandidaten, die sie nicht schlagen, müssen hinzugefügt werden. Um ungeschlagene Kandidaten zu finden, betrachten wir die Zellen in der Tabelle unterhalb des 2×2-Quadrats oben links, das {A, D} enthält (dieses Quadrat ist gestrichelt dargestellt): Die betreffenden Zellen sind in der Tabelle gelb schattiert. Wir müssen den niedrigsten (positionell) von Null verschiedenen Eintrag unter diesen Zellen finden, und zwar die Zelle in der Zeile G. Alle Kandidaten bis zu dieser Zeile und alle darunter liegenden Zeilen mit der gleichen Punktzahl müssen der Menge hinzugefügt werden, die sich zu {A, D, G} erweitert.

Nun betrachten wir alle neuen Zellen, die berücksichtigt werden müssen. Dies sind diejenigen unterhalb des Quadrats oben links, das {A,D,G} enthält, jedoch ohne die Zellen in den ersten beiden Spalten, die wir bereits berücksichtigt haben. Die relevanten Zellen sind hellblau schattiert. Wie zuvor suchen wir den positionell niedrigsten Eintrag ungleich Null unter den neuen Zellen und fügen alle Zeilen unterhalb dieses Eintrags sowie alle Zeilen mit demselben Wert zum erweiterten Satz hinzu, der nun {A,D,G,C} umfasst.

Wir wiederholen den Vorgang für die neuen Zellen unterhalb der vier Elemente, die bekanntermaßen zur Smith-Menge gehören. Diese sind rosa schattiert und ermöglichen es uns, alle Kandidaten zu finden, die nicht von einem der Elemente {A, D, G, C} ausgeschlossen werden. Auch hier gibt es nur einen Kandidaten, F, den wir der Menge hinzufügen.

Die relevanten Zellen sind hellgrün schattiert. Da alle ihre Einträge null sind, müssen wir keine weiteren Kandidaten hinzufügen. Die Menge bleibt somit bei {A, D, G, C, F}. Da alle Einträge im schwarzen Feld null sind, wissen wir, dass alle darüber liegenden Kandidaten alle darin liegenden Kandidaten ausschließen.

Die folgende C-Funktion veranschaulicht den Algorithmus, indem sie die Kardinalität der Smith-Menge für eine gegebene verdoppelte Ergebnismatrix r und ein Array s mit verdoppelten Copeland-Scores zurückgibt. Es gibt n Kandidaten; r <sub>ij</sub> ist gleich 2, wenn mehr Wähler i gegenüber j als gegenüber i bevorzugen, gleich 1 , wenn die Anzahl gleich ist, und 0, wenn mehr Wähler j gegenüber i als gegenüber i bevorzugen  ; s <sub> i </sub> ist die Summe über j von r <sub>ij</sub>  . Es wird angenommen, dass die Kandidaten in absteigender Reihenfolge ihres Copeland-Scores sortiert sind.

int smithset ( int ** r , int * s , int n ) { int row , col , lhs , rhs ; for ( rhs = 1 , lhs = 0 ; lhs < rhs ; lhs = rhs , rhs = row + 1 ) { for (; rhs < n && s [ rhs ] == s [ rhs - 1 ]; rhs ++ ); /* diese Zeile optional */ for ( col = rhs , row = n ; col == rhs && row >= rhs ; row-- ) for ( col = lhs ; col < rhs && r [ row - 1 ][ col ] == 0 ; col ++ ) ; } return lhs ; }

Siehe auch

Anmerkungen

  1. ^ Viele Autoren verwenden den Begriff „Schwartz-Menge“ ausschließlich für die im Folgenden beschriebene strikte Smith-Menge.

Referenzen

  1. ^ Soh, Leen-Kiat (2017-10-04). "Voting: Preference Aggregating & Social Choice [CSCE475/875 class handout]" (PDF) .
  2. ^ a b Brandt, Felix (17.07.2009). „Einige Bemerkungen zu Dodgsons Abstimmungsregel“. Mathematical Logic Quarterly . 55 (4). Wiley: 460–463 . doi : 10.1002/malq.200810017 . ISSN 0942-5616 . 
  3. ^ Boudet, Samuel (06.09.2023), Überparteiliche/Range-Voting in zwei Runden erreicht ein vielversprechendes Gleichgewicht zwischen Effizienz und Strategieresistenz , MDPI AG, doi : 10.20944/preprints202309.0388.v1
  4. ^ Brandt, Felix; Brill, Markus; Harrenstein, Paul (16.01.2018). „Erweiterung von Turnierlösungen“ (PDF) . Social Choice and Welfare . 51 (2). Springer Science and Business Media LLC. doi : 10.1007/s00355-018-1112-x . ISSN 0176-1714 . Für viele Turnierlösungen wurden in der Literatur Verallgemeinerungen oder Erweiterungen zu schwachen Turnieren vorgeschlagen. 

Weiterführende Literatur

  • Ward, Benjamin (1961). „Mehrheitsprinzip und Ressourcenverteilung“. Journal of Conflict Resolution . 5 (4): 379–389 . doi : 10.1177/002200276100500405 . S2CID  145231466 .In einer Analyse der seriellen Entscheidungsfindung auf Basis der Mehrheitsregel beschreibt er die Smith-Menge und die Schwartz-Menge.
  • Smith, JH (1973). „Aggregation von Präferenzen bei variablen Wählerschaften“. Econometrica . 41 (6). The Econometric Society: 1027–1041 . doi : 10.2307/1914033 . JSTOR  1914033 .Smith führt eine Version des verallgemeinerten Condorcet-Kriteriums ein, das erfüllt ist, wenn paarweise Wahlen auf einfacher Mehrheitsentscheidung beruhen und für jede dominierende Menge jeder Kandidat innerhalb dieser Menge kollektiv jedem Kandidaten außerhalb dieser Menge vorgezogen wird. Smith geht jedoch nicht auf die Idee einer kleinsten dominierenden Menge ein.
  • Fishburn, Peter C. (1977). „Condorcet Social Choice Functions“. SIAM Journal on Applied Mathematics . 33 (3): 469–489 . doi : 10.1137/0133030 .Er beschränkt Smiths verallgemeinertes Condorcet-Kriterium auf die kleinste dominierende Menge und nennt es Smiths Condorcet-Prinzip.
  • Schwartz, Thomas (1986). Die Logik kollektiver Entscheidungen . New York: Columbia University Press.Erörtert die Smith-Menge (genannt GETCHA) und die Schwartz-Menge (genannt GOTCHA) als mögliche Standards für eine optimale kollektive Entscheidung.
  • Schwartz, Thomas (1970). „Zur Möglichkeit rationaler Politikbewertung“. Theory and Decision . 1 : 89–106 . doi : 10.1007/BF00132454 . S2CID  154326683 . Am Ende des Artikels wird der Begriff der Schwartz-Menge als mögliche Alternative zur Maximierung bei Vorliegen zyklischer Präferenzen als Maßstab rationaler Entscheidung eingeführt.
  • Schwartz, Thomas (1972). „Rationalität und der Mythos des Maximums“. Noûs 6 (2). Noûs, Bd. 6, Nr. 2: 97–117. doi : 10.2307 / 2216143 . JSTOR 2216143 .  Liefert eine axiomatische Charakterisierung und Begründung der Schwartz-Menge als möglichen Standard für optimale, rationale kollektive Entscheidungen.
  • Deb, Rajat (1977). „Zur Schwartschen Regel“. Journal of Economic Theory . 16 : 103–110 . doi : 10.1016/0022-0531(77)90125-9 . Beweist, dass die Schwartz-Menge die Menge der nichtdominierten Elemente des transitiven Abschlusses der paarweisen Präferenzrelation ist.
  • Green-Armytage, James. Vier Condorcet-Hare-Hybridmethoden für Wahlen mit einem einzigen Gewinner .
  • Somdeb Lahiri (o. J.), „Gruppen- und multikriterielle Entscheidungsfindung“. Beschreibt einige Eigenschaften von Auswahlmengen.