Gibbard-Satterthwaite-Theorem

Das Gibbard-Satterthwaite-Theorem ist eine Aussage in der Sozialwahltheorie über Gruppenentscheidungen, speziell über die Grenzen von Vorzugswahlen. Bei Vorzugswahlen reiht jedes Gruppenmitglied eine Anzahl von Entscheidungsalternativen gemäß seiner individuellen Befürwortung.

Das Theorem besagt, dass jede Vorzugswahl bei drei oder mehr Entscheidungsalternativen durch strategisches Stimmverhalten manipulierbar ist, falls sie den demokratischen Werten genügt, dass alle Personen am Verfahren gleichberechtigt teilnehmen und vom Verfahren her jede Alternative die Chance hat, angenommen zu werden.

Für eine exakte Formulierung des Theorems sind zwei Definitionen hilfreich: Ein Verfahren heißt diktatorisch, wenn es eine ausgezeichnete Person gibt, deren Präferenz das Verfahren entscheidet. Ein Verfahren heißt manipulierbar, wenn es Situationen gibt, in denen ein Beteiligter – welcher sowohl das Verfahren als auch das Stimmverhalten aller anderen Beteiligten kennt – die Chancen einer Alternative verbessern kann, indem er nicht für diese, sondern für eine andere Alternative stimmt, oder die Chancen einer Alternative verschlechtern kann, indem er für sie stimmt. Mit diesen Definitionen lautet das Gibbard-Satterthwaite-Theorem:

Bei drei oder mehr Entscheidungsalternativen ist bei jeder Vorzugswahl mindestens eine der folgenden drei Bedingungen erfüllt:

1. Das Verfahren ist diktatorisch.
2. Es gibt eine Alternative, die niemals angenommen werden kann.
3. Das Verfahren ist manipulierbar.

Das Gibbard-Satterthwaite-Theorem ist mit dem Arrow-Theorem beweisbar.^[1]

Bei dem folgenden Beispiel gelten die Regeln des Instant-Runoff-Votings:

Jeder Wähler bestimmt unter allen Entscheidungsalternativen (Optionen) seine erste, zweite, …, letzte Wahl. Hat eine Option die Mehrheit der ersten Plätze, so ist sie gewählt. Andernfalls wird die Option mit der geringsten Anzahl an ersten Plätzen von allen Präferenzordnungen (Stimmzetteln) gestrichen, und die anderen Optionen rücken in die dadurch frei gewordenen Plätze auf. Insbesondere gelten die Optionen, die den zweiten Platz hinter der Gestrichenen belegt hatten, nunmehr als erste Wahl dieser Wähler.

Es sei zwischen vier Optionen A, B, C und D zu entscheiden. Unter den Wählern gibt es vier Gruppen, welche die Optionen wie folgt reihen:

Gruppe 1 (15 Personen): B > C > D > A

Gruppe 2 (24 Personen): C > D > A > B

Gruppe 3 (29 Personen): D > A > C > B

Gruppe 4 (32 Personen): A > D > C > B

Zuerst wird Option B gestrichen, dann D. Somit wird A mit einer Mehrheit von 61:39 kollektiv präferiert. Nun möchte Gruppe 1 aber auf alle Fälle verhindern, dass Kandidat A gewinnt. Da sie aus ideologischen Gründen die Präferenzen der anderen Gruppen zu kennen glauben, setzen sie A an die erste Stelle ihrer Präferenzordnung:

Gruppe 1 (15 Personen): A > B > C > D

Gruppe 2 (24 Personen): C > D > A > B

Gruppe 3 (29 Personen): D > A > C > B

Gruppe 4 (32 Personen): A > D > C > B

Aufgrund der neuen Präferenzen wird zuerst B gestrichen und sodann C. Unter den verbleibenden Kandidaten A und D wird D mit einer Mehrheit von 53:47 kollektiv präferiert.

• Allan Gibbard: Manipulation of voting schemes. A general result. In: Econometrica. Band 41, Nr. 4, 1973.
• Mark Satterthwaite: Strategy-proofness and Arrow’s Conditions. Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions. In: Journal of Economic Theory. Band 10, 1975.

• Lars-Gunnar Svensson: The Proof of the Gibbard-Satterthwaite Theorem Revisited. In: Scandinavian Working Papers in Economics.

1. ↑ Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF; 5,2 MB). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0