Un algoritmo sviluppato dal gruppo di teoria dei giochi del Politecnico di Milano è stato premiato alla conferenza NeurIPS2020, una delle più importanti nel campo dell'intelligenza artificiale e del machine learning. I ricercatori del Politecnico hanno risolto il problema del raggiungimento dei cosiddetti "equilibri correlati", una forma più generale degli equilibri di Nash, nel caso dei giochi in forma estesa. Uno dei possibili campi di applicazione è la costruzione di navigatori satellitari che, ammettendo un minimo scambio di informazioni tra i veicoli che condividono dei nodi decisionali, riescano contemporaneamente a minimizzare il traffico e il tempo di percorrenza dei singoli viaggiatori. L'algoritmo fa emergere spontaneamente una coordinazione tra i comportamenti dei singoli che minimizza il costo collettivo e individuale senza richiedere l'esistenza di un mediatore. Credit: Denys Nevozhai via Unsplash.
Si è conclusa sabato scorso l'edizione 2020 della Neural Information Processing Systems Conference (NeurIPS), una delle più importanti conferenze nel campo dell'intelligenza artificiale e del machine learning. Ogni anno alcuni fra gli articoli accettati per la presentazione alla conferenza ricevono dei riconoscimenti particolari e quest'anno tra i tre premiati c'è anche uno studio italiano. «Erano almeno quindici anni che un team italiano non otteneva questo riconoscimento, siamo molto soddisfatti», commenta Nicola Gatti, professore associato presso il Dipartimento di Elettronica, Informazione e Bioingegneria del Politecnico di Milano, e uno dei quattro autori dell'articolo. Non si tratta di un riconoscimento di poca importanza. Insieme al lavoro del Politecnico è stato premiato anche il generatore di linguaggio GPT-3 sviluppato dalla società di San Francisco OpenAI, di cui avevamo parlato qui, che spicca per essere uno degli algoritmi di machine learning con il più alto costo di calibrazione di sempre, circa 4,5 milioni di dollari.
Nicola Gatti e i suoi collaboratori, Andrea Celli (ora ricercatore postdoc nel Core Data Science team di Facebook), Alberto Marchesi (ricercatore postdoc al Politecnico di Milano) e Gabriele Farina (dottorando alla Carnegie Mellon University), hanno fatto un passo importante verso la soluzione di un problema introdotto nel 1974 dal premio Nobel per l'economia Robert Aumann nell'ambito della teoria dei giochi. Si tratta del lavoro in cui Aumann ha formulato il concetto di "equilibri correlati", una forma generalizzata del concetto di equilibrio proposto da Nash nel 19501. Gli equilibri correlati si ottengono supponendo che esista un "mediatore" che consiglia i partecipanti individualmente e privatamente sulle strategie da adottare. Un equilibrio correlato si raggiunge quando nessun giocatore ha un incentivo a deviare rispetto al comportamento suggerito dal mediatore, sotto l'ipotesi che tutti gli altri seguano i suggerimenti del mediatore. Aumann ha mostrato che in alcuni casi gli equilibri correlati possono portare a un'analisi più raffinata dell'interazione sociale. In un certo senso la figura del mediatore garantisce, sotto opportune ipotesi, che i giocatori producano un esito socialmente virtuoso pur perseguendo i loro obiettivi personali. «Gli equilibri correlati hanno anche un'altra proprietà interessante: sono molto più semplici da calcolare rispetto a quelli di Nash», spiega Nicolò Cesa-Bianchi, professore ordinario di computer science all'Università Statale di Milano che non è coinvolto nello studio. Cesa-Bianchi è autore di uno dei libri di riferimento sugli algoritmi di apprendimento per la previsione delle sequenze, rilevanti nel campo della teoria dei giochi, degli investimenti finanziari o della compressione dei dati.
Tuttavia realizzare nella pratica questo tipo di equilibri non è semplice. Chi svolge il ruolo del mediatore? E chi garantisce che i giocatori ne seguiranno davvero le indicazioni? Nel 2000 gli economisti teorici Sergiu Hart, della Hebrew University of Jerulasem, e Andreu Mas-Colell, economista alla Universitat Pompeu Fabra Barcelona, hanno dimostrato che ammettendo che gli individui apprendano dagli esiti dei loro comportamenti passati, possono raggiungere "spontaneamente" un equilibrio correlato, senza cioè aver bisogno di un mediatore. «Il risultato di Hart e Mas-Colell, che risolve il problema degli equilibri correlati nel caso dei cosiddetti giochi in forma normale, come la morra cinese, ha generato molto entusiasmo nell'area», commenta Cesa-Bianchi, «ma subito l'attenzione si è spostata sui giochi in forma estesa, che prevedono una serie di mosse alternate invece che una mossa simultanea, e in cui non si ha perfetta conoscenza dello stato del gioco, come accade ad esempio nel poker».
I giochi in forma estesa possono essere rappresentati da un albero decisionale. Un esempio è la situazione in cui una serie di veicoli si muovono su un reticolo di strade e a ogni incrocio devono decidere se proseguire dritti, girare a destra o a sinistra, con l'obiettivo di minimizzare il proprio tempo di percorrenza. Chiaramente la sequenza delle loro decisioni dipenderà dai comportamenti degli altri giocatori. Gatti e i suoi collaboratori hanno studiato proprio questo tipo di situazione, formulando l'algoritmo che ciascun individuo deve seguire per raggiungere un equilibrio correlato. L'algoritmo prevede uno scambio minimo di informazioni tra i partecipanti e risulta dunque desiderabile anche dal punto di vista della protezione della privacy. «Il loro lavoro risolve un problema rimasto aperto molto a lungo all'interfaccia tra teoria dei giochi, computer science ed economia. In passato erano stati formulati degli algoritmi che raggiungevano degli equilibri correlati nei giochi in forma estesa, ma erano notevolmente più complicati e non erano molto applicabili in pratica. Uno dei maggiori pregi del risultato di Gatti e dei suoi coautori è la semplicità dell'algoritmo proposto, una caratteristica importante per le sue applicazioni a problemi del mondo reale», commenta Cesa-Bianchi.
Per cercare di capire alcune caratteristiche fondamentali dei giochi presi in considerazione nel lavoro premiato a NeurIPS, è utile partire da un problema molto noto nell'ambito della teoria dei giochi e relativamente facile da descrivere, il problema di El Farol, un bar nella città di Santa Fe in New Mexico. Venne introdotto dall'economista W. Brian Arthur, che allora divideva il suo tempo tra Stanford e il Santa Fe Institute, uno dei centri di ricerca più prestigiosi al mondo sui sistemi complessi. Si tratta di una situazione apparentemente elementare, ma capace di rappresentare le dinamiche che si instaurano quando un gruppo di individui si trova a dover decidere i propri comportamenti riguardo all'utilizzo di risorse disponibili in misura limitata.
Ogni venerdì il bar El Farol organizza una serata di musica dal vivo. Gli abitanti di Santa Fe sanno che la serata sarà piacevole se il locale non è troppo affollato. Le loro valutazioni vanno più o meno così: «Se ci sono più di sessanta persone allora preferisco rimanere a casa; se ce ne sono meno di sessanta ma più di venti, la serata sarà di certo più divertente che quella passata a casa da soli». Tutti devono decidere se andare nello stesso momento e non si scambiano informazioni riguardo le loro intenzioni. Ora possiamo immaginare due situazioni estreme: se tutti si aspettano che il bar sarà pieno allora nessuno andrà e il bar rimarrà vuoto. Viceversa, se tutti si aspettano che il bar sarà vuoto, tutti andranno è il bar sarà pieno. Tradotto nel linguaggio della teoria dei giochi, questo vuol dire che se i partecipanti a questo gioco si comportano tutti seguendo la stessa strategia pura2, falliranno nell'obiettivo di massimizzare il loro divertimento, sia che decidano di andare oppure no.
La pandemia ci ha messo di fronte a tante situazioni di questo tipo. Se dobbiamo prendere i mezzi pubblici per andare al lavoro ci troveremo davanti alla domanda "a che ora è preferibile uscire per trovare autobus e metropolitane meno affollati possibile?". Immaginiamo che ci sia una certa flessibilità sull'orario di inizio della giornata lavorativa. Sarebbe ragionevole pensare che sia preferibile uscire alle 9 piuttosto che alle 8, ma se tutti facessero questa considerazione (cosa che possiamo considerare probabile e legittima) finiremmo col trovare autobus e metropolitane affollate alle 9 invece che alle 8 e il nostro rischio di contagiarci sarebbe uguale a se fossimo usciti al solito orario. Per poter abbassare il nostro rischio di contagio c'è bisogno di una qualche forma di coordinazione tra gli utenti dei mezzi pubblici, ma quale sia quella efficace e come si possa implementare è estremamente complicato da capire. Ci possono essere degli interventi esterni, come in effetti è successo in questo periodo. Per esempio si può scaglionare l'ingresso negli uffici, ma questo non garantisce che i lavoratori usciranno di casa in accordo con il loro nuovo orario di ingresso al lavoro. Esiste, quindi, un modo per far emergere questa coordinazione in maniera spontanea?
La difficoltà pratica di raggiungere l'equilibrio in giochi a cui si partecipa una volta sola è un fatto ben noto e anche abbastanza comprensibile. Come del resto è noto che l'esistenza di equilibri, di Nash o correlati, non è sufficiente a indicare come possano essere raggiunti. Tornando al problema del bar El Farol, se ammettiamo che gli abitanti di Santa Fe ripetano ogni venerdì le loro scelte e imparino dai loro successi o errori, possiamo congetturare l'identificazione dei "percorsi" per raggiungere l'equilibrio. In questa configurazione ripetuta del gioco possiamo ragionevolmente pensare che i partecipanti si comportino sulla base di aspettative formate osservando i livelli di afflusso al bar nelle settimane precedenti. Il modo in cui le osservazioni influenzano le aspettative dei partecipanti sul futuro potrebbe, ad esempio, dipendere dai risultati che diversi metodi di previsione hanno avuto in passato. Assumendo certe particolari forme di ragionamento induttivo, Arthur eseguì una serie di simulazioni al computer che mostrano che il livello di riempimento del bar tende a quello che massimizza il divertimento dei partecipanti.
Con questo esperimento computazionale, Arthur mostrò che esiste una qualche forma di coordinazione spontanea nel problema del bar di El Farol, ma non dimostrò in modo matematicamente rigoroso che tipo di apprendimento conduce a uno degli equilibri correlati di Aumann. Come abbiamo anticipato all'inizio, a farlo ci hanno pensato nel 2000 gli economisti Hart e Mas-Colell con un articolo pubblicato su Econometrica, una delle riviste più prestigiose nel campo dell'economia matematica. I due economisti dimostrano che se i giocatori apprendono dal passato secondo un meccanismo di minimizzazione del regret (rimpianto) convergeranno rapidamente verso uno degli equilibri correlati di Aumann. Per minimizzazione del rimpianto si intende l'approccio secondo il quale prima di ogni giocata il giocatore adotterà una certa strategia se rimpiange di averla usata poco in passato. È un po' quello che accade quando ci comportiamo sulla base di quello che ha funzionato o non funzionato in passato ammettendo un certo grado di sperimentazione.
Il gruppo del Politecnico di Milano ha esteso il concetto di minimizzazione del rimpianto al caso in cui i giocatori possono interagire sequenzialmente e ha definito un algoritmo che lo implementa. Per farlo ha scomposto il problema a livello locale, costruendo l'algoritmo di decisione che ciascun individuo deve adottare intorno a ogni nodo del proprio albero decisionale e dà lì definendo la strategia globale di ogni giocatore. «Questo approccio decentralizzato ha due vantaggi», spiega Gatti, «in primo luogo permette di mantenere trattabile il problema in termini computazionali anche per situazioni che coinvolgono un gran numero di giocatori; in secondo luogo permette di proteggere la privacy degli agenti che non hanno bisogno di condividere con un mediatore esterno le loro preferenze o intenzioni». Il risultato potrebbe essere rilevante in diversi campi: dalla progettazione di navigatori satellitari, al calcolo delle quote che ciascun viaggiatore deve corrispondere in un servizio di ride-sharing, l'ottimizzazione dell'accesso alla rete internet, la definizione di strategie per la compravendita economica di beni disponibili in quantità finita e più in generale ogni problema di allocazione di risorse limitate condivise fra agenti razionali. «Tra i tre articoli premiati quest'anno a NeurIPS uno ha carattere più pratico, il modello di linguaggio GPT-3, mentre gli altri due sono più teorici e il loro impatto sarà chiarito nel lungo termine» afferma Cesa-Bianchi, e conclude «ma anche se nel breve termine contribuisse solo alla costruzione di un'intelligenza artificiale capace di vincere a poker contro i migliori giocatori umani, sarebbe comunque un contributo fondamentale. Significherebbe un progresso sostanziale nell’ambito della pianificazione in presenza di incertezza. Del resto, anche DeepMind ha scelto come uno dei primi problemi da risolvere il gioco di strategia Go, questo non era evidentemente l'obiettivo finale ma soltanto un importante passo intermedio».
Note
1l'insieme delle decisioni di tutti i giocatori tali da rendere sconveniente il cambiamento di decisione unilaterale di ogni singolo giocatore
2 In teoria dei giochi si distinguono strategie pure e strategie miste. Le strategie pure sono quella che definiscono le azioni di un giocatore in tutte le possibili situazioni, mentre quelle miste sono descritte da una distribuzione di probabilità sulle strategie pure. Se un giocatore adotta una strategia mista, ogni volta che deve compiere un'azione sceglierà tra tutte le possibili strategie pure con diverse probabilità.
Per ricevere questo contenuto in anteprima ogni settimana insieme a sei consigli di lettura iscriviti alla newsletter di Scienza in rete curata da Chiara Sabelli (ecco il link per l'iscrizione). Trovi qui il testo completo di questa settimana.
Buona lettura, e buon fine settimana!
