Smith-Menge

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Smith-Menge spielt eine Rolle, wenn bei einem Wettbewerb oder einer Wahl, bei der jeder gegen jeden antritt, aus den Ergebnissen der Zweiertreffen einer oder mehrere Sieger des Gesamtwettbewerbs ermittelt werden sollen. Ein Mitspieler oder ein Kandidat gehört nach Definition dann zur Smith-Menge, wenn er alle anderen, die nicht zu dieser Menge gehören, besiegt hat.

Benannt ist die Smith-Menge nach John Howard Smith.[1]

Die Smith-Menge ist von Bedeutung für ein Kriterium für die Bestimmung des Siegers einer Wahl oder eines Wettbewerbs: Wahlsysteme, bei denen immer ein Kandidat aus der Smith-Menge gewinnt, erfüllen das Smith-Kriterium und gelten als „Smith-effizient“.

Ein einfaches Beispiel

[Bearbeiten | Quelltext bearbeiten]

Nehmen wir an, dass bei einem Schachwettbewerb mit den vier Teilnehmern A, B, C und D die Ergebnisse der Zweiertreffen wie folgt sind:

  • A gewinnt gegen C und D
  • B gewinnt gegen A, C und D

Dann besteht die Smith-Menge aus A und B, weil beide sowohl gegen C als auch gegen D gewonnen haben. Der „natürliche“ Gewinner des gesamten Wettbewerbs wäre B (wegen seines Sieges gegen alle anderen Teilnehmer), aber auch die Erklärung von A zum Gesamtsieger wäre Smith-effizient, weil A ja zur Smith-Menge gehört.

Sei eine antisymmetrische Relation auf einer nichtleeren Menge . Die Elemente von kann man als „Kandidaten“ bezeichnet und als „x besiegt y“ interpretieren. Dann heißt eine Teilmenge von Smith-Menge (bezüglich ), wenn die kleinste Menge ist, für die gilt: Aus folgt .

  • Die Smith-Menge existiert immer und ist eindeutig bestimmt. Es gibt nur eine kleinste dominierende Menge, da dominierende 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 Unentschieden oder aufgrund von Zyklen wie in Condorcets Paradoxon.
  • Der Condorcet-Gewinner, falls vorhanden, ist das einzige Mitglied der Smith-Menge. Wenn es schwache Condorcet-Gewinner gibt, sind sie alle in der Smith-Menge.
  • Die Smith-Menge ist immer eine Teilmenge der durch das Kriterium der Mehrheit für solide Koalitionen gegebenen Menge, falls dessen Voraussetzungen erfüllt sind.

Die Smith-Menge kann mit dem Floyd-Warshall-Algorithmus in der Zeit O berechnet werden. Sie kann auch mit einer Version des Kosaraju-Algorithmus oder des Tarjan-Algorithmus in der Zeit O berechnet werden.

Man kann sie auch finden, indem man eine paarweise Vergleichsmatrix der Kandidaten erstellt, die nach ihrer Anzahl paarweiser Siege minus paarweiser Niederlagen (eine Rangfolge nach der Copeland-Methode) geordnet sind, und dann nach dem kleinstmöglichen Quadrat der Zellen ganz links sucht, welches so abgedeckt werden kann, dass alle Zellen rechts von diesen Zellen paarweise Siege zeigen. Alle Kandidaten, die links von diesen Zellen genannt werden, befinden sich in der Smith-Menge

Beispiel mit dem Copeland-Ranking:

Verluste und Unentschieden sind fett gedruckt
A B C D E F G
A --- Sieg Verlust Sieg Sieg Sieg Sieg
B Verlust --- Sieg Sieg Sieg Sieg Sieg
C Sieg Verlust --- Verlust Sieg Sieg Sieg
D Verlust Verlust Sieg --- Unentschieden Sieg Sieg
E Verlust Verlust Verlust Unentschieden --- Sieg Sieg
F Verlust Verlust Verlust Verlust Verlust --- Sieg
G Verlust Verlust Verlust Verlust Verlust Verlust ---

A verliert gegen C, daher wird bestätigt, dass alle Kandidaten von A bis C (A, B und C) in der Smith-Menge sind. Es gibt einen Vergleich, bei dem ein Kandidat, der bereits als Mitglied der Smith-Menge bestätigt wurde, gegen jemanden verliert oder unentschieden ist, der noch nicht als Mitglied der Smith–Menge bestätigt wurde: C verliert gegen D; Dadurch wird also bestätigt, dass D zur Smith–Menge gehört. Es gibt einen weiteren solchen Vergleich: D unentschieden gegen E, also gehört E zur Smith–Menge hinzugefügt. Da alle Kandidaten von A bis E alle anderen, noch nicht bestätigten Kandidaten schlagen, besteht die Smith-Menge nur aus den Kandidaten A bis E.

  • Ward, Benjamin: Majority Rule and Allocation. In: Journal of Conflict Resolution. Band 5. Jahrgang, Nr. 4, 1961, S. 379–389, doi:10.1177/002200276100500405. (In an analysis of serial decision making based on majority rule, describes the Smith set and the Schwartz set).
  • Fishburn, Peter C.: Condorcet Social Choice Functions. In: SIAM Journal on Applied Mathematics. Band 33. Jahrgang, Nr. 3, 1977, S. 469–489, doi:10.1137/0133030. (Narrows Smith's generalized Condorcet Criterion to the smallest dominating set and calls it Smith's Condorcet Principle).
  • Thomas Schwartz: The Logic of Collective Choice. Columbia University Press, New York 1986 (Discusses the Smith set [named GETCHA] and the Schwartz set [named GOTCHA] as possible standards for optimal collective choice).

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. J. H. Smith: Aggregation of Preferences with Variable Electorates. In: Econometrica. Band 41, Nr. 6, 1973, S. 1027–1041, doi:10.2307/1914033.