matematiikan osa-alue, jossa tarkastellaan agenttien välistä strategista kanssakäymistä From Wikipedia, the free encyclopedia
Peliteoria on sovelletun matematiikan osa-alue, jossa tarkastellaan agenttien välistä strategista kanssakäymistä. Strategisissa peleissä ihmiset tai yleisemmin agentit valitsevat toimintastrategian, joka maksimoi heidän hyötynsä ottaen huomioon muiden agenttien valinnat. Peliteoria tarjoaa formaalin mallinnuksen sosiaalisille tilanteille, jota käytetään usein taloustieteellisessä analyysissa. Peliteoria laajentaa uusklassisen taloustieteen kehittämää yksinkertaista agenttien optimointia.
Perinteisesti peliteorialla on ollut merkittävä rooli etenkin yhteiskuntatieteissä, mutta nykyään sitä käytetään myös monilla muilla tieteenaloilla. 1970-luvun alussa peliteoriaa ryhdyttiin soveltamaan eläinten käyttäytymiseen sekä evoluutioteoriaan. Monia pelejä, erityisesti vangin dilemmaa, käytetään havainnollistamaan politiikan ja etiikan tutkimuksen ajatuksia. Peliteoria on kiinnostanut myös tietotekniikan tutkijoita, koska sillä on sovelluksia tekoälyn ja kybernetiikan kehityksessä. Vaikka peliteoreettinen analyysi vaikuttaa samankaltaiselta kuin päätösteoreettinen analyysi, poikkeaa peliteoria siitä tarkastelemalla tilanteita, joissa agentit ovat kanssakäymisessä. Toisin sanoen peliteoria tarkastelee optimaalisen toimintatavan valintaa, kun vaihtoehtojen hyödyt ja haitat riippuvat muiden agenttien valinnoista.
Peliteorian alan voidaan katsoa syntyneen vuonna 1944 John von Neumannin ja Oskar Morgensternin kirjan Theory of Games and Economic Behavior vaikutuksesta. Peliteoriaa kehitettiin erityisesti Yhdysvalloissa RAND:ssa, jossa sitä käytettiin ydinasestrategioiden määrittelyyn.
Akateemisen tutkimuksen lisäksi peliteoria on saanut huomiota myös populaarikulttuurissa. Taloustieteen Nobel-palkinnon saanut peliteorian tutkija John Nash oli aiheena vuoden 2001 elokuvassa Kaunis mieli. Jotkut viihdeohjelmat, kuten Selviytyjät, ovat soveltaneet peliteoreettisia tilanteita ohjelmissaan.
Peliteorian tarkastelemat pelit ovat hyvin määriteltyjä matemaattisia objekteja. Peli koostuu pelaajien joukosta, pelaajille mahdollisten strategioiden eli valintojen joukosta sekä eri strategioiden kombinaatioiden pelaajille tuottamista hyödyistä. Kirjallisuudessa käytetään tavallisesti kahta tapaa esittää pelejä.[1]
Pelaaja B vasen |
Pelaaja B oikea | |
---|---|---|
Pelaaja A ylös | 4, 3 | -1, -1 |
Pelaaja A alas | 0, 0 | 3, 4 |
Normaalin muodon tai strategisen muodon peli kuvataan tavallisesti matriisilla, joka esittää pelaajat, strategiat sekä pelaajien hyödyt (esimerkki oikeassa reunassa). Yleisemmin normaalin muodon peli voidaan kuvata funktiolla, joka liittää hyödyt pelaajiin kaikilla mahdollisilla valintojen kombinaatioilla. Esimerkin matriisissa on kaksi pelaajaa, joista toinen valitsee rivin ja toinen sarakkeen. Molemmilla pelaajilla on kaksi strategiaa, joita edustaa rivien sekä sarakkeiden lukumäärä. Pelaajien hyödyt on kuvattu matriisin soluissa, joissa ensin oleva luku kuvaa pelaajan A hyötyä ja toinen luku pelaajan B hyötyä. Jos pelaaja A valitsee vaihtoehdon ylös ja pelaaja B vaihtoehdon vasen, saa pelaaja A hyötyä 4 ja pelaaja B hyötyä 3.
Kun peli esitetään normaalimuodossa oletetaan yleensä, että pelaajat toimivat yhtäaikaisesti tai tietämättä toistensa valintaa. Jos pelaajilla on tietoa muiden valinnoista, esitetään peli tavallisesti ekstensiivisessä muodossa.
Ekstensiivistä muotoa käytetään kuvattaessa pelejä, joissa valintojen järjestyksellä on merkitystä. Pelit esitetään usein puugraafien avulla (esimerkki oikealla). Graafissa jokainen solmu esittää kohtaa, jossa pelaaja tekee valinnan. Valinnan tekevä pelaaja on merkitty solmun yläpuolelle. Solmuista alas lähtevät viivat kuvaavat mahdollisia valintoja. Pelin päätteeksi saatavat hyödyt ovat puun alareunassa.
Esimerkin pelissä on kaksi pelaajaa. Pelaaja 1 valitsee ensin vaihtoehdon F tai U, jonka jälkeen pelaaja 2 on tietoinen pelaajan 1 valinnasta ja valitsee itse joko A tai R. Jos pelaaja 1 valitsee esimerkiksi U, ja pelaaja 2 tämän jälkeen A, saa pelaaja 1 hyötyä 8 ja pelaaja 2 hyötyä 2.
Ekstensiivisellä muodolla voidaan kuvata myös samanaikaisten valintojen pelejä sekä epätäydellisen informaation pelejä. Tällöin merkitään solmut, jotka kuuluvat samaan informaatiojoukkoon (eli pelaajat eivät tiedä missä solmussa ovat. Merkintä tehdään joko yhdistämällä solmut katkoviivoilla tai piirtämällä soikiot solmujen ympärille.
Peli luokitellaan yhteistyön peliksi, jos pelaajat voivat tehdä sitovia sopimuksia. Sitovuus voi esimerkiksi toteutua, jos oikeusjärjestelmä valvoo sopimuksen noudattamista. Kilpailullisissa peleissä sopimukset eivät ole sitovia. Usein oletetaan, että pelaajien välinen kommunikointi on mahdollista yhteistyön, mutta ei kilpailullisissa peleissä.
Symmetrisessä pelissä pelaajien hyödyt riippuvat vain valituista strategioista mutta ei valinnan tehneestä pelaajasta. Eli jos pelaajien roolit voidaan vaihtaa muuttamatta peliä, on se symmetrinen. Monet tunnetut 2*2-pelit ovat symmetrisiä. Esimerkiksi Haukka ja kyyhky sekä Vangin dilemma esitetään yleensä symmetrisinä.
Yleisesti tarkastellut epäsymmetriset pelit ovat sellaisia, että niiden strategiat eivät ole samanlaisia kaikille pelaajille. Esimerkiksi Ultimatum-pelissä pelaajilla on erilaiset valinnat.
Nollasummapelit ovat erikoistapaus vakiosumman peleistä, joissa pelaajat eivät voi valinnoillaan muuttaa pelissä tarkasteltavia resursseja. Nollasummapeleissä jaettavissa oleva kokonaishyöty summautuu aina nollaan riippumatta pelaajien valitsemista strategioista. Pelaajat voivat siis hyötyä vain muiden kustannuksella. Esimerkiksi monet klassiset lautapelit, kuten shakki ja go, ovat nollasummapelejä.
Samanaikaisissa peleissä pelaajat joko tekevät päätökset samanaikaisesti tai eivät tiedä toistensa valintoja. Peräkkäisessä tai dynaamisessa pelissä pelaajilla on jotain tietoa aikaisemmista valinnoista. Tiedon ei tarvitse olla täydellistä. Pelaajille voi olla tiedossa esimerkiksi vain pelin ensimmäiset valinnat mutta ei jälkimmäisiä. Samanaikaiset pelit kuvataan usein normaalimuodossa kun taas peräkkäiset ekstensiivisessä muodossa.
Täydellisen informaation (engl. perfect information) pelit ovat tärkeä osa peräkkäisiä pelejä. Pelissä on täydellinen informaatio, jos kaikki pelaajat tietävät kaikkien pelaajien aikaisemmat valinnat. Näin ollen vain peräkkäisissä peleissä voi olla täydellistä informaatiota, koska samanaikaisissa peleissä pelaajat eivät tiedä muiden valintoja. Suurimmassa osassa peliteoriassa tutkittavista peleistä on epätäydellinen informaatio, mutta on myös kiinnostavia täydellisen informaation pelejä kuten ultimatum-peli. Perinteiset lautapelit ovat myös täydellisen informaation pelejä.
Taloustieteessä tarkasteltavat tai käytännön maailmassa havaittavat pelit päättyvät yleensä valintojen äärellisen määrän jälkeen. Teoreettisissa tutkimuksessa kuitenkin tarkastellaan myös pelejä, joissa on äärettömän paljon valintoja ja joissa pelaajien hyödyt selviävät vasta näiden valintojen jälkeen. Tällaisissa tapauksissa kiinnostuksen kohteena ei yleensä ole niinkään paras pelitapa vaan se, onko jollain pelaajalla voittostrategia.
Ensimmäinen tunnetun peliteoreettisen keskustelun kävi James Waldegrave vuonna 1713 kirjoittamassaan kirjeessä. Siinä Waldegrave esittää minmax-sekastrategiaratkaisun kahden pelaajan versioon le Her -korttipelistä. Varsinaisen yleisen peliteoreettisen analyysin esitti kuitenkin Augustin Cournot vuonna 1838 teoksessaan Recherches sur les principes mathématiques de la théorie des richesses (engl. Researches into the Mathematical Principles of the Theory of Wealth). Cournot tarkasteli teoksessa duopolia ja esittää ratkaisun, joka on rajoitettu versio Nash-tasapainosta.
Peliteoriasta syntyi varsinaisesti oma alansa, kun John von Neumann julkaisi sarjan artikkeleita vuonna 1928. Vaikka ranskalainen matemaatikko Émile Borel (1871-1956) oli tehnyt aikaisempaa tutkimusta peleistä, voidaan matemaatikko von Neumannia pitää peliteorian keksijänä. Hänen merkittävin teoksensa on Oskar Morgensternin kanssa kirjoitettu The Theory of Games and Economic Behavior (1944). Kirja sisältää menetelmän optimaallisen ratkaisun löytämiseksi kahden pelaajan nollasummapeleissä.
Ensimmäiset keskustelut vangin dilemmasta ilmaantuivat 1950, ja RAND:ssa tehtiin peliin liittyvä koe. Samoihin aikoihin John Nash kehitti optimaalisen strategian määritelmän monen pelaajan peleille. Aikaisemmin optimin määritelmää ei oltu määritelty, joten se nimettiin Nash-tasapainoksi. Tasapaino on riittävän yleinen ja se mahdollistaa sekä yhteistyön että kilpailullisten pelien analyysin.
Peliteoria kehittyi 1950-luvulla kiivaasti. Tuolloin kehitettiin muun muassa ytimen määritelmä, pelien ekstensiivinen muoto ja toistetut pelit. Lisäksi peliteorian ensimmäiset sovellukset filosofiassa ja yhteiskuntatieteissä ilmaantuivat.
Reinhard Selten esitti vuonna 1965 alipelitäydellisen tasapainon (engl. subgame perfect equilibria) käsitteen, joka täydensi Nash-tasapainoa. Bayesilaisen pelin ja complete information -käsitteen kehitti John Harsanyi vuonna 1967. Nash, Selten ja Harsanyi palkittiin Ruotsin keskuspankin taloustieteen Alfred Nobel -muistopalkinnolla vuonna 1994.
Vuoden 2005 taloustieteen Alfred Nobel-muistopalkinnon saivat peliteoriaa tutkineet israelilainen Robert Aumann ja yhdysvaltalainen Thomas Shelling.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.