Gibbard-Satterthwaite tétel

A társadalmi választás elméletében a Gibbard-Satterthwaite-tétel egy olyan eredmény, amelyet Allan Gibbard filozófus 1973-ban és Mark Satterthwaite közgazdász 1975-ben önállóan publikált . Ez azt mutatja, hogy minden determinista szavazási szabály kielégíti a következő tulajdonságok legalább egyikét:

A szabály diktatórikus, vagyis hogy van egy kiváltságos választópolgár, aki kiválaszthatja a győztest; vagy
A szabály csak két különböző jelölt megválasztását teszi lehetővé; vagy
A szabály érzékeny a taktikai szavazásra: vannak olyan helyzetek, amikor nem az őszinte szavazás védi a legjobban a választópolgár véleményét.

Ez a tétel csak a rendes szavazási szabályokra korlátozódik: a választópolgár cselekedete abból áll, hogy a javasolt opciókat preferencia sorrendben adja meg. A Gibbard tétel általánosabban figyelembe veheti a kollektív választási mechanizmusokat, amelyek nem feltétlenül sorosak: például olyan szavazási rendszerek, ahol a választók jegyzeteket rendelnek a jelöltekhez. Más, még általánosabb tételek , az 1978-as Gibbard-tétel és a Hilland-tétel kiterjesztik ezeket az eredményeket a nem determinisztikus mechanizmusokra, vagyis ahol az eredmény nemcsak a választók cselekedeteitől függhet, hanem a véletlen elemével is bírhat.

Bemutatás

Tekintsük a szavazók , és akik szeretnének választani együtt az egyik lehetőség közül négy jelölt , , és . Feltételezzük, hogy Borda-módszert alkalmaznak : minden választópolgár sorrendben közli a jelöltekkel. Minden szavazás után 3 pont jár az élmezőnynek, 2 pont a másodiknak, 1 pont a harmadiknak és az utolsónak nincs pont. Az összes szavazat összeszámlálása után a legtöbb ponttal rendelkező jelöltet választják meg. $1$ $2$ $3$ $nál nél$ $b$ $vs.$ $d$

Tegyük fel, hogy a preferenciák a következők.

nál nélvs.vs.bbbvs.dddnál nélnál nél{\ displaystyle {\ begin {tömb} {c | c | c} a & c & c \\ b & b & b \\ c & d & d \\ d & a & a \ end {tömb}}}

{\ displaystyle {\ begin {tömb} {c | c | c} a & c & c \\ b & b & b \\ c & d & d \\ d & a & a \ end {tömb}}}

Ez a jelölés azt jelenti, hogy a választó inkább , utána következik , és ; szavazók és mindegyiket előnyben részesítik , majd a , és . Ha a választók szavazati őszintén, akkor a pontszámok a következők: . Ezért választják meg, 7 ponttal.

1

nál nél

b

vs.

d

2

3

vs.

b

d

nál nél

{\ displaystyle (a: 3, b: 6, c: 7, d: 2)}

vs.

De a választópolgár megállapíthatja, hogy egy másik szavazás jobban védi a véleményét. Tegyük fel, hogy módosítja szavazólapját, hogy a következő helyzethez jusson. $1$

bvs.vs.nál nélbbdddvs.nál nélnál nél{\ displaystyle {\ begin {tömb} {c | c | c} b & c & c \\ a & b & b \\ d & d & d \\ c & a & a \ end {tömb}}}

{\ displaystyle {\ begin {tömb} {c | c | c} b & c & c \\ a & b & b \\ d & d & d \\ c & a & a \ end {tömb}}}

A választó stratégiai módon húzta fel és alá a jelöltet . Az új eredmények a következők: . Ezért választják meg. A választó megelégszik azzal, hogy őszinte preferenciáitól eltérő szavazólapot nyújtott be, mivel inkább az új eredményt részesíti előnyben , mint azt az eredményt, amelyet őszinte szavazással ért volna el.

1

b

vs.

{\ displaystyle (a: 2, b: 7, c: 6, d: 3)}

b

1

b

vs.

Állítólag Borda módszere manipulálható : vannak olyan helyzetek, amikor az őszinte szavazás nem a legjobban védi a választópolgár preferenciáit.

Sajnos a Gibbard-Satterthwaite-tétel azt mutatja, hogy a szavazási szabály szükségszerűen manipulálható, kivéve valószínűleg két esetet: ha van olyan privilegizált választópolgár, akinek diktatórikus hatalma van, vagy ha a szabály csak egy választását teszi lehetővé. ”Két lehetséges döntés között.

A tétel állítása

Megjegyezzük az állítólag elkészült alternatívák halmazát , amelyeket jelölteknek is nevezünk , még akkor is, ha nem feltétlenül emberek: egy adott tantárgy esetében is különböző lehetséges döntések lehetnek. Megjegyezzük az összes szavazót . A gyenge szigorú megrendelések halmazát (en) a következőkre jelöljük : ennek a halmaznak egy eleme lehetővé teszi a választói preferenciák képviseletét. A szavazási szabály függvény . Érvként egy preferencia-profilt vesz fel, és egy nyertes jelöltet ad vissza. ${\ mathcal {A}}$ ${\ displaystyle {\ mathcal {N}} = \ {1, \ ldots, n \}}$ $\ mathcal {P}$ ${\ mathcal {A}}$ ${\ displaystyle f: {\ mathcal {P}} ^ {n} \ - {\ mathcal {A}}}$ ${\ displaystyle (P_ {1}, \ ldots, P_ {n}) \ itt: {\ mathcal {P}} ^ {n}}$

Azt mondjuk, hogy az manipulálható akkor és csak akkor, ha van egy profilt , ahol egy bizonyos választói változtatásával a szavazólapon egy másik szavazás , be tudja szerezni az eredménye, hogy jobban kedveli (abban az értelemben, ). $f$ ${\ displaystyle (P_ {1}, \ ldots, P_ {n}) \ itt: {\ mathcal {P}} ^ {n}}$ $én$ $P_i$ ${\ displaystyle P_ {i} '}$ $P_i$

Megjegyezzük a választás képét , vagyis a választás lehetséges eredményeinek halmazát . Így azt mondjuk, hogy legalább három lehetséges kimenetele van, és csak akkor, ha legalább három eleme van. ${\ displaystyle f ({\ mathcal {P}} ^ {n})}$ $f$ $f$ ${\ displaystyle f ({\ mathcal {P}} ^ {n})}$

Azt mondják, hogy a diktatórikus akkor és csak akkor, ha van a választópolgár , aki a diktátor , ez azt jelenti, hogy a győztes alternatíva mindig a kedvenc közül a lehetséges következményeket. Ha a diktátornak több előnyben részesített alternatívája van a lehetséges eredmények között, akkor a győztes alternatíva egyszerűen az egyik. $f$ $én$

Gibbard-Satterthwaite-tétel - Ha egy szavazási szabálynak legalább 3 lehetséges eredménye van, és ha nem manipulálható, akkor diktatórikus.

Példák

Soros diktatúra

A soros diktatúra mechanizmusa a következőképpen működik. Ha az 1. választópolgár csak egy alternatívát preferál, akkor ezt az alternatívát választják. Ellenkező esetben a lehetséges eredményeket a holtversenyben szereplő kedvenc jelöltjeinkre korlátozzuk, és érdekel bennünket a 2. szavazó szavazata. Ha az utóbbinak csak egy előnyben részesített alternatívája van, akkor is ezt választják. Ellenkező esetben tovább korlátozzuk a lehetséges eredményeket stb. Ha az összes szavazólap megismerése után még mindig több jelölt indul, a jelöltekről önkényes kritérium alapján döntenek.

Ezt a szavazási szabályt nem lehet manipulálni: a választópolgárnak mindig érdeke, hogy bejelentse valódi preferenciáit. Ő is diktatórikus, és diktátora az 1. szavazó: a győztes alternatíva mindig a kedvence, vagy ha több egyenlőt szeret, akkor közülük választja.

Egyszerű többségi szavazás

Ha csak két lehetséges eredmény van, akkor a szavazási szabály nem lehet manipulálható anélkül, hogy diktatórikus lenne. Ilyen például az egyszerű többségi szavazás: minden szavazás 1 pontot ad a tetején felsorolt alternatívának, és 0 pontot a másiknak. Ezt a szabályt nem lehet manipulálni, mert a választópolgárnak mindig érdeke, hogy őszinte preferenciáit megadja; és nyilvánvalóan nem diktatórikus. Sok más szabály nem manipulálható és nem is diktatórikus: például el lehet képzelni, hogy az alternatíva akkor nyer, ha a szavazatok kétharmadát megkapja, és másképp nyer. $nál nél$ $b$

Olyan mechanizmus, amely megmutatja, hogy a fordított nem igaz

Vegye figyelembe a következő szabályt. Az összes jelölt kiesik, kivéve azokat a jelölteket, akik az 1. szavazó szavazólapján az első helyen szerepelnek. A továbbra is induló jelöltekről Borda módszerrel döntenek . Az így leírt szabály definíció szerint diktatórikus. Ugyanakkor kezelhető, ugyanazon okok miatt, mint a Borda módszer. Így a Gibbard-Satterthwaite-tétel valóban implikáció és nem ekvivalencia.

Következmény

Most arra az esetre vagyunk kíváncsiak, amikor feltételezik, hogy egy választópolgár közömbös két jelölt között. Jelöljük a készlet teljes szigorúan megtiltotta a és határozza meg a szigorú szavazási szabályt függvényében . A lehetséges , manipulálható , diktatórikus eredmények definíciói természetesen e keretek között terjednek ki. $\ mathcal {L}$ ${\ mathcal {A}}$ ${\ displaystyle f: {\ mathcal {L}} ^ {n} \ - {\ mathcal {A}}}$

Szigorú szavazási szabály esetén a Gibbard-Satterthwaite-tétel fordítottja igaz. A szigorú szavazási szabály valóban akkor diktatórikus, ha csak akkor választja ki a diktátor által preferált jelöltet a lehetséges eredmények közül; különösen egyáltalán nem függ a többi választópolgár szavazatától. Ezért nem manipulálható: a diktátort őszinte szavazata tökéletesen védi, a többi szavazónak pedig nincs befolyása az eredményre, így nincs őszintén szavazó veszteség. Ezért a következő egyenértékűségi eredményt kapjuk.

Következmény - Ha egy szigorú szavazási szabálynak legalább 3 lehetséges eredménye van, akkor csak akkor lehet manipulálni, ha diktatórikus.

Mind a tételben, mind a következményekben nem kell feltételeznünk, hogy bármilyen alternatíva megválasztható. Egyszerűen feltételezzük, hogy közülük legalább hárman lehetnek, vagyis a szavazási szabály lehetséges eredményei . Teljesen lehetséges, hogy más alternatívákat semmilyen körülmények között nem lehet megválasztani: a tétel és a következmény ugyanúgy érvényes. A következményeket azonban olykor kevésbé általános formában mutatják be: ahelyett, hogy azt feltételeznénk, hogy a szabálynak legalább három lehetséges eredménye van, néha azt a feltételezést tesszük, amely legalább három elemet tartalmaz, és hogy a szavazási szabály surjektív , vagyis , bármelyik alternatíva nyerhet. A szelektivitást néha még az a feltételezés is felváltja, hogy a szabály egyhangú , abban az értelemben, hogy ha az összes választópolgár ugyanazt a jelöltet részesíti előnyben, akkor ezt kell választani. ${\ mathcal {A}}$

Történelmi

A szavazási aktus stratégiai aspektusát 1876-ban Charles Dodgson, a társadalmi választás elméletének egyik úttörője, más néven Lewis Carroll jól felismerte . Idézetét (egy adott szavazási rendszerről) Duncan Black tette híressé :

"A szavazás ezen elve a választást inkább ügyességi játékgá teszi, mint a választók kívánságainak valódi próbáját."

Az ötvenes években Robin Farquharson befolyásos cikkeket tett közzé a stratégiai szavazás kérdésében. Michael Dummett- nel írt cikkében sejteti, hogy a determinisztikus, legalább három lehetséges kimenetelű szavazási szabályok szembesülnek a stratégiai szavazás belső problémájával. Ezt a Farquharson-Dummett sejtést Allan Gibbard és Mark Satterthwaite függetlenül bizonyítja . Egy 1973-as cikkben Gibbard Arrow tételével bizonyítja azt a tételt, amely most a nevét viseli, majd levezeti a jelenlegi eredményt, ami azonnali következménye. Függetlenül attól, hogy Satterthwaite ugyanezt az eredményt bizonyítja 1973-ban írt doktori disszertációjában, majd 1975-ben cikkként publikálja. Arrow-tételen is alapul , de anélkül, hogy kitenné a Gibbard-tétel által adott általánosabb változatot . Ezt követően különböző szerzők a bizonyítás variánsait fejlesztik, általában közvetlenebbek és rövidebbek, akár a tétel, akár a fent említett következmények és gyengített változatok esetében.

Kapcsolódó eredmények

A Gibbard-tétel lehetővé teszi számunkra, hogy megvizsgáljuk azokat a kollektív választási mechanizmusokat, amelyek nem sorosak lehetnek, vagyis amikor a választópolgár cselekedete nem feltétlenül elősegíti a jelöltek preferenciájának rendjét. A Gibbard tétel 1978 és tétel Hylland kiterjeszteni ezeket az eredményeket a nem-determinisztikus mechanizmusok vagyis ahol az eredmény esetenként nemcsak hírlevelek hanem magában eleme esélye.

A Duggan-Schwartz-tétel ezt az eredményt egy másik irányba terjeszti, figyelembe véve a determinisztikus szavazási szabályokat, de amelyek csak egy helyett a jelöltek nem üres részhalmazát választják ki.

Utókor

A Gibbard-Satterthwaite-tétel általában a választási rendszerekre vonatkozó társadalmi választási elmélet eredményeként kerül bemutatásra , de felfogható az ösztönző mechanizmus-elmélet megalapozó eredményének is , amely a kollektív döntéshozatali módszerekkel foglalkozik, esetleg monetáris transzferekkel is. . Noam Nisan a következőképpen mutatja be ezt a kapcsolatot:

"Úgy tűnik, hogy a Gibbard-Satterthwaite-tétel semmissé nem teszi azt a reményt, hogy olyan társadalmi választási funkciókat tervezzenek meg, amelyek valódi preferenciáinak felfedését indukálják. Az ösztönző mechanizmus-elmélet teljes diszciplináris területe megkísérli elkerülni ezt a lehetetlenségi tételt a modell különféle módosításaival."

E kiskapuk fő gondolata az, hogy a preferenciák korlátozott osztályaira kell korlátozni, ellentétben az önkényes preferenciákat lehetővé tevő Gibbard-Satterthwaite-tétellel. Így ebben a tudományágban gyakran feltételezik, hogy az ügynökök kvázi lineáris preferenciákkal rendelkeznek , ami azt jelenti, hogy hasznossági funkciójuk lineárisan változik a pénz mennyiségéhez képest. Ebben az esetben a készpénzátutalások ösztönözhetik őket az őszinte cselekvésre. Ezt az ötletet használják ki a Vickrey-Clarke-Groves aukción .

Megjegyzések és hivatkozások

(en) Allan Gibbard , „ A szavazási rendszerek manipulálása: általános eredmény ” , Econometrica , vol. 41,1973, P. 587-601
(en) Mark Allen Satterthwaite , „ Stratégiabiztonság és nyílfeltételek: létezési és levelezési tételek a szavazási eljárásokhoz és a szociális jóléti funkciókhoz ” , Journal of Economic Theory , vol. 10, n o 21975, P. 187–217 ( DOI 10.1016 / 0022-0531 (75) 90050–2 )
(in) Tjark Weber , " Alternatívák vs. Eredmények: Megjegyzés a Gibbard-Satterthwaite-tételhez ” , műszaki jelentés (Müncheni Egyetemi Könyvtár) ,2009( online olvasás )
(in) Philip Reny , " Arrow-tétel és a Gibbard-Satterthwaite-tétel: Egységes megközelítés " , Economics Letters , vol. 70, n o 1,2001, P. 99–105 ( online olvasás )
(en) Jean-Pierre Benoît , „ The Gibbard-Satterthwaite Theorem: A Simple Proof ” , Economics Letters , vol. 69, n o 3,2000, P. 319 –322 ( ISSN 0165-1765 , online olvasás )
(in) Arunava Sen , " A Gibbard-Satterthwaite tétel újabb közvetlen bizonyítéka " , Economics Letters , vol. 70, n o 3,2001, P. 381 –385 ( ISSN 0165-1765 , online olvasás )
(in) Duncan fekete , elmélete bizottságok és a választások , Cambridge University Press,1958
"A szavazásnak ez az elve a választást inkább ügyességi játékgá teszi, mintsem a választók kívánságainak valódi tesztjévé."
(in) Robin Farquharson , " őszinteség a szavazási eljárások " , Oxford Economic Papers, New Series , Vol. 8, n o 1,1956, P. 80–89 ( JSTOR 2662065 )
(in) Michael Dummett és Robin Farquharson , " stabilitása szavazás " , Econometrica , Vol. 29, n o 1,1961, P. 33–43 ( DOI 10.2307 / 1907685 , JSTOR 1907685 )
(in) Michael Dummett , " A munka és az élet Robin Farquharson " , Social Choice és Népjóléti , vol. 25, n o 22005, P. 475–483 ( DOI 10.1007 / s00355-005-0014-x , JSTOR 41106711 )
(in) Peter Gärdenfors , " A tömör tétel bizonyítása azt képességeivel Szociális Choice " , Public Choice , vol. 32,1977, P. 137–142 ( ISSN 0048-5829 , online olvasás )
(in) Salvador Barberá , " Stratégiabiztonság és sarkalatos szavazók: A Gibbard-Satterthwaite-tétel közvetlen igazolása " , International Economic Review , vol. 24, n o 21983, P. 413-417 ( ISSN 0020-6598 , olvasható online )
(in) Michael Dummett , szavazási eljárások , Oxford University Press ,1984( ISBN 978-0-19-876188-4 )
(in) Rudolf Fara és Maurice Hall , " Interjú Michael Dummett-szel: Az analitikus filozófiától a szavazás elemzéséig és azon túl " , Social Choice and Welfare , vol. 27, n o 22006, P. 347-364 ( DOI 10.1007 / s00355-006-0128-9 , JSTOR 41106783 )
(in) Herve Moulin , Axiómái Cooperative döntéshozatal , Cambridge University Press ,1991, 332 p. ( ISBN 978-0-521-42458-5 , online olvasás )
(hu-GB) Alan D. Taylor , „ A szavazási rendszerek manipulálhatósága ” , The American Mathematical Monthly , vol. 109,2002. április, P. 321–337 ( DOI 10.2307 / 2695497 , JSTOR 2695497 )
(in) John Duggan és Thomas Schwartz : " Stratégiai manipulálhatóság határozottság vagy megosztott meggyőződés nélkül: Gibbard-Satterthwaite általánosítva " , Social Choice and Welfare , vol. 17, n o 1,2000, P. 85–93 ( ISSN 0176-1714 , online olvasás )
(in) Vijay Vazirani Noam Niszán , Tim Roughgarden és Éva Tardos , algoritmikus játékelmélet , Cambridge, Egyesült Királyság, Cambridge University Press ,2007, 754 p. ( ISBN 978-0-521-87282-9 és 0-521-87282-0 ) , p. 215
"Úgy tűnik, hogy a GS-tétel megsemmisíti az ösztönzéssel kompatibilis társadalmi választási funkciók megtervezésének reményét. A Mechanism Design teljes területe a modell különféle módosításainak felhasználásával próbál menekülni e lehetetlenségi eredmény elől."

Kapcsolódó cikkek