Gibbards sætning - Gibbard's theorem

Inden for mekanismedesign og teori om socialt valg er Gibbards sætning et resultat bevist af filosofen Allan Gibbard i 1973. Det hedder, at mindst en af de følgende tre egenskaber skal indeholde for enhver deterministisk proces med kollektiv beslutning:

Processen er diktatorisk , dvs. der findes en fremtrædende agent, der kan påtvinge resultatet;
Processen begrænser de mulige resultater til kun to muligheder;
Processen er åben for strategisk afstemning : når en agent har identificeret deres præferencer, er det muligt, at de ikke har nogen handling til deres rådighed, der bedst forsvarer disse præferencer uanset de andre agenters handlinger.

En følge af denne sætning er Gibbard – Satterthwaite sætning om stemmeregler. Den væsentligste forskel mellem de to er, at Gibbard-Satterthwaite sætning er begrænset til rangerede (ordinære) afstemningsregler : en vælgers handling består i at give en præferencerangering frem for de tilgængelige indstillinger. Gibbards sætning er mere generel og overvejer processer med kollektiv beslutning, som muligvis ikke er ordinær: for eksempel stemmesystemer, hvor vælgerne tildeler kandidater karakterer. Gibbards sætning kan bevises ved hjælp af Arrow's umulighedssætning .

Gibbards sætning generaliseres i sig selv af Gibbards 1978-sætning og Hyllands sætning , der udvider disse resultater til ikke-deterministiske processer, dvs. hvor resultatet ikke kun afhænger af agenternes handlinger, men også kan medføre et element af tilfældighed.

Oversigt

Overvej nogle vælgere , og som ønsker at vælge en indstilling mellem tre alternativer: , og . Antag, at de bruger godkendelsesafstemning : hver vælger tildeler hver kandidat karakteren 1 (godkendelse) eller 0 (tilbageholder godkendelse). For eksempel er en autoriseret afstemning: det betyder, at vælgeren godkender kandidater og men ikke godkender kandidat . Når stemmesedlerne er samlet, erklæres kandidaten med den højeste samlede karakter som vinder. Bånd mellem kandidater er opdelt i alfabetisk rækkefølge: for eksempel, hvis der er uafgjort mellem kandidater og derefter vinder. ${\ displaystyle 1}$ ${\ displaystyle 2}$ ${\ displaystyle 3}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle c}$ ${\ displaystyle (1,1,0)}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle c}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$

Antag, at vælgeren foretrækker et alternativ , derefter og derefter . Hvilken afstemning vil bedst forsvare hendes meninger? Overvej f.eks. De to følgende situationer. ${\ displaystyle 1}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle c}$

Hvis de to andre vælgere henholdsvis kastet afstemninger og derefter vælgere har kun én stemmeseddel, der fører til valg af hendes foretrukne alternativ : . ${\ displaystyle (0,1,1)}$ ${\ displaystyle (1,1,1)}$ ${\ displaystyle 1}$ ${\ displaystyle a}$ ${\ displaystyle (1,0,0)}$
Men hvis vi antager i stedet, at de to andre vælgere henholdsvis kastet afstemninger og derefter vælgere bør ikke stemme , fordi det gør win; hun skulle hellere stemme , hvilket gør vinder. ${\ displaystyle (0,0,1)}$ ${\ displaystyle (0,1,1)}$ ${\ displaystyle 1}$ ${\ displaystyle (1,0,0)}$ ${\ displaystyle c}$ ${\ displaystyle (1,1,0)}$ ${\ displaystyle b}$

For at opsummere står vælgeren over for et strategisk afstemningsdilemma: afhængigt af de afstemninger, som de andre vælgere vil afgive, eller kan være en afstemning, der bedst forsvarer hendes meninger. Vi siger derefter, at godkendelsesafstemning ikke er strategisikker : når vælgeren har identificeret sine egne præferencer, har hun ikke en afstemning til rådighed, der bedst forsvarer hendes meninger i alle situationer; hun har brug for at handle strategisk, muligvis ved at spionere over de andre vælgere for at bestemme, hvordan de har til hensigt at stemme. ${\ displaystyle 1}$ ${\ displaystyle (1,0,0)}$ ${\ displaystyle (1,1,0)}$

Gibbards sætning siger, at en deterministisk proces med kollektiv beslutning ikke kan være strategisikker, undtagen muligvis i to tilfælde: hvis der er en fremtrædende agent, der har en diktatorisk magt, eller hvis processen kun begrænser resultatet til to mulige muligheder.

Formel erklæring

Lad være sæt af alternativer , som også kan kaldes kandidater i en kontekst af afstemning. Lad være sættet af agenter , som også kan kaldes spillere eller vælgere, afhængigt af applikationens kontekst. Lad være et sæt for hver agent , der repræsenterer de tilgængelige strategier for agent ; antage, at det er endeligt. Lad være en funktion, der til hvert -tuple af strategier kortlægger et alternativ. Funktionen kaldes en spilform . Med andre ord er en spilform i det væsentlige defineret som et n- spiller-spil , men uden hjælpeprogrammer forbundet med de mulige resultater: den beskriver kun proceduren uden at angive på forhånd den gevinst, som hver agent ville få fra hvert resultat. ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle {\ mathcal {N}} = \ {1, \ ldots, n \}}$ ${\ displaystyle i}$ ${\ displaystyle {\ mathcal {S}} _ {i}}$ ${\ displaystyle i}$ ${\ displaystyle {\ mathcal {S}} _ {i}}$ ${\ displaystyle g}$ ${\ displaystyle n}$ ${\ displaystyle (s_ {1}, \ ldots, s_ {n}) \ i {\ mathcal {S}} _ {1} \ times \ cdots \ times {\ mathcal {S}} _ {n}}$ ${\ displaystyle g}$

Vi siger, at det er strategibeskyttet (oprindeligt kaldet: ligetil ), hvis der for enhver agent og for enhver streng svag orden over alternativerne findes en strategi, der er dominerende for agent, når hun har præferencer : der er ingen profil for strategier for de andre agenter som sådan at en anden strategi , forskellig fra , ville føre til et strengt bedre resultat (i betydningen ). Denne egenskab er ønskelig for en demokratisk beslutningsproces: det betyder, at når først agenten har identificeret sine egne præferencer , kan hun vælge en strategi, der bedst forsvarer sine præferencer uden behov for at kende eller gætte de strategier, der er valgt af de andre agenter. ${\ displaystyle g}$ ${\ displaystyle i}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle s_ {i} ^ {*} (P_ {i})}$ ${\ displaystyle i}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle s_ {i}}$ ${\ displaystyle s_ {i} ^ {*} (P_ {i})}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle s_ {i} ^ {*} (P_ {i})}$

Vi lader og betegner med rækkevidden , dvs. sæt af de mulige resultater af spilformen. For eksempel siger vi, at det har mindst 3 mulige resultater, hvis og kun hvis kardinaliteten er 3 eller mere. Da strategisættene er endelige, er det også begrænset; således, selv om sæt af alternativer ikke antages at være endeligt, er delmængden af mulige resultater nødvendigvis sådan. ${\ displaystyle {\ mathcal {S}} = {\ mathcal {S}} _ {1} \ times \ cdots \ times {\ mathcal {S}} _ {n}}$ ${\ displaystyle g ({\ mathcal {S}})}$ ${\ displaystyle g}$ ${\ displaystyle g}$ ${\ displaystyle g ({\ mathcal {S}})}$ ${\ displaystyle g ({\ mathcal {S}})}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle g ({\ mathcal {S}})}$

Vi siger, at det er diktatorisk, hvis der findes en agent, der er en diktator , i den forstand, at agenten for ethvert muligt resultat har en strategi til rådighed, der sikrer, at resultatet bliver , uanset hvilke strategier de andre agenter vælger. ${\ displaystyle g}$ ${\ displaystyle i}$ ${\ displaystyle a \ in g ({\ mathcal {S}})}$ ${\ displaystyle i}$ ${\ displaystyle a}$

Gibbards sætning - Hvis en spilform ikke er diktatorisk og har mindst 3 mulige resultater, er den ikke strategisikker.

Eksempler

Seriediktatur

Vi antager, at hver vælger kommunikerer en streng svag orden over kandidaterne. Den serielle diktatur er defineret som følger. Hvis vælger 1 har en unik kandidat, kan denne kandidat vælges. Ellers er mulige resultater begrænset til hans ex-aequo mest elskede kandidater, og de andre kandidater elimineres. Derefter undersøges vælger 2's afstemning: hvis han har en unik bedst ønsket kandidat blandt de ikke-eliminerede, så vælges denne kandidat. Ellers reduceres listen over mulige resultater igen osv. Hvis der stadig er flere ikke-eliminerede kandidater, efter at alle stemmesedler er blevet undersøgt, anvendes en vilkårlig bindende regel.

Denne spilform er strategisikker: uanset hvilke vælgeres præferencer, han har en dominerende strategi, der består i at erklære sin oprigtige præferenceordning. Det er også diktatorisk, og dets diktator er vælger 1: hvis hans ønsker at se kandidat valgt, så er han bare nødt til at kommunikere en præferenceordre, hvor er den unikke mest foretrukne kandidat. ${\ displaystyle a}$ ${\ displaystyle a}$

Simpel flertalsafstemning

Hvis der kun er 2 mulige resultater, kan en spilform være strategisikker og ikke diktatorisk. For eksempel er det tilfældet med simpelt flertalsafstemning: hver vælger afgiver en afstemning om sit mest populære alternativ (blandt de to mulige resultater), og alternativet med flest stemmer erklæres vinder. Denne spilform er strategisikker, fordi det altid er optimalt at stemme på ens mest populære alternativ (medmindre man er ligeglad med dem). Det er dog tydeligvis ikke diktatorisk. Mange andre spilformer er strategisikre og ikke diktatoriske: antag for eksempel, at alternativet vinder, hvis det får to tredjedele af stemmerne og vinder ellers. ${\ displaystyle a}$ ${\ displaystyle b}$

En spilform, der viser, at det omvendte ikke holder

Overvej følgende spilform. Vælger 1 kan stemme på en kandidat efter eget valg, eller hun kan undlade at stemme. I det første tilfælde vælges den angivne kandidat automatisk. Ellers bruger de andre vælgere en klassisk afstemningsregel, for eksempel Borda-optællingen . Denne spilform er klart diktatorisk, fordi vælger 1 kan påtvinge resultatet. Det er dog ikke strategisikkert: de andre vælgere står over for det samme spørgsmål om strategisk afstemning som i den sædvanlige Borda-optælling. Således er Gibbards sætning en implikation og ikke en ækvivalens.

Languages

In other projects