martedì 19 agosto 2014

Dagli equilibri di Nash ai comportamenti collettivi

Quando ho condiviso il tweet qui sotto, non mi ero reso ancora conto del nome che avevo appena letto, eppure avrebbe dovuto suonarmi un campanello nella testa. Poi dopo è successo che sono andato a ricontrollare (che poi i campanelli magari suonano e semplicemente la suoneria è così bassa che non la senti, con il resto del rumore di fondo) ed ecco che quel nome accende la lampadina: Gianluigi Greco. Mio ex-compagno di classe al liceo. Il migliore della classe, da quel che ricordo, bravissimo in particolare in matematica e in informatica (che comunque erano un'unica materia, all'epoca, 20 e passa anni fa), con una carriera decisamente folta di articoli scientifici. I suoi interessi si sono sviluppati in particolare nella programmazione, nella logica, nella teoria dei giochi.
In particolare mi ha colpito il fatto che abbia lavorato sugli equilibri di Nash, soprattutto perché di questi avevo scritto un (per ora disperso) post poco prima dell'assegnazione di un Nobel per la pace di quattro anni fa.
In teoria dei giochi, l'equilibrio di Nash è una soluzione concettuale di un gioco non-cooperativo che coinvolge due o più giocatori, nel quale ogni giocatore assume di conoscere le strategie di equilibrio degli altri giocatori, e nessun giocatore ha alcunché da guadagnare solo dal cabiamento della propria strategia. Se ogni giocatore ha scelto una strategia e nessun giocatore può beneficiare dal cambio di strategia mentre gli altri giocatori mantengono invariata la propria, allora l'attuale insieme di scelte strategiche e le corrispondenti vincite costituiscono un equilibrio di Nash.
In poche parole, Amy e Will si trovano in un equilibrio di Nash se Amy sta prendendo la migliore decisione possibile, tenendo conto della decisione di Will, e Will sta prendendo la migliore decisione possibile, tenendo conto della decisione di Amy. Allo stesso modo, un gruppo di giocatori sono in un equilibrio di Nash se ognuno sta prendendo la migliore decisione possibile, tenendo conto delle decisioni degli altri in gioco.
Equilibri di Nash possono, per esempio, essere trovati nel gioco della coordinazione, nel dilemma del prigioniero, nel paradosso di Braess(6), o più in generale in qualunque gioco strategico. In particolare, dato un gioco, ci si può chiedere se esso possiede o meno un equilibrio di Nash: ebbene a quanto pare decidere l'esistenza di un equilibrio di Nash è un problema di tipo-NP, se non ci sono restrizioni alle relazioni tra i giocatori. Inoltre per un equilibrio di Nash forte il problema si trova al secondo livello della gerarchia polinomiale, che è una scala per la classificazione dei problemi in base alla complessità di risoluzione(1).
Oltre a questo studio sugli equilibri di Nash, Gianluigi, insieme con Francesco Scarcello, ha anche studiato gli equilibri di Nash (nel caso specifico gli equilibri forzati) nei giochi grafici, dove per gioco grafico si intende un gioco rappresentato in maniera grafica, attraverso un grafo(2).
Come ricorda un comunicato stampa dell'Unical, Gianluigi ha, però, vinto il Godel Research Prize per la fondazione logica delle intelligenze artificiali con il progetto Collective Behavior in Social Environments: Models and Complexity. Così, semplicemente leggendo il titolo del progetto, si potrebbe pensare a qualcosa di lontano da uno studio legato alle intelligenze artificiali, invece lo studio e la modellizzazione dei comportamenti collettivi ha una sua importanza in questo campo di ricerca specifico.
Comprendere il comportamento dei singoli ha sicuramente un certo interesse scientifico, non solo per comprendere il funzionamento del nostro cervello, ma anche per comprendere i meccanismi cognitivi, fondamentali nella costruzione di strategie didattiche efficaci. D'altra parte gruppi di persone interagenti tra loro sono in grado di far emergere organizzazioni di livello superiore rispetto all'individuo:
Formiche interagenti creano le architetture della colonia che nessuna singola formica comprende. Popolazioni di neuroni creano pensiero strutturato, memoria permanente e risposte adattive che nessun neurone può comprendere da solo.(3)
Da qui, dunque, l'interesse verso i modelli sul comportamento collettivo, dove quelli più utilizzati sembrano essere i modelli basati sugli agenti intelligenti, come il sistema basato sull'intelligenza dello sciame (swarm intelligence) introdotto nel 1989 da Gerardo Beni e Jing Wang(4): in questo caso alcuni agenti, programmati con delle regole semplici, vengono fatti interagire uno con l'altro e con l'ambiente circostante, in quella che può essere considerata come una evoluzione dell'idea alla base del gioco della vita di Conway.
Un simile sistema può sicuramente essere utile in biologia e nello studio reale di sciami (o dei comportamenti umani), e d'altra parte lo studio delle interazioni sociali all'interno degli sciami può suggerire strategie di ottimizzazione per gli algoritmi(5) che modellizzano il comportamento collettivo (ad esempio nello studio del problema del viaggiatore).
L'interesse nell'utilizzare questo approccio sta, quindi, nell'emergenza all'interno di un sistema di individui interagenti di una sorta di intelligenza collettiva(7) (o perché no anche di una coscienza!), e quindi nel cercare di comprendere se un sistema di neuroni artificiali interagenti uno con l'altro in base a delle regole più o meno semplici è in grado di far emergere una qualche forma di intelligenza artificiale, che poi magari possa essa stessa evolvere in base alle interazioni con l'ambiente esterno. In questo affresco trova (o immagino dovrebbe trovare) anche una sua sistemazione lo studio degli equilibri di Nash da cui siamo partiti: in fondo l'interazione tra agenti è una sorta di gioco, e quindi scoprire questi equilibri all'interno delle regole fissate potrebbe permettere, nel caso di trasporto dei modelli nelle società umane piuttosto che nello sviluppo dell'intelligenza artificiale, di scoprire i meccanismi di ottimizzazione delle scelte.
In questo senso sarebbe interessante poter dare un'occhiata a questo articolo sulle comunità on-line che propone un mix tra approccio teorico e sperimentale.
Nella speranza di non aver messo insieme cose che non vanno, al momento, a braccetto, o di non aver semplificato troppo o travisato il senso del titolo del progetto vincente, un saluto ai lettori pazienti (che lascio alla bibliografia e alle note) e, ovviamente, a Gianluigi.
Gli articoli di Nash che introducono l'equilibrio che porta il suo nome:
Nash, J. (1950). Equilibrium points in n-person games Proceedings of the National Academy of Sciences, 36 (1), 48-49 DOI: 10.1073/pnas.36.1.48
Nash J. (1951). Non-Cooperative Games, The Annals of Mathematics, 54 (2) 286-295. DOI: http://dx.doi.org/10.2307/1969529 (pdf)
(1) Gottlob G., Greco G. & Scarcello F. (2003). Pure Nash equilibria, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge - TARK '03, 215-230. DOI: http://dx.doi.org/10.1145/846241.846269 (arXiv)
(2) Greco, G., & Scarcello, F. (2009). On the complexity of constrained Nash equilibria in graphical games Theoretical Computer Science, 410 (38-40), 3901-3924 DOI: 10.1016/j.tcs.2009.05.030
(3) Goldstone, R., & Janssen, M. (2005). Computational models of collective behavior Trends in Cognitive Sciences, 9 (9), 424-430 DOI: 10.1016/j.tics.2005.07.009 (pdf)
(4) Beni G. (1993). Swarm Intelligence in Cellular Robotic Systems, Robots and Biological Systems: Towards a New Bionics?, NATO ASI Series Volume 102 703-712. DOI: http://dx.doi.org/10.1007/978-3-642-58069-7_38
(5) Bonabeau E., Dorigo M. & Theraulaz G. (2000). Inspiration for optimization from social insect behaviour, Nature, 406 (6791) 39-42. DOI: http://dx.doi.org/10.1038/35017500 (researchgate)
(6) Il dilemma del prigioniero è, dei tre che ho citato, sicuramente il più noto, anche grazie allo spettacolo teatrale dell'Oscar di Milano. Proposto da Flood e Dresher nel 1950, venne formalizzato, diventando "dilemma del prigioniero", da Albert Tucker nel 1992:
Due criminali appartenenti alla stessa banda sono stati arrestati e imprigionati. Ogni prigioniero è isolato, senza alcuna possibilità di parlare o scambiare messaggu con l'altro. La polizia, però, non ha prove sufficienti per condannare i due criminali utilizzando l'accusa più pesante. Il programma minimo prevede una condanna a un anno, così la polizia propone a ciascun prigioniero la possibilità di tradire il proprio compagno, testimoniando contro. Ovviamente ciascuno di loro può scegliere di restare in silenzio.
La situazione può essere, quindi, così descritta:
Se A e B tradiscono entrambi l'altro, ognuno di loro viene condannato a 2 anni di carcere.
Se A tradisce B, ma B resta in silenzio, A sarà libero e B condannato a 3 anni (e viceversa).
Se A e B restano entrambi in silenzio, saranno condannati a 1 anno di carcere per l'accusa minore.
Nash ha mostrato che la strategia migliore è quella di restare entrambi in silenzio.
(7) L'esistenza di una possibile intelligenza collettiva sta alla base della psicostoria introdotta da Asimov nel ciclo della Fondazione sviluppatosi tra il 1942 e il 1944. Questa è diventata ben presto una disciplina a tutti gli effetti (ad esempio il Journal of Psychohistory viene pubblicato a partire dal 1973). Un esempio di studio che potrebbe ricadere all'interno di questa disciplina viene segnalato su fantascienza.com: Kalev Leetaru, utilizzando l'automated sentiment mining, in pratica una rilevazione dello stato d'animo (un sistema che, per esempio, viene utilizzato anche da liquida per classificare i singoli post), sembra sia riuscito a costruire un modello in grado di descrivere la primavera araba. Ciò che manca è la conferma dell'eventuale capacità predittiva del modello (e di tutti i modelli del genere, ovviamente), cosa che capiremo solo con lo scorrere degli anni.
at

Nessun commento:

Posta un commento