際際滷

際際滷Share a Scribd company logo

Marcello Mastroleo Introduzione Alla Teoria Dei Giochi

Download as PPT, PDF
Mario Esposito
Mario Esposito
1 of 38
Downloaded 40 times
Introduzione alla Teoria dei Giochi Marcello Mastroleo Homo Ludens 5属 incontro 18 Novembre 2009
La Teoria dei Giochi. La teoria dei giochi studia i giochi e le loro soluzioni . Un gioco 竪 una descrizione di una interazione strategica tra dei giocatori. La soluzione di un gioco 竪 una descrizione dei possibili esiti che possono emergere a partire da esso.
Giochi e giochi. Tutti i giochi noti (es. dama, scacchi, tris, morra cinese) sono analizzabili nella teoria dei giochi. Solitamente per嘆, qui con gioco si indica qualcosa di molto semplice che non ha interesse in quanto tale (es. dama), ma quando estrema astrazione di un fenomeno naturale o sociale. Vi sono varie famiglie di giochi e ognuna di esse ha caratteristiche proprie che determinano differenti tipi di soluzioni. In questottica, lobiettivo della Teoria dei Giochi 竪 quello di parlare di cose complicate con strumenti semplici.
Giochi e giochi. La prima differenza, che si nota, 竪 a livello procedurale (modo di giocare). Le principali tipologie sono: Giochi in forma strategica: sono dei giochi in cui tutti i giocatori agiscono simultaneamente e indipendentemente (es. Morra Cinese); Giochi in forma estesa: sono giochi in cui si alternano le mosse dei giocatori finch辿 non si raggiunge uno stato di fine (es. Scacchi), questi giochi possono essere visti come una sequenza di problemi decisionali. Alcuni giochi in forma estesa possono essere rappresentati come giochi in forma strategica.
Giochi e giochi. Una seconda differenza 竪 legata allo stato informativo che posseggono i giocatori, ovvero: Completa informazione Giochi a informazione perfetta (es. tris); Informazione parziale (incertezza) Giochi a informazione imperfetta (es. asta al secondo prezzo). I giochi in forma strategica a informazione imperfetta (es. ) sono noti come giochi Bayesiani.
Giochi e giochi. Unulteriore differenza 竪 rappresentata dal concetto di cooperazione: Ogni azione 竪 associata a uno e un solo giocatore Giochi competitivi; Esistono azioni congiunte tra i giocatori Giochi cooperativi.
Ma chi 竪 il giocatore? La Teoria dei Giochi trova le sue radici nella Teoria delle Decisioni, che generalizza. Il perno della Teoria delle decisioni (quindi della Teoria dei giochi) 竪 il decisore razionale. Giocatore Decisore Razionale Il decisore razionale 竪 colui che sceglie massimizzando una relazione di preferenza, che spesso si rappresenta con una funzione di utilit * . *il passaggio da una relazione di preferenza a una utilit pu嘆 generare paradossi.
Giochi in forma Strategica. Un Gioco in forma Strategia 竪 composto da: Un insieme finito di giocatori {1, 2, , N}; Per ogni giocatore i, un insieme non vuoto A i di azioni possibili; Per ogni giocatore i, una relazione di preferenza i tra i possibili profili del gioco. Un profilo e una qualunque N-upla di azioni (a 1 , a 2 , , a N ) in A 1 A 2 A N .
Esempio.
Esempio di gioco a somma nulla.
La strategia. Per strategia si intende ci嘆 che il giocatore far durante il gioco. Una strategia 竪 quindi composta, a seconda del gioco, da una o pi湛 azioni in sequenza. Si chiama strategia per sottolineare che 竪 frutto di un ragionamento strategico ovvero razionale (ricordate il decisore?).
La Dominanza. Lazione a i del giocatore A domina lazione a j se, indipendentemente da quello che fanno gli altri giocatori, A preferisce ci嘆 che otterrebbe giocando a i . U i (a i ,b k ) U i (a j ,b k ) Se ogni giocatore ha una azione che domina tutte le altre, la soluzione del gioco 竪 univocamente determinata.
Esempio di soluzione.
Cosa succede qui?
Il dilemma del prigioniero.
Simulazione 1 Ogni gruppo sceglie unazione (Confessa / Non Confessa) e si gioca al Dilemma del Prigioniero. Vince il gruppo che fa pi湛 punti (meno anni di carcere) su 20 partite secche.
Cosa 竪 emerso?
Simulazione 2 Ogni gruppo deve preparare un elenco di 20 azioni (Confessa / Non Confessa) da confrontarsi simultaneamente in maniera ordinata (li-esima azione del Gruppo 1 con li-esima del Gruppo 2). Vince il gruppo che fa pi湛 punti (meno anni di carcere) al Dilemma del Prigioniero.
Cosa 竪 cambiato?
stabile lottimo?
Equilibrio di Nash Un equilibrio di Nash 竪 un esito del gioco da cui nessun giocatore ha interesse a spostarsi. E* = (a 1 *, a 2 *, , a N *) 竪 un equilibrio di Nash se per ogni giocatore i risulta: U i (a i *,a -i *) U i (a i ,a -i *) per ogni a i diversa da a i *.
Cosa succede con Nash?
Il salto. Lequilibrio di Nash 竪 dato dalle strategie che minimizzano la massima perdita, piuttosto che il massimo utile. Ci si riferisce a tale propriet degli equilibri di Nash come principio del Max/Min.
Boxe vs Balletto.
Simulazione 3 Ogni gruppo deve preparare un elenco di 20 azioni (Boxe / Balletto) da confrontarsi simultaneamente in maniera ordinata (li-esima azione del Gruppo 1 con li-esima del Gruppo 2). Vince il gruppo che fa pi湛 punti al gioco Boxe vs Balletto.
Cos竪 cambiato qui?
La coordinazione Boxe vs Balletto 竪 il classico esempio di gioco in cui, sebbene i giocatori sono in competizione, c竪 interesse a collaborare in qualche modo. C竪 interesse a coordinarsi. La coordinazione presuppone comunicazione, ma nella teoria dei giochi competitivi 竪 bandita ogni forma di comunicazione. Come ci si pu嘆 coordinare senza comunicare?
Equilibrio Correlato. Gli elementi dellequilibrio correlato sono 2: Una distribuzione di probabilit P sugli esiti del gioco; Una persona di cui tutti i giocatori si fidano che: Seleziona, in accordo con P, un esito del gioco E; Invia a ogni giocatore i solo ed esclusivamente la strategia s i che determina lesito E. Si parla di equilibrio correlato se lutilit che ogni giocatore si aspetta giocando la strategia raccomandata dalla persona di fiducia 竪 maggiore a quella di deviare da essa.
Equilibrio Correlato.
Ma come si gioca a Morra Cinese? Il gioco della Morra Cinese la relazione di preferenza data dalla dominanza 竪 contraddittoria, in pi湛 non esiste un equilibrio di Nash. Con gli strumenti visti non 竪 possibile individuare un equilibrio, quindi risolvere il gioco. Bisogna generalizzare il concetto di strategia per carpire lessenza del gioco.
Mixed Strategies Un giocatore usa una mixed strategy se al posto di definire unazione, definisce una distribuzione di probabilit P tra le possibili azioni con la quale sceglier a caso lazione da fare. Esempio P(Sasso) = 0.2, P(Carta) = 0.5, P(Forbici) = 0.3
Equilibrio di Nash. Un equilibrio di Nash, nel caso delle mixed strategies, 竪 sempre una strategia dalla quale i singoli giocatori non anno interesse a deviare. Quello che cambia ora, 竪 che la strategia non 竪 pi湛 una azione ma, una distribuzione di probabilit.
Soluzione: P(Sasso)=P(Carta)=P(Forbici)=1/3
I giochi ripetuti. Fino ad ora abbiamo analizzato i giochi in forma strategica, in cui non vi 竪 dipendenza dal tempo. Molto pi湛 interessante 竪 il caso in cui lo stesso gioco istantaneo si ripete un certo numero di volte avendo la possibilit di osservare ci嘆 che succede (Come si 竪 fatto nella Simulaizone 2 del Dilemma del Prigioniero).
Giochi Ripetuti. Se si vede un gioco come una interazione tra 2 o pi湛 parti, un gioco ripetuto rappresenta una interazione nel tempo. Qui, non 竪 detto che lequilibrio istantaneo (lequilibrio sulla singola istanza) sia preservato per tutta la durata del gioco. In realt, la situazione 竪 un po pi湛 complessa.
Folk Theorems Se un gioco viene ripetuto, ogni payoff possibile pu嘆 essere un equilibrio, a patto che i giocatori siano sufficientemente pazienti. Questo dicono i Folk Theorems che sono stati chiamati cos狸 perch辿, prima di essere dimostrati, sono stati creduti veri per anni. Tutto 竪 un equilibrio!
Cos竪 quindi la reputazione? La reputazione 竪 legata alla fiducia, in Teoria dei Giochi, la fiducia 竪 associata alla razionalit dei giocatori. La reputazione 竪 quindi legata al fatto che non sia razionale per un giocatore deviare dallequilibrio dinamico. C竪 una buona reputazione quando il guadagno futuro che si otterrebbe cambiando strategia (tradendo) 竪 minore di quello generato dallequilibrio.
Come vi suona?

More Related Content

Marcello Mastroleo Introduzione Alla Teoria Dei Giochi

  • 1. Introduzione alla Teoria dei Giochi Marcello Mastroleo Homo Ludens 5属 incontro 18 Novembre 2009
  • 2. La Teoria dei Giochi. La teoria dei giochi studia i giochi e le loro soluzioni . Un gioco 竪 una descrizione di una interazione strategica tra dei giocatori. La soluzione di un gioco 竪 una descrizione dei possibili esiti che possono emergere a partire da esso.
  • 3. Giochi e giochi. Tutti i giochi noti (es. dama, scacchi, tris, morra cinese) sono analizzabili nella teoria dei giochi. Solitamente per嘆, qui con gioco si indica qualcosa di molto semplice che non ha interesse in quanto tale (es. dama), ma quando estrema astrazione di un fenomeno naturale o sociale. Vi sono varie famiglie di giochi e ognuna di esse ha caratteristiche proprie che determinano differenti tipi di soluzioni. In questottica, lobiettivo della Teoria dei Giochi 竪 quello di parlare di cose complicate con strumenti semplici.
  • 4. Giochi e giochi. La prima differenza, che si nota, 竪 a livello procedurale (modo di giocare). Le principali tipologie sono: Giochi in forma strategica: sono dei giochi in cui tutti i giocatori agiscono simultaneamente e indipendentemente (es. Morra Cinese); Giochi in forma estesa: sono giochi in cui si alternano le mosse dei giocatori finch辿 non si raggiunge uno stato di fine (es. Scacchi), questi giochi possono essere visti come una sequenza di problemi decisionali. Alcuni giochi in forma estesa possono essere rappresentati come giochi in forma strategica.
  • 5. Giochi e giochi. Una seconda differenza 竪 legata allo stato informativo che posseggono i giocatori, ovvero: Completa informazione Giochi a informazione perfetta (es. tris); Informazione parziale (incertezza) Giochi a informazione imperfetta (es. asta al secondo prezzo). I giochi in forma strategica a informazione imperfetta (es. ) sono noti come giochi Bayesiani.
  • 6. Giochi e giochi. Unulteriore differenza 竪 rappresentata dal concetto di cooperazione: Ogni azione 竪 associata a uno e un solo giocatore Giochi competitivi; Esistono azioni congiunte tra i giocatori Giochi cooperativi.
  • 7. Ma chi 竪 il giocatore? La Teoria dei Giochi trova le sue radici nella Teoria delle Decisioni, che generalizza. Il perno della Teoria delle decisioni (quindi della Teoria dei giochi) 竪 il decisore razionale. Giocatore Decisore Razionale Il decisore razionale 竪 colui che sceglie massimizzando una relazione di preferenza, che spesso si rappresenta con una funzione di utilit * . *il passaggio da una relazione di preferenza a una utilit pu嘆 generare paradossi.
  • 8. Giochi in forma Strategica. Un Gioco in forma Strategia 竪 composto da: Un insieme finito di giocatori {1, 2, , N}; Per ogni giocatore i, un insieme non vuoto A i di azioni possibili; Per ogni giocatore i, una relazione di preferenza i tra i possibili profili del gioco. Un profilo e una qualunque N-upla di azioni (a 1 , a 2 , , a N ) in A 1 A 2 A N .
  • 10. Esempio di gioco a somma nulla.
  • 11. La strategia. Per strategia si intende ci嘆 che il giocatore far durante il gioco. Una strategia 竪 quindi composta, a seconda del gioco, da una o pi湛 azioni in sequenza. Si chiama strategia per sottolineare che 竪 frutto di un ragionamento strategico ovvero razionale (ricordate il decisore?).
  • 12. La Dominanza. Lazione a i del giocatore A domina lazione a j se, indipendentemente da quello che fanno gli altri giocatori, A preferisce ci嘆 che otterrebbe giocando a i . U i (a i ,b k ) U i (a j ,b k ) Se ogni giocatore ha una azione che domina tutte le altre, la soluzione del gioco 竪 univocamente determinata.
  • 15. Il dilemma del prigioniero.
  • 16. Simulazione 1 Ogni gruppo sceglie unazione (Confessa / Non Confessa) e si gioca al Dilemma del Prigioniero. Vince il gruppo che fa pi湛 punti (meno anni di carcere) su 20 partite secche.
  • 18. Simulazione 2 Ogni gruppo deve preparare un elenco di 20 azioni (Confessa / Non Confessa) da confrontarsi simultaneamente in maniera ordinata (li-esima azione del Gruppo 1 con li-esima del Gruppo 2). Vince il gruppo che fa pi湛 punti (meno anni di carcere) al Dilemma del Prigioniero.
  • 21. Equilibrio di Nash Un equilibrio di Nash 竪 un esito del gioco da cui nessun giocatore ha interesse a spostarsi. E* = (a 1 *, a 2 *, , a N *) 竪 un equilibrio di Nash se per ogni giocatore i risulta: U i (a i *,a -i *) U i (a i ,a -i *) per ogni a i diversa da a i *.
  • 23. Il salto. Lequilibrio di Nash 竪 dato dalle strategie che minimizzano la massima perdita, piuttosto che il massimo utile. Ci si riferisce a tale propriet degli equilibri di Nash come principio del Max/Min.
  • 25. Simulazione 3 Ogni gruppo deve preparare un elenco di 20 azioni (Boxe / Balletto) da confrontarsi simultaneamente in maniera ordinata (li-esima azione del Gruppo 1 con li-esima del Gruppo 2). Vince il gruppo che fa pi湛 punti al gioco Boxe vs Balletto.
  • 27. La coordinazione Boxe vs Balletto 竪 il classico esempio di gioco in cui, sebbene i giocatori sono in competizione, c竪 interesse a collaborare in qualche modo. C竪 interesse a coordinarsi. La coordinazione presuppone comunicazione, ma nella teoria dei giochi competitivi 竪 bandita ogni forma di comunicazione. Come ci si pu嘆 coordinare senza comunicare?
  • 28. Equilibrio Correlato. Gli elementi dellequilibrio correlato sono 2: Una distribuzione di probabilit P sugli esiti del gioco; Una persona di cui tutti i giocatori si fidano che: Seleziona, in accordo con P, un esito del gioco E; Invia a ogni giocatore i solo ed esclusivamente la strategia s i che determina lesito E. Si parla di equilibrio correlato se lutilit che ogni giocatore si aspetta giocando la strategia raccomandata dalla persona di fiducia 竪 maggiore a quella di deviare da essa.
  • 30. Ma come si gioca a Morra Cinese? Il gioco della Morra Cinese la relazione di preferenza data dalla dominanza 竪 contraddittoria, in pi湛 non esiste un equilibrio di Nash. Con gli strumenti visti non 竪 possibile individuare un equilibrio, quindi risolvere il gioco. Bisogna generalizzare il concetto di strategia per carpire lessenza del gioco.
  • 31. Mixed Strategies Un giocatore usa una mixed strategy se al posto di definire unazione, definisce una distribuzione di probabilit P tra le possibili azioni con la quale sceglier a caso lazione da fare. Esempio P(Sasso) = 0.2, P(Carta) = 0.5, P(Forbici) = 0.3
  • 32. Equilibrio di Nash. Un equilibrio di Nash, nel caso delle mixed strategies, 竪 sempre una strategia dalla quale i singoli giocatori non anno interesse a deviare. Quello che cambia ora, 竪 che la strategia non 竪 pi湛 una azione ma, una distribuzione di probabilit.
  • 34. I giochi ripetuti. Fino ad ora abbiamo analizzato i giochi in forma strategica, in cui non vi 竪 dipendenza dal tempo. Molto pi湛 interessante 竪 il caso in cui lo stesso gioco istantaneo si ripete un certo numero di volte avendo la possibilit di osservare ci嘆 che succede (Come si 竪 fatto nella Simulaizone 2 del Dilemma del Prigioniero).
  • 35. Giochi Ripetuti. Se si vede un gioco come una interazione tra 2 o pi湛 parti, un gioco ripetuto rappresenta una interazione nel tempo. Qui, non 竪 detto che lequilibrio istantaneo (lequilibrio sulla singola istanza) sia preservato per tutta la durata del gioco. In realt, la situazione 竪 un po pi湛 complessa.
  • 36. Folk Theorems Se un gioco viene ripetuto, ogni payoff possibile pu嘆 essere un equilibrio, a patto che i giocatori siano sufficientemente pazienti. Questo dicono i Folk Theorems che sono stati chiamati cos狸 perch辿, prima di essere dimostrati, sono stati creduti veri per anni. Tutto 竪 un equilibrio!
  • 37. Cos竪 quindi la reputazione? La reputazione 竪 legata alla fiducia, in Teoria dei Giochi, la fiducia 竪 associata alla razionalit dei giocatori. La reputazione 竪 quindi legata al fatto che non sia razionale per un giocatore deviare dallequilibrio dinamico. C竪 una buona reputazione quando il guadagno futuro che si otterrebbe cambiando strategia (tradendo) 竪 minore di quello generato dallequilibrio.