haku: @keyword peliteoria / yhteensä: 18
viite: 1 / 18
« edellinen | seuraava »
| Tekijä: | Kärki, Markus |
| Työn nimi: | Computing pure-strategy punishments in repeated games |
| Rangaistusten laskeminen puhtailla strategioilla toistetuissa peleissä | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2015 |
| Sivut: | 60 s. + liitt. 5 Kieli: eng |
| Koulu/Laitos/Osasto: | Perustieteiden korkeakoulu |
| Oppiaine: | Systeemi- ja operaatiotutkimus (F3008) |
| Valvoja: | Ehtamo, Harri |
| Ohjaaja: | Berg, Kimmo |
| Elektroninen julkaisu: | http://urn.fi/URN:NBN:fi:aalto-201604201802 |
| Sijainti: | P1 Ark Aalto 3664 | Arkisto |
| Avainsanat: | game theory repeated games subgame-perfect equilibria computational complexity algorithmic game theory peliteoria toistetut pelit osapelitäydellinen tasapaino laskennan kompleksisuus laskennallinen peliteoria |
| Tiivistelmä (fin): | 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. |
| Tiivistelmä (eng): | 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. |
| ED: | 2016-05-01 |
INSSI tietueen numero: 53436
+ lisää koriin
« edellinen | seuraava »
INSSI