Negli articoli precedenti abbiamo introdotto la teoria dei giochi (https://orbyta.it/teoria-dei-giochi/) e la teoria dei grafi (https://orbyta.it/teoria-dei-grafi/) e abbiamo visto come quest’ultima possa essere usata per risolvere giochi dall’equilibrio controintuitivo.

In questo articolo approfondiremo le reti andando a studiare i giochi dinamici e situazioni più complesse che ci permetteranno di analizzare la propagazione delle strategie all’interno di un network.

Giochi dinamici

Consideriamo i giochi in cui l’interazione tra i giocatori è intrinsecamente dinamica, cioè in cui i giocatori sono in grado di osservare le azioni degli altri giocatori prima di scegliere la loro miglior risposta [6].

Questo genere di giochi rientra nella categoria dei cosiddetti giochi dinamici insieme a quelli detti sequenziali nei quali i partecipanti prendono decisioni osservando a turno l’azione dell’avversario e stabilendo di conseguenza l’azione ottimale da adottare.

Si noti che l’attenzione non è posta all’alternanza sequenziale dei turni, bensì al fatto che i giocatori effettuano la loro scelta dopo che altri giocatori hanno già mosso, come nel gioco della briscola dove l’alternanza dei turni è stabilita di volta in volta in funzione di chi si è aggiudicato la mano precedente.

Si intuisce che la caratteristica principale di questi giochi è il fatto che le azioni di un giocatore possano influenzare le azioni ottimali degli altri, e questo incrementa il numero delle loro possibili strategie che adesso non coincidono più con le possibili azioni, infatti, a queste vanno aggiunte le cosiddette strategie condizionali.

È importante che i giocatori successivi abbiano informazioni sulle scelte precedentemente effettuate dagli altri giocatori, altrimenti la differenza di tempo non avrebbe alcun effetto strategico.

Esempio dinamico delle aziende

Finora abbiamo lavorato con quella che è chiamata forma normale di rappresentazione di un gioco in cui si specifica un insieme di giocatori e per ognuno di essi un insieme di strategie con i relativi payoff. Per descrivere un gioco dinamico necessitiamo, per esempio, di esplicitare quando e come i vari giocatori possono muovere.

Utilizziamo a tale scopo la cosiddetta forma estesa (o ad albero) della rappresentazione del gioco.

Immaginiamo che ci siano due aziende, P1 e P2, ognuna delle quali sta cercando di decidere in quale, tra due regioni A e B disponibili, focalizzare la propria pubblicità. P1 può decidere prima e supponiamo che:

• Se P2 scegliesse di seguire P1 nella stessa regione allora P1 otterrebbe i 2/3 del profitto ricavabile da tale regione, mentre P2 solo il rimanente terzo;
• Se P2 scegliesse l’altra regione allora entrambe le aziende otterrebbero il massimo ricavabile dalle zone.

Si assuma però che A abbia un potenziale di guadagno di 12 mentre B di 6. Rappresentiamo tale gioco col seguente diagramma ad albero da leggere dall’alto verso il basso.

Il nodo superiore rappresenta la mossa iniziale di P1 che può essere o A o B, da cui i due rami. I nodi sul secondo livello rappresentano le scelte di P2 che sono a loro volta A e B. I nodi inferiori coincidono con le possibili conclusioni del gioco e sotto di essi vengono riportati i rispettivi payoff di P1 e P2.

Notiamo che, una volta che P1 ha fatto la prima mossa, il comportamento di P2 è facilmente prevedibile:

• Se P1 avesse scelto A, a P2 converrebbe scegliere B (questo perchè P2 compara gli output 4 e 6);
• Se P1 avesse scelto B, P2 avrebbe dovuto scegliere A.

Ora cerchiamo di prevedere la mossa iniziale di P1.

• Se P1 scegliesse A allora ci si aspetterebbe che P2 scelga B e quindi un guadagno di 12;
• Se P1 scegliesse B, P2 sceglierebbe A e otterrebbe un guadagno di 6.

Concludiamo perciò che P1 sceglierà A e P2 B.

Generalizziamo ora la metodologia di risoluzione appena usata. Tale risoluzione, utile allo studio dei giochi dinamici, consiste nei seguenti passaggi:

• Costruito l’albero iniziamo a considerare i penultimi nodi partendo dall’alto (backward induction). In essi il giocatore che muove ha diretto controllo sul risultato delle vincite. Questo ci permette di prevedere ciò che l’ultimo giocatore farà in tutti i casi;
• Ci si sposta al livello superiore e, ragionando nello stesso modo, cerchiamo di capire cosa farà il giocatore nella mossa precedente;
• Itero il processo fino ad arrivare a stabilire il comportamento del primo giocatore.

Può sembrare strano, ma il precedente risultato implica che teoricamente il vincitore di un incontro di scacchi (o un eventuale esito di parità) sia noto a priori. Siccome un tale albero ha un numero di nodi al di là di ogni possibile rappresentazione e computazione, la procedura ricorsiva delineata non è fattibile e quindi il gioco degli scacchi continua a mantenere il suo interesse.

In alcuni casi, come in questo esempio, possiamo descrivere il gioco dinamico tramite una forma normale di rappresentazione. Purtroppo, il voler convertire una rappresentazione di tipo esteso in una di tipo normale a volte provoca la perdita di alcune informazioni e non permette, dunque, di preservare la struttura del gioco.

In generale, possiamo assumere che la forma normale sia più usata nel caso di giochi a mosse simultanee, mentre quella estesa sia spesso più opportuna nella descrizione di giochi sequenziali [15].

In riferimento all’esempio, per la conversione ragioniamo come segue.

Supponiamo che, prima che la partita inizi, ogni giocatore faccia un piano per capire quali mosse effettuare considerando ogni possibile evenienza. Tutte le possibili modalità di gioco sono (indicando con XY il fatto che P2 sceglierà X se P1 sceglie Y) (AA, AB), (AA, BB), (BA, AB) e (BA, BB).

A questo punto possiamo calcolare le vincite risultanti dalle varie combinazioni di strategie e otteniamo il seguente schema:

Notiamo che per P1 A è la strategia strettamente dominante, mentre P2 non ha una strategia del genere ma le sue migliori risposte sono (BA,AB) e (BA,BB). Poiché P1 sceglierà A avremo che, proprio come ci aspettavamo, P2 sceglierà B.

Diffusione di una strategia

Potremmo in prima approssimazione pensare che l’importanza di un nodo in una rete sia data meramente dal suo grado, cioè dal numero di archi a esso collegati.

L’esempio della seguente figura ci fa notare che ciò non è necessariamente vero, infatti se si vuole far passare un’informazione nella rete, abbiamo che il comportamento del nodo centrale è fondamentale per il raggiungimento o meno del nostro scopo anche se ha un grado basso rispetto a quello di altri nodi.

La centralità di un nodo può essere più proficuamente usata come misura dell’importanza di un nodo nella rete e tale concetto è formalizzato da quello di betweeness. La betweeness di un nodo i è il numero dei cammini minimi passanti da i. In particolare la betweeness centrality del nodo v è la somma, al variare della coppia di nodi s e t, dei rapporti tra il numero di cammini minimi tra s e t passanti per v e il numero di cammini minimi totale tra s e t.

A seguito di quando detto, supponendo di essere un’azienda che voglia diffondere il più possibile una nuova tecnologia A, per scegliere i “nodi chiave” (ovviamente limitati) a cui fornire gratuitamente il prodotto affinché si diffonda in tutto il territorio, dovremmo tenere in considerazione la betweeness centrality dei vari nodi a disposizione.

Il concetto di connessione (o densità) di una rete è esplicato da quello di coefficiente di clustering[11]. Il coefficiente di clustering del nodo i, C_i ∈ [0, 1] rappresenta la densità di connessioni nelle vicinanze del nodo stesso, in particolare C_i = 1 se tutti i nodi a esso collegato sono tra loro connessi a due a due e C_i = 0 se tutti i nodi a esso connessi sono tra loro isolati.

Si può calcolare un coefficiente medio di clustering per i nodi della rete per avere una visione più generale della stessa. Se C è piccolo ci aspettiamo un grafo con poche connessioni.

Vedremo che, per il diffondersi di una nuova tecnologia, in generale è auspicabile che la rete non sia fortemente connessa (a differenza di quanto avveniva per il sorgere di una rivolta negli articoli precedenti).

Presentiamo alcuni esempi.

Esempio di reazione a catena [9]

Supponiamo di avere un grafo in cui ogni nodo possa scegliere tra due possibili comportamenti e che se due nodi sono tra loro collegati essi sono incentivati ad adottare la stessa strategia, in particolare se entrambi

scegliessero A otterrebbero un guadagno individuale di a, se entrambi scegliessero B di b, ma se scegliessero strategie distinte di 0. Se ci fossero più nodi vicini, per esempio d, e una percentuale p di loro usasse A, mentre la restante (1-p) usasse B, avremmo che A risulta una strategia efficace da usare se dpa > d(1 − p)b ossia se la somma dei payoff individuali (a) ottenuti dai nodi (d*p) che scelgono A, è maggiore della somma dei payoff individuali (b) ottenuti dal gruppo di nodi d*(1-p) che sceglie B. In sintesi, la strategia A è vincente se p> b/(a+b) , cioè la percentuale di nodi che scelgono A deve superare la percentuale del payoff b rispetto al guadagno totale possibile (a+b). Chiameremo p valore soglia.

Quindi più la connessione di un grafo aumenta (mantenendo fisso il numero di nodi) più è difficile che una nuova strategia, che segue queste regole di profitto, si diffonda partendo da pochi iniziatori.

Si pensi al caso in cui, nel grafo in questione, una parte di nodi scelga A e la restante B. Seguendo il ragionamento precedente alcuni nodi potrebbero cambiare comportamento e si innescherebbe di  conseguenza un processo di mutazione della strategia dei nodi della rete che terminerebbe al raggiungimento di una condizione di stabilità.

Si prendano per esempio a=3 e b=2 e si consideri il seguente grafo

dove all’istante iniziale tutti i nodi scelgono B, tranne v e w che scelgono A. Denotando con p il

valore soglia b/(a+b) notiamo che q = 0.4, quindi se almeno il 40 per cento dei vicini di un nodo avesse una data strategia anch’esso la adotterebbe.

Notiamo che r ha come vicini v, w, s. Di questi ne abbiamo 2 su 3 che scelgono A (cioè il 66 per cento), quindi r passerà alla strategia A e a quel punto farà la stessa cosa anche s (avendo 2 vicini su 3 che scelgono A) e di conseguenza w e v la manterranno. Si arriverà rapidamente alla propagazione totale del comportamento A. Otteniamo dunque una “reazione a catena”.

 

Esempio di non-propagazione

Si consideri la situazione precedente ma in riferimento al grafo sottostante, in cui i nodi evidenziati hanno adottato la strategia A.

E’ facile verificare, con l’iterazione del ragionamento precedente, che non vi sarà una cascata ma solo i nodi 4, 5, 6, 7, 8, 9 e 10 avranno, una volta stabilizzata la situazione, scelto A.

Per ampliare la diffusione di A quel che si può fare è

• Diminuire il valore di q, per esempio aumentando a;
• Focalizzarsi su alcuni nodi chiave a cui far adottare la strategia A, ma come sceglierli?

Un cluster di densità P è un insieme di nodi tali che ognuno di loro ha almeno una frazione P dei suoi vicini in tale insieme. Una cascata si conclude quando entra in un cluster sufficientemente denso.

Si consideri un insieme iniziale X di individui che adottano la strategia A con una soglia q, definita come prima, che se superata porta i nodi rimanenti (raggruppati nell’insieme Y) ad adottare anch’essi tale strategia. Se e solo se Y contiene un cluster di densità maggiore a 1-q, l’insieme X non riuscirà a realizzare un effetto a cascata completo e quindi a diffondere la strategia A.

Esempio di massimizzazione della soglia

Data una rete possiamo chiederci quale sarà la soglia q più elevata che a essa si potrà applicare ottenendo comunque un effetto a cascata. Questa quantità è chiamata capacità di diffusione, per esempio la capacità di diffusione della seguente rete, in cui i nodi che hanno adottato la nuova strategia A sono indicati in nero, è 1/2 (se raggiunta, infatti, farà sì che A si diffonda come un’onda sulle code).

In particolare si può dimostrare che nessuna rete può avere capacità maggiore a 1/2. Supponiamo ora di avere la seguente matrice di payoff

ove ogni nodo può scegliere se adottare la tecnologia A, la B o entrambe. Nel caso in cui lui e un suo vicino scelgano entrambi la strategia AB il payoff per entrambi sarà del massimo tra a e b meno un costo aggiuntivo c.

Prendiamo per esempio c=1, a=2 e b=3. Partendo dalla situazione START sottoindicata abbiamo i seguenti sviluppi:

e quindi la strategia A si diffonderà sempre di più all’aumentare delle iterazioni. È intuitivo aspettarsi che se a è molto maggiore di b la tecnologia A si diffonderà rapidamente, ma come influisce c? La sua influenza, in relazione a quella di a è sintetizzata nelle immagini sottostanti.

I giochi ripetuti

Oltre ai giochi sequenziali menzioniamo brevemente che all’interno dei giochi dinamici esistono anche i giochi ripetuti che si ripetono più volte con gli stessi giocatori e le stesse azioni/strategie tra cui scegliere. Possiamo per esempio riprendere il dilemma del prigioniero descritto nel precedente articolo sulla teoria dei giochi (https://orbyta.it/teoria-dei-giochi/). In uno scenario “one-shot” il dilemma si risolve con un equilibrio di Nash non pareto-ottimale, infatti i due prigionieri si tradiscono a vicenda, subendo entrambi la condanna. Se invece il gioco venisse ripetuto, vengono prese in considerazione la reputazione dei giocatori, basata sulle decisioni da loro prese in passato, e la punizione/reazione dell’avversario nel turno successivo. L’esito finale in questo caso dipende dal numero di turni nel gioco. Se il numero di turni è predefinito, si può dimostrare che il gioco si conclude esattamente come nel scenario “one-shot”, in un equilibrio non-pareto efficiente, perché gli giocatori sono spinti comunque a tradire. Se invece il numero di turni è sconosciuto, i giocatori sono incentivati a cooperare temendo la reazione dell’avversario nel turno successivo arrivando così ad una conclusione di equilibrio pareto-ottimale.

In questo articolo abbiamo studiato i giochi dinamici e come si risolvono tramite la metodologia di backward induction. Abbiamo visto inoltre i concetti di centralità (betweeness centrality) e del coefficiente medio di clustering per i nodi all’interno di una rete. In particolare abbiamo visto tramite alcuni esempi che per la diffusione di una strategia è importante che la rete non sia fortemente connessa. Infine abbiamo introdotto i giochi ripetuti e come si può arrivare ad una risoluzione pareto-ottimale al loro interno.

 

Bibliografia e Sitografia

[1] R. Dawkins, Il gene egoista, I edizione collana Oscar saggi, Arnoldo Mondadori Editore, 1995.

[2] D. Easley e J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Con- nected World, Cambridge University Press, 2010.

[3] R. Gibbons, Teoria dei giochi, Bologna, Il Mulino, 2005.

[4] E. Martìn Novo  e A. Mendez Alonso, Aplicaciones  de la teoría  de grafos a algunos juegos   de estrategia, numero 64 di Suma, Universidad Politécnica de Madrid, 2004.

[5] S. Rizzello e A. Spada, Economia cognitiva e interdisciplinarità, Giappichelli Editore, 2011.

[6] G. Romp,Game Theory: Introduction and Applications, Mishawaka, Oxford University Press, 1997

[7] T. C. Schelling, The Strategy of Conflict, Cambridge, Massachusetts: Harvard, University Press, 1960.

[8] P. Serafini, Teoria dei Grafi e dei Giochi, a.a. 2014-15 (revisione: 28 novembre 2014).

[9] I. S. Stievano e M. Biey, Cascading behavior in networks, DET, Politecnico di Torino, 2015.

[10] I. S. Stievano e M. Biey, Interactions within a network, DET, Politecnico di Torino, 2015.

[11] I. S. Stievano, M. Biey e F. Corinto, Retie sistemicomplessi… , DET, Politecnico di Torino, 2015.

[12] A. Ziggioto e A. Piana, Modello di Lotka-Volterra, reperibile all’indirizzo http://www.itismajo.it/matematica/Lezioni/Vecchi%20Documenti%20a.s.%202011-12/Modello

%20di%20Lotka-Volterra.pdf, consultato il 15/05/2015.

[13] http://it.wikipedia.org/wiki/Equilibrio_di_Nash consultato il 12/05/2015.

[14] http://www.oilproject.org/lezione/teoria-dei-giochi-equilibrio-di-nash-e-altri-concetti-introduttivi-2471.html consultato il 13/05/2015.

[15] http://web.econ.unito.it/vannoni/docs/thgiochi.pdf consultato il 14/05/2015.

[16] https://www.youtube.com/watch?v=jILgxeNBK_8 consultato il 19/01/2021.

[17] http://www.andreaminini.it/teoriadeigiochi/giochi-ripetuti consultato il 06/07/2021.

[18] https://www.ed.ac.uk/files/atoms/files/lecture_8_game_theory.pdf consultato il 06/07/2021.

Articolo a cura di Carla Melia (Head Data Scientist), Augusto Cadini (IT Business Analyst) e Angeni Uminga (Software Developer), Orbyta Tech, 10.07.2021