Processing math: 100%

Izborni paradoksi


Mila Botić
Matematički odsjek PMF-a
Sveučilište u Zagrabu
Vedran Krčadinac
Matematički odsjek PMF-a
Sveučilište u Zagrabu
krcko@math.hr


Sažetak
Objašnjavamo matematički model za izborni proces. Iskazujemo teoreme nemogućnosti, prema kojima određeni „demokratski” zahtjevi na metodu određivanja pobjednika izbora dovode do postojanja „diktatora”.



1Uvod

Teorija društvenog izbora (eng. social choice theory) je disciplina društvenih znanosti na granici između ekonomije, politologije i filozofije. Bavi se načinom donošenja kolektivnih odluka na temelju preferencija pojedinaca. Početkom moderne teorije društvenog izbora smatra se knjiga Social choice and individual values [1] američkog ekonomista Kennetha J. Arrowa, dobitnika Nobelove nagrade za ekonomiju 1972. godine. Među ranijim autorima koji su pisali o sličnoj tematici su matematičari Jean-Charles de Borda (1733. - 1799.), Nicolas Caritat de Condorcet (1743. - 1794.), Pierre-Simon Laplace (1749. - 1827.) i Charles Lutwidge Dodgson (1832. - 1898.), poznatiji kao Lewis Carroll – autor „Alise u zemlji čudesa”. Teorija se i danas razvija, o čemu svjedoče znanstveni časopisi Social Choice and Welfare (ISSN 0176-1714) i Public Choice (ISSN 0048-5829) iz srodne discipline, teorije javnog izbora.

U modernim znanstvenim radovima iz ekonomije u velikoj se mjeri koristi precizan matematički jezik. Cilj ovog članka je prezentirati neke matematičke aspekte teorije društvenog izbora. Objašnjavamo osnovne definicije i ideje koje stoje iza njih te iskaze takozvanih teorema nemogućnosti, koji se mogu opisati kao izborni paradoksi. Riječ je o zahtjevima na metodu određivanja pobjednika izbora koji djeluju pravedno i razumno te ćemo ih stoga zvati „aksiomima demokracije”. Međutim, iz zahtjeva slijedi postojanje „diktatora”, tj. birača čiji glas jednoznačno određuje ishod izbora neovisno o glasovima ostalih birača. Dokaze teorema u ovom članku preskačemo i upućujemo zainteresirane čitatelje na literaturu u kojoj se nalaze. Na kraju svake cjeline navodimo zadatke koji služe boljem razumijevanju izloženih pojmova. Rješenja zadataka dajemo na kraju članka.

2Kako rangirati kandidate?

Na izborima biramo između konačnog skupa kandidata, stranaka ili opcija. Na predsjedničkim izborima biramo jednog kandidata, na parlamentarnim izborima biramo listu kandidata, a na referendumu odlučujemo između nekoliko opcija. Sva tri slučaja tretirat ćemo ravnopravno. Elemente skupa K koji su predmet izbora zvat ćemo kandidatima, a broj elemenata u K označavat ćemo s k.

Na većini izbora u Republici Hrvatskoj birači se trebaju izjasniti za točno jednog kandidata. Teorija društvenog izbora proučava općenitije izborne sustave, u kojima se uzima u obzir redoslijed u kojem birači rangiraju kandidate, a ne samo njihov prvi izbor. Jedan takav izborni sustav je takozvani instant runoff voting ili alternative vote [11]. Koristi se na nekim izborima u Australiji, Kanadi, SAD-u, Velikoj Britaniji i drugdje. Prvo ćemo objasniti što se točno podrazumijeva pod rangiranjem kandidata.

Svaki od birača uspostavlja uređaj na skupu kandidata koji odgovara njegovim preferencijama. Bitan je samo redoslijed kandidata u tom uređaju, a ne stupanj potpore pojedinim kandidatima. Naprimjer, ako se uređaj uspostavlja dodjeljivanjem bodova, birač uspostavlja identične uređaje time što kandidatima x, y, z redom dodijeli bodove 10, 20, 30 ili 5, 10, 100.

Formalno, uređaj ρ je binarna relacija na skupu kandidata K, tj. podskup Kartezijeva produkta ρK×K. Za parove kandidata koji su u relaciji pišemo xρy umjesto (x,y)ρ. U sljedećoj definiciji navedeni su zahtjevi koji se postavljaju na razne vrste relacija uređaja.

Definicija 1. Za relaciju ρK×K kažemo da je:
refleksivna, ako za svaki xK vrijedi xρx;
irefleksivna, ako za svaki xK ne vrijedi xρx (što zapisujemo kao xρx);
antisimetrična, ako iz xρy i yρx slijedi x=y;
tranzitivna, ako iz xρy i yρz slijedi xρz;
potpuna, ako za sve x,yK vrijedi xρy ili yρx ili x=y.


Relacija „manje ili jednako” na skupu realnih brojeva R ili nekom njegovom podskupu je refleksivna, antisimetrična, tranzitivna i potpuna. Relacija „strogo manje” < ima ista svojstva, osim što je irefleksivna umjesto refleksivna. Takve relacije nazivamo relacijama totalnog uređaja ili linearnog uređaja.

Općenitije su relacije parcijalnog uređaja, koje ispunjavaju zahtjeve refleksivnosti, antisimetričnosti i tranzitivnosti, ali ne moraju biti potpune. Primjeri su djeljivost na skupu prirodnih brojeva N i inkluzija (relacija „biti podskup”) na nekoj familiji skupova. I ovdje refleksivnost možemo zamijeniti s irefleksivnosti, prijelazom na strogu inkluziju skupova .

U parcijalno uređenom skupu mogu postojati neusporedivi elementi, tj. različiti elementi x,yK takvi da je xρy i yρx. Naprimjer, prirodni brojevi 2 i 3 su neusporedivi s obzirom na relaciju djeljivosti, a skupovi {1,2} i {2,3} su neusporedivi obzirom na inkluziju. Neusporedivost kandidata na izborima znači da su jednako rangirani. Zato parcijalni uređaj na K treba imati dodatno svojstvo: neusporedivost mora biti tranzitivna. Takve relacije nazivamo strogim slabim uređajima.

Definicija 2. Za relaciju ρK×K kažemo da je strogi slabi uređaj na K ako je irefleksivna, antisimetrična, tranzitivna i ako je neusporedivost obzirom na tu relaciju tranzitivna.


U teoriji društvenog izbora preferencije birača zadaju se relacijama strogog slabog uređaja. U njima možemo identificirati međusobno neusporedive kandidate kao ekvivalentne i dobiti totalni uređaj na klasama ekvivalencije. Ponekad se radi jednostavnosti ne dopušta jednako rangiranje kandidata, tj. zahtijeva se totalni uređaj na K. Tako postupamo i u ovom članku: pretpostavljamo da svaki birač zadaje irefleksivnu, antisimetričnu, tranzitivnu i potpunu relaciju na K. Skup svih takvih relacija označavamo s T, a pojedine relacije iz T označavamo s  (da bismo ih razlikovali od standardnog uređaja < na skupu realnih brojeva R).

Ako vrijedi xy, smatramo da je kandidat x bolje rangiran od kandidata y. Naravno, moguć je i obrnuti dogovor, baš kao što relaciju „manje” < na R možemo zamijeniti relacijom „veće” >. Te relacije imaju ista svojstva: obje su irefleksivne, antisimetrične, tranzitivne i potpune.

Totalne uređaje možemo identificirati s permutacijama skupa K, tj. bijekcijama s {1,,k} na K. Iz toga slijedi da totalnih uređaja na K ima točno k!. Inverzna funkcija neke permutacije je bijekcija u:K{1,,k} koju tumačimo kao funkciju korisnosti (eng. utility function): vrijednost u(x) je mjesto na kojem je rangiran kandidat x. Općenitije, bilo koja funkcija u:KR definira jedan strogi slabi uređaj na K s xyu(x)<u(y). Totalne uređaje dobivamo od injektivnih funkcija u:KR.



Zadaci

2.1 Dokažite da iz irefleksivnosti i tranzitivnosti binarne relacije slijedi njezina antisimetričnost. Prema tome, uvjet antisimetričnosti možemo izostaviti iz definicije 2.

2.2 Nađite primjer relacije parcijalnog uređaja u kojoj neusporedivost nije tranzitivna.

2.3 Neka je tranzitivna relacija. Dokažite da je tada tranzitivnost neusporedivosti ekvivalentna sljedećem zahtjevu: ako vrijedi xy, onda za svaki z vrijedi xz ili zy.

2.4 Dokažite da za svaki strogi slabi uređaj na skupu K postoji funkcija u:KR takva da vrijedi xyu(x)<u(y).

2.5 Koliko ima relacija strogog slabog uređaja na k-članom skupu?


3Kako odrediti pobjednika?

Pretpostavimo da na izbore izlazi n birača; identificiramo ih s prirodnim brojevima 1,2,,n. Svaki birač zadaje relaciju totalnog uređaja na skupu kandidata K kojom izražava svoje preferencije. Tako dobivamo uređenu n-torku (1,,n)Tn koju nazivamo profilom ili {n-torkom individualnih preferencija}. Glavni zadatak teorije društvenog izbora je na temelju profila odrediti pobjednika izbora, odnosno društvenu preferenciju: totalni uređaj koji predstavlja preferencije društva kao cjeline. Nicolas de Condorcet je 1785. godine demonstrirao jedan izborni paradoks i pokazao da zadatak nije jednostavan.

Pretpostavimo da na izborima glasaju samo tri birača 1, 2, 3 i da se izjašnjavaju o tri kandidata x, y, z. Neka su preferencije prvog birača x1y1z, drugog birača y2z2x, a trećeg birača z3x3y. Kandidat x ne bi trebao pobijediti na izborima jer većina birača preferira kandidata z: vrijedi z2x i z3x. Kandidat z također ne bi trebao pobijediti jer prvi i drugi birač preferiraju kandidata y. Niti y ne bi trebao pobijediti, zbog x1y i x3y. Ovaj profil individualnih preferencija je paradoksalan jer ne dopušta takozvanog Condorcetova pobjednika. To je kandidat koji bi u drugom krugu glasanja pobijedio svakog od preostalih kandidata, ako bi birači glasali konzistentno s preferencijama izraženim u prvom krugu.

Definicija 3. Neka je (1,,n)Tn profil individualnih preferencija na K. Za kandidata xK kažemo da je Condorcetov pobjednik zadanog profila, ako za svaki yK, yx vrijedi da je broj birača koji preferiraju x veći od broja birača koji preferiraju y: card{ixiy}>card{jyjx}.


Condorcetov paradoks pokazuje da za neke profile ne postoji Condorcetov pobjednik.

U ambicioznijoj verziji izbornog problema treba odrediti društvenu preferenciju za sve parove kandidata, a ne samo pobjednika. Godine 1770. Jean-Charles de Borda predložio je metodu za određivanje uređaja na temelju profila (1,,n). Kandidati dobivaju bodove ovisno o mjestu na kojem su rangirani u individualnim preferencijama i. Bodovi se sumiraju i na osnovi toga se uspostavlja društvena preferencija . Postoji više varijanti Bordine metode. Borda ju je predložio za izbor članova francuske Akademije znanosti i ondje se koristila od 1784. do 1800. [10]. Danas se sličan sistem koristi za izbor zastupnika nacionalnih manjina u slovenskom parlamentu te za izbor pjesme Eurovizije. Obično bolje rangirani kandidati dobivaju više bodova, no mi ćemo pretpostaviti suprotno.

Točnije, neka su ui:K{1,,k} funkcije korisnosti koje odgovaraju individualnim preferencijama i, za i=1,,n. Definiramo funkciju u:KR, u(x)=ni=1ui(x). Društvena preferencija je strogi slabi uređaj dobiven od te funkcije, tj. definiran s xyu(x)<u(y). Nije isključeno da se vrijednosti funkcije u podudaraju za različite kandidate, a tada su ti kandidati neusporedivi s obzirom na relaciju . Ako želimo totalni uređaj na K, možemo se dogovoriti da se u tom slučaju gleda preferencija unaprijed zadanog birača1 ili da se izjednačeni kandidati rangiraju na neki drugi način.

Općenito, teorija društvenog izbora proučava funkcije f:TnK i F:TnT. Funkcije s domenom i kodomenom kao f zovemo funkcijama društvenog izbora. One svakom profilu (1,,n) pridružuju pobjednika izbora {f(1,,n)K}. Arrow [1] je proučavao funkcije s domenom i kodomenom kao F, koje profilu (1,,n) pridružuju društvenu preferenciju F(1,,n)T. Zvao ih je funkcijama društvenog blagostanja (eng. social welfare function), a koristi se i naziv ustav (constitution).

Bordina metoda definira funkciju društvenog blagostanja FB, odnosno funkciju društvenog izbora fB (za pobjednika uzimamo kandidata x za kojeg je u(x) minimalno). Postoje mnogi drugi primjeri takvih funkcija. Najjednostavniji primjer je projekcija na koordinatu d{1,,n}: Fd(1,,n)=d, odnosno fd(1,,n)=x ako je x najbolje rangirani kandidat u d. To znači da preferencije birača d potpuno određuju rezultat izbora, a preferencije ostalih birača uopće ne utječu na rezultat. Takvog birača nazivamo diktatorom.

Diktatorske funkcije Fd i fd su krajnje nedemokratične i cijeli izborni proces dovode do apsurda. Zato se u teoriji društvenog izbora postavljaju zahtjevi koje trebaju zadovoljavati funkcije društvenog blagostanja i funkcije društvenog izbora. Takve zahtjeve zvat ćemo aksiomima demokracije.



Zadaci

3.1 Dokažite da je Condorcetov pobjednik jedinstven, ako postoji.

3.2 Neka je zadana funkcija društvenog blagostanja F:TnT. Tada na prirodan način možemo definirati funkciju društvenog izbora f:TnK, tako da f(1,,n) bude najbolje rangirani kandidat u uređaju F(1,,n). Možemo li na taj način dobiti svaku funkciju društvenog izbora f:TnK?


4Aksiomi demokracije

Prvi od zahtjeva na funkciju društvenog izbora f jest da svaki od kandidata može pobijediti, tj. da je f surjekcija.

Aksiom.(a1) Za svaki xK postoji profil (1,,n)Tn takav da je f(1,,n)=x.


Malo jači zahtjev je takozvani Paretov uvjet.

Aksiom.(a1) Ako je xK najbolje rangirani kandidat u svakoj od individualnih preferencija 1,,n, onda je f(1,,n)=x.


Vilfredo Pareto (1848. - 1923.) bio je talijanski ekonomist, sociolog i filozof. Zaslužan je za širenje matematičke notacije i matematičkih tehnika u radovima iz ekonomije. Očito iz Paretova uvjeta slijedi surjektivnost, a uz neke dodatne zahtjeve aksiomi (a1) i (a1) su ekvivalentni (vidi zadatak 4.1). Surjektivnost možemo zahtijevati i od funkcije društvenog blagostanja F.

Aksiom.(A1) Za svaki totalni uređaj na K postoji profil {(1,,n)} Tn takav da je F(1,,n)=.


Arrow u knjizi [1] postavlja malo blaži zahtjev: u društvenoj preferenciji svaki par kandidata može biti rangiran u bilo kojem redoslijedu.

Aksiom.(A1) Za svaka dva kandidata x,yK postoji profil (1,,n)Tn takav da za društvenu preferenciju =F(1,,n) vrijedi xy.


Arrow ovaj zahtjev zove uvjetom suvereniteta građana. Možemo ga malo ojačati u skladu s Paretovim uvjetom:

Aksiom.(A1) Ako u svakoj od individualnih preferencija vrijedi {xiy}, i=1,,n, onda u društvenoj preferenciji =F(1,,n) također vrijedi xy.


Druga vrsta zahtjeva na funkcije društvenog izbora i blagostanja je monotonost. Pojednostavljeno, monotonost znači da se položaj kandidata ne bi trebao pogoršati ako ga birači rangiraju bolje nego prije. Neka je xK kandidat i ,T dva totalna uređaja na K. Kažemo da je x bolje rangiran u nego u ako vrijedi:
(1) ako za kandidata y vrijedi xy, onda vrijedi xy;
(2) za sve kandidate y,z različite od x vrijedi yz ako i samo ako vrijedi yz.
To znači da je x u na istom ili boljem položaju nego u , a redoslijed ostalih kandidata je isti. Kažemo da je x bolje rangiran u profilu P=(1,,n) nego u profilu P=(1,,n) ako to vrijedi za svaki par individualnih preferencija i, i, i=1,,n. Tu činjenicu zapisujemo ovako: P<xP. Arrow [1] sljedeći zahtjev zove pozitivna asociranost društvene i individualnih preferencija. Mi ćemo ga zvati monotonost funkcije društvenog blagostanja.

Aksiom.(A2) Neka su x,yK kandidati, P,PTn profili i =F(P), =F(P) odgovarajuće društvene preferencije. Ako vrijedi xy i P<xP, onda vrijedi xy.


Oslabljivanjem pretpostavke dobivamo jači aksiom. Za profile P=(1,,n) i P=(1,,n) pišemo PxP ako za svaki i{1,,n} vrijedi
(1) ako za kandidata y vrijedi xiy, onda vrijedi xiy.
Dakle, x je u svakoj komponenti od P na istom ili boljem položaju nego u odgovarajućoj komponenti od P, ali redoslijed ostalih kandidata ne mora biti isti. Sljedeći aksiom zovemo jaka monotonost funkcije društvenog blagostanja ili jaka pozitivna asociranost društvene i individualnih preferencija.

Aksiom.(A2) Neka su x,yK kandidati, P,PTn profili i =F(P), =F(P) odgovarajuće društvene preferencije. Ako vrijedi xy i PxP, onda vrijedi xy.


Aksiome monotonosti i jake monotonosti možemo izreći i za funkcije društvenog izbora.

Aksiom.(a2) Ako za kandidata xK i profile P,PTn vrijedi x=f(P) i P<xP, onda vrijedi x=f(P).

Aksiom.(a2) Ako za kandidata xK i profile P,PTn vrijedi x=f(P) i PxP, onda vrijedi x=f(P).


Arrow [1] postavlja još jedan zahtjev na funkciju društvenog blagostanja, takozvanu nezavisnost od nevažnih alternativa (eng. independence of irrelevant alternatives).

Aksiom.(A3) Neka su P=(1,,n), P=(1,,n)Tn profili i SK podskup kandidata. Ako se restrikcije individualnih preferencija i|S=i|S podudaraju za svaki i=1,,n, onda se restrikcije društvenih preferencija =F(P), =F(P) također podudaraju: |S=|S.


Restrikcija relacije K×K na podskup SK je relacija |S=(S×S). Ako je totalni uređaj na K, onda je restrikcija |S totalni uređaj na S. Analogna tvrdnja vrijedi za stroge slabe uređaje. Smisao aksioma (A3) jest da odustajanje nekih kandidata ne bi trebalo utjecati na izborni položaj preostalih kandidata. U suprotnom neki kandidati mogu manipulirati izborima tako da potiču kandidiranje „lažnih kandidata”, kojima je cilj „pokupiti” glasove njihovih takmaca i odustati. Sličan aksiom mogao bi se formulirati za funkciju društevnog izbora f, ali se u tom kontekstu obično promatra druga vrsta manipulacije, koju provode birači.

Sjetimo se da birači rangiraju sve kandidate. Funkcija društvenog izbora f:TnK određuje samo jednog pobjednika, a svi ostali kandidati su gubitnici izbora. U tom kontekstu birači često reagiraju tako da svojeg favorita rangiraju najbolje, a kandidate koje doživljavaju kao njegove konkurente rangiraju lošije od svojih stvarnih preferencija. Takvo ponašanje naziva se strateškim glasanjem i smatra se nedostatkom izbornog sustava koji ga potiče. Idući aksiom naziva se otpornost na strateško glasanje.

Aksiom.(a4) Neka je P=(1,,n)Tn profil, i{1,,n} birač te P=(1,,i,,n) profil koji dobijemo zamjenom i-te koordinate od P s uređajem iT. Ako je f(P)f(P), onda je f(P)if(P).


Uređaj i tumačimo kao stvarnu preferenciju i-tog birača. Negacija aksioma (a4) glasi: postoji profil P i birač i takav da mu se isplati zamijeniti svoju stvarnu preferenciju s uređajem i. Tada će pobjednik izbora f(P) biti bolje rangiran od f(P) u stvarnoj preferenciji i. To znači da birač i ima razloga za strateško glasanje – u aksiomu zahtijevamo da to ne bude istina niti za jednog birača.



Zadaci

4.1 Dokažite da iz surjektivnosti (a1) i jake monotonosti (a2) funkcije društvenog izbora slijedi Paretov uvjet (a1).

4.2 Koje implikacije vrijede, a koje ne vrijede između aksioma (A1), (A1) i (A1)? Koje implikacije vrijede za jako monotone funkcije društvenog blagostanja, tj. pod dodatnom pretpostavkom (A2)?


5Teoremi nemogućnosti

Promotrimo koje od aksioma zadovoljava Bordina funkcija društvenog blagostanja FB. Funkcija je očito surjektivna: za bilo koji totalni uređaj T, ako se sve individualne preferencije podudaraju s , onda to vrijedi i za društvenu preferenciju FB(,,)=. Prema tome, ispunjen je aksiom (A1). Ispunjen je i aksiom (A1), iz kojeg direktno slijedi (A1): ako za individualne preferencije vrijedi xiy, onda za odgovarajuće funkcije korisnosti vrijedi ui(x)<ui(y), i=1,,n. Društvenu preferenciju određuje suma u(x)=ni=1ui(x)<ni=1ui(y)=u(y), pa je xy i za =FB(1,,n).

Bordina funkcija društvenog blagostanja FB je monotona, tj. zadovoljava aksiom (A2). Iz xy slijedi ni=1ui(x)<ni=1ui(y). Ako za profile P, P vrijedi P<xP, onda je ui(x)ui(x), za i=1,,n. Nadalje, ui(y) ostao je isti kao ui(y) ili se povećao za jedan ako je x „prestigao” y u i-toj individualnoj preferenciji i. U svakom slučaju vrijedi ui(y)ui(y), za i=1,,n. Zato imamo ni=1ui(x)ni=1ui(x)<ni=1ui(y)ni=1ui(y), iz čega slijedi xy.

Funkcija FB ipak ne zadovoljava jaku monotonost (A2) i nezavisnost od nevažnih alternativa (A3). Kao protuprimjer za (A3) promotrimo slučaj s tri birača i četiri kandidata x, y, z, w. Kandidati su u profilu (1,2,3) rangirani na sljedeći način:



x y z w
u1 1 2 3 4
u2 1 2 3 4
u3 2 1 3 4
u 4 5 9 12

Individualne preferencije zadane su funkcijama korisnosti u1, u2, u3, a u zadnjem retku tablice je suma u=u1+u2+u3 koja određuje društvenu preferenciju. Drugi profil (1,2,3) zadan je sljedećom tablicom:



x y z w
u1 1 2 3 4
u2 1 2 3 4
u3 4 1 2 3
u 6 5 8 11

Restrikcije individualnih preferencija na podskup kandidata {x,y} podudaraju se u oba profila. Za prva dva birača je x1y i x2y, a za trećeg birača je y3x. Isti odnosi vrijede u uređajima 1, 2 i 3. Međutim, restrikcije društvenih preferencija =FB(1,2,3) i =FB(1,2,3) se ne podudaraju: vrijedi xy i yx.

Ovaj primjer odgovara situaciji u kojoj većina birača preferira kandidata x nad y. Međutim, manjina koja preferira y izrazito je nesklona kandidatu x. Ako u izborima sudjeluju samo x i y, pobjeđuje x. Ako pak sudjeluju i druga dva kandidata z i w, pobjeđuje y jer njegovi birači stavljaju kandidata x na zadnje mjesto.

Bordina funkcija društvenog izbora fB očito zadovoljava Paretov uvjet (a1), iz čega odmah slijedi surjektivnost (a1). Slično kao za FB pokazuje se da je fB monotona (vrijedi (a2)), ali nije jako monotona (ne vrijedi (a2)). Osim toga fB nije otporna na strateško glasanje, tj. ne zadovoljava aksiom (a4). To se vidi iz istog primjera kao maloprije: trećem biraču isplati se umjesto stvarne preferencije 3 na glasanju iskazati 3 jer tada pobjeđuje njegov favorit y.

Za razliku od Bordinih funkcija, diktatorske funkcije društvenog blagostanja Fd i društvenog izbora fd zadovoljavaju sve aksiome demokracije. Teoremi nemogućnosti tvrde da je situacija još paradoksalnija: ako postoje bar tri kandidata, diktatorske funkcije jedine su koje zadovoljavaju sve aksiome!

Teorem 4.(Arrow) Neka je F:TnT funkcija društvenog blagostanja koja zadovoljava aksiome (A1), (A2) i (A3). Ako je k3, onda postoji d{1,,n} takav da je F=Fd.


Ovo je najvažniji rezultat iz [1]. Arrow je uz spomenute aksiome imao aksiom da funkcija društvenog blagostanja ne smije biti diktatorska. U tom kontekstu teorem tvrdi da nije moguća funkcija društvenog blagostanja koja zadovoljava sve aksiome – odatle naziv „teorem nemogućnosti”2.

U literaturi postoje mnogi alternativni dokazi i modifikacije Arrowljeva teorema. Jedan kratak dokaz dan je u knjizi [3]. Među najpoznatijim srodnim teoremima je takozvani Gibbard-Satterthwaiteov teorem, koji se odnosi na funkcije društvenog izbora.

Teorem 5.(Gibbard-Satterthwaite) Neka je f:TnK funkcija društvenog izbora koja zadovoljava aksiome (a1) i (a4). Ako je k3, onda postoji d{1,,n} takav da je f=fd.


Teorem su neovisno dokazali američki filozof Allan Gibbard [5] i ekonomist Mark A. Satterthwaite [9]. U radu [6] dokazana je ekvivalentnost aksioma jake monotonosti (a2) i otpornosti na strateško glasanje (a4). Zbog toga iz surjektivnosti (a1) i jake monotonosti (a2) također slijedi da je funkcija društvenog izbora diktatorska ako je k3. Direktan dokaz tog teorema i još jedan dokaz Arrowljeva teorema dan je u [8].



Zadaci

5.1 Pokažite primjerom da Bordina funkcija društvenog blagostanja FB ne zadovoljava aksiom (A2) (jaku monotonost).

5.2 Dokažite da Bordina funkcija društvenog izbora fB zadovoljava aksiom (a2) (monotonost). Pokažite primjerom da ne zadovoljava aksiom (a2) (jaku monotonost).

5.3 Dokažite da u slučaju samo dvaju kandidata (k=2) Bordina funkcija društvenog blagostanja FB zadovoljava aksiome (A2) i (A3), a Bordina funkcija društvenog izbora fB zadovoljava aksiome (a2) i (a4).

5.4 Dokažite da iz aksioma surjektivnosti (a1) i otpornosti na strateško glasanje (a4) slijedi jaka monotonost (a2).


6Zaključak

U ovom članku osvrnuli smo se na matematičko modeliranje izbornog procesa u okviru teorije društvenog izbora. Najviše pozornosti posvetili smo opisivanju izbornog sustava i svojstava koje treba zadovoljavati jezikom relacija i funkcija. Glavni teoremi o nemogućnosti tvrde da ne postoje funkcije društvenog izbora i blagostanja koje zadovoljavaju aksiome demokracije i nisu diktatorske. Postavlja se pitanje o posljedicama tih rezultata na stvarne izbore i donošenje kolektivnih odluka u praksi. Korištena terminologija nameće zaključak da „demokracija nije moguća”, odnosno da nužno vodi u „diktatorstvo”. Autori ovog članka ne slažu se s tom pojednostavljenom interpretacijom.

Po našem mišljenju, teoremi nemogućnosti pokazuju da ne treba pretjerivati s formalnim zahtjevima i pravilima. Pojedinačni aksiomi demokracije motivirani su željom da izbori budu pravedni, ali u kombinaciji dovode do paradoksalnog zaključka o diktatorstvu, tj. ne mogu svi biti zadovoljeni. Svjedoci smo da se slične situacije događaju u praksi. U Hrvatskoj se problem nepoštovanja ili „zaobilaženja” zakona i pravila često pokušava riješiti donošenjem novih pravila. Mnogobrojna i pretjerano komplicirana pravila mogu dovesti do paradoksalnih situacija.

Smatramo kako je za stvarne izbore iznimno važno da pravila budu jednostavna, razumljiva i lako provediva. Također, važno je da sudionici izbora (kandidati i birači) prihvaćaju mogućnost da ishod bude suprotan od onog koji priželjkuju. Drugim riječima, za uspjeh demokracije potrebna je dovoljno razvijena „demokratska svijest” društva, a ne samo dobra izborna pravila.

7Rješenja zadataka

2.1. Neka je relacija ρ irefleksivna i tranzitivna. Neka vrijedi xρy i yρx. Tada zbog tranzitivnosti slijedi xρx, što ne može biti istina zbog irefleksivnosti. Dakle, nikad se ne događa xρy i yρx, pa je implikacija da iz xρy i yρx slijedi x=y istinita „na prazno”.


2.2. Na skupu {1,2,3} definiramo relaciju {(1,1),(1,3),(2,2),(3,3)}. Ta relacija je parcijalni uređaj u kojem neusporedivost nije tranzitivna: 1 nije usporediv s 2 i 2 nije usporediv s 3, ali 1 jest usporediv s 3.


2.3. Neka je tranzitivna relacija za koju je i neusporedivost tranzitivna te neka vrijedi xy. Pretpostavimo da postoji z takav da je xz i zy. Tada vrijedi zx, jer bi u suprotnom iz tranzitivnosti slijedilo zy. Analogno vidimo da vrijedi yz. Dakle, x i y nisu usporedivi sa z, a međusobno su usporedivi. To je kontradikcija s tranzitivnosti usporedivosti pa takav z ne postoji.

Obrnuto, neka relacija zadovoljava uvjet iz zadatka. Neka je x neusporediv sa z i z neusporediv s y. Zbog uvjeta ne može vrijediti xy niti yx, pa su x i y također neusporedivi i neusporedivost je tranzitivna.


2.4. Neka je strogi slabi uređaj na K. Neusporedivost s obzirom na je relacija ekvivalencije na K, tj. relacija koja je refleksivna, simetrična i tranzitivna. Relacija inducira totalni uređaj na skupu klasa ekvivalencije K/ (stavimo [x][y]xy, gdje su [x] i [y] klase ekvivalencije kojoj pripadaju x i y). Označimo odgovarajuću funkciju korisnosti s v:K/∼→{1,,l} (l je broj klasa ekvivalencije). Možemo je proširiti do funkcije u:KR stavljajući u(x)=v([x]). Pokazuje se da za tako definiranu funkciju vrijedi xyu(x)<u(y).


2.5. Po prethodnom zadatku, relaciju strogog slabog uređaja, kod koje neusporedivost ima točno l klasa ekvivalencije, možemo identificirati sa surjekcijom u:K{1,,l}. Broj surjekcija s k-članog na l-člani skup je S(k,l)=li=0(1)i(li)(li)k (vidi [3, korolar 5.1.2] ili [7, teorem 2.6.3]). Prema tome, ukupan broj relacija strogog slabog uređaja je kl=1S(k,l)=kl=1li=0(1)i(li)(li)k. To je takozvani k-ti uređeni Bellov broj, tj. broj uređenih particija k-članog skupa.


3.1. Neka je (1,,n)Tn profil individualnih preferencija i neka su x1,x2K dva Condorcetova pobjednika za taj profil. Tada bi po definiciji broj individualnih preferencija u kojima je x1 bolje rangiran od x2 trebao biti istovremeno veći i manji od broja individualnih preferencija u kojima je x2 bolje rangiran od x1, što je nemoguće. Dakle, ne mogu postojati dva Condorcetova pobjednika.


3.2. Na opisani način možemo dobiti svaku funkciju društvenog izbora f:TnK. Zaista, za zadanu funkciju f definiramo funkciju društvenog blagostanja F:TnT tako da f(1,,n) bude najbolje rangirani kandidat u društvenoj preferenciji F(1,,n), a ostale kandidate poredamo proizvoljno. Tada se funkcija društvenog izbora pridružena funkciji F podudara s f.


4.1. Neka je PTn profil za koji je kandidat xK najbolje rangiran u svakoj od komponenti. Prema surjektivnosti (a1), postoji profil PTn takav da je x=f(P). Očito vrijedi PxP, pa iz aksioma (a2) slijedi x=f(P). Time je dokazan Paretov uvjet (a1).


4.2. Iz aksioma (A1) (surjektivnosti funkcije društvenog blagostanja) očito slijedi aksiom (A1). Obrat ne vrijedi – kao primjer možemo uzeti K={x,y,z} i bilo koju funkciju društvenog blagostanja koja za sliku ima sljedeće 3 od 6 mogućih permutacija kandidata: (x,y,z), (y,z,x), (z,x,y). Takva funkcija nije surjekcija, ali zadovoljava aksiom (A1) jer su mogući svi poretci parova kandidata. Slično, iz aksioma (A1) slijedi Arrowljev aksiom (A1), a obrat ne vrijedi. Iz aksioma (A1) slijedi i surjektivnost (A1). Zaista, ako vrijedi (A1), onda za bilo koji uređaj ≺∈T vrijedi F(,,)=≺. Nije teško naći primjer surjektivne funkcije društvenog blagostanja koja ne zadovoljava aksiom (A1).

Uz dodatnu pretpostavku jake monotonosti (A2) pokazuje se da iz (A1) slijedi (A1), analogno kao u prethodnom zadatku. Tada su sva tri zahtjeva (A1), (A1), (A1) međusobno ekvivalentna.


5.1. Neka na izborima sudjeluju tri kandidata x, y, z i dva birača. Neka su profili P=(1,2) i P=(1,2) zadani funkcijama korisnosti u1, u2 i u1, u2:



x y z
u1 1 3 2
u2 3 2 1
u 4 5 3


x y z
u1 1 2 3
u2 3 1 2
u 4 3 5

Bordine društvene preferencije ≺=FB(P) i =FB(P) odgovaraju funkcijama u=u1+u2 i u=u1+u2. Vidimo da je xy i PxP, ali ne vrijedi xy. Dakle, funkcija FB ne zadovoljava aksiom (A2).


5.2. Neka profilima P=(1,,n) i P=(1,,n) odgovaraju funkcije korisnosti u1,,un i u1,,un. Suma u=ni=1ui je minimalna za pobjednika izbora x=fB(P). Iz P<xP slijedi ui(x)ui(x) i ui(y)ui(y), za sve kandidate yK, yx i birače i{1,,n}. Prema tome, suma u(x)=ni=1ui(x) nije se povećala u odnosu na u(x), a u(y) se nije smanjila u odnosu na u(y), yx. Stoga u također poprima minimalnu vrijednost za kandidata x i vrijedi x=fB(P). Dakle, Bordina funkcija fB zadovoljava monotonost (a2). Iz sljedećeg primjera s četiri kandidata x, y, z, w i dva birača vidi se da ne zadovoljava jaku monotonost (a2).



x y z w
u1 1 3 4 2
u2 3 2 1 4
u 4 5 5 6


x y z w
u1 1 2 3 4
u2 3 1 2 4
u 4 3 5 8

Vrijedi x=fB(P) i PxP, ali fB(P) nije x nego y.


5.3. Za k=2 funkcija FB zadovoljava aksiom (A3) jer su tada jedini neprazni podskupovi SK jednočlani, pa se restrikcije društvenih preferencija sigurno podudaraju. Za aksiome (A2) i (a2) ključno je što za k=2 postoje samo dvije permutacije skupa K. U tom slučaju za profile vrijedi PxP ako i samo ako vrijedi P<xP, pa je aksiom (A2) ekvivalentan s (A2) i (a2) je ekvivalentan s (a2). Znamo da FB zadovoljava (A2) i fB zadovoljava (a2). Konačno, spomenuli smo da je (a4) ekvivalentan s (a2). Zato Bordina funkcija društvenog izbora fB za k=2 zadovoljava i aksiom (a4).


5.4. Kratak dokaz te tvrdnje nalazi se u [8].
Bibliografija
[1] K.J. Arrow, Social choice and individual values, Wiley, 1951. (prvo izdanje); 1963. (drugo izdanje). Dostupno na:
http://cowles.econ.yale.edu/P/cm/m12-2/
[2] M. Botić, Arrowljev teorem, diplomski rad, PMF-Matematički odsjek, Sveučilište u Zagrebu, 2011.
[3] P.J. Cameron, Combinatorics: topics, techniques, algorithms, Cambridge University Press, 1994.
[4] D. Ciraki, Teorija javnog izbora i paradoksi glasovanja, Politička misao 33 (1996), 198.–225. Dostupno na:
http://fakultet.fpzg.hr/politicka-misao/DataStorage/Articles/900.pdf
[5] A. Gibbard, Manipulation of voting schemes: a general result, Econometrica 41 (1973), 587.–601.
[6] E. Muller, M.A. Satterthwaite, The equivalence of strong positive association and strategy-proofness, Journal of Economic Theory 14 (1977), 412.–418.
[7] I. Nakić, Diskretna matematika, skripta, PMF-Matematički odsjek, Sveučilište u Zagrebu, 2009. Dostupno na:
http://web.math.hr/nastava/komb/predavanja/predavanja.pdf
[8] P.J. Reny, Arrow's theorem and the Gibbard-Satterthwaite theorem: a unified approach, Economics Letters 70 (2001), 99.–105. Dostupno na: http://home.uchicago.edu/ preny/papers/arrow-gibbard-satterthwaite.pdf
[9] M.A. Satterthwaite, Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions, Journal of Economic Theory 10 (1975), 187.–217.
[10] Wikipedia, Borda count, svibanj 2011.
http://en.wikipedia.org/wiki/Borda_count
[11] Wikipedia, Instant-runoff voting, svibanj 2011.
http://en.wikipedia.org/wiki/Instant-runoff_voting



Share this