Il dilemma del prigioniero iterato

Cooperazione di Agenti Informatici
Corso di Laurea Specialistica in “Informatica”
A.A. 2008/09
Prof. Alberto Postiglione
UD 2.2.2: Dilemma del Prigioniero
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 2
Bibliografia

Axelrod, Robert “Giochi di reciprocità”, Feltrinelli, 1985
Vincent Van Gogh,
La ronda dei prigionieri, 1890
1
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 3
Dilemma


Un dilemma è una di quelle situazioni apparentemente
insolubili in cui qualsiasi strategia ha i suoi pro e i suoi
contro.
Qual è la cosa migliore da fare? Analizzare le possibilità e
optare per la scelta che consenta
• di correre i minori rischi possibili
• e, allo stesso tempo, di garantire il risultato più alto.

il che spesso significa non ottenere il risultato migliore in
assoluto, ma il migliore tra quelli che permettono di limitare i
rischi.
Ma la maggior parte delle volte la partita è composta da
molte manches ma a tutti non interessa vincere la battaglia, ma
la guerra.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 4
Antefatto

(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!
2
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 5
La 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!”
• 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.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 6
Formalizzando la situazione
Prigioniero B
Confessa contro
il compagno
Non parla
Prigioniero A
Non parla
Confessa
contro il
compagno
Pena molto
lieve per
entrambi
Scarcerazione per
B, massima pena
per A
Scarcerazione per Pena piuttosto
A, massima pena
severa per
per B
entrambi
3
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 7
Quale scelta è la migliore?


Se i due prigionieri potessero interagire e scegliere una
strategia comune, con ogni probabilità opterebbero per non
parlare.
Dovendo scegliere senza conoscere l’intenzione del
compagno, la strategia che minimizza il rischio risulta essere
quella di tradire. 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.
Siccome il singolo individuo è portato a tradire, la situazione
raggiunta è per forza di cose una soluzione sub-ottimale del
problema!
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 8
Il dilemma del prigioniero

Il gioco si svolge sotto le ipotesi dell’Assioma di Razionalità’
• Nessun giocatore sceglie un’azione se ne ha a
disposizione un’altra che gli permette di ottenere risultati
migliori, qualunque sia il comportamento dell’avversario

Questo gioco (forse, in assoluto, quello più studiato) mostra
una situazione in cui
• Un comportamento razionale prescrive, necessariamente, ai
giocatori un comportamento che li porta ad una situazione
peggiore, per entrambi, di un’altra situazione possibile

Il dilemma del prigioniero (sopratutto nella sua versione
iterata) ha innumerevoli applicazioni
4
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 9
Il dilemma del prigioniero

Due agenti razionali hanno la possibilità di scegliere tra 2
mosse:
• COOPERAZIONE (C)
• DEFEZIONE (D)

Essi giocano l’uno contro l’altro, in modo simultaneo (alla
mossa n uno non conosce la scelta che farà l’altro)

Gioco simultaneo, a somma non nulla, con
informazione imperfetta, dato che ogni giocatore sceglie
senza conoscere la scelta dell’altro giocatore, in cui i giocatori
muovono una volta sola
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 10
Il dilemma del prigioniero

La matrice dei payoff è la seguente:
Coopera Non Coopera

Coopera
(3, 3)
(0, 5)
Non Coopera
(5, 0)
(1, 1)
Le ricompense sono:
• R=3 Premio per la reciproca cooperazione
• P=1 Punizione per la mutua defezione
• T=5 Premio per la tentazione
• S=0 Ricompensa del “babbeo”

Si noti che 2R > T+S (in questo modo è premiato un
comportamento cooperativo)
5
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 11
Il dilemma del prigioniero

Cosa faranno i due agenti?
• Se il secondo agente COOPERA allora il primo:
• guadagna 3 se COOPERA
• guadagna 5 se NON COOPERA
• Se il secondo agente DEFEZIONA allora il primo:
• guadagna 0 se COOPERA
• guadagna 1 se NON COOPERA
• In entrambi i casi gli conviene DEFEZIONARE
• In questo caso si dice che la strategia di Defezionare è quella
DOMINANTE
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 12
Il dilemma del prigioniero

L’assioma di razionalità impone ad entrambi di NON
COOPERARE (è l’unico comportamento “razionale”)
• e guadagnano entrambi 1
• invece che 3 che guadagnerebbero se entrambi cooperassero



La defezione assicura una ricompensa superiore alla
cooperazione
Se entrambi defezionano la ricompensa è minore di quella
che avrebbero ottenuto se avessero cooperato.
Dilemma del prigioniero giocato 1 sola volta:
COMPORTAMENTO NON COOPERATIVO
6
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 13
Il dilemma del prigioniero iterato

Molto più interessante è il caso del gioco nella sua variante
ITERATA che è un gioco COOPERATIVO.
• Si suppone che ad ogni ripetizione (prova), i giocatori facciano
•
le loro scelte simultaneamente
e, subito dopo una prova, ciascuno venga a conoscenza della
scelta effettuata dall’altro.

Nella versione iterata il guadagno di un giocatore è la somma
di tutte le ricompense ottenute nelle varie mosse intermedie.

Nella versione Iterata nessun giocatore sa quando terminerà
il gioco (altrimenti la strategia dominante, in base all’assioma
della razionalità, è ancora quella Non Cooperativa)
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 14
Perché il modello è così generale?

Esistono moltissimi esempi, nelle interazioni umane tanto
quanto in natura, che rispettano la stessa matrice dei payoff.

La molteplicità delle applicazioni del modello basato sul
dilemma del prigioniero iterato dipende dal fatto che esso
cattura con semplicità una caratteristica fondamentale di
molte interazioni, cioè la tensione tra
• i vantaggi, a breve periodo, di un comportamento
•
completamente egoistico
la necessità di ottenere la cooperazione degli altri agenti per
avere successo nel lungo periodo.
7
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 15
Perché il modello è così generale?

Il dilemma del prigioniero è un paradigma per le scienze
sociali (come economia, politica e sociologia) e per le scienze
biologiche (come l’etologia o la biologia evolutiva).

Molti processi naturali vengono spiegati per mezzo di
modelli in cui gli esseri umani sono impegnati in giochi come
il dilemma del prigioniero iterato.

Questa vasta applicabilità conferisce a questo gioco la sua
sostanziale importanza.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 16
Perché il modello è così generale?

Dilemma del prigioniero tra due imprese
• In questo caso cooperare significa fissare un prezzo alto e non
•

cooperare fissare un prezzo basso.
La reciproca non cooperazione comporta un risultato peggiore
rispetto alla reciproca cooperazione, in termini di minori
profitti.
Dilemma del prigioniero tra impresa e consumatore
• Per l'impresa cooperare significa offrire un prodotto di alta
•
•
qualità mentre non cooperare offrirne uno di bassa qualità.
Per il consumatore cooperare significa acquistare il prodotto
mentre non cooperare non acquistarlo.
La strategia dominante dell'impresa è di offrire un prodotto di
bassa qualità. Il consumatore sceglie di non acquistarlo.
8
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 17
Perché il modello è così generale?

Dilemma del prigioniero tra creditore e nuovo debitore
• Per il creditore cooperare significa concedere il credito mentre
•
•
non cooperare non concederlo.
Per il nuovo debitore cooperare corrisponde alla restituzione
del debito, mentre non cooperare alla mancata restituzione.
Poichè la strategia debolmente dominante del nuovo debitore
è quella di non restituire il debito, il creditore non concede il
credito richiestogli.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 18
Perché il modello è così generale?


Negli ultimi due casi, il Dilemma del prigioniero ha payoffs
asimmetrici, in quanto a parità di coppie di strategie il payoff
per i due giocatori non è eguale.
Rispetto alla matrice dei payoffs presentata in precedenza, il
Dilemma del prigioniero asimmetrico potrebbe avere, ad
esempio, i seguenti payoffs
Consumatore-Creditore/
Impresa-Debitore
No restituzione Sì restituzione
(=Non coopera) (coopera)
No credito(=Non coopera)
0,0
7,-2
Sì credito(Coopera)
0,0
5,5
9
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 19
Perché il modello è così generale?

I biologi Paul E. Turner dell’Università di Valencia e Lin
Chao dell’Università della California hanno dimostrato che
un virus, il fago φ6 , si comporta anch’esso secondo le regole
del dilemma del prigioniero.
• Un virus è una particella che vive sfruttando le funzioni vitali
di una cellula ospite.

Turner e Chao hanno lavorato sul φ6 e sul suo clone mutante
φH2.Le premesse sono due:
• il fago φ6 produce una grande quantità di prodotti
•
intracellulari necessari alla replicazione del suo cugino mutante
φH2
il mutante φH2 vive meglio quando è in solitudine.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 20
Perché il modello è così generale?

Il virus egoista φH2, vivendo meglio “in solitudine”, si
accaparra la maggior parte delle risorse disponibili,
abbassando, però la potenziale capacità cooperativa di φ6
(che consiste nel riprodurre e generare prodotti che servono
ad entrambi).

In termini evolutivi, il virus egoista, privando φ6 delle risorse
necessarie, allo stesso tempo peggiora anche la sua
condizione perché φ6 è indispensabile affinché φH2 stesso
possa replicarsi.
10
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 21
Perché il modello è così generale?

Entrambi trarrebbero maggior vantaggio se cooperassero
(esattamente come i due prigioniero), infatti così facendo il
generoso φ6 avrebbe le risorse che gli servono e,
continuando a sopravvivere, garantirebbe anche la
replicazione dell’egoista φH2.

Tuttavia φH2 vive meglio se solo e, temendo di non
sopravvivere, preferisce sfruttare per sé tutte le risorse
disponibili e dunque non cooperare.

Ancora una volta ci troviamo di fronte ad un equilibrio che
sembra irrazionale perché non consente ad entrambi di trarre
il maggiore profitto possibile dalla situazione in corso.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 22
Perché il modello è così generale?


Lo scenario del dilemma del prigioniero è spesso usato per
illustrare il problema di due Stati impegnati in un conflitto
armato.
Entrambi saranno d’accordo nelle due possibili strategie a
loro disposizione:
• incrementare la presenza militare
• o giungere ad un accordo.



Se mai si optasse per l’accordo, nessuno dei due potrà mai
avere la certezza che l’altro rispetti l’accordo stesso;
per questa ragione la strategia dominante di entrambi sarà
incrementare la presenza militare.
Il paradosso è che si tratta della scelta razionale, che tuttavia
produce un effetto apparentemente irrazionale.
11
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 23
Perché il modello è così generale?





Un altro interessante esempio si rifà alle corse ciclistiche
Prendiamo in considerazione due ciclisti a metà percorso,
mentre il gruppo è a grande distanza dietro di loro.
I due ciclisti spesso lavorano insieme (mutua cooperazione)
dividendo tra loro la fatica data dal trovarsi davanti, senza
nessuno che li difenda dal vento.
Se nessuno dei ciclisti fa la fatica di stare davanti, il gruppo li
raggiungerà presto (mutua defezione).
Una situazione frequente vede uno dei ciclisti fare tutto il
duro lavoro da solo (coopera) e ciò, alla fine condurrà alla
vittoria del secondo (tradisce) che ha avuto l’opportunità di
sfruttare la scia apertagli dall’altro ciclista.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 24
Perché il modello è così generale?

Una banale ma familiare serie di esempi del dilemma del
prigioniero può essere constatata alla guida di un auto.
• Dalle violazioni del codice stradale
• alla guida imprudente,
questi comportamenti avvantaggiano chi li adotta, ma
peggiorano la situazione generale del traffico e la sicurezza di
tutti.
12
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 25
Tornei di strategie (Axelrod)

Prima di procedere oltre, facciamo un breve resoconto degli
studi di Axelrod che precedono la pubblicazione del volume
“The Complexity of Cooperation”

Axelrod era alla ricerca di una strategia
ottimale per la versione iterata del
Dilemma del Prigioniero
Robert Axelrod

Pensò di mettere direttamente e confronto varie strategie,
organizzando due “tornei”, aperti all’intera comunità
scientifica.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 26
Tornei di strategie (Axelrod)

Ai tornei vennero iscritte strategie implementate al computer.

Coloro che fornirono le strategie facevano parte di una
comunità molto variegata

Ogni strategia poteva essere al massimo di “memoria 6”

Le strategie vennero fatte “scontrare” a due alla volta, con un
girone all’italiana
13
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 27
Tornei di strategie (Axelrod)

Per stabilire quali fossero le strategie migliori, Axelrod
assegnò dei valori numerici alle varie situazioni di gioco:

Il punteggio di ogni strategia è dato dalla somma dei
punteggi ottenuti in ognuno degli n-1 incontri.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 28
1° Torneo

1° torneo: 14 programmi;

Durata del gioco: 200 iterazioni (valore sconosciuto ai
partecipanti)
14
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 29
Analisi dei risultati del 1° Torneo

Strategia vincente: Tit-For-Tat (di tipo molto cooperativo)

La strategia TFT ha un comportamento molto semplice:
• come prima mossa, sceglie la cooperazione;
• successivamente, ripropone l’ultima mossa giocata
dell’avversario.
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 30
Analisi dei risultati del 1° Torneo

Nel 1° torneo, su 14 strategie,
• Nessuna delle prime 8 deviava per prima dalla cooperazione
• Strategie che erano impazienti di deviare ottennero presto il
•
pagamento 5, ma poi dovettero sopportare la ripetizione di
reciproche deviazioni e pagamenti miseri.
D’altra parte, i programmi che erano sempre remissivi e
cooperativi furono duramente maltrattati dai loro avversari.
15
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 31
2° Torneo

2° torneo: 63 programmi + 1 (che si comportava in maniera
totalmente casuale)

Durata del gioco: ogni match non aveva una durata fissata.
Invece, dopo ogni singola mossa, in una partita:
• c’era una probabilità di 1/200 che il gioco finisse
• e una probabilità di 199/200 che il match andasse avanti, con
una durata media quindi, per ogni match, di circa 200 mosse.

Tutti erano a conoscenza dei risultati del primo torneo (con
la vittoria di TFT)
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 32
Analisi dei risultati del 2° Torneo

Strategia vincente: Tit-For-Tat (di tipo molto cooperativo)

TFT non vinse tutti i singoli match,
• ma quando andò sotto, andò sotto di poco,
• mentre i programmi realizzati espressamente per batterlo si
massacrarono tra di loro.
16
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 33
Strategia Tit-for-Tat (TFT)

La strategia che risultò vincente in entrambi i tornei, fu
la più semplice tra tutte quelle ricevute: la “Tit-for-Tat”
• ideata dal teorico dei giochi canadese Anatol Rapoport ed era
costituita da cinque “istruzioni” in Fortran

Axelrod spiegò il successo di TFT in termini di quattro
comportamenti:
• Non essere invidioso
• Non essere il primo a deviare
• Ricambia cooperazione e deviazione
• Non essere troppo furbo
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 34
Strategia Tit-for-Tat (TFT)

Quindi, nel caso di 1 iterazione:

Nel caso di n iterazioni (n non noto a priori)

Successivamente la TFT è stata applicata anche in altri
ambiti.
• La strategia più razionale è quella non cooperativa
• La strategia migliore è quella cooperativa
• La strategia migliore è quella cooperativa
• in politica internazionale nel periodo della guerra fredda
• In branchi di pesci per raggiungere la cooperazione
• In cause di divorzio per ottenere equità di comportamento
•…
17
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 35
Bibliografia aggiuntiva






Robert Axelrod, Giochi di reciprocità, Feltrinelli, 1985
Robert. S. Pindyck Daniel L. Rubinfeld, Microeconomia,
cap 12-13, Zanichelli
Powers Richard, Il dilemma del prigioniero, Bollati
Boringhieri, 1996
I “dilemmi” della vita in un romanzo che racconta la storia di
una famiglia americana di provincia
Marek e Kaminski, Games Prisoners Play, Princeton
University Press, 2004
Youssef Cohen, Radicals, Reformers, and Reactionaries:
The Prisoner's Dilemma and the Collapse of
Democracy in Latin America, University Of Chicago
Press, 1994
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 36
Bibliografia aggiuntiva


Anatol Rapoport, Albert M. Chammah, Prisoner's
Dilemma, University of Michigan Press, 1965
Richard Dawkins, The Selfish Gene, Oxford University
press, 1989
• Un capitolo è dedicato alle implicazioni del Dilemma del
Prigioniero nella biologia.


William Poundstone, Prisoner's dilemma: John von
Neumann, game theory and the puzzle of the bomb,
Anchor Books, 1993
Fostering Economic Policy Coordination in Latin
America: The REDIMA Approach to Escaping the
Prisoner's Dilemma United Nations, 2005
18
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 37
Bibliografia aggiuntiva

Armando Massarenti, Strategie per cooperare, anzi per competere,
Il Sole 24 ore, 1, 10, 2000.
•

Franco Carlini, L’altruismo conviene, Il Manifesto, 23/12/01
•

http://www.swif.uniba.it/lei/rassegna/011223c.htm
Un articolo di Giampietro Allasia e Umberto Cerruti
•

http://www2.polito.it/didattica/polymath/htmlS/info/BIBLIOID/Axel
rod.htm
http://alpha01.dm.unito.it/personalpages/cerruti/dochtml/dilemma/dilemma.htm
Scoprire gli URP e la loro presentazione del Dilemma
•
•
http://www.urp.it/Sezione.jsp?idSezione=952&idSezioneRif=949
http://www.urp.it/Sezione.jsp?idSezione=949&idSezioneRif=38
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 38
Bibliografia aggiuntiva

Il Dilemma interattivo
• http://www.dm.unito.it/personalpages/cerruti/Az1/dilframe
s.html


The ethical spectacle, Vol. I, No. 9 September 1995,
dedicato al Prisoner’s Dilemma.
Il Dilemma del Prigioniero nell’amore, nella politica, nel
cinema e molto altro
• http://www.spectacle.org/995/index.html

Prisoner’s Dilemma sulla Stanford Enciclopedia of Philosophy
• http://plato.stanford.edu/entries/prisoner-dilemma/
19
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 39
Bibliografia aggiuntiva




Prisoner’s Dilemma in Mathworld
http://mathworld.wolfram.com/PrisonersDilemma.html
Prisoner’s Dilemma da giocare in classe
http://www.indiana.edu/~econed/pdffiles/summer00/Holt
.pdf
Frattali e Dilemma del Prigioniero
http://classes.yale.edu/fractals/Panorama/SocialSciences/P
risDil/PrisDil.html
Prisoner’s Dilemma sulla Wikipedia
http://it.wikipedia.org/wiki/Dilemma_del_prigionierohttp:/
/en.wikipedia.org/wiki/Prisoner%27s_dilemma
Prof Alberto Postiglione
Cooperazione di Agenti Informatici (08/09)
UD 2.2
13/05/2009
Dia 40
Bibliografia aggiuntiva

Il Dilemma del Prigioniero da giocare contro il computer
• http://www.princeton.edu/~mdaniels/PD/PD.html
• http://serendip.brynmawr.edu/playground/pd.html
20