6 x 9 = 42

“Ho sempre detto che c’era qualcosa di fondamentalmente sbagliato nell’universo…” (Arthur Dent)

Posts Tagged ‘giochi’

La Tragedia delle Persone (non troppo) Razionali

Posted by scardax su ottobre 22, 2012

In questo blog ci siamo già interessati diverse volte alle tematiche della Teoria dei Giochi: abbiamo visto, tra le altre cose, quanto è complessa la cooperazione fra individui; abbiamo accennato “l’impossibilità” della democrazia; abbiamo scherzato sul populismo della politica. Tutti questi sono ovviamente esempi molto semplificati di problemi più complessi, ma apprezzarne le sfumature ci ha permesso di cogliere brevi rivelazioni su quella che poi è la vita reale. In fondo, comprendere i problemi è il primo passo, forse il maggiore, verso la loro risoluzione.

Vero è che la Teoria dei Giochi in certi casi non riesce a togliersi di dosso la sua patina di “uccello del malaugurio”. Vedersi confermati certi comportamenti egoistici sulla carta sembra a volte quasi peggio che osservare questi comportamenti nella vita reale. In questo senso, nulla è peggiore della cosidetta “tragedia dei beni comuni”, meglio conosciuta con il termine originale “tragedy of the commons”, che è poi una generalizzazione di quanto avevamo visto nel passato sul dilemma del prigioniero. In particolare, considerate una risorsa condivisa da numerose persone. Ciascuna di queste sa che uno sfruttamento intensivo della risorsa porterà al suo completo annichilimento, ma è nel loro interesse individuale portare avanti questo sfruttamento nel breve periodo. La teoria dei giochi ci dice che le persone continueranno a sfruttare la risorsa indipendentemente dal sapere perfettamente bene che questo sarà estremamente dannoso sul lungo periodo.

Come spiega l’economista Ken Binmore, questa è conoscenza popolare intimamente legata alle volte in cui vostra madre ha commentato “immagina se tutti facessero così”. La brutta notizia dell’economia è che, in mancanza di incentivi sufficientemente forti a deviare il proprio comportamento, tutti faranno esattamente così. L’aria delle città si inquinerà, il traffico aumenterà, la foresta Amazzonica scomparirà. E’ compito del legislatore sviluppare meccanismi per salvare tutte queste risorse: affidarsi unicamente al buon senso delle persone è, oltre che stupido, particolarmente dannoso e poco realistico.

Per apprezzare la dimostrazione di tutto ciò, vediamo qui una derivazione del problema originale con cui fu introdotta la tragedia dei beni comuni nel lontano 1968 da Garrett Hardin, esposizione che a mia volta riprendo dal testo Playing for Real del già citato Binmore.

Supponete di essere un matematico particolarmente talentuoso che il caso ha voluto vivere in un piccolo villaggio di campagna, nel quale è presente un terreno di circa un km² su cui pascolano le capre di 10 contadini. La produzione di latte (espressa in secchielli) di ciascuna capra dipende dalla quantità di erba che riesce ad avere per sé  ed in particolare segue una legge esponenziale rispetto alla frazione a di terreno a sua disposizione:

b = e^{1 - \frac{1}{10a}}

Se preferite visualizzarlo graficamente, la produzione di latte fa più o meno così:

Grafico Tragedia dei Beni Comuni

Espresso a parole, ogni capra produce un secchiello di latte avendo a disposizione un decimo di km² su cui pascolare, per poi decrescere fino a non produrre quasi più nulla. Poiché nel villaggio la vostra bravura matematica è piuttosto rinomata, vi viene chiesto di calcolare quante capre dovrebbe avere ciascun pastore per massimizzare la quantità M di latte prodotta complessivamente. Indicando con N questo numero di capre, poiché ciascuna capra avrà a disposizione uno spazio pari a 1/N,  immediatamente vi accorgete che la produzione complessiva è data da:

M = Nb = Ne^{1 - \frac{N}{10}}

Massimizzando tale funzione concludete quindi che sarebbe una buona idea far pascolare 10 capre, corrispondenti a 10 secchielli di latte, ovvero un secchiello ed una capra a testa per i vari contadini. Tutti i contadini annuiscono, ma visto che nessuno concede troppo ascolto ad un matematico, nessuno si cura di stabilire per iscritto niente. Tornati a casa, ciascun pastore scopre un’innata abilità matematica e si accorge che il proprio profitto è dato invece dalla seguente funzione:

m = gb = ge^{1 - \frac{g+G}{10}}

Che assomiglia molto a quella di prima, ma dove ora g sono le proprie capre e G le capre degli altri nove contadini. Ormai i pastori hanno imparato ad ottimizzare una funzione di questo tipo e scoprono quindi che, dato che gli altri pastori hanno già deciso quante capre comprare e G rimane fisso, il problema è lo stesso di prima e la soluzione ottimale è che essi stessi facciano pascolare 10 capre.

Tutti i pastori sono ugualmente bravi in matematica, ed il risultato sono 100 simpatici animali che si spintonano per dodici foglie d’erba, con una produzione complessiva di 0.012 secchielli di latte, che divisi sono 0.0012 secchielli a testa, mentre il resto del secchiello è riempito dal pianto di ciascun pastore che pensa a quanto era migliore la propria vita prima di scoprire le gioie della matematica.

Scherzi a parte, come sempre Wikipedia è un punto di partenza decente per approfondire la conoscenza di questo importantissimo risultato scientifico: http://en.wikipedia.org/wiki/Tragedy_of_the_commons.

Annunci

Posted in Economia, Teoria dei Giochi | Contrassegnato da tag: , , , , , , , , , , | 4 Comments »

Introduzione alla Teoria dei Giochi – Parte 1

Posted by scardax su ottobre 8, 2009

Cominciamo oggi una serie di articoli che parlano della Teoria dei Giochi e delle sue applicazioni, dall’evoluzionismo alla computer science passando per l’economia. Per il momento non c’é nulla di completamente definito, quindi li scrivero’ man mano a seconda del gradimento e/o delle richieste (e prendetelo come un consiglio: se vi piace, commentate! 🙂 ).

La Teoria dei Giochi é estremamente interessante perché, in fin dei conti, il suo oggetto di studio é tanto astratto da risultare anche difficilmente definibile: in termini generali, si occupa di analizzare tutte quelle situazioni in cui due o più agenti (razionali) si confrontano in un’attività competitiva, o cooperativa, cercando di prevalere sugli altri, o formando opportune alleanze. Ma quante situazioni di questo tipo potete immaginare? Provate a rifletterci per pochi attimi:

  • Animali in lotta per prevalere in un determinato habitat naturale.
  • Computer connessi in rete che cercano di ottenere l’accesso al mezzo condiviso (ad esempio un cavo telefonico, o l’etere).
  • Ognuno dei moduli cerebrali che si sforzano di guadagnare l’attenzione del settore cosciente del cervello.
  • Aziende in competizione, politici in gara per un seggio.
  • Giochi nel termine ludico della parola: scacchi, dama, backgammon…

Questa varietà di applicazioni spiega il suo enorme successo: in pratica, non vi é materia che non l’abbia sfruttata per i propri scopi. La teoria dei Giochi, quindi, non é altro che un insieme di strumenti, a disposizione di chiunque ne necessiti: se riuscite a modellare una qualche situazione con uno delle tante definizioni di “gioco” che la teoria vi mette a disposizione, potrete sfruttare tutte le tecniche risolutive a lui associate per ottenere importanti chiarimenti sulla situazione stessa.

Cominciamo dalla situazione più semplice in assoluto: ci sono una serie di giocatori, e ciascuno é chiamato a compiere una qualche scelta, all’insaputa delle decisioni degli altri. Dalla decisione complessiva dipende l’esito del gioco. Questo (o, meglio, il modello matematico corrispondente) viene detto gioco in forma normale, e costituisce il mattoncino fondamentale con cui vengono costruite ed analizzate tutte le situazioni più complesse.

Come possiamo definirlo matematicamente? Abbiamo bisogno di tre categorie di oggetti:

  1. Un insieme I per i giocatori: il caso più semplice é quello in cui ve ne sono due, ma niente impedisce che ve ne siano di più (purché in numero finito).
  2. Per ciascun giocatore, un insieme di azioni A_i che gli é permesso compiere. Generalmente queste vengono dette le sue strategie (e l’insieme indicato con S_i), ma nei casi più complessi i due concetti sono separati: qui, ad ogni scelta di un’azione corrisponde una strategia, ma in generale questo non é vero.
  3. Una qualche funzione che ci indichi il grado di soddisfazione di ogni giocatore per ogni possibile esito del gioco. Il gioco ha una diversa conclusione per ogni possibile combinazione delle scelte dei giocatori: indicando l’insieme di queste scelte con S (matematicamente, é un prodotto cartesiano degli insiemi delle azioni di ciascun giocatore), possiamo dire che ad ogni giocatore deve essere associata una funzione di utilità u_i(s): S \rightarrow R, ovvero una funzione che ritorni un numero reale per ogni esito.

L’ultimo punto é quello più misterioso: come ottenere questa funzione? In realtà, é estremamente semplice, perché é importante solo che i suoi valori permettano di comparare fra loro due diverse scelte. Per costruirla, é sufficiente ordinare tutti i possibili esiti di un gioco dal peggiore al migliore (dal punto di visto del giocatore per il quale la stiamo costruendo) e poi assegnare valori numerici crescenti a ciascuno di essi. Facciamo un esempio preso dal mondo reale:

E’ tardo pomeriggio, e state decidendo con il vostro compagno (o la vostra compagna) come passare la serata. Lui (o lei) preferirebbe andare al cinema, mentre voi preferireste andare a teatro. Se non riuscite a mettervi d’accordo, rimanete a casa entrambi.

Vi sono due persone in ballo, ed in competizione, quindi é sicuramente terreno fertile per la teoria dei Giochi. Vediamo come ottenere la forma normale di questo gioco:

  1. L’insieme dei giocatori ha due elementi, voi ed il vostro compagno/a. Per facilità, lasciatemi chiamarvi A e B. Quindi I = \{ A, B \}.
  2. Ognuno di voi ha le stesse due azioni possibili: decidere di andare al cinema (chiamiamola C), e decidere di andare a teatro (chiamiamola T). Quindi A_A = A_B = \{ C, T \}.
  3. Assumiamo che ciascuno di voi due preferisca uscire per fare qualcosa (pur avendo una preferenza fra le due alternative). Assegnando 0 all’utilità dello stare a casa, 1 all’uscire andando dove preferisce l’altro, e 2 al fare quello che si preferisce, e riorganizzando tutte queste informazioni in una comoda tabella, otteniamo:

A / B C T
C (2, 1) (0, 0)
T (0, 0) (1, 2)

La tabella dovrebbe essere abbastanza intuitiva da leggere: le righe sono le possibili azioni del primo giocatore, le colonne le possibili azioni del secondo giocatore, ogni casella un esito del gioco con relative utilità.

Ma ora, cosa ce ne facciamo di questo modello? Se fossimo A, cosa dovremmo giocare per vincere? E se fossimo B? Nel prossimo post vedremo alcuni esempi di concetti risolutivi che ci permetteranno di rispondere, almeno parzialmente, a queste domande.

Prima di concludere, pero’, un ultimo dettaglio. Abbiamo detto che il giocatore ha una strategia possibile per ogni azione: in realtà, ne ha molte di più. Ciascun giocatore potrebbe decidere di associare una qualche distribuzione di probabilità al suo insieme di strategie, e decidere in funzione di quello. Ad esempio, A potrebbe decidere di giocare C il 60% delle volte e T un altro 40%: questa é quella che viene detta strategia mista, in opposizione alle strategie pure (la scelta sicura di un’azione).

Più che mista, quest’ultima trovata puo’ sembrare molto mistica: che vuol dire “scegliere in funzione di una distribuzione di probabilità“? Riempire una ciotola di palline colorate ed estrarne una a caso? Tirare una monetina? Quando mai si vedono cose del genere nella realtà? In realtà, é più comprensibile se lo vediamo come un espediente matematico: il più delle volte le strategie miste servono per modellare alcuni casi particolari, come quando non sappiamo con certezza quello che giocherà un giocatore, o quando vogliamo rappresentare la “scelta media” di un insieme di giocatori, o ancora quando vogliamo rappresentare la scelta di uno stesso giocatore, ma quando si trova davanti al gioco un numero ripetuto di volte.

E questo é tutto per i giochi in forma normale. Commenti, consigli, proposte ed insulti: commentate!

Posted in Teoria dei Giochi | Contrassegnato da tag: , , , , , , , | 4 Comments »

Cooperazione ed Equilibri

Posted by scardax su settembre 1, 2008

Oggi voglio parlarvi di un esempio tratto da una branca della matematica relativamente recente, la cosiddetta “Teoria dei Giochi“, che nonostante l’apparente semplicità risulta una vera miniera per discussioni morali e filosofiche sulla cooperazione fra le persone. L’esempio viene detto Dilemma del Prigioniero.

Supponiamo che due membri di una banda criminale vengano arrestati, e portati al commissariato vengano interrogati separatamente. I poliziotti si trovano leggermente in crisi, visto che al momento non possono accusare i due se non per piccoli reati, che li terrebbero in prigione per poco tempo. L’unica soluzione per loro é che ciascuno dei due banditi collabori con la giustizia ed accusi il suo compagno di reati maggiori (come ad esempio una rapina). Ciascuno dei due criminali (che chiameremo A e B) ha quindi due opportunità: collaborare ottenendo uno sconto di pena, oppure tacere prendendo una piccola condanna, ma ha al tempo stesso l’angoscia di non sapere se il suo compagno ha parlato oppure no. Possiamo riassumere questa situazione in una semplice tabella (C sta per collaborare con la polizia, mentre T per tacere):

A / B T C
T Entrambi prendono 1 anno di galera. A non va in galera, mentre B prende 5 anni.
C B non va in galera, mentre A prende 5 anni. Entrambi prendono 3 anni di galera.

Chiaramente, se uno dei due confessa ma viene contemporaneamente accusato dal compagno prende uno sconto di pena su una condanna decisamente maggiore. La prima domanda che puo’ sorgere spontanea é: dov’é il gioco? In effetti, per la matematica un gioco é semplicemente una situazione in cui abbiamo diversi contendenti (in questo caso 2), ciascuno dei quali ha la possibilità di scegliere fra un insieme di strategie (generalmente finito), e ad ogni coppia di strategie dei due giocatori corrispondono determinati “guadagni“. Possiamo pensare che ciascuno dei due prigionieri abbia due strategie, che corrispondono rispettivamente alle righe della tabella (strategie di A) ed alle colonne (strategie di B).

La domanda naturale successiva é: qual’é la soluzione del gioco? O, per dirla in altri termini: quale strategia conviene adottare ad A e B? Per la teoria dei giochi, una soluzione corrisponde ad un cosiddetto “Equilibrio di Nash“, che possiamo definire (in maniera estremamente informale e senza scomodare la matematica) cosi: quell’insieme di strategie (una per ogni giocatore), rispetto al quale non é conveniente a nessun partecipante cambiare la propria (per convenienza si intende massimizzazione dei guadagni). Esaminiamo la tabella: la coppia TT (entrambi i malviventi non parlano) é un’equilibrio? Chiaramente no: a ciascuno dei due converebbe parlare, in modo da non andare neanche per un anno in galera. Il ragionamento é simile anche per la coppia TC: ad A in questo caso converrebbe parlare in modo da diminuire la pena (stessa cosa, ma con protagonisti invertiti, per la coppia CT). In effetti, l’equilibrio é CC: a nessuno dei due conviene tacere, poiché aumenterebbe la propria pena.

Ed eccoci al succo del discorso: la soluzione che, ad occhio, ci poteva sembrare quella “migliore”, ovvero che entrambi tacessero, non si rivela ad una migliore analisi efficace, in quanto é instabile, troppo soggetta alla possibilità per il proprio avversario di tradire e massimizzare il profitto. E’ interessante che il discorso non varia neanche se A e B, prima di essere catturati, si fossero accordati sul non parlare: comunque per entrambi ci sarebbe stata la tentazione al tradimento!

Questa situazione (che in pratica risulta da ragionamenti puramente matematici, nonostante qui abbia cercato di evitarli), é qualcosa con cui abbiamo molta familiarità: le strategie basate sulla fiducia sono quelle che portano un profitto abbastanza buono all’insieme dei membri di una comunità, eppure spesso sono rovinate da persone che vogliono comunque massimizzare i propri guadagni a discapito di altri, e quindi ci si ritrova in situazioni in cui tutti hanno, sostanzialmente, perso qualcosa rispetto a quello che potrebbero avere!

Se volete approfondire il discorso, vi rimando alla homepage di Fioravante Patrone, docente di TdG dai cui pdf ho anche tratto la versione del Dilemma del Prigioniero che vi ho presentato (nonostante l’abbia leggermente adattata).

Posted in Teoria dei Giochi | Contrassegnato da tag: , , , , , | 3 Comments »