Strumenti e Teoria dei Giochi: Adaptive Heuristics Studente: Armidoro Davide Docenti: Vincenzo Auletta Francesco Pasquale Paolo Penna Università degli Studi di Salerno - Corso di Laurea Specialistica in Informatica
Transcript
Slide 1
Universit degli Studi di Salerno - Universit degli Studi di
Salerno - Corso di Laurea Specialistica in Informatica
Slide 2
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 3
Breve Introduzione (1) Una configurazione dinamica
rappresentata da uninsieme 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 - Universit degli Studi di Salerno
- Corso di Laurea Specialistica in Informatica
Slide 4
Breve Introduzione (2) Universit degli Studi di Salerno -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica Una semplice Adaptive heuristics potrebbe essere quella
di scegliere sempre la best response in base a ci che hanno fatto i
giocatori nellimmediato 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.
Slide 5
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 - Universit
degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 6
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 7
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 - Universit degli Studi di Salerno
- Corso di Laurea Specialistica in Informatica
Slide 8
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 allinterno del gioco, ogni giocatore
aggiorna la propria opinione e gioca la sua best respons. Universit
degli Studi di Salerno - Universit degli Studi di Salerno - Corso
di Laurea Specialistica in Informatica
Slide 9
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 10
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) sulinsieme di strategie (L, R). Le Evolutionary Dynamics
si basano su due punti di forza: Selection Mutation Universit degli
Studi di Salerno - Universit degli Studi di Salerno - Corso di
Laurea Specialistica in Informatica
Slide 11
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 - Universit degli Studi di Salerno - Corso
di Laurea Specialistica in Informatica
Slide 12
Adaptive Heuristics (1) Abbiamo gi detto che uneuristica 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 - Universit degli Studi di Salerno - Corso di
Laurea Specialistica in Informatica
Slide 13
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 unazione 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
- Universit degli Studi di Salerno - Corso di Laurea Specialistica
in Informatica
Slide 14
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 15
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. Dallaltro 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 - Universit degli Studi di Salerno - Corso
di Laurea Specialistica in Informatica
Slide 16
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 allambiente del gioco (diversamente dalle
Evolutionary Dynamics) ma dalllatro lato bisogna pur dire che
questi calcoli sono molto distanti dai calcoli altamente razionali
fatti nei modelli Learning Dynamics. Universit degli Studi di
Salerno - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica
Slide 17
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 18
Definizione del problema (1) Insieme N di giocatori (i = 1, 2,
, n). Ad ogni giocatore corrisponde un insieme di azioni S i
Funzione di utilit u i : S R S = (S 1 x S 2 x x S n ) linsieme
delle azioni. Dato che il gioco verr ripetuto nel tempo indicheremo
con (s i t ) lazione giocata dal giocatore i al tempo t. Universit
degli Studi di Salerno - Universit degli Studi di Salerno - Corso
di Laurea Specialistica in Informatica
Slide 19
Definizione del problema (2) Il concetto base quello del
perfect monitoring: alla fine di ogni periodo t, tutti i giocatori
osservano linsieme s t in base al quale verr scelta la successiva
azione. s t = (s 1 t, s 2 t, ., s n t ) = azioni intraprese da
tutti i giocatori nel periodo t. Universit degli Studi di Salerno -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 20
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 21
Regret Matching LAdaptive 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 lincremento
di utilit ottenuto se avessimo utilizzato questazione nel passato.
Pi formalmente..... Universit degli Studi di Salerno - Universit
degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 22
Definizione Formale (1)... consideriamo il giocatore i al tempo
T+1 e denotiamo con U la media dellutilit ottenuta fino al tempo T:
Consideriamo j = s i T lazione che il giocatore i ha giocato al
tempo T, e unazione alternativa k = j. Naturalmente sia j che k
devono appartenere ad S i. Universit degli Studi di Salerno -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 23
Definizione Formale (2) Calcoliamo adesso V(k) ossia la media
di utilit che il giocatore i avrebbe ottenuto sostituendo lazione k
al posto di j ogni volta che i ha giocato j: Dove: Universit degli
Studi di Salerno - Universit degli Studi di Salerno - Corso di
Laurea Specialistica in Informatica
Slide 24
Definizione Formale (3) Possiamo ora definire il regret per
lazione 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
- Universit degli Studi di Salerno - Corso di Laurea Specialistica
in Informatica
Slide 25
Come usiamo R(k) Ogni azione k differente dallazione 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 lazione k al tempo T+1 data da : Universit degli
Studi di Salerno - Universit degli Studi di Salerno - Corso di
Laurea Specialistica in Informatica
Slide 26
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 =|S i |. M la massima utilit ottenibile da i quindi M
= max s in S |u i (s)| Una tale c garantisce una corretta
distribuzione di probabilit sullinsieme S i e che la probabilit di
j sia strettamente positiva. Universit degli Studi di Salerno -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 27
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 -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 28
Caso 1 : R(k) = 0 Questo caso avviene quando lutilit media che
avremmo ottenuto utilizzando k (V(k)) minore o uguale dellutilit
media ottenuta utilizzando j (U), quindi non c regret per lazione
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 - Universit degli Studi di Salerno - Corso
di Laurea Specialistica in Informatica
Slide 29
Caso 2 : R(k) > 0 Questo caso, invece, avviene quando
lutilit media che avremmo ottenuto utilizzando k (V(k)) maggiore
dellutilit 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 lazione k al posto di j in base alla
distribuzione di probabilit mostrata in precedenza. Universit degli
Studi di Salerno - Universit degli Studi di Salerno - Corso di
Laurea Specialistica in Informatica
Slide 30
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 31
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 - Universit degli Studi di Salerno
- Corso di Laurea Specialistica in Informatica
Slide 32
Esempio 1 (1) Supponiamo che nei periodi dispari i giocatori 1
e 2 utilizzino un distribuzioni di probabilit: E nei periodi pari
ne utilizzino unaltra: Universit degli Studi di Salerno - Universit
degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica TB 3/41/4 LR 3/41/4 TB 3/4 LR 1/43/4
Slide 33
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 -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 34
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 - Universit degli Studi di Salerno
- Corso di Laurea Specialistica in Informatica
Slide 35
Esempio 2 : Matching Pennies (1) Universit degli Studi di
Salerno - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica Pensiamo al gioco del Matching Pennies
Supponiamo che met delle volte viene giocato HH e laltra met TT. I
giocatori se ne accorgeranno molto rapidamente e almeno un
giocatore cambier il proprio comportamento. Matching PenniesTH T1,
-1-1, 1 H 1, -1
Slide 36
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 - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica
Slide 37
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 - Universit degli Studi di
Salerno - Corso di Laurea Specialistica in Informatica
Slide 38
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 39
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 loutcome? Universit degli Studi di Salerno - Universit
degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 40
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 - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica
Slide 41
Esempio: Battle of Sexes (1) Universit degli Studi di Salerno -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica Matrice dei payoff: 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). Battle of SexesHockeyTheater Hockey2,10, 0 Theater0, 01,
2
Slide 42
Esempio: Battle of Sexes (2) Di conseguenza la matrice degli
equilibri correlati risulter la seguente: 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 -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica Battle of SexesHockeyTheater Hockey1/20
Theater01/2
Slide 43
Esempio: Chicken Game (1) Matrice dei payoff: In questo tipo di
gioco possiamo raggiungere un equilibrio correlato che rende
equiprobabili tutte le combinazioni tranne (Stay, Stay). Universit
degli Studi di Salerno - Universit degli Studi di Salerno - Corso
di Laurea Specialistica in Informatica Chicken GameLeaveStay
Leave5,53, 6 Stay6, 30, 0
Slide 44
Esempio: Chicken Game (2) La matrice degli equilibri correlati
risulter la seguente: 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 -
Universit degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica Chicken GameLeaveStay Leave1/3 Stay1/30
Slide 45
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 - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica
Slide 46
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 - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 47
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 allinsieme degli
equilibri correlati. Universit degli Studi di Salerno - Universit
degli Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 48
Distribuzione congiunta di gioco Per esempio la distribuzione
congiunta per le prime T fasi di gioco una distribuzione di
probabilit z T 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 - Universit degli Studi di Salerno
- Corso di Laurea Specialistica in Informatica
Slide 49
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 z 1, z 2,..... z T,.... converge
ad un equilibrio correlato, 0, in modo equivalente possiamo dire
che essa un equilibrio correlato approssimato. N.B.: converge verso
linsieme di equilibrio correlato non necessariamente ad un punto
nellinsieme. Universit degli Studi di Salerno - Universit degli
Studi di Salerno - Corso di Laurea Specialistica in
Informatica
Slide 50
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 - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica
Slide 51
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 - Universit degli Studi di Salerno - Corso di Laurea
Specialistica in Informatica
Slide 52
Grazie a tutti per lattenzione alla prossima!!! Universit degli
Studi di Salerno - Universit degli Studi di Salerno - Corso di
Laurea Specialistica in Informatica