Johdatus peliteoriaan : kahden pelaajan nollasummapelien ratkaiseminen ja Nashin tasapainojen olemassaolo usean pelaajan yleisessä summapelissä

Abstract

Tämän tutkielman tarkoituksena on osoittaa, että jokaisella usean pelaajan yleisellä summapelillä on olemassa vähintään yksi Nashin tasapaino. Lisäksi osoitetaan, että kahden pelaajan nollasummapeleissä Nashin tasapainojen mukaiset pelaajien voittojen odotusarvojen suuruudet ovat yksikäsitteiset, ja näytetään kuinka kyseiset odotusarvot voidaan ratkaista lineaarisen optimoinnin avulla.

Tutkielmassa määritellään yleiset summapelit kolmikkoina, jotka muodostuvat äärellisestä määrästä pelaajia, joista jokaiseen on liitetty äärellinen joukko. Näiden joukkojen alkioita kutsutaan pelaajien puhtaiksi strategioiksi. Kolmikon viimeisen jäsenen muodostaa jokaiselle pelaajalle erikseen määritelty kuvaus edellä mainittujen strategioiden joukosta reaalilukujoukkoon. Kyseinen kuvaus, eli hyötyfunktio, mallintaa pelaajan menestystä pelissä. Nollasummapeliksi peli määritellään silloin, kun häviäjät maksavat voittajille tietyn ennalta määrätyn määrän rahaa.

Pelitapaa, jossa pelaajat valitsevat pelissä käytettävän strategian jollakin kiinnitetyllä todennäköisyydellä, sanotaan pelaajan sekastrategiaksi. Kaikkien sekastrategioiden muodostama joukko osoitetaan konveksiksi. Konveksisuutta hyväksikäyttäen todistetaan minimax-lause. Lauseen mukaan kahden pelaajan nollasummapeleissä pelaajien voitoilla on olemassa odotusarvoiset alarajat, jotka saavutetaan optimaalisiksi strategioiksi kutsuttujen sekastrategioiden avulla. Minimax-lauseen takaaman voiton alarajan sekä optimaalisten strategioiden selvittämiseksi käytetään simplex-algoritmia, jolla voidaan ratkaista lineaarisia optimointitehtäviä.

Yleisissä summapeleissä optimaalisten strategioiden yleistyksien muodostamia pelaajien strategiajoukkoja kutsutaan Nashin tasapainoiksi. Toisin kuin kahden pelaajan nollasummapeleissä, yleisissä summapeleissä Nashin tasapainojen mukaiset voittojen odotusarvojen arvot eivät aina ole yksikäsitteiset. Brouwerin kiintopistelauseen avulla näytetään, että jokaisessa yleisessä summapelissä on oltava vähintään yksi Nashin tasapaino.