La Teoria dei Giochi per fronteggiare l’incertezza

L’incertezza derivante da decisioni di altri agenti, e in particolare dall’interazione competitiva fra diversi agenti, può essere analizzata mediante la Teoria dei Giochi, I giochi più semplici sono quelli sequenziali con informazioni perfette; per questi giochi è possibile utilizzare la ricerca

minimax per trovare le mosse ottime; altri aspetti della teoria dei giochi riguardano i giochi a

mosse simultanee. La teoria dei giochi è una teoria concretamente utilizzata per decisioni molto importanti in diversi campi: la finanza, la vendita delle frequenze radio, la difesa nazionale, e anche nel commercio per lo sviluppo dei prodotti e le decisioni di prezzo dei prodotti. La teoria dei giochi può essere utilizzata per la progettazione di agenti (analisi delle decisioni dell’agente e calcolo dell’utilità attesa per ciascuna decisione nell’ipotesi che anche gli altri giocatori stiano agendo in modo ottimo secondo la stessa teoria) e la progettazione di meccanismi (quando un ambiente è popolato da più agenti può essere possibile definirne le regole (ovvero il gioco a cui gli agenti devono partecipare) in modo tale da massimizzare il bene comune quando ogni agente adotta i comportamenti che, in base alla teoria dei giochi, massimizzano la sua utilità.

principale per rappresentare problemi semplici è stato l’albero delle decisioni. Le reti di decisioni, o diagrammi d’influenza, sono state introdotte da Howard e Matheson (1984), basandosi sul lavoro svolto da un gruppo di ricerca allo Stanford Research Institute (SRI). Nilson e Lauritzen (2000) hanno collegato gli algoritmi per le reti di decisioni agli sviluppi degli algoritmi di clustering per reti bayesiane. Articoli sulle reti di decisione e sulla modellazione dell’utilità compaiono regolarmente nella rivista Management Science. Dopo il ritorno di interesse nei metodi probabilistici in intelligenza artificiale negli anni ottanta, i sistemi esperti basati sulla teoria delle decisioni hanno avuto un’ampia diffusione.

54 L’esempio più famoso di teoria dei giochi è il “dilemma del prigioniero”29: due presunti ladri, A e B, sono arrestati dalla polizia e interrogati separatamente. Ognuno dei due sa che se entrambi confessano verranno condannati a 5 anni di prigione ciascuno, mentre se nessuno dei due confessa potranno essere condannati a un anno di prigione ciascuno per dei reati minori. La polizia offre a ognuno dei due l’opportunità di confessare, testimoniando contro il complice, promettendo che, se uno soltanto dei due confessa, a chi confessa sarà condonata completamente la pena, mentre al complice che non confessa verrà inflitta la pena di 10 anni di reclusione. Supponendo che l’utilità di ciascuno dei due complici non dipende in alcun modo di ciò che accadrà al complice, quali sono le decisioni razionali dei due agenti? La soluzione proposta per questo dilemma dalla teoria dei giochi è che per ciascuno dei due agenti la strategia dominante è confessare; per strategia dominante per A si intende una strategia che, indipendentemente dalla decisione dell’altro agente, comporta una utilità maggiore per A, analogamente è definita una strategia dominante per B. Quando ogni agente ha una strategia dominante, la combinazione delle strategie dominanti prende il nome di “equilibrio con strategie dominanti”; in questo esempio l’equilibrio di strategie dominanti corrisponde alla decisione di confessare sia per A che per B, e quindi a una pena di 5 anni di reclusione sia per A che per B. In generale, un profilo di strategie forma un equilibrio se a nessun agente conviene una strategia diversa se gli altri agenti mantengono invariata la loro strategia. Il “dilemma” sta nel fatto che l’equilibrio con strategie dominanti è peggiore per entrambi gli agenti di quello che si potrebbe ottenere se entrambi decidessero di non confessare e testimoniare contro il complice. Certamente è possibile che entrambi si rifiutino di testimoniare, ma è molto improbabile; entrambi i giocatori, considerando l’opzione di rifiutarsi, si rendono conto che farebbero meglio a testimoniare; è il potere di attrazione del punto di equilibrio.”

La soluzione (testimoniare, testimoniare) può essere evitata se si suppone che gli agenti sappiano che si incontreranno ancora un numero indefinito di volte, o che abbiano una certa predisposizione alla cooperazione, nel senso che l’utilità di ogni agente dipende positivamente anche dall’utilità dell’altro agente, o limitando la potenza computazionale degli agenti in modo che non possano ragionare in modo perfettamente razionale, oppure se uno degli agenti ritiene che l’altro abbia una “razionalità limitata”.

Un campo di ricerca di grande interesse è costituito dall’impiego della teoria dei giochi per progettare ambienti o “meccanismi” idonei a ottenere la massimizzazione di una funzione di utilità globale, attraverso l’interazione fra agenti razionali30. La progettazione di meccanismi, o teoria dei giochi inversa, rappresenta un argomento di grande importanza e attualità per l’economia e la politica, oltre che per l’intelligenza artificiale. Dato un insieme di agenti, e utilizzando le tecniche della teoria dei giochi, si cerca di costruire sistemi intelligenti partendo da sistemi più limitati, anche non cooperativi, in maniera simile a quella per cui squadre di esseri umani possono raggiungere obiettivi che vanno molto al di là delle capacità dei singoli individui che le compongono. Esempi di progettazione di meccanismi includono la messa all’asta di biglietti aerei economici, l’instradamento di pacchetti di informazioni tra computer, la suddivisione di un gruppo di medici in più ospedali, la cooperazione all’interno di una squadra di calciatori robot. La ricerca accademica sulla progettazione dei meccanismi è stata stimolata a

29 _{Il “dilemma del prigioniero” fu inventato come esercizio per gli studenti da Albert W. Tucker nel 1950.}

30 _{Leonid Hurwicz (1973) presentò i fondamenti matematici per la progettazione di meccanismi; nel 2007 Hurwicz}

ha ottenuto, a 90 anni, il premio Nobel per l’economia, insieme a Roger B. Myerson ed Eric S. Maskin, di oltre 30 anni più giovani, che contribuirono a sviluppare il lavoro di Hurwicz. Leonid Hurwicz aveva iniziato le sue ricerche negli anni cinquanta, quando era molto vivo il dibattito sugli effetti delle riforme di ispirazione socialista sull’efficienza economica. Nella motivazione per l’assegnazione del premio Nobel si afferma che Hurwicz fu un pioniere nell’applicare a questo problema una più rigorosa, matematica, analisi, e riporta una frase di Myerson, secondo cui “per diversi decenni Leo Hurwicz ha lavorato per mostrare in che modo modelli economici matematici possono fornire una impostazione generale per analizzare diverse istituzioni economiche, come quelle del capitalismo e del socialismo, come meccanismi per coordinare gli individui in una società”.

55 partire dagli anni novanta anche dal fatto che alcuni governi ritennero di aver perso centinaia di milioni di dollari per non essere riusciti a progettare meccanismi adeguati per la vendita all’asta delle licenze di trasmissione in diverse bande di frequenza. Formalmente un meccanismo è costituito da un linguaggio per la descrizione dell’insieme, potenzialmente infinito, delle possibili strategie adottabili dagli agenti, e da una regola per i risultati che determina le vincite degli agenti dato un profilo di strategie adottabili. Il meccanismo di gran lunga più rilevante riguarda l’organizzazione complessiva di un sistema economico; secondo l’intuizione di Adam Smith della “mano invisibile”, un’organizzazione economica in cui ogni agente persegue la massimizzazione della propria utilità realizza indirettamente il massimo benessere per tutti. L’analisi economica e l’esperienza storica hanno mostrato che questa intuizione ha una grande capacità esplicativa, ma che vi sono delle cause che possono far fallire” questo meccanismo, in particolare le esternalità, i beni pubblici, le asimmetrie informative, le forme di mercato non concorrenziali (fallimento dei mercati) [Russel, Norvig, 2005, vol. 2, pag 300].

Attenzione particolare è stata dedicata alle aste, un meccanismo per la compravendita di beni31; le strategie corrispondo alle offerte dei diversi partecipanti all’asta, il risultato determina chi ottiene i beni e quanto deve pagarli. Un possibile esempio di applicazione di un’asta in intelligenza artificiale si ha quando una collezione di agenti deve decidere se cooperare su un piano congiunto. Hunsberger e Grosz hanno dimostrato che questo risultato si può ottenere in modo efficiente con un’asta in cui gli agenti puntano sui rispettivi ruoli all’interno del piano congiunto [Hunsberger, Grosz, 2000]. Il tipo più comune di asta è l’asta inglese standard al primo prezzo, in cui il banditore aumenta progressivamente il prezzo del bene, fino a quando rimane un solo agente disposto a pagare il prezzo proposto dal banditore. Con questo meccanismo il vincitore dell’asta paga un prezzo pari alla puntata più alta effettuata da almeno un altro agente, e l’incremento di prezzo fra una puntata e l’altra. La strategia dominante dei partecipanti all’asta inglese è semplice: continuare a puntare fino a quando il prezzo proposto dal banditore è più basso della propria valutazione del bene, senza tener conto delle strategie degli altri agenti; l’asta inglese è un meccanismo “a prova di strategia”, nel senso che stimola i partecipanti a rivelare le loro valutazioni del bene. Un limite dell’asta inglese è che i partecipanti devono essere riuniti tutti contemporaneamente, eventualmente anche stando in posti diversi, ma collegati con linee di comunicazione ad alta velocità. Un meccanismo alternativo è l’asta segreta (sealed bid auction o asta a busta chiusa); in questo caso ogni partecipante comunica segretamente al venditore la propria puntata, e quella più alta vince. Con questo meccanismo la strategia di dichiarare il valore reale del bene per l’agente non è più dominante; se l’agente i valuta il bene 100.000 euro, ma è convinto che la puntata massima degli altri agenti sarà 60.000 euro, non è razionale per i offrire un prezzo significativamente maggiore di 60.000 euro. Se l’agente con la valutazione più elevata sottovaluta le valutazioni degli altri agenti, è possibile che il bene venga venduto a un agente diverso da quello che lo valuta di più. Un meccanismo che consente di evitare questo rischio è l’asta segreta al secondo prezzo o “asta Vickrey”, dal nome dello studioso che la propose, vincitore del premio Nobel per l’economia nel 1996. In queste aste vince l’agente che offre il prezzo più elevato, ma paga non il prezzo offerto, ma il prezzo corrispondente alla seconda puntata più alta. Con questo meccanismo la strategia dominante di ciascun agente è offrire un prezzo uguale al valore effettivo del bene per sé. Per la sua semplicità, e per i requisiti computazionali minimi richiesti sia al venditore che ai partecipanti, l’asta Vickrey è usata largamente nella costruzione di sistemi intelligenti artificiali distribuiti.

Nel caso dell’instradamento di pacchetti su internet, gli agenti corrispondono agli archi nel grafo delle connessioni di rete; ogni agente conosce il costo di inviare il messaggio sul proprio arco, il costo di non avere alcun messaggio da inviare è zero. L’obiettivo è trovare il cammino più economico per far viaggiare ciascun messaggio dall’origine alla destinazione; il

31 _{Paul Milgrom (1997) ha presentato un meccanismo per gestire aste per valori di miliardi di dollari; egli ha}

56 costo totale del cammino è uguale alla somma dei costi dei diversi archi. Il cammino più breve può essere calcolato se si conoscono i costi di passo, è quindi essenziale che ogni agente comunichi il suo costo reale; il problema è che ciascun agente ha interesse a segnalare costi elevati per far sì che il traffico sia instradato altrove. Un meccanismo “a prova di strategia” potrebbe esser ottenuto facendo pagare a ogni agente i una somma pari alla lunghezza del cammino più breve che non contiene l’arco i, meno la lunghezza del cammino più breve in cui il costo dell’arco i è uguale a zero. Con questo meccanismo la strategia dominante di ciascun agente è di dichiarare il valore reale del costo di inviare un messaggio sul proprio arco, in modo da consentire di individuare il cammino più economico. In pratica questo meccanismo non è tuttavia utilizzato, a causa dei suoi alti costi di comunicazione e di calcolo; il progettista del meccanismo dovrebbe comunicare con tutti gli altri giocatori, e poi risolvere il problema di ottimizzazione; potrebbe valerne la pena se questi costi potessero essere ammortizzati su più messaggi, ma in realtà i costi fluttuano in continuazione per via delle congestioni nel traffico, e perché alcune macchine si scollegheranno mentre altre andranno online.