Il Dilemma del Prigioniero e
la teoria del Punctuated
Equilibrium
Fabio Ruini ([email protected])
Università degli Studi di Modena e Reggio Emilia
Facoltà di Scienze della Comunicazione e dell’Economia
Corso di Laurea Specialistica in Economia e Gestione delle
Reti e dell’Innovazione
Anno Accademico 2004/05
Corso di Teoria della Complessità e dell’Informazione
Prof. David Avra Lane
Il Dilemma del Prigioniero
(Von Neumann e Morgenstern, 1944)
 2 persone, sospettate di aver commesso un grave
crimine insieme, vengono arrestate
 la polizia non ha sufficienti prove per dimostrare la
loro colpevolezza
 e quindi può solo incriminarli per reati minori
… a meno che uno dei due
confessi!
Una proposta
Chiusi in celle separate a ciascuno dei due
prigionieri viene fatta una proposta:
“se confessi il crimine ed accetti di
testimoniare contro il tuo
compagno, ti libereremo!”
Prospettiva interessante, ma…
 se entrambi accettano la proposta, si
discrediteranno a vicenda agli occhi del
giudice, ed incapperanno in una dura
condanna;
 se nessuno dei due accetta, la pena sarà
molto lieve per entrambi.
Formalizzando la situazione
Prigioniero A
Non parla
Prigioniero B
Confessa
contro il
Non parla
compagno
Pena molto Scarcerazione
per B,
lieve per
massima pena
entrambi
per A
Confessa Scarcerazione
contro il per A, massima
pena per B
compagno
Pena
piuttosto
severa per
entrambi
Quale scelta prendere?
Se i due prigionieri potessero
interagire e scegliere una strategia
comune, con ogni probabilità
opterebbero per non parlare.
Ma la scelta è individuale…
Dovendo scegliere senza conoscere
l’intenzione del compagno, la
strategia che minimizza il rischio
risulta essere quella di tradire.
Dimostrazione
Scegliendo di tradire, infatti:
 si
viene scarcerati, nel caso in cui il
compagno non confessi a sua volta;
 si evita la pena massima, nel caso in cui il
compagno tradisca.
Il dilemma
Siccome il singolo individuo è portato a
tradire, la situazione raggiunta è per
forza di cose una soluzione sub-ottimale
del problema!
Iterazione
Il dilemma si manifesta in misura
ancora maggiore se prendiamo in
considerazione una versione iterata
del gioco.
Gli studi di Axelrod (1984)
Axelrod, alla ricerca di una strategia ottimale
per giocare la versione iterata del Dilemma
del Prigioniero, lanciò due “tornei” aperti
all’intera comunità scientifica.
I partecipanti potevano sottoporre ad Axelrod la
propria strategia, che al massimo poteva
essere di “memoria 6”
I due tornei
I tornei, di tipo round-robin, vennero giocati al
computer.
 1° torneo: 14 programmi;
 2° torneo: 63 programmi + 1 (che si
comportava in maniera totalmente casuale)
Matrice dei payoff
Per stabilire quali fossero le strategie migliori,
Axelrod assegnò dei valori numerici alle varie
situazioni che potevano verificarsi nel gioco:
(fonte: Mitchell, 1999)
And the winner is…
La strategia che risultò vincente in entrambi i
tornei, fu la più semplice tra tutte quelle
ricevute:
la “Tit-for-Tat”
Strategia Tit-for-Tat (TFT)
La strategia TFT ha un comportamento
estremamente semplice:
 come prima mossa, sceglie la cooperazione;
 successivamente, ripropone l’ultima mossa
giocata dell’avversario.
Domanda
Un algoritmo genetico (GA) potrebbe
sviluppare strategie in grado di giocare
con successo il Dilemma del Prigioniero
nella sua versione iterata?
Per rispondere alla questione, Axelrod
sviluppò due diversi algoritmi.
Primo GA: ambiente stabile
Axelrod analizzò le strategie utilizzate nei tornei
precedenti e ne estrapolò le 8 maggiormente
rappresentative.
Queste strategie costituivano l’ambiente contro
cui si scontravano le strategie elaborate dal
GA per ottenere un valore di fitness.
Primo GA: risultati
Il GA venne eseguito con una popolazione
iniziale di 20 elementi e fermato dopo sole 50
generazioni (1000 individui generati, su uno
spazio possibile di 270);
Questo fu tuttavia sufficiente per far evolvere
strategie con performance decisamente
superiori a quella ottenuta dalla TFT!
Secondo GA: ambiente in evoluzione
In alternativa ad un ambiente stabile, nel suo
secondo GA, Axelrod eliminò le 8 strategie
“umane”.
Tutti i membri della popolazione, in ciascuna
generazione, giocavano contro tutti gli altri.
Secondo GA: risultati
Inizialmente, il GA faceva evolvere strategie
non-cooperative.
Dopo 10/20 generazioni, però, l’algoritmo inizia
a scoprire strategie che ricambiano la
cooperazione e puniscono il tradimento.
Implicazioni degli studi di Axelrod
Gli studi di Axelrod portarono a due risultati
decisamente rilevanti:
 un GA poteva far evolvere soluzioni ad un problema
interessante;
 un GA poteva servire per creare modelli di evoluzione
e di co-evoluzione.
La strada era così aperta a nuovi utilizzi degli
algoritmi genetici.
Dilemma del Prigioniero con rumore
(Lindgren, 1991)
Lindgren realizzò un nuovo GA dedicato al
Dilemma del Prigioniero iterato.
Gli elementi di novità introdotti erano due:
 l’introduzione del rumore;
 la possibilità che le strategie modifichino la
propria memoria nel corso dell’evoluzione.
Codifica binaria delle storie
Lindgren adottò una codifica binaria per le mosse
compiute dai giocatori
(0: tradimento, 1: cooperazione).
E’ così possibile identificare con un numero binario la
storia (di lunghezza m) di due giocatori:
(dove a0 è l’ultima azione dell’avversario, a1 la propria ultima
azione, a2 la penultima azione dell’avversario, ecc…).
Ad esempio: h2 = (10)
L’ordinamento delle storie
A seconda della lunghezza m delle storie
considerate, è possibile ordinarle con un
numero sequenziale.
Ad esempio, per m=2, abbiamo:
 la storia (00) -> corrispondente a 1;
 la storia (01) -> corrispondente a 2;
 la storia (10) -> corrispondente a 3;
 la storia (11) -> corrispondente a 4.
Codifica genetica delle strategie
Analogamente alle storie, anche le strategie dei
singoli individui (che costituiscono il loro
genoma) sono rappresentabili mediante un
numero binario:
(dove A0 è l’azione intrapresa al verificarsi della storia 0, A1 è
l’azione intrapresa al verificarsi della storia 1, ecc…).
esempio: strategie di memoria 1
Le strategie di memoria 1, prendono in considerazione l’ultima
mossa giocata dall’avversario e possono così riferirsi a 2 storie
diverse:
 (0), ossia la storia 1;
 (1), ossia la storia 2.
Esistono dunque 4 strategie a memoria 1:




S1 = [00] = tradisce in qualunque caso (ALL-D);
S2 = [01] = coopera quando l’avversario coopera (TFT);
S3 = [10] = coopera quando l’avversario tradisce (A-TFT);
S4 = [11] = coopera in qualunque caso (ALL-C).
Dinamiche della popolazione
La popolazione di partenza è composta
da N individui.
In ciascuna generazione, ciascun
individuo gioca contro tutti gli altri,
ottenendo un certo punteggio
(la matrice dei payoff è la stessa utilizzata
da Axelrod).
esempio di gioco: ALL-C contro ALL-D
Ad esempio, nel momento in cui si incontrano
due individui, il cui genoma codifica
rispettivamente le strategie ALL-C ed ALL-D,
il punteggio che essi totalizzano è:
giocata punteggio
realizzato
ALL-C [11]
1
0
ALL-D [00]
0
5
Calcolo del punteggio
Il punteggio si conseguito da un individuo con
genotipo i risulta essere:
Più in generale, il punteggio medio totalizzato
dall’intero sistema è dato dalla formula:
Fitness
La fitness wi di un individuo viene
calcolata come la differenza tra il suo
punteggio individuale ed il punteggio
medio del sistema:
wi  si  s
Crescita della popolazione
Da una generazione t ad una generazione
t+1, assumiamo che, per via delle
interazioni, la frazione xi della
popolazione per il genotipo i cambi
secondo la formula:
xi (t  1)  xi (t )  dwi xi (t )
(dove d è una costante di crescita che attenua l’effetto
moltiplicativo della fitness wi).
Gli operatori genetici
Ma gli operatori genetici possono influire su
questo processo riproduttivo.
Lindgren utilizza infatti tre tipi di operatori, oltre
alla selezione (proporzionale alla fitness):
 mutazione puntuale;
 duplicazione genica;
 split mutation.
La crescita per effetto delle mutazioni
La numerosità di una popolazione può dunque variare
anche per effetto delle mutazioni che hanno luogo
durante le dinamiche evolutive.
Se i tassi di mutazione sono sufficientemente bassi
(pp + pd + ps << 1/N), allora tale effetto può essere
ben approssimato dalla formula:
1
mi 
N
 (Q
ij
 Q ji )
j
(dove Qij è una variabile che assume il valore 1 se l’individuo j muta in i).
Equazione di crescita (completa)
L’equazione di crescita della popolazione,
comprensiva del termine aggiuntivo che tiene
in considerazione le possibili mutazioni da
una specie differente, risulta dunque essere:
xi (t  1)  xi (t )  dwi xi (t )  mi
Parametri utilizzati nel modello
 N = 1000;
 p = 0.01;
 pp = 2 * 10-5;
 pd = ps = 10-5;
 d = 0.1;
 max lunghezza genoma = 32;
 x00 = x01 = x10 = x11 = 1/4.
Studio delle dinamiche evolutive
(fonte: Lindgren, 1991)
Comportamento iniziale del sistema
Inizialmente, con tutte e 4 le strategie presenti,
quella che fa registrare il comportamento
migliore è ALL-D, che si impone su ALL-C ed
A-TFT, fino a portarle all’estinzione.
Una volta estinte ALL-C ed A-TFT, le condizioni
diventano favorevoli per TFT (non più
exploitata dalle due specie in questione), che
si impone su ALL-D.
Prime estinzioni e dominazioni
In figura è possibile
osservare l’estinzione
delle strategie [11],
[10] e [00].
(fonte: rielaborazione
da Lindgren, 1991 )
Gli effetti del rumore
TFT sembrerebbe in grado di mantenere a
lungo il proprio dominio sulla popolazione, ma
i risultati che consegue sono penalizzati dalle
interferenze dovute al rumore:
TFT1
C
C
…
C
D
C
…
D
D
TFT2
C
C
…
D
C
D
…
D
D
Rumore
Il ritorno in gioco di ALL-C…
Così, attraverso una mutazione puntuale
[01] [11], la strategia ALL-C rientra in gioco,
trovando terreno fertile per riprodursi.
A farne le spese è ovviamente TFT, in quanto
unica popolazione presente al momento, che
decresce rapidamente.
… e quello di A-TFT ed ALL-D
Le dinamiche, fortemente
oscillatorie, portano alla
ricomparsa di A-TFT e
ALL-D, che si
impongono, in due
momenti temporali
seguenti, sulla
popolazione
(fonte: rielaborazione
da Lindgren, 1991 )
Dinamiche di più lungo periodo
Dopo alcune migliaia di
generazioni, il sistema si
stabilizza con un mix di
TFT ed A-TFT.
(fonte: rielaborazione
da Lindgren, 1991 )
Stasi evolutiva
Sia TFT che ATFT ottengono ottimi punteggi
contro le mutanti ALL-D ed ALL-C,
impedendo loro di proliferare.
Quella che si verifica è dunque una situazione
di stasi evolutiva: nessuna strategia a
memoria 1 è ora in grado di imporsi nella
popolazione.
Uno spiraglio
L’unica strategia che potrebbe imporsi su
una popolazione di TFT ed A-TFT è la
strategia a memoria 2 [1100].
Ma è una strategia molto difficile da
ottenere: a partire da TFT sono infatti
necessarie una duplicazione genica e
due mutazioni puntuali.
La strategia [1100]
Tale strategia alterna tra cooperazione e
tradimento indipendentemente
dall’azione dell’avversario:
(00) o (01)  1
(10) o (11) -> 0
In questo modo, la strategia è in grado di
exploitare, a turno, sia TFT che A-TFT.
L’interruzione della stasi
La difficoltà nell’ottenere la nascita della
strategia [1100] fa sì che la stasi del sistema
si protragga per diverso tempo (ca. 3/4000
generazioni).
In seguito, anche la popolazione composta da
strategie a memoria 2 incapperà in una stasi
evolutiva, risolta soltanto dalla nascita di
strategie a memoria 3. Le quali, a loro volta,
cederanno il passo a quelle a strategia 4.
Dinamica complessiva del sistema
(fonte: Lindgren, 1991)
L’evoluzione del punteggio medio e
della dimensionalità del sistema
(fonte: Lindgren, 1991)
Osservazioni
 Non vi è una tendenza generale del
sistema verso configurazioni a
punteggio più alto.
 La dimensionalità del sistema varia nel
corso dell’evoluzione.
Strategie evolutivamente stabili
Una strategia si definisce “evolutivamente
stabile”, quando tutta la popolazione è
composta da individui il cui genoma
rappresenta tale strategia e non vi sono
mutanti in grado di sopravvivere.
Gli studi di Boyd e Lobermann (1987)
Boyd e Lobermann dimostrarono che, nel
Dilemma del Prigioniero, non esiste alcuna
strategia “pura” che possa definirsi
“evolutivamente stabile”.
Queste si trovano invece nel modello di
Lindgren, grazie al rumore, che fa sì che ogni
strategia possa essere vista come un mix di
due strategie pure distinte.
Un altro effetto del rumore
E’ dunque il rumore la principale causa
del particolare comportamento del
sistema, caratterizzato da lunghi periodi
di stasi, alternati a brevi periodi di
brusco cambiamento.
Tale dinamica non è una novità in senso
assoluto.
La teoria del Punctuated Equilibrium
(Gould ed Eldredge, 1972)
Gould ed Eldredge, giovani neo-laureati in
paleontologia, vennero incaricati di
compiere uno studio empirico
sull’evoluzione, così come evidenziata
dai reperti fossili.
Il problema dei fossili
I due giovani incapparono presto in un
problema ben conosciuto dai paleontologi: le
enormi lacune presenti nella documentazione
paleontologica.
In altre parole, il loro data base principale non
conteneva alcun esempio del fenomeno che
avevano intenzione di studiare.
La spiegazione tradizionale
Nel contesto di un modello rigidamente
gradualista, il mancato ritrovamento di fossili
che documentino la gradualità delle variazioni
tra le specie può essere interpretato con il
carattere discontinuo della documentazione
paleontologica.
Non una semplice giustificazione
Il processo di sedimentazione non è quasi mai
continuo, non solo negli ambienti continentali,
ma anche negli ambienti marini.
Le lacune di sedimentazione a piccola o grande
scala, dovute a mancata deposizione o a
fenomeni di erosione, costituiscono una
regola più che un fatto eccezionale.
Speciazione filetica
La speciazione filetica consiste nella
trasformazione di una specie in un’altra lungo
la stessa linea.
Il patrimonio genetico di una popolazione,
sottoposta alla pressione selettiva delle
variazioni ambientali, va a modificarsi dando
luogo a popolazioni “vissute a diversi livelli di
tempo” (Dobzansky, 1962).
Speciazione allopatrica (Mayr 1963)
Per speciazione allopatrica si intende la
separazione di una specie a causa di barriere
geografiche che provocano l’impossibilità di
interscambio del pool genico, permettendo
così l’evoluzione di una stessa specie in
diverse direzioni.
I processi di speciazione s.s., tra cui quella
allopatrica, sono gli unici che possono
causare la moltiplicazione delle specie.
Un raffronto grafico:
speciazione s.s. v. speciazione filetica
(fonte: Raffi e Serpagli, 1999)
La teoria sintetica
La moderna teoria sintetica dell’evoluzione, che
integrò gli studi sulla genetica delle
popolazioni con la sistematica, considerava la
speciazione “sensu stricto” un semplice
corollario della speciazione filetica
(Huxley, 1957).
Il solo Simpson (1949, 1954) ammise che, in
alcuni casi, anche la speciazione s.s. potesse
essere altrettanto importante.
L’intuizione di Gould ed Eldredge
Agli occhi dei due giovani scienziati, il carattere
discontinuo della documentazione
paleontologica apparve invece come il fedele
riflesso fossile di eventi di speciazione
allopatrica.
Da questo derivò la loro convinzione secondo
cui l’evoluzione biologica fosse basata, in
massima parte, proprio su eventi di
speciazione allopatrica.
Stasi e improvvisi sconvolgimenti
Considerare la speciazione allopatrica come il
principale fenomeno evolutivo giustifica in
maniera esaustiva le dinamiche emergenti
dalla documentazione paleontologica:
 lunghi periodi di stasi,
 alternati a brevi ed improvvisi periodi di forte
sconvolgimento.
Un raffronto grafico: gradualismo
filetico v. Punctuated Equilibrium
(fonte: Raffi e Serpagli, 1999)
Il contesto storico
Il lavoro di Gould ed Eldredge fu pubblicato in
un momento storico in cui le lobby
creazionistiche stavano esercitando le
massime pressioni sull’opinione pubblica,
affinché all’insegnamento dell’evoluzionismo,
nelle scuole, fosse affiancato anche quello
del creazionismo.
Equal-time bills
La pressione lobbystica dei creazionisti fece sì
che, in alcuni stati degli USA, venissero
promulgate leggi che imponevano agli
insegnanti di dedicare lo stesso tempo
all’insegnamento della teoria darwinista e di
quella creazionista.
La parola fine a questa assurda situazione fu
sancita da un tribunale, nell’ambito della
causa “Edwards v. Aguillard” (1987)
Una teoria anti-darwinista?
In un contesto del genere, la teoria del
Punctuated Equilibrium attirò un enorme
attenzione mediatica, in quanto venne vista
come un attacco alle fondamenta stesse delle
teoria darwinista.
Malgrado le numerose smentite di Gould ed
Eldredge, dovettero passare diversi anni
prima che questa etichetta venisse scrollata
di dosso.
Critiche alla teoria del Punctuated
Equilibrium
Furono mosse diverse critiche alla teoria di Gould ed
Eldredge:
 “falsa o inutile nel principio e nella logica” (Gingerich):
i fenomeni di stasi sarebbero spiegabili in un’ottica
gradualista come momenti di “gradualism at zero
rate”;
 non verificabile, data la natura dei record fossili;
 verificabile, ma non testato.
L’importanza delle gerarchie
Una delle caratteristiche peculiari della teoria
del Punctuated Equilibirum è il suo forte
carattere gerarchico.
I fenomeni di stasi e di bruschi cambiamenti si
riferiscono infatti ad aggregati di livello
“macro”.
esempio: proloculo
(fonte: Raffi e Serpagli, 1999)
esempio: Homoeorhynchia
(fonte: Raffi e Serpagli, 1999)