Giocare con il sistema

Tu e un complice di una grossa rapina siete stati beccati dalla polizia e siete stati interrogati in stanze separate. Se entrambi tacete sul crimine, avrete ciascuno un anno di prigione per un'accusa minore. Se strillate entrambi, avrete cinque anni ciascuno. Ma se solo uno di voi strilla, quello sarà libero mentre l'altro avrà 10 anni. Se non sai cosa farà il tuo complice, qual è la decisione razionale?

Asuman Ozdaglar

Questo enigma, noto come dilemma del prigioniero, è l'esempio più familiare di gioco, nel senso tecnico impiegato dai teorici dei giochi. La teoria dei giochi è un modo matematico per descrivere il ragionamento strategico e il dilemma del prigioniero illustra i tre requisiti fondamentali delle situazioni che racchiude: il gioco deve coinvolgere più agenti (qui, i due complici); ognuno deve prendere una decisione (strillare o non strillare); e ogni decisione deve portare un compenso quantificabile (le pene detentive) che varia a seconda delle decisioni degli altri agenti.

La teoria dei giochi è stata un punto fermo della ricerca economica dal 1950, quando John Nash, che ha insegnato al MIT dal 1951 al 1959 ed è il soggetto del film Una mente brillante , ha pubblicato il carta seminale che gli avrebbe fatto vincere il premio Nobel per l'economia. Man mano che la teoria dei giochi è maturata, è diventata ancora più centrale in quel campo. Solo negli ultimi otto anni, il Premio Nobel è andato tre volte ai teorici dei giochi, per aver messo in luce, tra l'altro, la logica della deterrenza nucleare, le circostanze in cui il libero mercato può e non può massimizzare il benessere pubblico e le migliori soluzioni ai problemi di corrispondenza: organi e pazienti, medici e ospedali e simili.

Ma recentemente la teoria dei giochi ha attirato l'attenzione anche nell'ingegneria e nell'informatica. I ricercatori lo stanno usando per analizzare problemi spinosi come l'ottimizzazione del flusso di traffico o la prevenzione dei blackout.

Asuman Ozdaglar, SM '98, PhD '03, professore di ingegneria elettrica e informatica, afferma che l'ascesa di Internet lo ha reso necessario. Storicamente, gli ingegneri delle reti di comunicazione hanno dovuto fare i conti con un'ampia gamma di questioni tecniche, come i vincoli di potenza ei relativi meriti della centralizzazione o del decentramento. Ma con Internet, all'improvviso hanno dovuto fare i conti anche con l'azione umana.

Se un abbonato Comcast a Boston e un abbonato EarthLink a San Francisco stanno scambiando dati, le loro trasmissioni viaggiano su reti gestite da diversi provider: Comcast, EarthLink e altri nel mezzo. L'intera operazione si basa sia sulla collaborazione che sulla concorrenza di queste diverse parti, afferma Ozdaglar. Come si progettano protocolli che forniscano effettivamente i giusti incentivi per le persone a collaborare? In altre parole: perché Internet funziona anche se è composta da singole reti? La teoria dei giochi fornisce un modo per rispondere a questo tipo di domande.

Tuttavia, quando gli ingegneri hanno iniziato ad applicare la teoria dei giochi alle questioni all'interno del loro campo, si sono anche resi conto che gli strumenti del loro mestiere erano applicabili alle questioni in sospeso della teoria dei giochi. Infatti, della manciata di ricercatori del Dipartimento di Ingegneria Elettrica e Informatica (EECS) che lavorano ampiamente sulla teoria dei giochi, tutti hanno dedicato molto tempo a questioni più tipicamente affrontate dalle scienze sociali.

Andare una volta
Il professore dell'EECS Constantinos Daskalakis è un buon esempio. Nel 2008 ha vinto il premio di tesi dell'Association for Computing Machinery mostrando come le tecniche tratte dall'informatica teorica potrebbero gettare nuova luce su uno dei concetti centrali della teoria dei giochi: l'equilibrio.

Constantinos Daskalakis

L'equilibrio è l'idea che ha fatto vincere a Nash il suo Nobel, e l'equilibrio di Nash è il tipo di equilibrio più comunemente studiato. Descrive un equilibrio di strategie che nessun giocatore di un gioco ha motivo di modificare unilateralmente. L'esempio più elementare di equilibrio di Nash riguarda il cosiddetto gioco del calcio di rigore. Nel calcio, un calcio di rigore dà a un giocatore offensivo un tiro libero in porta con solo il portiere che difende. La palla viaggia così velocemente che il portiere deve indovinare da che parte tuffarsi prima di essere colpita. Nella versione teorica del gioco, se entrambi i giocatori scelgono la stessa metà della porta, il portiere vince; se scelgono due metà diverse, vince il tiratore.

Lo stato di equilibrio per questo gioco è che entrambi i giocatori scelgano una direzione casualmente su un dato calcio, ma per garantire che, nel complesso, scelgano entrambe le direzioni con la stessa frequenza. In tal caso, vinceranno ciascuno la metà delle volte e nessuno dei due potrà migliorare le proprie probabilità deviando da quella strategia. Ad esempio, se il portiere iniziasse improvvisamente ad andare nella stessa direzione ogni volta e il tiratore si attenesse alla strategia originale, la percentuale di vincita del portiere rimarrebbe semplicemente la stessa. Tuttavia, un tiratore che ha notato lo spostamento potrebbe vincere ogni tiro andando ogni volta nella direzione opposta, quindi il portiere non ha alcun incentivo a fare questo cambiamento.

Ma il gioco dei calci di rigore è uno dei giochi più semplici. Trovare equilibri per giochi anche leggermente più complessi può essere enormemente difficile. Nella sua tesi, Daskalakis ha dimostrato che per alcune situazioni che possono essere descritte attraverso la teoria dei giochi, l'equilibrio di Nash è così difficile da calcolare che tutti i computer del mondo non sono riusciti a trovarlo nel corso della vita dell'universo. In questi casi, sostiene Daskalakis, probabilmente nemmeno gli umani l'hanno trovata attraverso tentativi ed errori. Ciò significa che i teorici dei giochi hanno bisogno di strumenti analitici diversi dall'equilibrio di Nash se vogliono qualche speranza di descrivere il mondo reale.

Fortunatamente, allo stesso modo in cui l'informatica ha sviluppato una batteria di tecniche per determinare la complessità dei calcoli come quelle che producono equilibri di Nash, ha anche sviluppato una batteria di tecniche per identificare soluzioni approssimative a problemi altrimenti intrattabili. Daskalakis ei suoi studenti, ad esempio, sono riusciti a trovarne uno per un problema di economia che durava da 30 anni.

Nel 1981, Roger Myerson dell'Università di Chicago ha mostrato come strutturare un'asta per un singolo oggetto in modo che se tutti gli offerenti adottassero le strategie di offerta nel loro migliore interesse, il venditore avrebbe realizzato il massimo profitto. Quel lavoro gli è valso il Premio Nobel 2007. Ha anche sollevato una domanda correlata: qual è il modo migliore per strutturare un'asta per più di un articolo? (Nel gergo degli economisti, qualsiasi mercato con un singolo venditore e più acquirenti conta come un'asta; un'asta di Christie è una, ma lo sono anche le vendite in un negozio al dettaglio.) È una domanda con una complessità così grande che non esiste una descrizione succinta per asta che ti dà il profitto ottimale, dice Daskalakis. Per massimizzare le entrate su più articoli, il venditore probabilmente deve vendere ogni articolo a un prezzo inferiore al prezzo più alto che qualcuno sarebbe disposto a pagare. Ma lo sconto varia in base a fattori come il mix di articoli venduti e le popolazioni da cui provengono gli acquirenti.

L'informatica offre una nuova prospettiva sul problema, quella che Daskalakis chiama la prospettiva dell'approssimazione. Forse non sei in grado di trovare l'asta ottimale, dice, ma anche un'asta che garantisce il 99 percento delle migliori entrate è una buona asta. Daskalakis e i suoi studenti hanno dimostrato che per qualsiasi mercato multi-oggetto, l'asta ideale, quella che massimizza le entrate del venditore, potrebbe essere approssimata da una combinazione dei risultati di aste più semplici.

Un approccio un po' diverso ai problemi delle aste caratterizza il lavoro del professore di ingegneria Silvio Micali. Lui e il professore EECS Shafi Goldwasser sono i destinatari più recenti del Turing Award, il più alto riconoscimento in informatica. In gran parte, il premio onora il loro lavoro sulle cosiddette prove interattive, in cui un interrogante con risorse computazionali limitate cerca di ottenere il risultato di un calcolo da un interlocutore inaffidabile con risorse computazionali illimitate. Un esempio è una dimostrazione a conoscenza zero, in cui uno dei partecipanti stabilisce il possesso di un'informazione, come una chiave crittografica, senza rivelare di cosa si tratta. Le prove a conoscenza zero vengono utilizzate per proteggere le transazioni tra istituti finanziari e sono state fondate diverse startup per commercializzarle.

Micali sta portando avanti diversi progetti di ricerca sulla teoria dei giochi, ma uno di questi è molto vicino nello spirito alle prove a conoscenza zero. In molte aste pubbliche, come, ad esempio, quando il governo federale mette all'asta lo spettro radio inutilizzato alle società di telecomunicazioni, il banditore è tenuto a rivelare le offerte di tutti i partecipanti per motivi di trasparenza. Per un'azienda che partecipa a un'asta del genere e perde, è davvero il peggiore di tutti i risultati possibili, afferma Micali. I tuoi concorrenti ora sanno quanto apprezzi questa cosa, da cui possono dedurre quanta clientela servi o quale tecnologia hai a disposizione.

Quindi il gruppo di Micali sta sviluppando aste in cui i partecipanti possono divulgare pubblicamente informazioni sufficienti sulle loro offerte per decidere un vincitore, senza rivelare le offerte stesse. Credo che alla fine questo diventerà mainstream nella teoria dei giochi, dice Micali. Non puoi davvero avere una scienza significativa del comportamento umano ignorando la privacy.

Chi ha il controllo?
Per molte situazioni che possono essere espresse come giochi, l'equilibrio di Nash può essere, come ha mostrato Daskalakis, quasi impossibile da calcolare. Ma ciò non significa che il comportamento dei giocatori sia casuale. Considera una griglia di strade cittadine in cui i conducenti prendono innumerevoli decisioni a dozzine di incroci. Anche se i conducenti non stanno valutando ogni possibile conseguenza di decisioni alternative, stanno comunque adottando alcune semplici strategie, ad esempio, se sei rimasto fermo troppo a lungo, svolta in una strada laterale. Secondo Munther Dahleh, il capo associato di EECS, l'analisi di tali sistemi avvicina la teoria dei giochi al suo campo, la teoria del controllo, che studia le strategie per controllare i sistemi dinamici come gli arti dei robot e le ali degli aerei. Abbiamo una visione diversa di questi problemi, dice Dahleh. Invece di imporre la nozione di equilibrio e dire 'Quali strategie giocherebbero le persone sotto quell'equilibrio?', osserviamo il comportamento dinamico controllato e ci poniamo la domanda 'Quale nozione di equilibrio emerge?'

Dahleh ha infatti applicato gli strumenti della teoria dei giochi all'analisi dei flussi di traffico, indagando le tipologie di tracciati stradali che meglio possono assecondare la chiusura di particolari percorsi. Il suo approccio si applica anche ad altri sistemi dinamici su larga scala, come la rete elettrica.

Ogni giorno, i produttori di energia - gestori di centrali nucleari, centrali a carbone, parchi eolici e simili - offrono nuovi programmi di quanta elettricità sono disposti a produrre, a quale prezzo, a quali ore del giorno. Le utenze che erogano energia elettrica hanno anche degli amministratori che decidono, in base alla domanda attesa dei consumatori, quanta energia acquistare da ciascun fornitore. La produzione e il consumo di energia devono corrispondere esattamente o le conseguenze sono disastrose.

Utilizzando gli strumenti della teoria dei giochi per analizzare gli incentivi sia dei fornitori di energia che dei consumatori, Dahleh e Mardavij Roozbehani, PhD '08, uno dei principali ricercatori del Laboratorio per i sistemi di informazione e decisione, hanno dimostrato che i contatori intelligenti in casa, che possono fornire informazioni sui prezzi spot nel mercato dell'elettricità e consentire ai consumatori di rinviare le attività domestiche ad alta intensità energetica fino a quando non sono più convenienti, potrebbero effettivamente causare picchi di domanda che farebbero crollare l'intera rete.

Dahleh ha anche collaborato con Ozdaglar e suo marito, l'economista del MIT Daron Acemoglu, per analizzare come le informazioni si propagano attraverso le popolazioni. Il gioco in questo caso è quello in cui le persone soppesano la verità o la falsità delle informazioni che le raggiungono, mentre si sforzano di massimizzare l'accuratezza delle proprie convinzioni.

Queste sono domande che sono state studiate sia in sociologia che in economia, dice Ozdaglar. Tradizionalmente, tuttavia, queste indagini presumevano che qualsiasi persona in una data popolazione potesse ricevere informazioni direttamente da qualsiasi altra. Ciò che gli ingegneri offrono, sostiene Ozdaglar, sono strumenti ben affinati per analizzare la struttura di rete sottostante della popolazione. La maggior parte delle persone, ad esempio, in effetti riceve la maggior parte delle informazioni da pochi vicini immediati nella rete e assegna probabilità diverse all'accuratezza delle affermazioni di vicini diversi.

In passato, penso che le scienze sociali e l'economia si occupassero dei problemi in modo diverso dagli ingegneri, dice Dahleh. Ora stiamo tutti parlando di social network - decisioni nei social network, dinamiche sui network - quindi penso che i due campi stiano convergendo.

nascondere