Università degli Studi di Salerno - Università degli Studi di Salerno - Corso di Laurea...

Universit degli Studi di Salerno - 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 - Universit degli Studi di Salerno - Corso di Laurea Specialistica in Informatica

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Grazie a tutti per lattenzione alla prossima!!! Universit degli Studi di Salerno - Universit degli Studi di Salerno - Corso di Laurea Specialistica in Informatica

Università degli Studi di Salerno - Università degli Studi di Salerno - Corso di Laurea...

Documents

Transcript of Università degli Studi di Salerno - Università degli Studi di Salerno - Corso di Laurea...