'Vær ikke for klog, og lad være med at være unfair.' Det har man troet var den bedste strategi for et af spilteoriens mest berømte spil, Fangernes Dilemma.

Men nu viser det sig, at det både kan betale sig at være klog og unfair.

Sådan udlægger den amerikanske skribent William Poundstone, som har skrevet flere bøger om spilteori og Fangernes Dilemma, en ny matematisk analyse af William Press og Freeman Dyson.

Hans udlægning bekræftes af en række numeriske eksperimenter med forskellige strategier foretaget af evolutionsbiologerne Alexander Stewart og Joshua Plotkin fra University of Pennsylvania.

Det diskuteres nu ivrigt blandt eksperter, hvad denne nye overraskende indsigt betyder for evolutionsbiologien og samfundsvidenskaberne, hvor spilteori er taget i anvendelse til at forklare bl.a. klimaforhandlinger og nedrustningsforhandlinger.

Det er ikke hvem som helst, der står bag analysen.

Den 89-årige Freeman Dyson fra Institute for Advanced Study i Princeton, USA, er en af verdens mest respekterede matematiske fysikere, mens den noget yngre, 'kun' 64-årige, William Press fra University of Texas i Austin har ydet store bidrag både inden for teoretisk biologi, astrofysik og datalogi.

Problemstillingen kort fortalt

Problemstillingen blev lanceret i 1950 af to forskere fra den amerikanske tænketank RAND og formaliseret samme år af den canadiske matematiker Albert W. Tucker, som også opfandt navnet Fangernes Dilemma.

Dilemmaet drejer sig om to personer, som er anklaget for en alvorlig forbrydelse. Hver person får valget mellem at forholde sig tavs til anklagen eller at forråde den anden.

Opretholder de begge tavshed, slipper de begge med en mild straf for en mindre forbrydelse. Forråder de begge hinanden får de begge en mellemlang straf. Hvis den ene forråder, og den anden forholder sig tavs, går forråderen derimod fri, og den tavse får en meget hård staf. Uanset hvad fange nr. 1 vælger at gøre, vil fange nr. 2 få den laveste straf ved at forråde - og omvendt.

Derfor vælger de at forråde hinanden og får begge den mellemlange straf, selv om de kunne være sluppet billigere ved begge at være tavse.

Det er den såkaldte Nash-ligevægt, opkaldt efter matematikeren John Nash, hvis liv i 2001 blev skildret i filmen 'A Beautiful Mind'.

Hvis fangerne mødes gentagne gange i fængslet og hver gang får samme tilbud, opstår et mere interessant problem, der kendes som Gentagne Fangernes Dilemma eller IPD efter det engelske navn Iterated Prisoner's Dilemma.

I dette problem er opgaven at vælge en strategi, som i det lange løb giver mindst mulig straf.

En lang række turneringer mellem forskellige strategier gennemført af den amerikanske samfundsvidenskabelige forsker Robert Axelrod fra University of Michigan i 1980 viste, at en svar på tiltale-strategi ('tit for tat' på engelsk), hvor en fange i næste runde vælger samme beslutning, som den anden fange valgte i forrige runde, generelt var andre strategier overlegen.

William Press og Freeman Dyson har nu vist, at der findes strategier, hvor den ene fange kan påtvinge den anden en bestemt gennemsnitstraf eller kan afpresse den anden fange, så afpresseren får en lavere straf end den, der afpresses.

Selv om Fangernes Dilemma oprindeligt er tænkt som et valg mellem forskelige straffe, analyseres spillet normalt i en udgave, hvor der er positive gevinster til fordeling mellem to parter.

Vælger begge spillere at samarbejde, får de begge en præmie på R. Vælger de begge at modarbejde hinanden, får de en præmie på P. Vælger den ene at samarbejde og den anden at modarbejde, er præmien S til den, der samarbejder, og præmien er T til den, som modarbejder.

Spillet er kun interessant, hvis T > R > P > S, og det samtidig gælder, at 2R > T + S. Den første betingelse sikrer, at Nash-ligevægten er, at begge vil modarbejde hinanden. Den anden betingelse sikrer, at den bedste løsning samlet set for begge parter er samarbejde. I konkrete regneeksempler er det kutyme at sætte (T, R, P, S) = (5, 3, 1, 0).

Nul-determinantstrategier

De nye strategier kaldes nul-determinantstrategier, fordi de er baseret på, at X skal fastsætte en sandsynlighed for samarbejde i næste spil, som medfører, at en 4 x 4-matrix har en determinant på nul (læs mere i artiklen om nul-determinantstrategier).

Med denne strategi kan X bestemme, hvilken værdi Y's gennemsnitsgevinst pr. spil skal have i intervallet 1-3 (for P=1 og R=3). Gevinsten for X afhænger derimod af, hvad Y gør.

Hvis Y er en såkaldt evolutionær spiller, der udelukkende vil søge at optimere sin egen gevinst, kan X også med en nul-determinantstrategi afpresse Y til at give X en endnu større gevinst end Y.

X kan endda i grænsen vælge, at Y's maksimale gevinst kan være 1, og X vil i givet fald få en gevinst på 4 1/3.

Følger X en nul-determinantstrategi, vil spillets udfald afhænge af, om Y følger en strategi, som søger at optimere Y's egen gevinst, eller om Y er klar over, at han bliver udsat for en afpresningsstrategi.

Y kan nemlig da vælge sabotage-udvejen og ødelægge sin egen score for også at ødelægge X's score med henblik på at få X til at skifte strategi.

Endelig er der også den mulighed, at både X og Y kender til nul-determinantstrategier. De kan da hver især bestemme modspillerens gevinst eller afpresse hinanden med det resultat, at de begge får en lav gevinst.

William Press forklarer, at det bedste, X og Y kan gøre i denne situation, er at sætte hinandens gennemsnitsgevinst til den maksimale værdi på 3 og samtidig tillade X at sætte Y's gevinst ned, hvis X's gevinst bliver lavere. Det kan nemlig kun ske, hvis Y ikke følger den indgåede aftale.

Det vil give et bedre resultat end svar på tiltale-strategien, som kun garanterer, at X og Y får samme gevinst, men ikke gevinstens størrelse.

Fangernes Dilemma er med de nye nul-determinantstrategier blevet et meget mere kompliceret og meget mere interessant spil, end man hidtil havde troet.

Alexander Stewart og Joshua Plotkin udtrykker det på denne måde:

»X må i spillet finde ud af, hvad Y kender til spillet og til X, og hvad Y kan være i stand til at finde ud af. Først da kan X anvende sig egen viden om spillet og nul-determinantstrategier til at vælge en strategi, som bedst tjener X's egne interesser.«

Matematikeren Michael Shulman fra University of California, San Diego, anerkender i et langt indlæg på matematik-bloggen 'The n-Category Café', at Press og Dysons analyse er banebrydende, og opdagelsen har implikationer, som endnu ikke er forstået til bunds.

Han advarer dog mod overfortolkninger, og han er tvivlende over for, om nul-determinantstrategier virkeligt er bedre end svar på tiltale.

Han bemærker, at svar på tiltale generelt ikke klarer sig bedre end de strategier, den konkurrerer mod.

Det viser sig ved, at svar på tiltale ikke vinder mange matcher. Til gengæld akkumulerer svar på tiltale store gevinster, når den spiller mod andre 'pæne' strategier, som man definerer som strategier, som ikke er først til at modarbejde.

Hvis det gælder om at vinde matcher snarere end at akkumulere point, vil nul-determinantstrategier derimod have en klar fordel, bemærker Michael Shulman.

Men han mener, at det generelt kun er i spil, som svar på tiltale aldrig har været påstået at være bedst til, at afpresning baseret på nul-determinantstrategier er bedre.

Evolution er en barsk modspiller

Den engelske biolog John Maynard Smith indførte for 40 år siden spilteori og Fangernes Dilemma i evolutionsbiologien.

Derfor har biologer også straks set nærmere på betydningen af de nye nul-determinantstrategier.

I en ny artikel har Christoph Adami og Arend Hintze fra Michigan State University vist, at det er muligt for andre strategier at vinde indpas i en population, hvor nul-determinantstrategier oprindeligt dominerede. Det betyder, at nul-determinantstrategier ikke er evolutionært stabile.

Forklaringen er ifølge Adami og Hintze kort fortalt, at nul-determinantstrategier klarer sig dårligt i kamp mod hinanden, som Press og Dyson også er inde på i deres artikel.

Det kan muligvis forklare, hvorfor ingen endnu har fundet eksempler på nul-determinantstrategier i naturen.

Adami og Hintze bemærker dog også, at hvis spillere med nul-determinantstrategier kan finde ud af, om en anden spiller følger samme strategi, kan de undgå tabene, når de spiller mod hinanden, og vinde stort over uvidende spillere.

Sådan en fordel vil dog være kortlivet, i takt med at andre strategier udvikler sig med henblik på at undgå at blive opdaget, skriver de to forskere i en artikel, der er indsendt til offentliggørelse i Proceedings of the National Academy of Sciences (PNAS) - samme tidskrift, som har publiceret Press og Dysons artikel.

Eksistensen af nul-determinantstrategier er meget overraskende, men det drejer sig ikke udelukkende om at vinde, er konklusionen fra Adami og Hintze - i trå d med Michael Shulmans bemærkninger.

Den generelle konklusion må foreløbig være, at Press og Dysons opdagelse af nul-determinantstrategier har sat gang i en diskussion, som endnu ikke er afsluttet. Det er dog også ret imponerende inden for et område, som alle indtil for nylig troede for længst var analyseret til bunds.

Fakta:

Prøv teorien i praksis

Prøv selv at spille mod et program, som følger en nul-determinantstrategi, der har fastsat modstanderens gennemsnitsgevinst til 2. Følg linket ing.dk/k#bchu eller scan QR-koden på din mobiltelefon.

Programmet viser styrken ved nul-determinantstrategier, men illustrerer også nogle af de kritikpunkter, der er rejst. For godt nok vil modstanderens gennemsnitsgevinst efter nogle hundrede spil altid være tæt på 2, men gevinsten til den, som følger strategien, kan variere fra under 1 til næsten 4.

Strategien, der kan bestemme modpartens gevinst

I mange spil forbedrer man sin chance for at vinde, hvis man har god hukommelse. Det er dog ikke tilfældet i Gentagne Fangernes Dilemma.

Press og Dysons matematiske analyse viser, at man kun behøver at tage hensyn til det netop afsluttede spil, når man skal vælge mellem samarbejde eller modarbejde i det næste spil.

Analysen er baseret på, at det foregående spil kan have haft fire forskellige udfald: SS, SM, MS, MM, hvor S står for samarbejde og M for modarbejde, og det første bogstav er X's valg, det andet bogstav er Y's valg. For hver af disse situationer fastsætter X nu en sandsynlighed for næste gang at samarbejde, disse sandsynligheder kaldes p1, p2, p3 og p4, og sandsynligheden for at modarbejde er derfor (1-p1) osv.

Spillet kan matematisk set beskrives som et system, som overgår fra en tilstand til en anden, og det kan som sådan analyseres med en Markov-kæde og en Markov-matrix, som i det aktuelle tilfælde en 4 x 4-matrix, hvor elementerne i matricen er bestemt af de forskellige sandsynligheder for samarbejde ud fra de fire forskellige foregående udfald.

Det viser sig, at både X og Y har muligheden for uafhængigt af hinanden at vælge deres fire sandsynligheder for at samarbejde på en måde, så determinanten for en bestemt matrix, som har en relation til Markov-matricen, er nul.

Den matematiske analyse viser, at når X vælger en sådan nul-determinantstrategi, så kan X bestemme præcis, hvilken gevinst Y i gennemsnit vil få i intervallet mellem R og P - henholdsvis gevinsten ved, at begge samarbejder eller begge modarbejder (se også hovedartiklen).

Analysen viser også, at X ikke kan bestemme sin egen gevinst, og at X har en mulighed for at afpresse Y. Det betyder, at X kan vælge en strategi, der betyder, at Y for at få maksimalt udbytte må forfølge en strategi, der giver X endnu større gevinst.

Det er med til at gøre spillet yderligere kompliceret, at Y naturligvis har samme muligheder som X.