Fangens dilemma
Fangens dilemma (prisoner's dilemma) er eit spill for to spillarar med ufullstendig informasjon. Spillet har overføringsverdi til både økonomi, psykologi og biologi, og vart oppdaga av Melvin Dresher og Merrill Flood i 1950. Dilemmaet er følgande:
To fangar er mistenkte for ein grov forbrytelelse, men politiet har ikkje bevis nok til å få dei dømt. Dei kan likevel få eit års fengsel for ein mindre forbrytelse. Politiet gir kvar av dei mistenkte valget mellom å tysta på den andre eller halda munn. Hvis begge held munn får dei eit års fengsel. Hvis den eine sladrar, men ikkje den andre får sladrehanken sleppa fri mens den andre får ti års fengsel. Hvis begge sladrar får dei begge fem års fengsel. Dei to sit i forhøyr samtidig, og veit ikkje om kva den andre gjer, men dei veit at den andre har fått same betingelsar.
Dette kan visast i følgande utbyttematrise:
| |
Halda tett | Tysta |
|---|---|---|
| Halda tett | -1, -1 | -10, 0 |
| Tysta | 0, -10 | -5, -5 |
Blå farge er fange A, og rødt er fange B. Tala angir "utbyttet" eller utbetalingen, og dei er negative fordi straff er negativ. Det beste ein kan få er altså null.
Så spørsmålet er: kva ein bør gjera? Det er opplagt at det beste, totalt sett, ville vera hvis begge to held munn, for då vil begge sleppa unna med eit år i fengsel. Problemet er at ingen av dei to tør stola på at den andre held tett, fordi han då risikerer ti år, og begge er frista til å sladra. Spillteoretisk er altså den beste individuelle strategien å sladra. Dermed får vi ein såkalt Nash-likevekt der begge fangane sladrar, og dermed får mykje verre straff enn hvis dei hadde samarbeida. Dette viser at to aktørar som tar individuelle rasjonelle valg i sum kan ta kollektive irrasjonelle valg. Slike dilemma kallast sosiale dilemma, og fangens dilemma er eit av mange eksempel. Ved å endra på utbyttematrisa kan vi få andre eksempel som dei såkalte "Chicken" og "Stag Hunt".
Axelrods turnering
Sjøl om det fins eksempel
frå verkeligheten på Fanges Dilemma så vil ein kunna hevda at
spillet blir meir realistisk derson spelarane kjenner kvarandre frå før,
og speler gjentatte gonger. Derfor fant Robert
Axelrod i 1980 ut at han skulle laga ein turnering*. Han inviterte
deltakarane til å senda inn program som skulle spela mot kvarandre
i 200 rundar. Reglane er dei same som vanlig FD, men spelarane (dvs.
programma) har no informasjon om dei forrige trekka både til seg sjøl og
motstandaren. Dermed kan dei gjera sine beslutningar basert på om
motstandaren har samarbeida eller ikkje. Og det viste seg at dette har
stor konsekvens for kva som er ein god strategi.
Mulige strategiar
Det er eit uendelig antal meir eller mindre sofistikerte strategiar som ein kan tenkja seg. Men dei enklaste er:
- Alltid samarbeid. Denne gjer det bra mot andre "snille" strategiar, men kan utnyttast i det uendelige av mindre snille.
- Alltid sladra. Dette er ei ganske sikker strategi, sidan den er umulig å vinna mot. I tillegg vil den kunna utnytta snille strategiar.
- Tilfeldig. Denne gjer det bra mot snille og seg sjøl, men ikkje mot andre.
Hvis bare program med ein av disse tre strategiane deltok, ville altså "Alltid sladre-strategien" vinna turneringen. Men problemet med alle disse variantane er at dei ikkje har noko "minne", og kan derfor ikkje utnytta informasjonen om kva som har skjedd i tidligare spel. Men då dukka den russiske matematikaren Anatol Rapaport opp med eit program han kalla Tit for Tat. TFT-algoritmen var veldig enkel: Det opnar alltid med samarbeid, men deretter vil det bare kopiera motstandaren sitt forrige trekk. Med andre ord, hvis motstandaren ikkje samarbeida i forrige trekk, så gjer heller ikkje TFT det. Hvis derimot motstandaren samarbeida, så gjer også TFT det. Vi kan kanskje kalla det ein "Fantomet-algoritme". (Fantomet er hard mot de harde). Av dei fjorten programma som vart sendt inn til Axelrod sin turnering, så var TFT det kortaste. Men overraskande gjekk det likevel av med seieren. Oppmuntra av dette gjekk Axelrod i gang med ein ny turnering. Denne gong deltok sekstito program laga av både amatørar og akademikarar, og alle kjente til TFT-algoritmen og kunne designa sitt program deretter. Men likevel vant programmet nok ein gong!
Kva er ein god strategi?
Til tross for at TFT vant begge turneringane, kan vi ikkje slutta at det er den optimale strategien for turnering med Fangens Dilemma. Faktisk fins det ikkje noko slikt som ein optimal stragegi for FD. Hvis for eksempel ei overvekt av konkurrentane er av typen "Alltid samarbeid", så vil det lønna seg å vera egoistisk. Men med meir variert mengde program, så vil TFT ofte gjera det veldig bra. Så akkurat kva er det som gjer TFT bra? Axelrod meinte at følgande trekk er viktig for at ein strategi skal oppnå suksess:
- Ver snill: samarbeid. Ver aldri den første som sluttar å samarbeida.
- Ver provoserbar: besvar samarbeid med samarbeid og motarbeid med motarbeid.
- Ikkje ver misunnelig: fokuser på å maksimera din egen poengskår heller enn å slå motstandaren i enkeltspill. TFT kan faktisk aldri vinna enkeltspill, men sidan den som regel kjem som ein god nummer to, så blir sluttsummen god.
- Ikkje ver for smart: tydelighet er viktig for at andre skal kunna samarbeida med deg.
Axelrod vurderte også spørsmålet frå eit biologisk perspektiv, og kom fram til tre grunnleggjande krav til ein algoritme: For det første må den vera enkel nok til at sjøl enkle organismar skal kunne praktisera slik oppførsel. For det andre må den vera robust, slik at den vil fungera i mange ulike miljø. For det tredje må motstandsdyktiv mot invasjonar frå muterte strategiar. Dette siste kravet liknar på begrepet Evousjonært Stabil Strategi, som biologen John Maynard Smith# brukte på 1960-talet då han brukte spillteori for å beskriva evolusjonære system. Axelrod skreiv i 1981 ein artikkel saman med biologen W. D. Hamilton, kalla The Evolution of Cooperation som beskreiv turneringen. Seinare vart den utvida til ei bok med same navn.