Utente:Mazzu75/Teorema di Gibbard-Satterthwaite

Il Teorema di Gibbard–Satterthwaite stabilisce, in analogia col Teorema dell'impossibilità di Arrow, che non esiste un processo decisionale (basato su uno schema di votazione in grado di considerare tre o più alternative) immune da strategie di manipolazione, che soddisfi sia l'assioma di non dittatura che di efficienza del processo decisionale (ovvero rispetti i criteri di razionalità, efficienza paretiana, dominio illimitato e indipendenza delle alternative irrelevanti).

Propongono i seguenti assiomi:

1) Decisività dell'Ordinamento di preferenza collettivo: si richiede semplicemente l'esistenza di un vincitore, e non di un ordinamento completo tra tutte le alternative sub-ottimali 2)Dominio non ristretto 3)Assenza di dittatura 4) A prova di stratedia

TEOREMA: Non esiste aluna regola di decisione collettiva che soddisfi le condizioni 1-4.

Il Teorema ha aperto la strada a una letteratura scientifica molto ampia, nel campo dell'economia pubblica, in cui si cerca di disegnare regole e meccanismi pubblici in grado di incentivare gli agenti privati, individui e imprese che in diversi contesti hanno rapporti con il settore pubblico, a rivelare correttamente le informazioni di cui dispongono.

http://www.unipr.it/arpa/defi/papers/paper1.pdf

http://www.dse.uniba.it/Corsi/docenti/Longobardi/SceltePubbliche_dispense.pdf

Il teorema Gibbard-Satterthwaite e una asserzione di sistemi di votazione designati di scegliere un vincitore delle preferenze di alcuni individui, dove ogni individuo annovera tutti candidati in ordine di preferenza. Il teorema dice che, per tre candidati o di più, una delle seguenti tre cose devono tenere per ogni regola di voto:.

The Gibbard–Satterthwaite theorem is a result about voting systems designed to choose a single winner from the preferences of certain individuals, where each individual ranks all candidates in order of preference. It states that, for three or more candidates, one of the following three things must hold for every voting rule:

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.

Formulazione Rigorosa del Teorema

Per una formulazione rigorosa del teorema ci sono due definizioni utili: una procedura è denominata dittatoriale, se c’e una persona eccellente, la cui preferenza decide la procedura. Una procedura è denominata manipolatrice quando c’e una situazione dove un partecipante – il quale conosce sia il funzionamento della procedura, e anche il voto comportamento tutte le altre parti – può migliorare la possibilità di un alternativa quando non vota per questa pero per un'altra alternativa, oppure può peggiorare la possibilità d’una alternativa, quando sceglie questa. Con queste definizioni il gibbard-satterthwaite teorema è:

Per tre o più opzioni con ogni preferenza almeno una delle tre condizioni sono soddisfatte:

1. La procedura è dittatoriale. 2. Esiste un'alternativa, non potrà mai essere accettati 3. La procedura è sensibile

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.

Un Esempio

Nell'esempio seguente, contano le norme del Instant-Runoff-Votings:

ogni elettore decide l'ordine delle sue preferenze: il suo primo candidato, il secondo, …, e così via fino all'ultima scelta. Il candidato prescelto per in maggioranza dei primi posti è eletto. Altrimenti, l'opzione con il minor numero di primi posti di tutti voti e tolto e le altre opzioni indietro si spostano un posto avanti. In particolare, le opzioni scelto al secondo posto dietro l’opzione tolto contano come la prima scelta degli elettori.

Si deve decidere tra quattro opzioni A, B, C e D. Tra gli elettori non ci sono quattro gruppi, che mettono l’opzioni nelle quattro serie seguente:

Gruppo 1 (15 Persone): B > C > D > A Gruppo 2 (24 Persone): C > D > A > B Gruppo 3 (29 Persone): D > A > C > B Gruppo 4 (32 Persone): A > D > C > B

Prima opzione B e soppresso, poi D. Quindi A ha la preferenza collettiva con 61:39. Ora gruppo 1 in ogni caso vuole evitare la vittoria di candidato A. Poiché conoscono l’ideologiche delle preferenze di altri gruppi, mettono A in primo luogo del loro ordine:

Gruppo 1 (15 Persone): A > B > C > D Gruppo 2 (24 Persone): C > D > A > B Gruppo 3 (29 Persone): D > A > C > B Gruppo 4 (32 Persone): A > D > C > B

A causa delle nuove preferenze prima e soppresso B e poi C. Tra gli altri candidati A e D, D ha la preferenze con una maggioranza di 53:47.

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.

Literatur

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

Weblinks

• The Proof of the Gibbard–Satterthwaite Theorem Revisited