Väitöskirja implementaatioteoriasta

Väitöskirja implementaatioteoriasta

^*

Ville Korpela

FM, VTT, Erikoistutkija

julkisen valinnan tutkimuskeskus (PCrC), turun yliopisto

a

lun perin, 1920–1940 luvulla, peliteoria luo- tiin tarkoituksena kehittää jonkinlainen yleinen kehikko, jossa strategista vuorovaikutusta voi- taisiin analysoida (ks. von Neumann ja mor- genstern 1944). tarkoituksena oli etsiä mene- telmiä, joilla voidaan ennustaa annetun pelin lopputulema, kun pelaajien preferenssit tunne- taan. Hieman myöhemmin kävi kuitenkin sel- väksi, että monet käytännössä tärkeät ongelmat ovat täysin päinvastaisia tämän alkuperäisen ongelman muotoilun kanssa. toisin sanottuna monissa käytännön tilanteissa pelaajien prefe- renssejä ei tunneta ja tarkoituksena on löytää peli, joka tuottaa halutun lopputuleman huoli- matta siitä, mitkä ovat pelaajien todelliset pre- ferenssit. tämä on huomattavasti vaikeampi ongelma kuin alkuperäinen, sillä nyt itse peli

on tuntematon muuttuja. sitä peliteorian osa- aluetta, joka kehittää menetelmiä tällaisten on- gelmien ratkaisemiseksi kutsutaan mekanismin suunnitteluksi tai implementaatioteoriaksi.¹

Yleisessä muodossa implementaatioteorian perusongelma voidaan ilmaista seuraavalla ta- valla. olkoon I = {1,…,n} kaikkien mekanis- miin osallistuvien henkilöiden joukko ja A kaikkien mahdollisten lopputulemien joukko (lopputulema voi olla esimerkiksi jokin resurs- sien allokaatio). jokaisella henkilöllä on jokin tyyppi t_i, joka on peräisin joukosta T_i (tyyppi saattaa pitää sisällään hieman eri asioi- ta tilanteesta riippuen, mutta se määrittää mi- nimissään ainakin henkilön preferenssit yli joukon A). suunnittelija, joka voi olla esimer- kiksi jokin kolmas osapuoli, kuten oikeuslaitos, ei tunne henkilön i tyyppiä t_i tarkasti, vaan ai- noastaan joukon T_i, josta tyyppi on peräisin.

suunnittelijan tarkoituksena on toteuttaa jokin päämäärä F: T → A, missä T_n,

* Kirjoitus perustuu Turun yliopistossa 10.12.2011 tarkas- tettuun väitöskirjaan ”Four Essays on Implementation The- ory”. Väitöskirjan esitarkastajina toimivat professori Juuso Välimäki (Aalto-yliopisto) ja professori Klaus Kultti (Hel- singin yliopisto). Vastaväittäjänä toimi professori Tomas Sjöström (Rutgersin yliopisto) ja kustoksena professori Han- nu Salonen (Turun yliopisto). Väitöskirjan ohjaaja oli Han- nu Vartianen (HECER).

1 Maskin ja Sjöström (2002) sekä Jackson (2001) ovat hyviä yleisesityksiä alan keskeisistä tuloksista.

joka riippuu siitä, mitkä ovat henkilöiden to- delliset tyypit. koska suunnittelija ei oletetta- vasti voi luottaa siihen, että henkilöt paljastavat todellisen tyyppinsä, hänen täytyy löytää sellai- nen mekanismi, tai pelimuoto, joka tuottaa ha- lutun lopputuleman olipa henkilöiden todelli- set tyypit mitä tahansa.

mekanismilla tarkoitetaan kaksikkoa G = (M,g), missä 1 on viestiavaruus ja funktio määrittää mekanismin lop- putuleman. kun tyypit on annet- tu, määrittelee mekanismi G pelin . olkoon S jokin peliteoreettinen ratkaisukäsite ja kaikkien S-ratkaisujen joukko pelis- sä . Päämäärän F sanotaan olevan S-imple- mentoituva, mikäli on olemassa sellainen meka- nismi G, että

(1)

toisin sanottuna mekanismin G lopputule- ma kaikissa S-ratkaisuissa vastaa päämäärää F olivat todelliset tyypit mitä tahansa. käytän- nössä implementaatio-ongelmat jakaantuvat eri luokkiin sen perusteella, minkälaista mekanis- mia (normaalimuodon peli, ekstensiivisen muodon peli, toistettu peli) ja ratkaisukäsitettä (Nash-tasapaino, Bayesin taspaino, vahva tasa- paino, dominoivat strategiat) käytetään.

Leonid Hurwicz (1960, 1972) formuloi en- simmäisenä mekanismin käsitteen eksaktisti ja häntä pidetäänkin yleisesti mekanisminsuunnit- telun isänä. käsite muotoiltiin alunperin sel- ventämään pitkään jatkunutta kinastelua (joka tunnetaan nykyään Hayek-mises-Lange-Ler- ner-debattina) siitä, kumpi – markkinatalous vai suunnitelmatalous – on parempi resurssien allokaatiomenetelmä. Hurwicz huomautti koko kinastelun olevan ideologisesti värittynyt, kos- ka ei ole mitään syytä olettaa, että kumpikaan

allokaatiomenetelmistä olisi paras. sen sijaan, että tarkastellaan vain kahta allokaatiomenetel- mää, meidän tulisi muotoilla yleisesti, mitä tar- koitetaan resurssien allokaatiomenetelmällä, tai allokaatiomekanismilla, ja tämän jälkeen valita paras tiettyjen ominaisuuksien suhteen. Yhtenä mekanisminsuunnittelun merkittävimpänä tu- loksena voidaankin pitää todistusta siitä, että markkinamekanismi on informatiivisesti tehok- kain kaikkien mahdollisten resurssien allokaa- tioon käytettävien mekanismien joukossa.

mekanisminsuunnittelusta jaettiin ruotsin keskuspankin taloustieteen palkinto vuonna 2007 (erik maskin, Leonid Hurwicz ja roger myerson), ja sen jälkeen on tutkimuksen määrä alalla kasvanut räjähdysmäisesti. Nykyisin alaan perehtyneelläkin on vaikeuksia pysyä mukana siinä, mitä kaikkea on tekeillä, ennen kaikkea sovellutusten puolella. omassa väitös- kirjassani kehitetään mekanisminsuunnittelun teoreettista koneistoa vastaamalla seuraaviin kysymyksiin: (a) kuinka paljon viestejä |M| tar- vitaan (minimissään), jotta annettu päämäärä F voidaan implementoida dominoivissa strategi- oissa; (b) mikä on yksinkertaisin päämäärää F koskeva ehto, joka takaa että ongelma (1) on ratkeava (niin sanottu karakterisointi) ja (c) missä määrin oletus rationaalisuudesta on tär- keä ongelman (1) yhteydessä.

1. Minimaaliset mekanismit

Palataan hetkeksi hieman taaksepäin ja pilko- taan ongelma (1) pienempiin osiin. oletetaan, että jokainen henkilö seuraa tiettyä proto- kollaa . toisin sanottuna, jos henki- lön i todellinen tyyppi on t_i, niin tällöin hän valitsee viestin huolimatta siitä, tuot- taako tämä parhaan mahdollisen lopputule- man. mikäli

(2)

sanotaan että protokolla p = (p₁,…,p_n) realisoi päämäärän F. Huomaa, että tämän määritel- män mukaan mikä tahansa päämäärä F voidaan realisoida (toisin kuin implementoinnin tapa- uksessa) – ei tarvitse kuin valita g = F sekä

Luonnollinen kysymys tässä yhteydessä on, . mikä on pienin mahdollinen viestiavaruuden

|M| koko, jolla annettu päämäärä F voidaan realisoida. Hurwicz ja reiter (2008) ovat vas- tanneet tähän kysymykseen kehittämällä algo- ritmeja, joiden avulla minimaalinen mekanismi voidaan konstruoida. Väitöskirjani ensimmäi- sessä esseessä ositetaan, että Hurwicz-reiter- konstruktiota voidaan käyttää myös dominoi- vissa strategioissa implementoituvien päämää- rien (pienellä varauksella) sekä turvallisesti implementoituvien päämäärien yhteydessä.² toisin sanottuna, Hurwicz-reiter-konstruktio säilyttää myös insentiivit. tämä on kaikkea muuta kuin selvä asia –nythän minimaalisessa realisoivassa mekanismissa on täsmälleen yhtä monta viestiä kuin minimaalisessa implemen- toivassa mekanismissa. minimaalisten mekanis- mien tunnistaminen on tärkeää, koska juuri näitä mekanismeja voi odottaa näkevänsä to- dellisuudessa.

2. Nash-implementoituvien päämäärien karakterisointi implementaatioteoriassa karakterisoinnilla tar- koitetaan sellaista tulosta, joka hävittää meka-

nismin G ongelmasta (1). Yleensä karakteri- sointi koostuu päämäärää F koskevista ominai- suuksia, jotka yhdessä takaavat, että jokin implementoiva mekanismi G pystytään löytä- mään. ensimmäisen karakterisoinnin Nash- implementoituvista päämääristä antoi erik maskin (1977).³ tämä karakterisointi antoi kuitenkin vain riittävän ehdot Nash-implemen- toituvuudelle, jolloin kysymys riittävästä ja välttämättömästä ehdosta jäi vielä avoimeksi.

tästä huolimatta maskinin paperi on ehdotto- masti tärkein implementaatiopaperi, joka on koskaan kirjoitettu, mikä johtuu yksinkertai- sesti siitä, että lähes kaikki myöhemmin kirjoi- tetut paperit käyttävät oleellisesti samoja me- netelmiä.

ensimmäisen täydellisen karakterisoinnin (välttämätön ja riittävä ehto) Nash-implemen- toituvista päämääristä antoi moore ja repullo (1990). tämä karakterisointi on melko moni- mutkainen ja itse asiassa täsmälleen samat pää- määrät, jotka tuottavat ongelmia maskinin karakterisoinnin yhteydessä, tuottavat ongel- mia myös moore-repullo-karakterisoinnin yh- teydessä. Hieman myöhemmin sjöström (1991) osoitti, että moore-repullo-karakterisointi voi- daan muuttaa erittäin yksinkertaiseen muotoon (ehto m), joka on käytännössä vain yksi mono- tonisuutta muistuttava ehto. sjöströmin karak- terisointi ei kuitenkaan ole aivan täydellinen – siinä joudutaan olettamaan että T:llä on tulora- kenne. tämä on hieman rajoittavaa, koska kirjallisuus on täynnä esimerkkejä, joissa näin ei ole. Väitöskirjani toisessa esseessä (korpela 2010) johdetaan hyvin samankaltainen karak-

2 Turvallisella implementoinilla tarkoitetaan sitä, että me- kanismi implementoi samanaikaisesti sekä Nash-tasapainos- sa että dominoivissa strategioissa (ks. Saijo, Sjöström ja Ya- mato 2007).

3 Tämä työpaperi julkaistiin vasta 1999 (Maskin 1999).

Maskin itse on kertonut, ettei paperia kannattanut enää julkaista, koska se oli jo työpaperina niin hyvin tunnettu.

terisointi, joka on täydellinen. Ehto on nimel- tään yleistetty monotonisuus.⁴

3. Rajoitettu rationaalisuus ja implementaatioteoria

Perinteisesti ongelman (1) yhteydessä oletetaan lähes poikkeuksetta, että henkilön tyyppi mää- rittää täydellisen ja transitiivisen preferenssire- laation yli joukon A. toisaalta implementaatio- teorian perusajatuksessa ei ole mitään, mikä vaatii meitä tekemään tällaisen oletuksen. tar- koituksenahan on yksinkertaisesti löytää meka- nismi, joka tuottaa halutun lopputuleman käyt- täytymisen funktiona. toisin sanottuna aina, kun käyttäytyminen muuttuu, lopputulemakin muuttuu halutulla tavalla. Hurwicz (1986) esit- ti ensimmäisenä ongelman (1) sellaisessa muo- dossa, jossa henkilön tyyppi määrittää prefe- renssirelaation sijaan jonkin valintafunktion

, missä C(B) B kaikilla B 2^A.⁵ täl- löin voidaan periaatteessa käsitellä minkälaista käyttäytymistä tahansa eikä rationaalisuusole- tusta enää tarvita. täydellisen rationaalisuuden tapaus saadaan tunnetusti erikoistapauksena, kun kaksi ehtoa, ominaisuus ja ominaisuus , ovat kummatkin voimassa (ks. kreps 1988).

Väitöskirjani kolmannessa esseessä (korpe- la 2012) osoitetaan, että Hurwiczin (1986) käyttämä taspainokäsite ei ole täysin yhteenso- piva valintafunktion perusajatuksen kanssa.

jotta Hurwiczin (1986) esittämää tasapainokä- sitettä voidaan soveltaa, täytyy valintafunktion

C olla normaali (ks. sen 1977). Valintafunkti- oille voidaan kuitenkin määritellä myös sellai- nen tasapainokäsite, jossa mitään lisäoletuksia itse valintafunktioista ei tarvitse tehdä (käytän tästä tasapainosta nimeä behavioral Nash equi- librium). tämän jälkeen voidaan osoittaa, että implementaatioteorian tulokset pätevät sellai- senaan, kunhan kaikki valintafunktiot toteut- tavat ominaisuuden . tämä on huomattavasti vähemmän kuin täydellinen rationaalisuus vaa- tii.

Lopullisena päämääränä on tietenkin ka- rakterisoida kaikki implementoituvat päämää- rät riippumatta siitä, miten mekanismiin osal- listuvat henkilöt käyttäytyvät. Nyt tiedetään, että olemassa olevat tulokset pätevät, kunhan ominaisuus on voimassa. tämän jälkeen täy- tyy keksiä uudenlainen karakterisointi. sellai- set tilanteet, joissa käyttäytyminen ei toteuta tätä ominaisuutta, ovat vielä tällä hetkellä täy- sin tutkimatonta aluetta. Viimein neljännessä esseessä osoitetaan, että myös tunnettu revelaa- tioperiaate on voimassa täsmälleen niin kauan kuin ominaisuus on voimassa. jos tämä omi- naisuus ei päde, joudutaan astumaan aidosti epäsuorien mekanismien maailmaan. tällöin mekanismin suunnittelu muuttuu huomatta- vasti vaikeammaksi. itse asiassa, jokainen joka tuntee mekanismin suunnittelua, ymmärtää, että juuri tämä tulos pohjimmiltaan ajaa kol- mannessa esseessä johdettua tulosta. □

Kirjallisuus

Hurwicz, L. ja reiter, s. (2008), Designing Econom- ic Mechanisms, Cambridge university Press, New York, usa.

Hurwicz, L. (1986), “on the implementation of so- cial Choice rules in irrational societies”, teok- sessa Heller, W., starr, r. ja starrett, d. (toim.),

4 Jälkeenpäin harmittaa, etten käyttänyt nimeä yleistetty ehto M.

5 Normaalisti valintafunktio esitetään muodossa . Implementaatioteorian yhteydessä kuitenkin voidaan käsitellä myös tilanteita, joissa henkilö kieltäytyy tekemästä mitään valintaa. Kyseessä ei siis ole virhe.

Social Choice and Public Decision Making, Essays in Honor of Kenneth J. Arrow: Volume I, Cam- bridge university Press, usa.

Hurwicz, L. (1972), “on informationally decentral- ized systems”, teoksessa mcGuire, C.B. ja rad- ner, r. (toim.) Decision and Organization, North- Holland, amsterdam.

Hurwicz, L. (1960), “optimality and information efficiency in resource allocation Processes”, teoksessa arrow, k., karlin, s. ja suppes, P.

(toim.), Mathematical Methods in Social Sciences, stanford university Press: 27–46.

jackson, m.o. (2001), “a Crash Course in imple- mentation theory”, Social Choice and Welfare 18: 655–708.

korpela, V. (2012), “implementation without ra- tionality assumptions” Theory and Decision 72:

189–203.

korpela, V. (2010), “Nash implementation theory – a Note on Full Characterizations”, Economics Letters 108: 283–285.

kreps, d. (1988), Notes on the Theory of Choice, Undergroung Classics in Economics, Westview Press, usa.

maskin, e. ja sjöström, t. (2002), “implementation theory”, teoksessa arrow, k.j. ja sen, a.k.

(toim.), Handbook of Social Choice and Welfare, elsevier: luku 5.

maskin, e. (1977), “Nash Equilibrium and Welfare Optimality”, department of economics, mit, mimeo.

maskin, e. (1999), “Nash equilibrium and Welfare optimality”, Review of Economic Studies 66:

23–38.

moore, j. ja repullo, r. (1990), “Nash implementa- tion – a Full Characterization”, Econometrica 58: 1083–1099.

morgenstern, o. ja von Neumann, j. (1944), Theory of Games and Economic Behavior, Princeton uni- versity Press, usa.

saijo, t., sjöström, t. ja Yamato, t. (2007), “secure implementation”, Theoretical Economics 2: 204–

229.

sen, a. (1977), “social Choice theory: a re-exam- ination”, Econometrica 45: 53–89.

sjöström, t. (1991), “on the Necessary and suffi- cient Conditions for Nash implementation”, Social Choice and Welfare 8: 333–340.