Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Breve Introduzione (1)
 Una configurazione dinamica è rappresentata da
un’insieme di giocatori che interagiscono
ripetutamente tra di loro.
 In tale situazione le nostre regole di comportamento
saranno chiamate Adaptive heuristics se sono
semplici e allo stesso tempo portano i giocatori in una
“buona” direzione.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Breve Introduzione (2)
 Una semplice Adaptive heuristics potrebbe essere
quella di scegliere sempre la best response in base a ciò
che hanno fatto i giocatori nell’immediato passato.
 Possiamo subito notare una differenza con gli
argomenti visti durante il corso: i giochi non saranno
più one-step, ma saranno dinamici ossia i giocatori
interagiranno più volte tra di loro.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Domanda…
 La domanda di maggiore interesse è:
 Queste semplici regole comportamentali (Adaptive
heuristics), a lungo andare, possono rendere il
comportamento dei giocatori razionale e altamente
sofisticato?
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Classificazione delle Dinamiche
 Nella teoria dei giochi e nella teoria economica è
possibile suddividere i modelli dinamici in tre classi:
 Learning Dynamics
 Evolutionary Dynamics
 Adaptive Heuristics
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Learning Dynamics
 Ogni giocatore inizia con una predeterminata
opinione sui dati pertinenti al gioco (“state of the
world”), i quali includono il gioco che si sta giocando e
le strategie che possono intraprendere gli altri
giocatori.
 Ad ogni fase, dopo aver osservato le azioni prese
all’interno del gioco, ogni giocatore aggiorna la propria
opinione e gioca la sua best respons.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Evolutionary Dynamics (1)
 Ogni giocatore i viene sostituito da una serie di
individui che giocano sempre la stessa azione
(genotype) al posto del giocatore i.
 Le relative frequenze delle azioni degli individui
possono essere viste come una mixed action del
giocatore i.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Evolutionary Dynamics (2)
 Per esempio un terzo della popolazione gioca la
strategia R e due terzi giocano la strategia L. Tutto ciò
può essere visto come una mixed action con
probabilità (1/3 , 2/3) sul’insieme di strategie (L , R).
 Le Evolutionary Dynamics si basano su due punti di
forza:
 Selection
 Mutation
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Evolutionary Dynamics (3)
 Selection: è il processo per il quale le strategie migliori
prevalgono;
 Mutation: è il processo che genera azioni in maniera
randomizzata (che siano esse buone o cattive).
 Possiamo vedere come questi due punti di forza sono
nettamente contrapposti, ma è proprio la
combinazione di entrambi che permette il naturale
adattamento (il “mutante” migliore sopravvive).
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Adaptive Heuristics (1)
 Abbiamo già detto che un’euristica è una regola
comportamentale semplice che il giocatore usa per
prendere le proprie decisioni.
 Chiameremo adaptive queste euristiche se inducono il
giocatore a comportarsi nel modo apparentemente
migliore rispetto a come si sta svolgendo il gioco.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Adaptive Heuristics (2)
 Per esempio fare sempre la stessa azione o
randomizzare le scelte sono heuristic, ma non sono
adaptive dato che non sappiamo se le decisioni prese
convergeranno ad una buona soluzione.
 Invece una buona adaptive heuristic è quella di giocare
ad ogni passo un’azione che risulta la migliore in base
alla distribuzione di frequenza delle azioni fatte in
passato dagli altri giocatori (fictitious play).
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Differenze tra le dinamiche (1)
 Un modo per capire le differenze tra le tre dinamiche
viste prima è tramite il concetto di Razionalità intesa
come un processo di ottimizzazione in un ambiente
interattivo.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Differenze tra le dinamiche (2)
 Learning Dynamics richiedono un alto livello di
razionalità infatti è molto difficile aggiornare ad ogni
passo il proprio comportamento e calcolare poi la best
response.
 Dall’altro lato invece nelle Evolutionary Dynamics il
livello di razionalità è praticamente nullo in quanto
ogni individuo fa sempre la stessa azione dettata dal
proprio genotype.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Differenze tra le dinamiche (3)
 Nel mezzo troviamo le Adaptive Heuristics che da un
lato fanno si che i giocatori eseguano dei semplici
calcoli in base all’ambiente del gioco (diversamente
dalle Evolutionary Dynamics) ma dall’latro lato
bisogna pur dire che questi calcoli sono molto distanti
dai calcoli altamente razionali fatti nei modelli
Learning Dynamics.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Definizione del problema (1)
 Insieme N di giocatori (i = 1 , 2 , …… , n).
 Ad ogni giocatore corrisponde un insieme di azioni Si
 Funzione di utilità ui: S  R
 S = (S1 x S2x … x S n) è l’insieme delle azioni.
 Dato che il gioco verrà ripetuto nel tempo indicheremo
con (sit) l’azione giocata dal giocatore i al tempo t.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Definizione del problema (2)
 Il concetto base è quello del perfect monitoring: alla
fine di ogni periodo t, tutti i giocatori osservano
l’insieme st in base al quale verrà scelta la successiva
azione.
 st = (s1t, s2t, ……. , snt) = azioni intraprese da tutti i
giocatori nel periodo t.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Regret Matching
 L’Adaptive Heuristic che prenderemo in considerazione
sarà il Regret Matching così definito:
Passaremo nella prossima fase di gioco ad una differente
azione con una probabilità proporzionale al regret, dove il
regret è definito come l’incremento di utilità ottenuto se
avessimo utilizzato quest’azione nel passato.
 Più formalmente . . . . .
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Definizione Formale (1)
 . . . consideriamo il giocatore i al tempo T+1 e denotiamo
con U la media dell’utilità ottenuta fino al tempo T:
 Consideriamo j = siT l’azione che il giocatore i ha giocato al
tempo T, e un’azione alternativa k = j.
Naturalmente sia j che k devono appartenere ad Si.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Definizione Formale (2)
 Calcoliamo adesso V(k) ossia la media di utilità che il
giocatore i avrebbe ottenuto sostituendo l’azione k al
posto di j ogni volta che i ha giocato j:
 Dove:
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Definizione Formale (3)
 Possiamo ora definire il regret per l’azione k:
 Dove [x]+ = max{x , 0} cioè la parte positiva di x.
 Cosa ce ne facciamo del parametro R(k)?
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Come usiamo R(k)
 Ogni azione k differente dall’azione j viene giocata con
una probabilità proporzionale al suo regret R(K),
mentre con la rimanente probabilità rigiochiamo j.
 Quindi la probabilità σT+1(k) di giocare l’azione k al
tempo T+1 è data da :
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Come calcoliamo la costante c
 c è una costante maggiore di zero che deve essere
minore di 1/(2mM) dove:
 m è il numero di azioni di i vale a dire m =|Si|.
 M è la massima utilità ottenibile da i quindi
M = maxs in S|ui(s)|
 Una tale c garantisce una corretta distribuzione di
probabilità sull’insieme Si e che la probabilità di j sia
strettamente positiva.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Torniamo al regret R(k)
 Adesso il giocatore i deve considerare se continuare ad
utilizzare j come prossima azione oppure cambiare ed
utilizzare k al posto di j.
 Praticamente il giocatore i non deve fare altro che
controllare il valore del regret R(k). Due casi possibili:
 R(k) = 0
 R(k) > 0
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Caso 1 : R(k) = 0
 Questo caso avviene quando l’utilità media che
avremmo ottenuto utilizzando k (V(k)) è minore o
uguale dell’utilità media ottenuta utilizzando j (U),
quindi non c’è regret per l’azione k.
 Per questo motivo il giocatore i non sarà portato a
cambiare azione dato che non avrà nessun incremento
di utilità.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Caso 2 : R(k) > 0
 Questo caso, invece, avviene quando l’utilità media che
avremmo ottenuto utilizzando k (V(k)) è maggiore
dell’utilità media ottenuta utilizzando j (U), quindi il
regret di k è maggiore di zero ed uguale proprio a
V(k) - U.
 A questo punto il giocatore i utilizzerà l’azione k al
posto di j in base alla distribuzione di probabilità
mostrata in precedenza.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Distribuzione Congiunta di gioco
 Misura la frequenza relativa di ogni n-upla di azioni
giocata. Ad ogni fase i giocatori randomizzano le
proprie scelte indipendentemente dagli altri giocatori.
 Ma questo non implica che la distribuzione congiunta
sia indipendente tra i giocatori o che essa potrebbe
diventare indipendente a lungo andare
 Questo accade perché le probabilità che i giocatori
usano possono cambiare andando avanti nel tempo.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio 1 (1)
 Supponiamo che nei periodi dispari i giocatori 1 e 2
utilizzino un distribuzioni di probabilità:
T
B
L
R
3/4
1/4
3/4
1/4
 E nei periodi pari ne utilizzino un’altra:
T
B
L
R
1/4
3/4
1/4
3/4
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio 1 (2)
 La distribuzione congiunta di gioco convergerà quasi
sicuramente a (5/16 , 3/16, 3/16, 5/16) per TL , TR , BL e
BR rispettivamente. Che non corrisponde al prodotto
delle probabilità marginali (1/2, 1/2) su (T , B) e (1/2,
1/2) su (L, R).
 La distribuzione congiunta è completamente
determinata dalla storia del gioco che i giocatori
osservano.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio 1 (3)
 Quindi i giocatori determinano le loro azioni
basandosi sulla distribuzione congiunta (invece che
sulla marginale) il che è quello che di solito avviene.
 Vediamo un esempio di tutto ciò rapportandolo ad un
gioco visto durante il corso:
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio 2 : Matching Pennies (1)
 Pensiamo al gioco del Matching Pennies
Matching Pennies
T
H
T
1 , -1
-1 , 1
H
-1 , 1
1 , -1
 Supponiamo che metà delle volte viene giocato HH e
l’altra metà TT. I giocatori se ne accorgeranno molto
rapidamente e almeno un giocatore cambierà il
proprio comportamento.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio 2 : Matching Pennies (2)
 Possiamo vedere che se il mismatching player avesse
guardato solo le distribuzioni marginali, in questo caso
(1/2 , 1/2) per entrambi i giocatori, non avrebbe avuto
ragione di cambiare azione.
 Ma il fatto che abbia cambiato azione ci porta a
pensare che il mismatching player abbia osservato la
distribuzione congiunta di gioco.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Per riassumere . . . .
. . . un modello di gioco che si rispetti può
(e dovrebbe) prendere in considerazione la
distribuzione congiunta di gioco.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Equilibri Correlati (1)
 È un equilibrio di Nash dove gli agenti fanno le proprie scelte in base ad
un segnale ricevuto prima che il gioco inizi.
 Consideriamo un gioco one-shot e assumiamo che prima di iniziare a
giocare ogni agente riceva un segnale θi.
 Questi segnali possono essere correlati a seconda di una distribuzione
di probabilità congiunta F conosciuta da tutti i giocatori.
Notiamo che i segnali non cambieranno le utilità dei giocatori.
 Può tutto ciò influenzare l’outcome?
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Equilibri correlati (2)
 La risposta è SI.
 Dato che i giocatori possono utilizzare questi segnali
per correlare le proprie scelte. E per dimostrarlo
utilizzeremo due esempi visti anche durante il corso:
 Battle of Sexes
 Chicken Game
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio: Battle of Sexes (1)
 Matrice dei payoff:
Battle of Sexes
Hockey
Theater
Hockey
2 ,1
0,0
Theater
0,0
1,2
 Introduciamo adesso un lancio della moneta per
determinare i segnali. Diciamo che Θ1 = Θ2, quindi il
segnale ricevuto dai due giocatori è lo stesso con
probabilità (1/2 , 1/2).
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio: Battle of Sexes (2)
 Di conseguenza la matrice degli equilibri correlati risulterà
la seguente:
Battle of Sexes
Hockey
Theater
Hockey
1/2
0
Theater
0
1/2
 Così facendo i giocatori decideranno la stessa cosa e le loro
utilità saranno sempre positive.
 In pratica abbiamo raggiunto un equilibrio di Nash che non
potevamo raggiungere prima.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio: Chicken Game (1)
 Matrice dei payoff:
Chicken Game
Leave
Stay
Leave
5 ,5
3,6
Stay
6, 3
0,0
 In questo tipo di gioco possiamo raggiungere un
equilibrio correlato che rende equiprobabili tutte le
combinazioni tranne (Stay , Stay).
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio: Chicken Game (2)
 La matrice degli equilibri correlati risulterà la seguente:
Chicken Game
Leave
Stay
Leave
1/3
1/3
Stay
1/3
0
 Possiamo vedere che quando il giocatore riga riceve il
segnale Leave, lo stesso giocatore assegnerà una probabilità
di (1/2 , 1/2) alle due combinazioni di segnali possibili
(Leave , Stay) o (Leave , Leave).
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Esempio: Chicken Game (3)
 Così che il giocatore riga avrà un payoff atteso uguale a 4 =
(1/2)5 + (1/2)3 dalla giocata Leave, mentre il payoff atteso
dalla giocata Stay sarà 3 = (1/2)6 + (1/2)0.
 Mentre quando il giocatore riga riceverà il segnale Stay,
potrà dedurre che la combinazione di segnali sarà
sicuramente (Stay , Leave) dato che (Stay , Stay) ha
probabilità zero).
 Anche in questo caso si è raggiunto un equilibrio di Nash.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Il nostro percorso







Breve introduzione
Classificazione dei modelli dinamici
Definizione del problema
Regret Matching
Distribuzione Congiunta di gioco
Equilibri Correlati
Teorema del Regret Matching
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Teorema del Regret Matching
 Lasciamo che ogni giocatore giochi in base alla teoria del
Regret Matching. In questo modo la distribuzione
congiunta di gioco convergerà all’insieme degli equilibri
correlati.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Distribuzione congiunta di gioco
 Per esempio la distribuzione congiunta per le prime T
fasi di gioco è una distribuzione di probabilità zT su S,
dove per ogni s in S,
 è la proporzione su T periodi nei quali la
combinazione di azioni s è stata giocata
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Teorema del Regret Matching
 Il Teorema del Regret Matching dice che, per quasi
tutte le storie di gioco, la sequenza di distribuzione
congiunta di gioco z1 , z2 , . . . . . zT , . . . . converge ad un
equilibrio correlato, 0, in modo equivalente possiamo
dire che essa è un equilibrio correlato approssimato.
 N.B.: converge verso l’insieme di equilibrio correlato
non necessariamente ad un punto nell’insieme.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Dimostrazione 
 Per dimostrare il teorema si dovrebbe mostrare:
 che tutti i regret svaniscono nel tempo;
 e che questa situazione di assenza di regret corrisponde
ad un equilibrio correlato approssimato.
Ma noi questo non lo vedremo!!!

Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
In definitiva . . . .
 . . . . Da dove viene fuori questa correlazione?
 La risposta è, di sicuro, dal fatto che i giocatori
osservano tutti la storia del gioco (come il gioco si è
svolto in quel momento). Infatti ogni azione dei
giocatori è determinata dal suo regret, che è
determinato esso stesso dalla storia.
Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Grazie a tutti per l’attenzione …
… alla “prossima”!!!