GAME THEORY

STRUTTURA DELLE RETI SOCIALI A.A. 2014/15

Docente: Vincenzo Auletta

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 GAME THEORY

¢  La Network Science si occupa della connettività dei sistemi sociali, naturali e tecnologici �   Struttura dei collegamenti (teoria dei grafi) �   Interdipendenza tra i comportamenti dei singoli

componenti (teoria dei giochi)

¢  La Teoria dei Giochi fornisce modelli e strumenti matematici per descrivere il comportamento di agenti che devono prendere decisioni in situazioni in cui le loro azioni si influenzano vicendevolmente

¢  La Teoria dei Giochi è nata negli anni 30 e si è sviluppata negli anni 40-50 �   Sviluppata soprattutto in ambito economico �   Recentemente sta trovando applicazione in tantissimi

campi

1

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 PERCHÈ UTILIZZARE LA TEORIA DEI GIOCHI?

¢  La Teoria dei Giochi ci permette di modellare diverse situazioni �   Definire i prezzi di un nuovo prodotto �   Decidere quali relazioni sociali mantenere �   Scegliere il percorso da seguire in una rete di trasporto �   Decidere l’offerta da fare in un’asta �   Decidere se utilizzare sostanze dopanti

¢  Alcune idee della Teoria dei Giochi trovano applicazione anche in situazioni in cui non ci sono individui che prendono decisioni �   Es. Biologia evolutiva �   Quali comportamenti tendono a autosostenersi quando

utilizzati nell’ambito di una popolazione più numerosa? v  Ne parleremo nelle prossime lezioni

2

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 IPOTESI OPERATIVE

La Teoria dei Giochi assume che i giocatori sono egoisti e razionali e ragionano strategicamente

¢  gli agenti sono egoisti �   Ogni agente ha il proprio obiettivo e cerca di

raggiungerlo

¢  Gli agenti sono razionali �   Sono in grado di discernere cosa e meglio per loro

¢  Gli agenti ragionano strategicamente �   tengono conto della loro conoscenza o aspettativa sul

comportamento degli altri agenti

3

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 COS’È UN GIOCO?

¢  Un gioco è una situazione in cui �   Singoli giocatori devono prendere decisioni �   Il payoff ottenuto da un giocatore dipende anche dalle decisioni

degli altri giocatori

¢  Molti degli esempi utilizzati sono effettivamente dei giochi ... �   Tick-tack-toe, scacchi, morra cinese, penalty game

¢   ... Ma il modello si applica a contesti molto più ampi

¢  Un gioco è costituito da �   insieme dei giocatori �   insieme delle alternative tra cui può scegliere ciascun giocatore �   Una funzione che fornisce il payoff ricevuto da ciascun giocatore

in base alle scelte di tutti i giocatori

4

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 CLASSIFICAZIONE DEI GIOCHI

In questo corso distingueremo i giochi rispetto a tre criteri ¢   cooperazione

�   non-cooperative games: ogni agente decide senza interagire con gli altri giocatori �   cooperative games: gli agenti cooperano per decidere il loro comportamento per

massimizzare l’utilita globale

¢   informazione �   perfect (full) information games: gli agenti hanno una conoscenza completa del

gioco v   conoscono le mosse degli altri, sanno che anche gli altri le conoscono e sanno che gli altri

sanno di sapere e così via

�   imperfect (partial) information games: i giocatori hanno una conoscenza parziale del gioco

¢   tempo �   strategic (normal) games: i giocatori decidono la strategia prima di iniziare a

giocare e non la possono più modificare v   La strategia puo consistere di varie mosse

�   extensive games: gioco in fasi, dove ad ogni fase un giocatore decide in base alla sua conoscenza dello stato attuale del gioco e alla storia passata

5

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 UN GIOCO IN FORMA STRATEGICA

¢  Un gioco in forma strategica è una tripla (N, (Ai)i, (ui)i) �   N = insieme dei giocatori �   Ai = insieme delle alternative tra cui può scegliere il

giocatore i �   ui è la funzione che fornisce il payoff ricevuto dal

giocatore in base alle scelte di tutti i giocatori

¢  I profili del gioco sono l’insieme delle scelte che possono fare i giocatori

¢  Una soluzione è un profilo del gioco �   La soluzione definisce il payoff di ogni giocatore

6

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 UN ESEMPIO

¢  Alice e Bob devono preparare un esame ed una presentazione (comune) �   Entrambi vogliono massimizzare il proprio punteggio

complessivo �   Entrambi hanno tempo per lavorare solo su una delle due

attività e non possono coordinarsi ¢  Esame

�   Se lo studente fa l’ultima ripetizione può prendere 28, altrimenti prende 20

¢  Presentazione �   Se entrambi gli studenti lavorano sulla presentazione prendono

entrambi 28 �   Se solo uno studente lavora sulla presentazione prendono

entrambi 24 �   Se nessuno dei due lavora alla presentazione prendono entrambi

22

¢  Cosa deve scegliere ciascuno studente?

7

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 FORMALIZZAZIONE DEL GIOCO

¢  Due giocatori �   Alice e Bob

¢  Ogni giocatore ha due alternative �   Esame, Presentazione

8

25, 25 26, 22

22, 26 24, 24

Esame

Present

Esame Present

Se il collega lavora alla presentazione conviene studiare l’esame

Cosa deciderà il collega?

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 COME SI DEVONO COMPORTARE I GIOCATORI?

¢  Analizziamo il comportamento dei due studenti ¢  Ogni studente ha una strictly dominant strategy

�   Indipendentemente da cosa fa il collega gli conviene studiare per l’esame

¢  È possibile prevedere l’esito del gioco �   Ogni giocatore otterrà una media di 25

¢  Ogni giocatore potrebbe ottenere di più a discapito del collega �   Non è un comportamento razionale

9

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 IL DILEMMA DEL PRIGIONIERO

¢  Due persone sospettate per un reato grave sono fermate per un reato minore

¢  Ogni sospetto è interrogato separatamente �   Se nessuno dei due confessa vengono condannati ad 1 anno

ciascuno �   Se entrambi confessano prendono 4 anni a testa �   Se uno solo confessa, lui viene liberato e l’altro prende 10

anni

10

-4, -4 0, -10

-10, 0 -1, -1

C

NC

C NC ¢  A ciascun sospetto conviene confessare �   Strategia dominante �   Ad ogni giocatore converrebbe

non confessare ma non è razionale

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 BEST RESPONSE

¢  Un giocatore razionale sceglie la migliore alternativa possibile sulla base della sua convinzione su cosa faranno gli altri giocatori

¢  Formalizziamo

�   il giocatore 1 sceglie la strategia S �   Il giocatore 2 sceglie la strategia T �   Payoff per il giocatore i è Pi(S,T)

¢  Def: S è una best response rispetto a T se P1(S,T) ≥ P1(S’,T) per tutte le altre strategie S‘ del giocatore 1. �   S è una strict best response se P1(S,T) > P1(S‘,T)

11

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 DOMINANT STRATEGY

¢  Def: Una dominant strategy è una strategia che è best response rispetto a tutte le strategie dell’altro giocatore �   Analogamente per strictly dominant strategy.

¢  Nel Dilemma del Prigioniero entrambi i giocatori hanno una strictly dominant strategy �   Possiamo facilmente prevedere l’esito del gioco

¢  Non tutti i giochi hanno dominant strategies

¢  Cosa possiamo dire sui giochi che non hanno dominant strategies per tutti i giocatori?

12

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 MARKETING GAME

�   Due aziende stanno valutando se lanciare un nuovo prodotto sul mercato

�   Il mercato è formato da v  60% di persone interessate a prodotti a basso costo v  40% di persone interessate a prodotti di alto livello

�   Se le aziende competono per lo stesso settore di mercato v  L’azienda R ottiene l’80% delle vendite

�   Altrimenti ognuno ottiene tutte le vendite del suo segmento

13

.48, .12 .60, .40

.40, .60 .32, .08

low

high

low high ¢  Per l’azienda R low è una

dominant strategy ¢  All’azienda C conviene

prendere atto della scelta di R e scegliere high

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 GIOCHI SENZA DOMINANT STRATEGIES

¢  Cosa possiamo dire sul gioco se nessun giocatore ha una dominant strategy? �   Come dovremmo ragionare per questi giochi? �   Sappiamo per certo che ogni giocatore utilizzerà una

strategia che è una best response a quella degli avversari v  non è in grado di prevedere con certezza cosa giocheranno gli altri v  ma può immedesimarsi e ragionare strategicamente

14

A

A B C

B

C

4, 4 0, 2 0, 2

0, 0 1, 1 0, 2

0, 0 0, 2 1, 1

¢   Ad R conviene giocare �   A se C gioca A �   B se C gioca B �   C se C gioca C

¢   A C conviene giocare �   A se R gioca A �   B se R gioca C �   C se R gioca B

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 EQUILIBRIO NASH

¢  Un Equilibrio Nash è un profilo di strategie in cui ogni giocatore sta giocando una best response alle strategie degli avversari �   ad ogni giocatore non conviene cambiare la sua scelta

se gli altri non cambiano

¢  John Nash (1952) ha dimostrato che ogni gioco finito ha almeno un Equilibrio Nash

¢  Ogni giocatore può immedesimarsi nell’avversario e immaginare come reagirebbe alle proprie mosse e ragionare di conseguenza

15

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 EQUILIBRI NASH

¢  (A, A) è un Equilibrio Nash �   Se R gioca A a C conviene giocare A �   Se C gioca A a R conviene giocare A

¢  È l’unico Equilibrio Nash

16

A

A B C

B

C

4, 4 0, 2 0, 2

0, 0 1, 1 0, 2

0, 0 0, 2 1, 1

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 COORDINATION GAMES

¢  I due giocatori preferiscono coordinarsi e fare la stessa scelta piuttosto che fare scelte differenti

¢  Quali sono gli Equilibri Nash di questo gioco? �   (A, A) e (B, B) �   Quali scelte faranno i giocatori?

17

1, 1 0, 0

0, 0 1, 1

A

B

A B

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 BATTLE OF SEX

¢   Un ragazzo ed una ragazza devono decidere cosa fare per la serata �   Possono scegliere tra una partita di basket e fare shopping �   La ragazza preferisce lo shopping, il ragazzo il basket �   Entrambi preferiscono stare insieme

¢   Quali sono gli Equilibri Nash di questo gioco? �   (B, B) e (S, S)

¢   E’ possibile prevedere l’esito del gioco? �   Le convenzioni sociali possono farci preferire un equilibrio all’altro �   Es. Per cavalleria il ragazzo accetta di far scegliere alla ragazza

18

1, 2 0, 0

0, 0 2, 1

B

S

B S

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 STAG HUNT

¢  Caccia al cervo �   Se due cacciatori collaborano possono catturare un cervo �   Ognuno da solo può catturare soltanto una lepre

¢  Quali sono gli Equilibri Nash di questo gioco? �   (Cervo, Cervo) e (Lepre, Lepre)

¢  Un equilibrio è più rischioso dell’altro �   Se caccio il cervo e il mio collega non mi segue non becco nulla �   Se caccio la lepre ho un payoff assicurato

19

4, 4 0, 3

3, 0 3, 3

Cervo

Lepre

Cervo Lepre

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 FALCO O COLOMBA

¢   Falco o colomba (o Chicken game) �   Due animali devono dividersi una preda �   Ogni animale può decidere se essere aggressivo (falco) o remissivo (colomba) �   Se entrambi sono remissivi si dividono la preda �   Se uno è aggressivo e l’latro remissivo, l’aggressivo prende quasi tutto �   Se entrambi sono aggressivi si distruggono a vicenda

¢   Quali sono gli Equilibri Nash di questo gioco? �   (Falco, Colomba) e (Colomba, Falco)

¢   Può servire a modellare i rapporti tra le persone o le relazioni politiche

20

3, 3 1, 5

5, 1 0, 0

Colomba

Falco

Colomba Falco

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 MATCHING PENNIES

¢  Matching Pennies �   Ogni giocatore mette una moneta sul tavolo �   Il giocatore R vince se le due monete hanno la stessa faccia �   Il giocatore C vince se le due monete hanno facce diverse

¢  Esempio di gioco a somma zero �   La somma dei payoff è 0 �   Se un giocatore vince, l’altro perde

¢  Il gioco non ha Equilibri Nash �   Come giochereste questo gioco?

21

1, -1 -1, 1

-1, 1 1, -1

Testa

Croce

Testa Croce

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 STRATEGIE MISTE

¢  Una strategia mista è una distribuzione di probabilità (lotteria) sulle azioni possibili �   Invece di scegliere un’azione (strategia pura) scegliamo di

utilizzare una particolare lotteria per scegliere l’azione da eseguire

¢  Per il gioco del Matching Pennies �   Il giocatore R sceglie di giocare Testa con probabilità p �   Il giocatore C sceglie di giocare Testa con probabilità q

¢  Come si calcolano i payoff? �   Valore atteso su tutte le possibili combinazioni di strategie

pure giocate dai giocatori

22

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 CALCOLO DEI PAYOFF

¢  Il giocatore R valuta le sue strategie pure assumendo che il giocatore C gioca la strategia mista (q, 1-q) �   Se sceglie Testa, il payoff atteso è q + (1-q)(-1) = 2q-1 �   Se sceglie Croce, il payoff atteso è (-1)q + (1-q) = 1-2q

¢  Qual è la sua best move? �   Dipende da q �   Se q < ½ gli conviene giocare Croce �   Se q > ½ gli conviene giocare Testa �   Se q = ½ le due strategie pure sono equivalenti

v  Possiamo randomizzare tra le due

23

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 CALCOLO DEI PAYOFF

¢  Il giocatore C valuta le sue strategie miste sapendo il suo avversario risponderà giocando la sua best move �   Se sceglie q < ½ il suo avversario giocherà Croce

v  Il suo payoff atteso è 2q-1 < 0

�   Se sceglie q > ½ il suo avversario giocherà Testa v  Il suo payoff atteso è 1-2q < 0

�   Se sceglie q = ½ il suo avversario dovrà scegliere tra due alternative equivalenti v  Se l’avversario gioca (p, 1-p) il suo payoff atteso è 1/2 (-p + (1-p) + p - (1-p)) = 0

¢  Qualunque scelta di q ≠ ½ non è razionale

24

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 STRATEGIE MISTE IN EQUILIBRIO NASH

¢  Due strategie miste sono in Equilibrio Nash se ognuna è una best move rispetto all’altra �   L’avversario non ha nessun incentivo a cambiare la sua strategia

¢  Nash ha dimostrato che ogni gioco finito ha almeno un Equilibrio Nash con strategie miste

¢  Nel Matching Pennies non esiste nessun Nash Equilibrium che utilizza strategie pure �   In ogni profilo c’è un giocatore che è incentivato a cambiare

strategia

¢   (½, ½) è un Equilibrio Nash �   Ogni giocatore ha un payoff atteso = 0 e non ci sono alternative

che garantiscono un payoff migliore

25

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 INTERPRETAZIONI DI EQUILIBRI NASH

¢  Una strategia mista viene utilizzata per rendere più difficile all’avversario prevedere come si giocherà �   scegliendo q=1/2, il giocatore C rende le due strategie

dell’avversario indifferenti

¢  Possibili intepretazioni di Equilibri Nash con strategie miste �   Negli sport o nei giochi

v   I giocatori randomizzano le loro azioni per renderle meno prevedibili �   La competizione per il cibo tra varie specie

v   Gli individui sono predisposti per giocare certe strategie e non possono cambiarle

v   In una popolazione ci sono individui diversi v   Strategie miste definiscono le proporzioni tra i diversi tipi all’interno di

una popolazione v   La popolazione nel suo complesso è un equilibrio misto

�   Un Equilibrio Nash è un equilibrio tra convinzioni v   Se un giocatore pensa che l’avversario giocherà una strategia in

Equilibrio Nash allora gli conviene giocare una strategia in Equilibrio Nash

26

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 CALCI DI RIGORE

¢   La squadra riga attacca, la squadra colonna difende �   Gli attaccanti devono decidere se fare un azione di corsa o lanciare

v   I difensori devono decidere su quale tipo di attacco predisporre la difesa

¢   La difesa decide di difendere sulla corsa con probabilità q �   Per l’attaccante le due alternative sono equivalenti se 5(1-q) = 10q �   q =1/3

¢   L’attacco decide di correte con probabilità p �   Per il difensore le due alternative sono equivalenti se -10(1-p) = -5p �   p=2/3

¢   (1/3, 2/3) è un Equilibrio Nash misto

27

0, 0 Run

Pass

Run Pass

5, -5

10, -10 0, 0

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 FOOTBALL AMERICANO

¢   Il giocatore riga tira il rigore ed il giocatore colonna para �   Il portiere si butta a sinistra con probabilità q �   Per l’attaccante le due alternative sono equivalenti se (0.58)(q) + (0.95) (1-q) = (0.93)(q) + (0.70) (1-q) q =0.42 �   Analogamente, possiamo calcolare la probabilità dell’attaccante

di calciare a simistra p=0.39

¢   (0,39, 0,42) è un Equilibrio Nash misto �   Dati reali molto vicini a quelli previsti dalla teoria

28

0,58, -0,58 Destra

Sinistra

Destra Sinistra

0,95, -0,95

0,93, -0,93 0,70, -0,70

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 PARETO OTTIMALITÀ

¢  Anche se i giocatori giocano le loro best move non sempre la soluzione prodotta è l’esito migliore come gruppo �   Es. Il Dilemma del Prigioniero

¢  Vogliamo definire un outcome che sia socialmente buono

¢  Un profilo di strategie è Pareto Ottimale se non esiste un altro profilo tale che: �   Ogni giocatore ottiene almeno lo stesso payoff �   C’è almeno un giocatore che ottiene un payoff strettamente

maggiore

29

Stru

ttura

delle R

eti So

ciali – P

rima

vera

2015 OTTIMALITÀ SOCIALE

¢  Un profilo di strategie è socialmente ottimo se massimizza la somma dei payoff dei giocatori ¢   massimizzatore del social welfare

30

25, 25 26, 22

22, 26 24, 24

Esame

Present

Esame Present

¢   In questo gioco l’unico Equilibrio Nash è anche socialmente ottimo