Nashin tasapainon löytämisen laskennallinen vaativuus
| Contribuinte(s) |
University of Helsinki, Faculty of Science, Department of Mathematics and Statistics Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, matematiikan ja tilastotieteen laitos Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, matematiska och statistiska institutionen |
|---|---|
| Data(s) |
08/10/2007
|
| Resumo |
Tässä tutkielmassa käsitellään approksimatiivisen Nashin tasapainon löytämisongelmaa laskennallisen vaativuuden kannalta. Vaikka Nashin tasapainon tiedetään olevan aina olemassa, on tasapainon löytäminen osoittautunut vaikeaksi ongelmaksi. Approksimatiivisen Nashin tasapainon löytämisongelma on PPAD-ongelmaluokan täydellinen ongelma. PPAD-luokkaan kuuluvat sellaiset etsintäongelmat, joissa etsittävän ratkaisun olemassaolo seuraa suunnattujen graafien pariteettiargumentista. Suunnattujen graafien pariteettiargumentti toteaa, että jos graafin jokaisen solmun lähtö- ja tuloasteet ovat korkeintaan yksi ja graafissa on tunnettu lähdesolmu, niin graafissa on myös nielusolmu tai toinen lähdesolmu. PPAD-täydellisyyden takia on luultavaa, ettei approksimatiivista Nashin tasapainoa voi löytää polynomisessa ajassa. Tässä kirjoituksessa esitetään uudelleenmuotoiltu ja tarkennettu versio approksimatiivisen Nashin tasapainon löytämisongelman PPAD-vaikeustodistuksesta. Lisäksi esitetään todistus ongelman kuulumiselle luokkaan PPAD. Vastaavaa todistusta ei löydy kirjallisuudesta, vaikka approksimatiivisen Nashin tasapainon löytämisongelman kuuluminen luokkaan PPAD mainitaan. |
| Identificador |
URN:NBN:fi-fe200805091360 |
| Idioma(s) |
fi |
| Publicador |
Helsingin yliopisto Helsingfors universitet University of Helsinki |
| Direitos |
Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. |
| Tipo |
Pro gradu Master's thesis Pro gradu Text |
