www.wikidata.de-de.nina.az

Gibbard Satterthwaite Theorem Das ist eine Aussage in der Sozialwahltheorie über Gruppenentscheidungen speziell über die

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.

Exakte Formulierung Bearbeiten

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.

Ein Beispiel Bearbeiten

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

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:

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:

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.

Literatur Bearbeiten

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

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Gibbard Satterthwaite Theorem ist eine Aussage in der Sozialwahltheorie uber Gruppenentscheidungen speziell uber die Grenzen von Vorzugswahlen Bei Vorzugswahlen reiht jedes Gruppenmitglied eine Anzahl von Entscheidungsalternativen gemass seiner individuellen Befurwortung Das Theorem besagt dass jede Vorzugswahl bei drei oder mehr Entscheidungsalternativen durch strategisches Stimmverhalten manipulierbar ist falls sie den demokratischen Werten genugt dass alle Personen am Verfahren gleichberechtigt teilnehmen und vom Verfahren her jede Alternative die Chance hat angenommen zu werden Inhaltsverzeichnis 1 Exakte Formulierung 2 Ein Beispiel 3 Literatur 4 Weblinks 5 EinzelnachweiseExakte Formulierung BearbeitenFur eine exakte Formulierung des Theorems sind zwei Definitionen hilfreich Ein Verfahren heisst diktatorisch wenn es eine ausgezeichnete Person gibt deren Praferenz das Verfahren entscheidet Ein Verfahren heisst 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 fur diese sondern fur eine andere Alternative stimmt oder die Chancen einer Alternative verschlechtern kann indem er fur 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 erfullt Das Verfahren ist diktatorisch Es gibt eine Alternative die niemals angenommen werden kann Das Verfahren ist manipulierbar Das Gibbard Satterthwaite Theorem ist mit dem Arrow Theorem beweisbar 1 Ein Beispiel BearbeitenBei dem folgenden Beispiel gelten die Regeln des Instant Runoff Votings Jeder Wahler bestimmt unter allen Entscheidungsalternativen Optionen seine erste zweite letzte Wahl Hat eine Option die Mehrheit der ersten Platze so ist sie gewahlt Andernfalls wird die Option mit der geringsten Anzahl an ersten Platzen von allen Praferenzordnungen Stimmzetteln gestrichen und die anderen Optionen rucken in die dadurch frei gewordenen Platze auf Insbesondere gelten die Optionen die den zweiten Platz hinter der Gestrichenen belegt hatten nunmehr als erste Wahl dieser Wahler Es sei zwischen vier Optionen A B C und D zu entscheiden Unter den Wahlern gibt es vier Gruppen welche die Optionen wie folgt reihen Gruppe 1 15 Personen B gt C gt D gt A Gruppe 2 24 Personen C gt D gt A gt B Gruppe 3 29 Personen D gt A gt C gt B Gruppe 4 32 Personen A gt D gt C gt B dd Zuerst wird Option B gestrichen dann D Somit wird A mit einer Mehrheit von 61 39 kollektiv praferiert Nun mochte Gruppe 1 aber auf alle Falle verhindern dass Kandidat A gewinnt Da sie aus ideologischen Grunden die Praferenzen der anderen Gruppen zu kennen glauben setzen sie A an die erste Stelle ihrer Praferenzordnung Gruppe 1 15 Personen A gt B gt C gt D Gruppe 2 24 Personen C gt D gt A gt B Gruppe 3 29 Personen D gt A gt C gt B Gruppe 4 32 Personen A gt D gt C gt B dd Aufgrund der neuen Praferenzen wird zuerst B gestrichen und sodann C Unter den verbleibenden Kandidaten A und D wird D mit einer Mehrheit von 53 47 kollektiv praferiert Literatur BearbeitenAllan 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 Weblinks BearbeitenLars Gunnar Svensson The Proof of the Gibbard Satterthwaite Theorem Revisited In Scandinavian Working Papers in Economics Einzelnachweise Bearbeiten Vazirani Vijay V Nisan Noam Roughgarden Tim Tardos Eva 2007 Algorithmic Game Theory PDF 5 2 MB Cambridge UK Cambridge University Press ISBN 0 521 87282 0 Abgerufen von https de wikipedia org w index php title Gibbard Satterthwaite Theorem amp oldid 223463288