Arrowin mahdottomuusteoreema ja kansan tahto

Tuomas Korppi

Johdanto

Usein vaalien jälkeen vaalit voittaneet poliitikot sanovat, että kansan tahto on toteutunut. On tietysti tapauksia, joissa kansan tahto on selvä, jos esimerkiksi 70 % kansasta pitää tiettyä ehdokasta parhaana presidentiksi, mutta yleisessä tapauksessa ei ole mitään yhtä, itsestään selvää tapaa koostaa kansalaisten mielipiteistä “kansan tahtoa”. Tätä kuvaa se, että eri maissa on erilaisia vaalijärjestelmiä käytössä, ja vaikka ne yleensä toimivat suhteellisen järkevästi, jokaiselle vaalijärjestelmälle voidaan rakentaa (usein keinotekoinen) esimerkkitapaus, jossa kyseinen vaalijärjestelmä toimii järjenvastaisesti.

Tässä artikkelissa esitetään ja todistetaan Arrowin mahdottomuusteoreema, joka sanoo, että jos järjestelmälle, joka koostaa “kansan tahdon” kansalaisten mielipiteistä, asetetaan tietyt minimaaliset järkevyysvaatimukset, ollaan tilanteessa, jossa vaatimukset toteuttavan, kaikissa tilanteissa toimivan järjestelmän muodostaminen on mahdotonta.

Sen ymmärtäminen, mitä Arrowin mahdottomuusteoreema tarkalleen ottaen väittää, lienee sopiva haaste useimmille. Todistuksessakaan ei tapahdu mitään yliopistotietoja vaativaa, mutta se on pitkä ja monimutkainen, joten sen lukemista suosittelemme pelkästään niille, joilla on jonkunlaista taustaa matematiikassa.

Kehällisyys

Pienenä harjoituksena ennen Arrowin mahdottomuusteoreemaan menemistä käsitellään eräs helposti mieleen tuleva tapa koostaa “kansan tahto”.

Rationaaliselta päätöksentekijältä voidaan vaatia, että jos hän pitää vaihtoehtoa \(a\) parempana kuin vaihtoehtoa \(b\) ja vaihtoehtoa \(b\) parempana kuin vaihtoehtoa \(c\), hän myös pitää vaihtoehtoa \(a\) parempana kuin vaihtoehtoa \(c\). Muodostetaan “kansan tahto” niin, että \(a\) on parempi vaihtoehto kuin \(b\), jos yli 50 % kansasta pitää \(a\):ta parempana vaihtoehtona kuin \(b\):tä. Nyt edellä mainittu rationaalisuusvaatimus ei “kansan tahdossa” välttämättä toteudu, vaikka jokainen yksilö olisikin rationaalinen.

Merkitään \(a > b\), että \(a\) on parempi vaihtoehto kuin \(b\). Oletetaan, että 33,3 % kansasta on sitä mieltä, että \(a > b > c\), 33,3 % kansasta sitä mieltä, että \(c > a > b\) ja 33,3 % kansasta sitä mieltä, että \(b > c > a\). Nyt 66,7 % on sitä mieltä, että \(a > b\), 66,7 % on sitä mieltä, että \(b > c\), ja 66,7 % sitä mieltä, että \(c > a\), eli näin koostettu “kansan tahto” on kehällinen.

Kehällisyyden aikaansaamiseksi eri paremmuusjärjestysten kannatusprosenttien ei tarvitse olla juuri samat. Sama ilmiö saadaan aikaan, jos 33,3 % tilalla on esimerkiksi 32 %, 33 % ja 35 %.

Jatkossa tutkimme, löytyisikö jotain muuta tapaa koostaa “kansan tahto” kansalaisten mielipiteistä, joka ei johtaisi kehällisyyteen.

Arrowin mahdottomuusteoreeman muotoilu

Olkoon \(K\) kansalaisten joukko. Oletamme, että kansalaisia on vähintään 3, ja olkoon \(V\) vaihtoehtojen joukko. Oletamme, että vaihtoehtoja on myös vähintään 3.

Joukon \(V\) paremmuusjärjestys tarkoittaa sitä, että \(V\):n alkioista on valittu paras, toiseksi paras, kolmanneksi paras jne. niin, että kaikki \(V\):n alkiot on asetettu järjestykseen. Merkitsemme \(a > b\), jos \(a\) on korkeammalla tässä paremmuuslistassa kuin \(b\).

Sanomme, että \(P\) on paremmuusprofiili, jos \(P\):ssä on kerrottu kunkin kansalaisen (joukon \(K\) alkion) mielen mukainen vaihtoehtojen joukon \(V\) paremmuusjärjestys.

Esimerkki 1. Oletetaan, että \(K=\{x,y,z\}\) ja \(V=\{a,b,c\}\). Nyt yksi mahdollinen \(P\) on seuraava: Kansalaisen \(x\) mielestä \(a > b > c\), kansalaisen \(y\) mielestä \(c > b > a\) ja kansalaisen \(z\) mielestä \(b > a > c\).

Olkoon \(K\) ja \(V\) kuten edellä. Merkitään symbolilla \(\mathcal{P}\) kaikkien mahdollisten paremmuusprofiilien \(P\) joukkoa. Merkitään symbolilla \(\mathcal{V}\) kaikkien mahdollisten joukon \(V\) paremmuusjärjestysten joukkoa.

Nyt tapa muodostaa “kansan tahto” tarkoittaa funktiota \(f \colon \mathcal{P} \rightarrow \mathcal{V}\). Tämä tarkoittaa sitä, että \(f\) saa parametrikseen jonkun paremmuusprofiilin, eli systeemin, jossa on kerrottu kunkin kansalaisen mielen mukainen vaihtoehtojen paremmuusjärjestys, ja se palauttaa yhden kaikkien vaihtoehtojen paremmuusjärjestyksen, joka oletettavasti on “kansan tahto”. Funktiolta \(f\) oletetaan seuraavat järkevyysvaatimukset:

Vaatimus 1. Jos \(P\) on paremmuusprofiili, jossa jokainen kansalainen on sitä mieltä, että \(a > b\), niin tällöin \(f(P)\) rankkaa \(a > b\).

Tämä sanoo, että jos kaikki ovat sitä mieltä, että \(a > b\), niin tällöin on kansan tahto, että \(a >b\).

Vaatimus 2. Olkoon \(a \in V\). Olkoot \(P\) ja \(P'\) paremmuusprofiileja, jotka eroavat vain sen osalta, missä kohdin kullakin kansalaisella on vaihtoehto \(a\) paremmuusjärjestyksessä (ts. jos tutkitaan pareittaisia vertailuja, \(P\) ja \(P'\) eroavat vain sellaisten parien osalta, joiden toinen jäsen on \(a\)). Jos \(b,c \neq a\), niin \(f(P)\) ja \(f(P')\) rankkaavat \(b\):n ja \(c\):n keskinäisen paremmuusjärjestyksen samalla tavalla.

Tämä on myös ihan luonnollinen järkevyysvaatimus. Se sanoo, että jos on kansan tahto, että \(b\) on parempi vaihtoehto kuin \(c\), tätä ei muuta se, mitä jonkun kolmannen vaihtoehdon \(a\) suosiolle tapahtuu.

Vaatimus 3. Ei ole kansalaista \(k\), jolle kaikilla paremmuusprofiileilla \(P\) pätee, että \(k\):n mielen mukainen kaikkien vaihtoehtojen paremmuusjärjestys \(P\):ssä on sama kuin kaikkien vaihtoehtojen paremmuusjärjestys \(f(P)\):ssä.

Tällaista kansalaista \(k\) voitaisiin kutsua diktaattoriksi. Vaatimus 3 toteutuu mm. silloin, kun tapa muodostaa kansan tahto kohtelee kaikkia kansalaisia samalla tavalla.

Nyt voimme muotoilla Arrowin mahdottomuusteoreeman:

Teoreema 1 (Arrowin mahdottomuusteoreema). Olkoon \(K\) ja \(V\) kuten edellä. Ei ole olemassa Vaatimukset 1–3 toteuttavaa tapaa \(f \colon \mathcal{P} \rightarrow \mathcal{V}\) muodostaa kansan tahto.

Arrowin mahdottomuusteoreeman todistus

Käytämme pohjana Wikipediasta löytyvää todistusta (https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem).

Olkoon \(f \colon \mathcal{P} \rightarrow \mathcal{V}\) Vaatimukset 1–3 toteuttava tapa määrätä kansan tahto. Todistamme tässä luvussa ensin \(f\):ää koskevia lemmoja, ja luvun lopussa johdamme niiden pohjalta ristiriidan siitä vastaoletuksesta, että tällainen \(f\) on olemassa.

Määritelmä 2. Olkoon \(G \subset K\). Sanomme, että \(G\) määrää preferenssin \(a > b\), jos seuraava pätee kaikilla paremmuusprofiileilla \(P\): Jos kaikkien \(g \in G\) mielestä \(a > b\), niin tällöin \(f(P)\) rankkaa \(a > b\).

Sanomme, että \(G\) määrää heikosti prefrenssin \(a > b\), jos seuraava pätee kaikilla paremmuusprofiileilla \(P\): Jos kaikkien \(g \in G\) mielestä \(a > b\) ja kaikkien \(k \in K \setminus G\) mielestä \(b > a\), niin tällöin \(f(P)\) rankkaa \(a > b\).

Sanomme, että \(G\) on määräävä joukko, jos se määrää jokaisen preferenssin \(a > b\), missä \(a,b \in V\).

Lemma 3. Olkoon \(G \subset K\). Oletetaan, että on olemassa \(P\), jolle

kaikkien \(g \in G\) mielestä \(a > b\),
kaikkien \(k \in K \setminus G\) mielestä \(b > a\),
\(f(P)\) rankkaa \(a > b\).

Tällöin \(G\) määrää heikosti preferenssin \(a > b\). Lisäksi pätee, että jos \(G\) määrää preferenssin \(a > b\), niin \(G\) määrää heikosti preferenssin \(a> b\).

Todistus: Jälkimmäinen “lisäksi” osa on itsestäänselvä. Todistetaan ensimmäinen osa. Olkoon \(P\) kuten lemman oletuksessa, ja olkoon \(P'\) sellainen, että se toteuttaa lemman oletuksen kaksi ensimmäistä pykälää. Pitää todistaa, että \(f(P')\) rankkaa \(a > b\).

Olkoon \(c \in V\), \(c \neq a,b\). Lähdetään liikkeelle \(P\):stä ja siirretään \(c\):tä niin, että se on suhteessa \(a\):han ja \(b\):hen jokaisen kansalaisen paremmuusjärjestyksessä samoin kuin \(P'\):ssa (ts. saadussa paremmuusprofiilissa jokaisen kansalaisen kohdalla \(a\):n, \(b\):n ja \(c\):n keskinäinen järjestys on samoin kuin \(P'\):ssä). Kutsutaan saatua paremmuusprofiilia \(P_c\):ksi. Vaatimuksen 2 mukaan \(f(P_c)\) rankkaa \(a > b\). Valitaan sitten \(d \in V\), \(d \neq a,b,c\). Jatketaan paremmuusprofiilista \(P_c\) ja siirretään \(d\) niin, että se on jokaisen kansalaisen kohdalla suhteessa alkioihin \(a,b,c\) samoin kuin \(P'\):ssä. Kutsutaan tulosta \(P_d\):ksi. Nyt \(f(P_d)\) rankkaa \(a >b\). Jatketaan samaan tapaan, kunnes kaikilla kansalaisilla kaikki \(v \in V\) ovat samassa järjestyksessä kuin \(P'\):ssä. Saatu paremmuusprofiili \(P_x\) on siis sama paremmuusprofiili kuin \(P'\), ja koska \(f(P_x)\) rankkaa \(a > b\), myös \(f(P')\) rankkaa \(a > b\). \(\square\)

Lemma 4. Olkoon \(x,y \in V\) ja \(G \subset K\), joille \(G\) määrää heikosti preferenssin \(x > y\). Tällöin kaikille \(z \neq x,y\) pätee, että \(G\) määrää preferenssit \(x > z\) ja \(z > y\).

Todistus: Olkoon \(P\) sellainen, että \(P\):ssä kaikilla \(g \in G\) pätee, että \(g\):n mielestä \(x > z\). Olkoon \(P'\) sellainen paremmuusprofiili, joka on saatu \(P\):stä muuttamalla vain \(y\):n sijainteja eri kansalaisten paremmuusjärjestyksissä. Näitä on muutettu niin, että kansalaisten \(g \in G\) mielestä \(x > y > z\) ja kansalaisten \(k \in K \setminus G\) mielestä \(y > x\) ja \(y > z\).

Nyt Vaatimuksen 2 perusteella \(f(P)\) rankkaa \(x > z\), jos ja vain jos \(f(P')\) rankkaa \(x > z\). Ensimmäisen rankkauksen todistamiseksi riittää siis todistaa jälkimmäinen. Vaatimuksen 1 perusteella \(f(P')\) rankkaa \(y > z\), ja lemman oletuksen perusteella \(f(P')\) rankkaa \(x > y\). Siis \(f(P')\) rankkaa \(x > z\). Siis \(f(P)\) rankkaa \(x > z\), ja siis \(G\) määrää preferenssin \(x > z\).

Se että \(G\) määrää preferenssin \(z >y\) on yllä olevan todistuksen peilikuva. Vain \(x\):n ja \(y\):n roolit vaihdetaan, samoin \(>\):n ja \(<\):n roolit. \(\square\)

Lemma 5. Olkoon \(a,b \in V\) ja \(G \subset K\), joille \(G\) määrää heikosti preferenssin \(a > b\). Tällöin \(G\) on määräävä.

Todistus: Soveltamalla edellistä lemmaa niin, että \(x=a\), \(y=b\) ja \(z=c\) saadaan tulos, että \(G\) määrää preferenssit \(a > c\) ja \(c > b\) kaikilla \(c \neq a,b\).

Soveltamalla edellistä lemmaa niin, että \(x=a\), \(y=c\) ja \(z =b\) saadaan tulos, että \(G\) määrää preferenssit \(a > b\) ja \(b > c\). Soveltamalla edellistä lemmaa niin, että \(x=b\), \(y=c\) ja \(z=a\) saadaan tulos, että \(G\) määrää preferenssin \(b > a\), ja soveltamalla edellistä lemmaa niin, että \(x=c\), \(y=b\) ja \(z=a\) saadaan tulos, että \(G\) määrää preferenssin \(c > a\). Jos siis \(V\) koostuu kolmesta alkiosta, \(G\) on määräävä.

Oletetaan sitten, että \(V\) koostuu vähintään neljästä alkiosta. Olkoon nyt \(d \neq a,b,c\). Soveltamalla edellistä lemmaa niin, että \(x=a\), \(y=c\) ja \(z=d\), saadaan tulos, että \(G\) määrää preferenssin \(d > c\), ja soveltamalla edellistä lemmaa niin, että \(x=c\), \(y=b\) ja \(z=d\) saadaan tulos, että \(G\) määrää preferenssin \(c > d\). Toisaalta edellisen kappaleen perusteella \(G\) määrää kaikki preferenssit, joiden toinen jäsen on \(a\) tai \(b\). Siis \(G\) on määräävä. \(\square\)

Lemma 6. Oletetaan, että \(G\) on määräävä joukko, jossa on vähintään kaksi alkiota. Jos \(G\) jaetaan kahteen epätyhjään osaan, toinen näistä osista on määräävä.

Todistus: Olkoon \(G_1, G_2\) joukon \(G\) jako kahteen epätyhjään osaan. Olkoon \(a,b,c \in V\). Määritellään \(P\) seuraavasti:

Jokaisen \(g \in G_1\) mielestä \(a > b > c\).
Jokaisen \(g \in G_2\) mielestä \(c > a > b\).
Jokaisen \(k \in K \setminus G\) mielestä \(b > c > a\).

Muiden \(V\):n alkioiden osalta järjestyksellä ei ole merkitystä. Koska \(G\) on määräävä, \(f(P)\) rankkaa \(a > b\). Koska \(c\) ei voi olla \(f(P)\):n mukaan sekä huonompi kuin \(b\) että parempi kuin \(a\), \(f(P)\) rankkaa joko \(a > c\) tai \(c > b\).

Jos \(f(P)\) rankkaa \(a > c\), \(G_1\) määrää heikosti preferenssin \(a > c\), ja edellisen lemman nojalla \(G_1\) on määräävä. Jos taas \(f(P)\) rankkaa \(c > b\), \(G_2\) määrää heikosti preferenssin \(c > b\), ja edellisen lemman nojalla \(G_2\) on määräävä.

Joka tapauksessa siis joko \(G_1\) tai \(G_2\) on määräävä, ja lemman todistus on valmis. \(\square\)

Teoreeman 1 todistus: Tehdään vastaoletus, että Vaatimukset 1–3 toteuttava \(f\) on olemassa. Vaatimuksen 1 nojalla \(K\) on määräävä joukko, joten se saadaan edellisen lemman nojalla jaettua kahteen osaan \(K_1\) ja \(K_2\), joista toinen on määräävä. Jakamalla tämä puolestaan kahteen osaan, joista toinen on määräävä, ja jatkamalla jakamista niin kauan kuin mahdollista tullaan lopulta yhden alkion kokoiseen määräävään joukkoon. Kuitenkin yhden alkion kokoisen määräävän joukon olemassaolo on Vaatimuksen 3 vastaista. Ristiriita. \(\square\)

Lopuksi

On kokonainen tutkimusala, social choice theory, joka käsittelee matemaattisesti sitä, kuinka yksilöiden mielipiteistä koostetaan ryhmän mielipide, ja tämä tutkimusala hiukan yllättäen luetaan taloustieteen eikä matematiikan alle. Tässä artikkelissa esitelty tulos on alan peruskiviä, ja muista alan tärkeistä tuloksista mainittakoon:

Gibbardin teoreema, joka sanoo, että olipa vaalijärjestelmä mikä tahansa, kunhan vaalissa on vähintään kolme vaihtoehtoa, äänestäjälle voi aina tulla tilanne, jossa taktinen äänestäminen on kannattavaa.
Mediaaniäänestäjäteoreema, joka sanoo, että siinä erikoistapauksessa, jossa vaihtoehdot ovat yksiulotteisella akselilla (esim. oikeisto-vasemmisto), ja jokaisella kansalaisella on akselilla suosikkipiste, josta etäännyttäessä vaihtoehdot muuttuvat vähemmän ja vähemmän mieluisiksi, pystytään löytämään järkevällä tavalla paras vaihtoehto, joka on “kansan tahto.”