Computing pure-strategy punishments in repeated games

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Berg, Kimmo
dc.contributor.author Kärki, Markus
dc.date.accessioned 2016-04-20T10:34:00Z
dc.date.available 2016-04-20T10:34:00Z
dc.date.issued 2016-04-05
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/20142
dc.description.abstract A repeated game is a decision making situation where players interact over and over again. They are used to model long-term relationships, cooperation and competition in a rational manner. In repeated interaction a basic solution concept is subgame-perfect equilibrium. It a special case of Nash equilibrium and requires players to play Nash equilibrium in all possible situation during the game. Often many subgame-perfect equilibria exist and computing those areas complex as in single-shot games, where players meet and choose an action only once [Borgs et al., 2010]. Worst equilibria allows a computationally efficient way to check, if an arbitrary solution is an equilibrium solution of a game [Abreu, 1986].Berg and Kitti [2011] have introduced a method for computing all the equilibrium solutions of a game, assuming that the worst equilibrium payoffs are known. This is because rational players can only play an equilibrium solution. The worst equilibrium is the strongest punishment, which the players can use for threaten each other and force others to play another equilibrium. It is an open question, whether it is possible to solve these punishment strategies in practice. This work examines computing threat points and strategies first with unlimited and then with bounded rationality meaning bounded computing capacity. An algorithm for optimal punishments with pure strategies is introduced. It is suitable for an arbitrary number of players and strategies and it accepts also unequal discount factors. In the end the performance of the algorithm is analyzed and limits to finding punishment strategies with given computing capacity is discussed. en
dc.description.abstract Toistetulla pelillä tarkoitetaan päätöksentekotilannetta, jossa samat pelaajat kohtaavat toisensa yhä uudelleen. Toistettuja pelejä käytetään, jotta voidaan mallintaa rationaalisella tavalla pitkäaikaisia vuorovaikutussuhteita ja niissä tapahtuvaa kilpailua ja yhteistyötä. Toistetussa vuorovaikutuksessa vakiintunut ratkaisukäsite on osapelitäydellinen tasapaino, joka vaatii pelaajaa toimimaan Nashin tasapainoperiaatteen mukaisesti kaikissa tilanteissa. Usein toistetussa pelissä tällaisia tasapainoja on useita ja niiden laskeminen on yhtä vaikeaa kuin kertapelissäkin, jossa pelaajat kohtaavat päätöksentekotilanteen vain kerran [Borgs et al., 2010]. On todistettu, että pelaajien kannalta huonoimpien tasapainoratkaisujen tunteminen mahdollistaa muiden tasapainoehdokkaiden tarkistamisen laskennallisesti tehokkaasti [Abreu, 1986]. Lisäksi Berg ja Kitti [2011] ovat kehittäneet laskentamenetelmän, jolla pelin tasapainoratkaisut voidaan löytää, mikäli huonoimmat tasapainoratkaisut tunnetaan. Tämä perustuu siihen, että rationaaliset pelaajat voivat päätyä ainoastaan tasapainoratkaisuun ja huonoin tasapainoratkaisu on voimakkain uhka, jota pelaajat voivat käyttää painostuskeinona pysyäkseen muissa tasapainoratkaisuissa. On kuitenkin avoin kysymys, pystytäänkö uhkausstrategioita käytännössä ratkaisemaan. Tässä työssä tarkastellaan uhkausstrategioiden laskemista ensin rajoittamattoman ja sitten rajoitetutun rationaalisuuden, eli käytännössä rajoitetun laskentakapasiteetin näkökulmasta. Työssä esitellään algoritmi, jolla voidaan laskea voimakkaimmat puhtailla strategioilla aikaansaadut uhat annetulle kertapelille ja tarkastellaan sitä, millaisia uhkausstrategioita voidaan löytää annetun laskentakapasiteetin rajoissa. fi
dc.format.extent 60 + 5
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Computing pure-strategy punishments in repeated games en
dc.title Rangaistusten laskeminen puhtailla strategioilla toistetuissa peleissä fi
dc.type G2 Pro gradu, diplomityö en
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword game theory en
dc.subject.keyword repeated games en
dc.subject.keyword subgame-perfect equilibria en
dc.subject.keyword computational complexity en
dc.subject.keyword algorithmic game theory en
dc.identifier.urn URN:NBN:fi:aalto-201604201802
dc.programme.major Systeemi- ja operaatiotutkimus fi
dc.programme.mcode F3008 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Ehtamo, Harri
dc.programme Teknillisen fysiikan ja matematiikan koulutusohjelma fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account