Dilema del presoner

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de jocs, el dilema del presoner és un tipus de joc de suma no nul·la en el qual dos jugadors poden «cooperar» o «trair-se». En aquest joc, igual que en totes les situacions de teoria de jocs, l'única preocupació de cada jugador individual és maximitzar els seus beneficis, independentment del benefici de l'altre jugador.

En la formulació clàssica d'aquest problema l'estratègia dominant és la traïció, de manera que l'únic equilibri possible del joc és que tots els jugadors traeixin. És a dir, independentment de què faci l'altre jugador, sempre s'obtindrà un major benefici traint. Les tècniques d'anàlisi de la teoria de jocs estàndard, per exemple la determinació de l'equilibri de Nash, poden dur a cada jugador a escollir trair a l'altre, però curiosament ambdós jugadors obtindrien un resultat global millor si col·laboressin. Es tracta d'un tipus de solució anomenada «solució de Pareto subòptima», en què l'elecció racional duu ambdós jugadors a trair-se malgrat que la recompensa individual seria major si cooperessin. Aquest és el punt clau del dilema.

En el dilema del presoner iterat, la cooperació pot obtenir-se com un resultat d'equilibri. Aquí es juga repetidament, per la qual cosa, quan es repeteix el joc, s'ofereix a cada jugador l'oportunitat de castigar l'altre jugador per la no cooperació en jocs anteriors. Així, l'incentiu per trair pot ser superat per l'amenaça del càstig, la qual cosa condueix a un resultat cooperatiu. Si el joc es repeteix indefinidament s'assoleix un equilibri de Nash, tot i que la traïció segueix sent una possible situació d'equilibri.

El dilema del presoner clàssic[modifica | modifica el codi]

La formulació clàssica del dilema del presoner és:

« La policia arresta dos sospitosos. No hi ha proves suficients per condemnar-los i, després d'haver-los separat, els interroga i els ofereix el mateix tracte. Si un confessa i el seu còmplice no, el còmplice serà condemnat a la pena total, deu anys, i el primer serà alliberat. Si un calla i el còmplice confessa, el primer rebrà aquesta pena i serà el còmplice qui sortirà lliure. Si ambdós romanen callats, com a màxim podran tancar-los durant sis mesos per un càrrec menor. Si ambdós confessen, ambdós seran condemnats a sis anys. »

El dilema es pot resumir en forma de taula:

El presoner B calla El presoner B confessa
El presoner A calla Tots dos són condemnats a sis mesos A és condemnat a deu anys.
B surt lliure
El presoner A confessa A surt lliure.
B és condemnat a deu anys
Tots dos són condemnats a sis anys

Suposarem que ambdós presoners són completament egoistes i que l'únic objectiu que persegueixen és reduir la seva pròpia condemna. Cada presoner té dues opcions: cooperar amb el seu còmplice i romandre callat, o trair-lo i confessar. El resultat de cada elecció depèn de l'elecció del còmplice. Desafortunadament, un no coneix què ha decidit fer l'altre. Fins i tot si poguessin parlar entre ells, no podrien estar segurs de confiar l'un en l'altre.

Si un dels dos espera que el còmplice escollirà cooperar amb ell i romandre en silenci, l'opció òptima per al primer seria confessar, ja que això significaria ser alliberat immediatament, mentre el còmplice hauria de complir una condemna de 10 anys. Si espera que el seu còmplice decidirà confessar, la millor opció torna a ser confessar, ja que almenys no rebrà la condemna completa de 10 anys, i només n'haurà d'esperar 6, igual que el còmplice. Si, tanmateix, ambdós decidissin cooperar i romandre en silenci, ambdós serien alliberats en només 6 mesos. Confessar és una estratègia dominant per a ambdós jugadors: sigui quina sigui l'elecció de l'altre jugador, poden reduir sempre la seva pena confessant. Per desgràcia per als presoners, això condueix a un resultat regular, en el qual ambdós confessen i ambdós reben llargues condemnes. Aquí es troba el punt clau del dilema. El resultat de les interaccions individuals produeix un resultat que no és òptim en el sentit de Pareto; existeix una situació en la qual el resultat per a un dels detinguts podria millorar (fins i tot per a ambdós) sense que això impliqués un empitjorament per a la resta. En altres paraules, el resultat en el qual ambdós detinguts no confessen domina al resultat en el qual els dos elegeixen confessar. Aquesta situació, en termes més tècnics, il·lustra perfectament que en un joc de suma no nul·la un equilibri de Nash no és necessàriament un òptim de Pareto.

Si hom ha tingut una oportunitat per castigar l'altre jugador per haver confessat, llavors pot mantenir-se un resultat cooperatiu. La forma iterada d'aquest joc (vegeu la secció «El dilema del presoner iterat») ofereix una oportunitat per a aquest tipus de càstig. En aquest joc, si el còmplice traeix i confessa una vegada, se'l pot castigar traint-lo a la pròxima. Així, el joc iterat ofereix una opció de càstig que és absent en la forma clàssica del joc.

Forma generalitzada[modifica | modifica el codi]

Es pot analitzar el problema eliminant la història dels presoners i ampliant-lo a l'anomenada «forma generalitzada», que s'utilitza habitualment en economia experimental. L'enunciat següent és una formulació habitual del problema:

Hi ha dos jugadors i un banquer. Cada jugador té un conjunt de dues cartes: una impresa amb la paraula «cooperar» i l'altra amb la paraula «trair». Cada jugador situa una carta cara avall davant del banquer; en fer-ho així s'elimina la possibilitat que un jugador sàpiga amb antelació la selecció de l'altre (tot i que mostrar les opcions escollides no afecta l'anàlisi de dominància). Una vegada situades les cartes, es mostren i el banquer dóna els pagaments corresponents: si el jugador 1 (vermell) traeix i el jugador 2 (blau coopera, el jugador 1 obté el resultat de «Temptació de trair» amb 5 punts, mentre que el jugador 2 rep el resultat de «Babau» amb 0 punts. Si ambdós cooperen obtenen el «Premi de cooperació mútua» amb 3 punts i si ambdós es traeixen reben el «Càstig de traïció mútua» amb 1 punt.

En aquesta formulació la matriu de beneficis del problema és, en la forma canònica i en terminologia «guanyar-perdre»:

Matriu canònica de beneficis
Cooperar Trair
Cooperar 3, 3 0, 5
Trair 5, 0 1, 1
Matriu «guanyar-perdre»
Cooperar Trair
Cooperar guanya-guanya perd molt-guanya molt
Trair guanya molt-perd molt perd-perd

Els valors concrets de la matriu canònica s'assignen de forma arbitrària, ja que és possible generalitzar-los a qualsevol valor sempre que es compleixi la regla següent, establerta per Douglas Hofstadter:

T > R > P > S

on T és la «Temptació de trair», R és el «Premi de cooperació mútua», P és el «Càstig de traïció mútua» i S és el «Babau». Si es tracta del dilema del presoner iterat, a la desigualtat anterior cal afegir la condició:

2R > T + S

Si no es compleix aquesta darrera condició, la cooperació completa no és necessàriament un òptim de Pareto, ja que els jugadors obtenen globalment més beneficis alternant a cada joc la cooperació i la traïció.

El dilema del presoner iterat[modifica | modifica el codi]

Si dos jugadors participen en el joc més d'una vegada i successivament (és a dir, amb memòria del resultat de, com a mínim, el joc anterior) s'obté l'anomenat «dilema del presoner iterat» (DPI). Entre els resultats demostrats per Robert Aumann en un article de l'any 1959, els jugadors reacionals que interaccionen repetidament en jocs indefinidament llargs, poden suportar un resultat cooperatiu. L'interès popular en el dilema del presoner iterat augmentà arran del llibre de Robert Axelrod The Evolution of Cooperation («L'evolució de la cooperació», 1984), en què explica un torneig que organitzà en el qual els participants havien d'escollir la seva estratègia mútua una vegada rere una altra, conservant la memòria dels jocs anterior. Axelrod convidà investigadors d'arreu del món a que dissenyessin estratègies reproduïbles en un programa informàtic per competir en el torneig del DPI. Els programes que hi participaren foren molt variats pel que fa a complexitat algorítmica, hostilitat inicial, capacitat de perdó, etc.

Axelrod descobrí que quan es repetien aquests torneigs durant molt de temps i amb molts jugadors, cada un amb estratègies diferents, les estratègies egoístes tendien a obtenir resultats pobres a llarg termini, mentre que les estratègies més altruistes obtenien millors resultats, sempre des del punt de vista de l'interès propi, independentment del resultat dels altres. Axelrod postulà que això podria ser un mecanisme per a l'evolució per selecció natural de comportaments altruistes a partir de mecanismes que, inicialment, són exclusivament egoistes.

En aquests experiments es descobrí que la millor estratègia determinista per maximitzar els beneficis era l'anomenada «ull per ull» (o estratègia cooperació-reciprocitat-perdó, en anglès Tit for Tat), que desenvolupà Anatol Rapoport i amb el qual participà en el torneig. Era el programa més simple de tots els participants, amb només quatre línies de codi en BASIC, i guanyà el torneig. L'estratègia és simplement cooperar en la primera iteració del joc i, posteriorment, fer allò que l'oponent ha fet en la iteració anterior. Una estratègia lleugerament millor és l'anomenada «ull per ull amb perdó»: quan l'oponent traeix, a la següent iteració el jugador a vegades pot cooperar, amb una probabilitat baixa (1% - 5%). Això permet recuperar-se de la possible situació d'un cicle continu de traïcions.

Analitzant les estratègies que obtingueren una major puntuació, Axelrod determinà diverses condicions perquè una estratègia obtingués bons resultats:

  • Amabilitat: la condició més important és que l'estratègia sigui «amable»; és a dir, que no traeixi abans que ho faci l'oponent. Això vol dir que, curiosament, una estratègia òptima purament egoísta, amb objectius totalment egoistes, mai trairà el seu oponent abans que aquest ho faci.
  • Presa de represàlies: la millor estratègia no ha de ser cegament optimista, però, i ha de prendre represàlies quan calgui. Una estratègia del tipus «cooperar sempre» dóna resultats molt dolents, ja que les estratègies «malvades» les guanyen indefectiblement.
  • Perdó: l'estratègia òptima ha de poder tornar a cooperar si l'oponent deixa de trair. D'aquesta manera es trenquen els cicles infinits de revenja i contra-revenja i es maximitzen els punts aconseguits.
  • Manca d'enveja: l'estratègia òptima no ha d'intentar obtenir més punts que els seus oponents (cal recordar que l'objectiu és maximitzar els beneficis propis independentment de quins beneficis obtinguin els altres).

D'aquí, una de les conclusions d'Axelrod, és que els individus egoistes, per obtenir els seus objectius egoistes, tendiran a ser amables, perdonaran i no seran envejosos (en el sentit explicat abans).

L'estratègia òptima del dilema del presoner clàssic és trair, independentment de l'estratègia triada per l'oponent. Nogensmenys, en el dilema del presoner iterat l'estratègia òptima sí depèn de l'estratègia escollida pels possibles oponents i de com reaccionen a la cooperació i a la traïció. Per exemple, consideri's una població en què tothom traeix sempre, excepte per a un sol individu que segueix l'estratègia «ull per ull»; aquest individu es troba en un cert desavantatge, ja que ha perdut la primera iteració del joc i, per tant, en aquesta població l'estratègia òptima individual és trair sempre. En canvi, en una població amb un cert percentatge d'individus que traeixen sempre i la resta que segueix l'estratègia «ull per ull», l'estratègia òptima individual depèn del percentatge i del nombre d'iteracions del joc.

Per obtenir l'estratègia òptima en un dilema del presoner iterat es poden seguir dos mètodes:

  • Determinar l'equilibri de Nash bayesià. Si es pot determinar la distribució estadística de les estratègies enfrontades (p. ex. 50% «ull per ull» i 50% sempre cooperar) llavors es pot obtenir matemàticament la contra-estratègia òptima.
  • Realitzar simulacions pel mètode de Monte Carlo. En aquestes simulacions els individus amb les puntuacions baixes desapareixen i els individus amb puntuacions més altes es reprodueixen (amb un algorisme genètic per trobar l'estratègia òptima). La barreja d'algorismes en la població final acostuma a dependre de la barreja en la població inicial; si s'introdueixen mutacions (variacions aleatòries durant la reproducció) disminueix la dependència de la població inicial. Els experiments amb aquests sistemes tendeixen a produir jugadors amb l'estratègia «ull per ull», però no hi ha cap demostració analítica que això sempre sigui així.

Tot i que l'«ull per ull» es considera l'estratègia bàsica més robusta, un grup de la Universitat de Southampton introduí una nova estratègia a la competició celebrada amb motiu del 20è aniversari del primer torneig d'Axelrod, que demostrà ser més reeixida que l'«ull per ull». Aquesta estratègia es basava en la cooperació entre programes perquè un d'aquests programes assolís la màxima puntuació. El grup de la universitat presentà 60 programes a la competició, dissenyats per reconèixer-se mútuament mitjançant un conjunt de cinc a deu moviments inicials. Una vegada realitzat aquest reconeixement un dels programes sempre cooperava i l'altre sempre traïa, per tal de garantir el màxim de punts per al traïdor; si, en canvi, el programa detectava que s'estava enfrontant a un programa que no era del grup de Southampton, traïa sistemàticament, per intentar minimitzar la puntuació del contrincant. Com a resultat, aquesta estratègia aconseguí els tres primers llocs de la competició, i també algunes de les darreres posicions.

Altres jocs similars[modifica | modifica el codi]

Intercanvi de bosses tancades[modifica | modifica el codi]

Douglas Hofstadter va suggerir que la gent sovint troba problemes com el dilema del presoner més fàcils d'entendre quan estan presentats com a un simple joc o intercanvi. Un dels exemples que va usar va ser el de dues persones que es troben i intercanvien bosses tancades, amb l'entesa que una d'elles conté diners i l'altra conté un objecte que està sent comprat. Cada jugador pot escollir seguir l'acord posant a la seva bossa el que va acordar, o pot enganyar oferint una bossa buida. En aquest joc d'intercanvi l'engany és sempre la millor opció, i això vol dir que cap agent racional el jugarà; és a dir aquesta situació serà un «mercat absent» a causa de selecció adversa.

En una variant del joc, popular entre hackers i programadors, cada agent intercanviador de bosses té memòria (o accés a una memòria col·lectiva) i es van repetint intercanvis a mesura que passa el temps. Igual que en el cas del dilema del presoner, sense la introducció de temps i de memòria poques coses es poden induir del comportament de sistemes i grups de persones reals.

Amic o enemic?[modifica | modifica el codi]

Friend or Foe? («Amic o enemic?») és un joc que s'està emetent actualment al canal de cable i satèl·lit nord-americà Game Show Network. És un exemple del dilema del presoner provat en persones reals, però en un entorn artificial. En el concurs, competeixen tres parells de persones. Quan cada parella és eliminada, juguen a un joc del dilema del presoner per determinar com es repartiran els guanys. Si ambdós cooperen («amic») comparteixen els seus beneficis al 50%. Si un coopera i l'altre traeix («enemic»), el traïdor s'emporta tots els guanys i el cooperador cap. Si ambdós traeixen, cap no s'endú res. Cal fer notar que la matriu de beneficis és lleugerament diferent que en el cas del dilema del presoner estàndard, ja que els beneficis de la situació «ambdós traeixen» i el de «jo coopero i l'altre traeix» són idèntics. Això fa que la situació «ambdós traeixen» sigui un equilibri neutral.

Exemples a la vida real[modifica | modifica el codi]

Les situacions de la formulació habitual del dilema del presoner, en què intervenen presoners, intercanvi de bosses i coses semblants poden semblar rebuscats, però existeixen, de fet, molts exemples d'interaccions humanes i d'interaccions naturals en les quals s'obté la mateixa matriu de beneficis. El dilema del presoner és per això d'interès per a ciències socials com l'economia, les ciències polítiques i la sociologia, a més de per a la biologia, especialment en etologia i biologia evolutiva.

En ciències polítiques, per exemple, l'escenari del dilema del presoner s'usa sovint per il·lustrar el problema de dos estats involucrats en una cursa armamentística. Ambdós raonaran que tenen dues opcions: o bé incrementar la despesa militar, o bé arribar a un acord per reduir el seu armament. Cap dels dos estats no pot estar segur que l'altre complirà l'acord; d'aquesta manera, ambdós s'inclinaran cap a l'expansió militar. La ironia rau en el fet que tots dos Estats semblen actuar racionalment, però el resultat és del tot irracional.

Un altre exemple interessant té a veure amb un concepte conegut de les curses de ciclisme, per exemple el Tour de França. Considereu dos ciclistes a meitat de cursa, amb l'escamot a gran distància. Tots dos ciclistes treballen sovint conjuntament (cooperació mútua) compartint la pesant càrrega de la posició davantera, en què no es poden refugiar del vent. Si cap dels ciclistes no fa un esforç per romandre a davant, l'escamot els atraparà ràpidament (traïció mútua). Un exemple que es veu sovint és que només un dels ciclistes fa tota la feina (cooperi), i els manté a tots dos lluny de l'escamot. Al final, això probablement comportarà a una victòria del segon ciclista (traïdor) que ha tingut una cursa fàcil seguint l'estela del primer corredor.

La conclusió teòrica del dilema del presoner és una raó per la qual a molts països es prohibeix arribar a acords judicials. Sovint s'aplica precisament l'escenari del dilema del presoner: és en l'interès dels dos sospitosos, confessar i testificar contra l'altre sospitós, fins i tot si tots dos són innocents del presumpte crim. Podem dir que el pitjor cas es dóna quan només un d'ells és culpable: no és probable que l'innocent confessi, mentre que el culpable tendirà a confessar i testificar contra l'innocent.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  • Robert Aumann. «Acceptable points in general cooperative n-person games», a R. D. Luce i A. W. Tucker (editors), Contributions to the Theory 23 of Games IV, Annals of Mathematics Study 40, 287–324, Princeton University Press, Princeton, Nova Jersey.
  • Axelrod, R. (1984). The Evolution of Cooperation. ISBN 0-465-02121-2
  • Kenneth Binmore, Fun and Games.
  • David M. Chess (1988). «Simulating the evolution of behavior: the iterated prisoners' dilemma problem». Complex Systems 2:663–670.
  • Dresher, M. (1961). The Mathematics of Games of Strategy: Theory and Applications Prentice-Hall, Englewood Cliffs, NJ.
  • Flood, M.M. (1952). Some experimental games. Research memorandum RM-789. RAND Corporation, Santa Monica, Califòrnia
  • Kaminski, Marek M. (2004) Games Prisoners Play Princeton University Press. ISBN 0-691-11721-7 http://webfiles.uci.edu/mkaminsk/www/book.html
  • Poundstone, W. (1992) Prisoner's Dilemma Doubleday, Nova York.
  • Greif, A. (2006). Institutions and the Path to the Modern Economy: Lessons from Medieval Trade. Cambridge University Press, Cambridge, Regne Unit.
  • Rapoport, Anatol and Albert M. Chammah (1965). Prisoner's Dilemma. University of Michigan Press.
  • Le, S. & Boyd, R. «Evolutionary dynamics of the continuous iterated Prisoner's dilemma», Journal of Theoretical Biology, text complet Noia 64 mimetypes pdf.pngPDF.
  • A. Rogers, R. K. Dash, S. D. Ramchurn, P. Vytelingum and N. R. Jennings (2007) «Coordinating team players within a noisy iterated Prisoner's Dilemma tournament», Theoretical Computer Science 377 (1-3) 243-259, text complet Noia 64 mimetypes pdf.pngPDF.