Smith-Menge

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 H. Smith.

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

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.

Definition

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

Eigenschaften

• 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.

Algorithmen

Die Smith-Menge kann mit dem Floyd-Warshall-Algorithmus in der Zeit O$(n^{3})$ berechnet werden. Sie kann auch mit einer Version des Kosaraju-Algorithmus oder des Tarjan-Algorithmus in der Zeit O$(n^{2})$ 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.

Siehe auch

• Condorcet-Kriterium
• Condorcet-Methode
• Präordnung
• Partial order

Literatur

• Ward, Benjamin: Majority Rule and Allocation. In: Journal of Conflict Resolution. Band 5, 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, 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).

Weblinks

• Beispielalgorithmen zur Berechnung die Smith-Menge