Nella teoria della scelta sociale , il teorema di Gibbard-Satterthwaite è un risultato pubblicato indipendentemente dal filosofo Allan Gibbard nel 1973 e dall'economista Mark Satterthwaite nel 1975. Mostra che qualsiasi regola di voto deterministica soddisfa almeno una delle seguenti proprietà:
Questo teorema è limitato alle regole di voto ordinali: l'azione di un elettore consiste nel fornire un ordine di preferenza sulle opzioni proposte. Il teorema di Gibbard più generale consente di considerare i meccanismi di scelta collettiva che non sono necessariamente ordinali: ad esempio, i sistemi di voto in cui gli elettori assegnano note ai candidati. Altri teoremi ancora più generali, il teorema di Gibbard del 1978 e il teorema di Hilland , estendono questi risultati a meccanismi non deterministici, cioè dove il risultato non può dipendere solo dalle azioni degli elettori ma ha anche un elemento di casualità.
Considerare gli elettori , e che desiderano scegliere insieme un'opzione tra quattro candidati , , e . Si presume che utilizzino il metodo Borda : ogni elettore comunica un ordine di preferenza ai candidati. Per ogni scrutinio vengono assegnati 3 punti al primo candidato, 2 punti al secondo, 1 punto al terzo e nessun punto all'ultimo. Conteggiati tutti i voti, viene eletto il candidato con il maggior numero di punti.
Supponiamo che le preferenze siano le seguenti.
avsvsbbbvsdddaa{\ displaystyle {\ begin {array} {c | c | c} a & c & c \\ b & b & b \\ c & d & d \\ d & a & a \ end {array}}} Questi mezzi notazione che l'elettore preferisce , seguiti da , e ; elettori e preferiscono ciascuno , seguito da , e . Se gli elettori votano sinceramente, poi i punteggi sono i seguenti: . È dunque chi viene eletto, con 7 punti.Ma l'elettore potrebbe scoprire che un altro scrutinio difende meglio le sue opinioni. Supponiamo che modifichi il suo voto per finire con la seguente situazione.
bvsvsabbdddvsaa{\ displaystyle {\ begin {array} {c | c | c} b & c & c \\ a & b & b \\ d & d & d \\ c & a & a \ end {array}}} L'elettore ha strategicamente tirato il candidato su e giù per il candidato . I nuovi punteggi sono: . È quindi chi viene eletto. L'elettore è soddisfatto di aver presentato una votazione diversa dalle sue sincere preferenze, poiché preferisce il nuovo risultato piuttosto che , il risultato che avrebbe ottenuto votando sinceramente.Si dice che il metodo di Borda sia manipolabile : ci sono situazioni in cui un voto sincero non difende al meglio le preferenze di un elettore.
Sfortunatamente, il teorema di Gibbard-Satterthwaite mostra che una regola di voto è necessariamente manipolabile, tranne forse in due casi: se c'è un elettore privilegiato che ha un potere dittatoriale, o se la regola consente di scegliere solo 'tra due possibili decisioni.
Notiamo l'insieme delle alternative (presumibilmente finite), chiamate anche candidati , anche se non necessariamente persone: possono anche essere diverse possibili decisioni per un dato argomento. Prendiamo atto di tutti gli elettori . Indichiamo l'insieme degli ordini rigidi deboli (en) su : un elemento di questo insieme permette di rappresentare le preferenze di un elettore. Una regola di voto è una funzione . Accetta un profilo di preferenza come argomento e restituisce un candidato vincente.
Diciamo che è manipolabile se e solo se c'è un profilo in cui un certo elettore , cambiando la sua scheda per un'altra scheda , può ottenere un risultato che preferisce (nel senso di ).
Notiamo l'immagine , cioè l'insieme dei possibili risultati delle elezioni. Quindi, diciamo che ha almeno tre possibili risultati se e solo se ha almeno tre elementi.
Si dice che sia dittatoriale se e solo se c'è un elettore che è un dittatore , vale a dire che l'alternativa vincente è sempre la sua preferita tra i possibili esiti. Se il dittatore ha diverse alternative preferite legate tra i possibili risultati, allora l'alternativa vincente è semplicemente una di queste.
Teorema di Gibbard-Satterthwaite - Se una regola di voto ha almeno 3 possibili risultati e se non è manipolabile, allora è dittatoriale.
Il meccanismo della dittatura seriale funziona come segue. Se l'elettore 1 preferisce una sola alternativa, allora tale alternativa è eletta. In caso contrario, limitiamo i risultati possibili ai nostri candidati preferiti in parità, e ci interessa il ballottaggio dell'elettore 2. Se quest'ultimo ha una sola alternativa preferita tra quelle ancora in corsa, allora viene eletta questa. Altrimenti, limitiamo ulteriormente i possibili risultati, ecc. Se ci sono ancora più candidati in lizza dopo aver consultato tutte le schede, si decide tra i candidati secondo un criterio arbitrario.
Questa regola di voto non può essere manipolata: un elettore ha sempre interesse ad annunciare le sue reali preferenze. È anche dittatoriale, e il suo dittatore è l'elettore 1: l'alternativa vincente è sempre la sua preferita o, se preferisce più uguali, scelta tra queste.
Se ci sono solo due possibili risultati, una regola di voto può essere non manipolabile senza essere dittatoriale. È il caso, ad esempio, del voto a maggioranza semplice: ogni scrutinio attribuisce 1 punto all'alternativa elencata in alto e 0 punti all'altra. Questa regola non può essere manipolata perché un elettore ha sempre interesse a dare le sue preferenze sincere; ed è chiaramente non dittatoriale. Molte altre regole non sono né manipolabili né dittatoriali: ad esempio, si può immaginare che l'alternativa vince se riceve i due terzi dei voti e vince altrimenti.
Considera la seguente regola. Vengono eliminati tutti i candidati, ad eccezione del candidato / i posto / i al primo posto nel ballottaggio per l'elettore 1. I candidati ancora in lizza vengono poi decisi con il metodo Borda . La regola così descritta è dittatoriale per definizione. Tuttavia, può essere gestito, per gli stessi motivi del metodo Borda. Quindi, il teorema di Gibbard-Satterthwaite è davvero un'implicazione e non un'equivalenza.
Ci interessa ora il caso in cui si ipotizzi che un elettore sia indifferente tra due candidati. Indichiamo l'insieme di totale ordini severi su e definire una regola di voto rigida come una funzione . Le definizioni di risultati possibili , manipolabili e dittatoriali si estendono naturalmente in questo quadro.
Per una regola di voto rigorosa, è vero il contrario del teorema di Gibbard-Satterthwaite. In effetti, una regola di voto rigorosa è dittatoriale se e solo se sceglie sempre il candidato preferito del dittatore tra i possibili risultati; in particolare, non dipende affatto dai voti degli altri elettori. Pertanto, non è manipolabile: il dittatore è perfettamente difeso dal suo voto sincero, e gli altri elettori non hanno alcuna influenza sul risultato, quindi non hanno nulla da perdere votando sinceramente. Si ottiene quindi il seguente risultato di equivalenza.
Corollario - Se una regola di voto rigorosa ha almeno 3 possibili risultati, non può essere manipolata se e solo se è dittatoriale.
Sia nel teorema che nel corollario, non è necessario assumere che qualsiasi alternativa possa essere eletta. Si presume semplicemente che almeno tre di essi possano essere, ovvero siano possibili risultati della regola di voto. È perfettamente possibile che altre alternative non possano essere elette in nessuna circostanza: il teorema e il corollario valgono lo stesso. Tuttavia, il corollario è talvolta presentato in una forma meno generale: invece di presumere che la regola abbia almeno tre possibili esiti, a volte facciamo l'ipotesi che contenga almeno tre elementi e che la regola di voto sia suriettiva , cioè , qualsiasi alternativa può vincere. La surroganza a volte viene addirittura sostituita dal presupposto che la regola sia unanime , nel senso che se tutti gli elettori preferiscono lo stesso candidato, allora questo deve essere eletto.
L'aspetto strategico dell'atto di voto era già ben identificato nel 1876 da Charles Dodgson, uno dei pionieri della teoria della scelta sociale, noto anche come Lewis Carroll . La sua citazione (su un particolare sistema di voto) è stata resa famosa da Duncan Black :
"Questo principio di voto rende un'elezione più un gioco di abilità che un vero test dei desideri degli elettori".
Durante gli anni '50, Robin Farquharson pubblicò articoli influenti sulla questione del voto strategico. In un articolo scritto con Michael Dummett , ipotizza che le regole di voto deterministiche con almeno tre possibili risultati affrontino un problema intrinseco con il voto strategico. Questa congettura di Farquharson-Dummett è provata indipendentemente da Allan Gibbard e Mark Satterthwaite . In un articolo del 1973, Gibbard usa il teorema di Arrow per dimostrare il teorema che ora porta il suo nome e quindi deduce il risultato attuale, che è una conseguenza immediata. Indipendentemente, Satterthwaite dimostra questo stesso risultato nella sua tesi di dottorato nel 1973, quindi lo pubblica come articolo nel 1975. Anche lui si basa sul teorema di Arrow , ma senza esporre la versione più generale data dal teorema di Gibbard . Successivamente, vari autori sviluppano varianti della dimostrazione, generalmente più dirette e più brevi, sia per il teorema stesso, sia per i corollari e le versioni indebolite di cui sopra.
Il teorema di Gibbard ci permette di considerare i meccanismi di scelta collettiva che possono essere non ordinali, cioè dove l'azione di un elettore non è necessariamente quella di fornire un ordine di preferenza sui candidati. Il teorema di Gibbard del 1978 e il teorema di Hylland estendono questi risultati ai meccanismi non deterministici, vale a dire dove l'esito può dipendere non solo dalle newsletter ma coinvolgere anche un elemento di casualità.
Il teorema di Duggan-Schwartz estende questo risultato in un'altra direzione, considerando regole di voto deterministiche, ma che selezionano un sottoinsieme non vuoto di candidati invece di uno solo.
Il teorema di Gibbard-Satterthwaite è generalmente presentato come il risultato della teoria della scelta sociale che si applica ai sistemi elettorali, ma può anche essere visto come il risultato fondamentale della teoria dei meccanismi di incentivazione , che si occupa dei metodi decisionali collettivi di progettazione, possibilmente coinvolgendo trasferimenti monetari . Noam Nisan presenta questa relazione come segue:
"Il teorema di Gibbard-Satterthwaite sembra annullare ogni speranza di progettare funzioni di scelta sociale che inducano a rivelare le proprie vere preferenze. L'intero campo disciplinare della teoria dei meccanismi di incentivazione tenta di sfuggire a questo teorema di impossibilità utilizzando varie modifiche di questo modello".
L'idea principale di queste scappatoie è di limitarsi a classi ristrette di preferenze, a differenza del teorema di Gibbard-Satterthwaite che consente preferenze arbitrarie. Pertanto, in questa disciplina, si presume spesso che gli agenti abbiano preferenze quasi lineari , il che significa che la loro funzione di utilità varia linearmente rispetto alla quantità di denaro. In questo caso, i trasferimenti di denaro possono essere utilizzati per incoraggiarli ad agire sinceramente. Questa idea è sfruttata nell'asta Vickrey-Clarke-Groves .