6 x 9 = 42

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

Archive for the ‘Teoria dei Giochi’ Category

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 »

Utopie Matematiche

Posted by scardax su gennaio 28, 2010

Nel 1951, a pochi anni dalla conclusione della Seconda Guerra Mondiale, l’americano Kenneth Arrow dimostro’ matematicamente un risultato che sconvolse l’intera comunità scientifica, e che gli valse in seguito anche il premio Nobel: nessun sistema di voto, egli disse, esistente o ancora da inventarsi, puo’ realmente considerarsi “giusto”; di conseguenza, nessuna democrazia potrà mai realmente dirsi “perfetta”, almeno in un senso classico del termine.

Da allora, questo teorema fu ripreso e frainteso infinite volte, fino ad entrare nell’immaginario collettivo di molte persone insieme ad altri teoremi “incapacitanti” simili come quello di Gödel. Ma cosa dimostro’ realmente Arrow?

Per capirlo, partiamo dall’inizio: cos’é un sistema di voto?

Un sistema di voto puo’ considerarsi come un qualcosa che fa corrispondere ad una serie di preferenze individuali (quelle di ogni cittadino) un’unica preferenza della società; e per poter essere considerato corretto, ovviamente, il sistema deve cercare di rispettare equamente ciascuna delle preferenze di partenza. Matematicamente parlando, supponiamo di avere un certo numero di candidati per un’elezione (C1, …, Cn). Ciascun elettore ha un proprio ordine di preferenza per questi candidati, ed in tutto vi sono m elettori. Se indichiamo con P(C) un possibile ordinamento dei candidati, possiamo definire un generico sistema di voto come una funzione che associa alle m preferenze degli elettori una singola preferenza (di società):

V: (P(C))^m \rightarrow P(C)

Qualunque sistema di voto che conoscete, in sostanza, puo’ essere descritto in questa maniera: dal più semplice “contare le preferenze in ciascuna posizione”, a modalità estremamente più complesse, questa formalizzazione cattura lo spirito della discussione. A questo punto, arriviamo al punto focale del dibattito: come possiamo definire “giusto” un sistema di voto? Quali proprietà esso deve possedere? Arrow ne scelse tre (potete divertirvi a formalizzarle rispetto a quanto detto prima):

  • Unanimità (o efficienza di Pareto): se tutti gli elettori preferiscono un candidato A ad un candidato B, allora anche nell’ordine risultante A sarà preferito a B.
  • Non Dittatorialità: non esiste un elettore le cui preferenze prevalgono sempre sugli altri, ovvero non esiste un elettore tale che il risultato del voto sia sempre uguale alle sue scelte personali.
  • Indifferenza delle Alternative: se A é preferito a B dati un certo numeri di candidati, introdurne di nuovi non cambierà questa preferenza (ovvero, non é possibile che un candidato perda contro tre concorrenti, ma vinca se vi si aggiunge un quarto).

Ed eccoci infine al risultato: Arrow dimostro’ che, se vi sono almeno due elettori e tre candidati, non esiste nessuna funzione matematica che soddisfi queste tre condizioni insieme!

Da qualunque lato lo si guardi, é comunque un teorema sconfortante, in quanto dimostra che una votazione, nonostante la sua facilità di descrizione, é un problema estremamente complesso e difficile da analizzare (e da progettare). Sembra che, comunque vadano le cose, dobbiamo accontentarci di un sistema non ottimale. Ovviamente, un risultato matematico é valido nei limiti in cui sono valide le premesse. In particolare, in che misura deve essere realmente verificata la terza condizione? E’ proprio vero che un candidato nuovo non possa modificare le mie preferenze individuali? E soprattutto, é proprio vero che io debba avere un ordine completo di tutti i candidati in testa?

Per una rapida discussione su questi problemi, potete tranquillamente cominciare dalla pagina di Wikipedia (e dai suoi links):
http://en.wikipedia.org/wiki/Arrow’s_impossibility_theorem

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

Dove Nasce la Cooperazione

Posted by scardax su novembre 29, 2009

Come i lettori di più lungo corso ricorderanno, più di un anno fa vi avevo parlato di un gioco molto interessante chiamato Il Dilemma del Prigioniero: riepilogando, si tratta di un gioco a due giocatori in cui ciascuno di essi ha la possibilità di cooperare o di non cooperare. Se entrambi cooperano ottengono un’utilità abbastanza alta, ma hanno anche la tendenza a non cooperare in quanto, se uno coopera e l’altro no, quello che non coopera ottiene un’utilità maggiore, mentre l’altro un’utilità estremamente bassa. In conclusione, se entrambi sono razionali finiranno sempre per non cooperare, ottenendo cosi’ un’utilità relativamente bassa, come riassunto nella seguente tabella (i due giocatori sono A e B, C indica l’azione di cooperare, mentre NC quella di non cooperare):

A / B C NC
C (2, 2) (-1, 3)
NC (3, -1) (0, 0)

(Per maggiori delucidazioni sulla struttura del gioco, potete fare riferimento all’articolo linkato ad inizio post. Se non siete molto familiari con le nozioni di giocatore, di gioco o di utilità, potete dare un’occhiata alla prima parte dell’Introduzione alla Teoria dei Giochi (la cui seconda parte é ancora in fase di scrittura)).

Come si puo’ capire da questa formulazione molto generale, questo gioco permette di descrivere una grandissima gamma di possibili situazioni. Una molto famosa, seppur leggermente ambiziosa, é la corsa al nucleare: se i due giocatori sono due nazioni, che cooperano non costruendo bombe nucleari e non cooperano costruendole (entrambe le nazioni preferirebbero essere le uniche a possedere la bomba, o che nessuno dei due la possieda, ma in nessun caso vorrebbero non averla mentre l’altro ce l’ha), ne concludiamo che la corsa al nucleare é “scontata“.

In generale, possiamo dire che la conclusione che i due giocatori non coopereranno é abbastanza deludente. Pero’, cosa succederebbe se si decidesse di ripetere numerose volte questo gioco? L’utilità di un giocatore sarebbe l’utilità ottenuta in ciascuna partita, e diversi problemi verrebbero alla luce: in particolare, vale la pena non cooperare, sapendo che l’altro giocatore, nel turno successivo, se ne ricorderà e potrebbe “farcela pagare”? Analizziamo due diversi casi, e poi cerchiamo di vedere come se la cavano le nostre conclusioni teoriche quando messe in pratica.

  1. Prima di tutto, pensiamo di ripetere il gioco N volte, con N fissato in anticipo e conosciuto da entrambi i giocatori. Si puo’ facilmente dimostrare che la strategia ottima é non cooperare per N volte di fila: all’n-sima iterazione del gioco, esso é un normale Dilemma del Prigioniero, e quindi la strategia ottima é non cooperare; all'(n-1)esima, i risultati dell’iterazione successiva sono prefissati, quindi nuovamente l’azione ottima é non cooperare; per induzione, la strategia ottima é non cooperare sempre. Deludente, come prima, forse anche peggio di prima.
  2. Supponiamo invece che N non sia conosciuto, o sia infinito. L’analisi di prima non tiene più, e si puo’ dimostrare che in questo caso é possibile portare l’avversario a cooperare “minacciandolo” di non cooperare per un certo numero di turni se anch’esso non coopera. Intuitivamente, questo equivale ad annullare i vantaggi dati dal non cooperare riducendo la sua utilità in un certo numero di turni successivi (una strategia del genere é sempre possibile in tutti i giochi ripetuti infinite volte).

Quanto sono vere queste idee in pratica? Nel 1984 Axelrod decise di indire un torneo in cui diversi programmi avrebbero potuto confrontarsi giocando il Dilemma del Prigioniero N volte, ma con N piuttosto grande. In generale, ne usci’ fuori che i programmi migliori adottavano si’ varianti della strategia vista al punto (2), ma avevano anche tratti che potremmo definire “gentili”: tendevano a cooperare il più possibile, tendevano a “perdonare” eventuali non cooperazioni dell’avversario, e non cercavano di fare più punti del loro avversario.

La cosa più impressionante di tutte, pero’, fu che la strategia vincente fu anche la più semplice: Tit for Tat (traducibile più o meno come “occhio per occhio”), che faceva semplicemente questo:

  • Coopera al primo turno.
  • Copia la mossa fatta dall’avversario al turno precedente.

Come ci dice la saggezza popolare, “le cose semplici sono sempre le migliori”.

Per un’estesa discussione su questi aspetti, vi é un intero capitolo a loro dedicato nel best-seller di Dawkins Il Gene Egoista, ed anche una pagina di Wikipedia fatta piuttosto bene (in Inglese):
http://en.wikipedia.org/wiki/Prisoner’s_dilemma

Posted in Teoria dei Giochi | Contrassegnato da tag: , , , , , , | 3 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 »

Giochi da Politici

Posted by scardax su maggio 14, 2009

Le elezioni si avvicinano nuovamente, e visto che proprio ieri mi é capitato di studiare una divertente formulazione della teoria dei Giochi della competizione elettorale (seppur molto semplicistica), cerco di riprodurre il ragionamento qua lasciando un po’ da parte la matematica.

Per cominciare, pensiamo ad una retta in cui ciascun punto rappresenta una posizione elettorale. Ogni elettore si colloca da qualche parte lungo questa retta, e di elettori ce n’é un numero molto alto. Non conosciamo la loro esatta distribuzione sulla retta (possiamo pensare che sia relativamente bassa agli estremi, e che abbia dei picchi vicino alle zone centrali), pero’ sappiamo che vi é un punto, che chiamiamo m, che li divide esattamente a metà, e che conosciamo.

I giocatori sono i partiti politici, che devono scegliere dove collocarsi lungo la retta in modo da vincere le elezioni. Ovviamente, ciascun elettore vota il partito a lui più “vicino” sulla retta, come nella figura qua sotto (le frecce rosse indicano i consensi dei partiti):

Consenso Elettori

Supponiamo di essere un partito, di avere un solo opponente e di dover decidere la nostra strategia. Ovviamente, questa dipenderà dal posizionamento sulla retta dell’altro partito. Proviamo a vedere cosa succede in alcuni casi:

  • Il nostro avversario si posiziona a sinistra del punto m. Ovviamente, posizionarci ancora più a sinistra di lui si rivelerebbe una strategia alquanto fallimentare: lui avrebbe tutti i voti alla destra della mediana (che sono già metà) più altri compresi tra il centro e la sua posizione, e vincerebbe sicuramente. Quindi, dobbiamo posizionarci alla sua destra, ma non troppo, in quanto altrimenti perderemmo troppi voti “centristi”.
  • Se il nostro avversario si posiziona a destra di m, il ragionamento é speculare: dobbiamo posizionarci alla sua sinistra, ma non troppo.
  • E se si posiziona esattamente su m? Se ci posizioniamo alla sua sinistra, perdiamo. Alla sua destra, perdiamo. L’unica alternativa é posizionarci a nostra volta su m, spartire i voti a metà con l’altro partito e sperare nel ballottaggio.

Ora, il nostro avversario conosce questi ragionamenti, e li applica a sua volta. Quindi sa che, dovunque lui si metta sulla retta, noi ci metteremo più vicini al punto mediano, e vinceremo. L’unica sua alternativa é posizionarsi ancora più vicino al punto m, al che replicheremo avvicinandoci sempre più. Il ragionamento a questo punto si puo’ estendere a più di due partiti, ma già vediamo la conclusione: alla fine, tutti i giocatori decideranno di posizionarsi su m e si spartiranno più o meno equamente i voti.

Ovvero, quando non sono gli elettori ad andare ai partiti, sono i partiti ad andare agli elettori! Ovviamente é tutto molto semplificato, ma bisogna ammettere che la nostra esperienza ci fa fiutare qualche verità nascosta.

PS: ci avviciniamo alle cinquemila visite, vediamo se riesco a preparare qualcosa di divertente per quel momento. Divertente dal mio punto di vista, of course.

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

Piccoli Giochi Crescono

Posted by scardax su ottobre 6, 2008

Esiste un modo estremamente rigoroso per misurare la “noiosità” di una qualche lezione universitaria: il numero di partite a Tris che siete disposti a giocare prima di stufarvi anche di quello. Sotto i cinque, probabilmente la lezione non é cosi noiosa. Sotto i dieci, indubbiamente facevate meglio a restare a casa. Sotto le venti, forse é ora che riconsideriate la vostra vita. Il Tris é sicuramente uno dei passatempi più semplici da giocare: quattro linee su un foglio di carta, niente di più. Dopo un po’, pero’, si tende a stufarsi in quanto si ha la sensazione di stare rigiocando, più o meno, sempre le solite partite, facendo sempre le stesse mosse.

Ed allora la domanda é: quante possibili partite si possono effettuare a Tris? Un modo per cominciare a farsene un’idea é quello di pensare: al primo turno, il giocatore 1 ha a sua disposizione 9 possibili mosse (una per ogni quadrato della griglia), mentre il giocatore 2, successivamente, ne avrà 8 (9 meno il quadrato in cui il primo giocatore ha disegnato il suo cerchietto o la sua croce), e cosi via finché la griglia non si riempie. Quindi, in tutto si dovrebbero avere 9 * 8 * … * 1 = 9! = 362 880 partite diverse. Questo numero sembra esagerato, ed in effetti nel nostro ragionamento ci sono svariate “falle”: prima di tutto, non é necessario che la griglia si riempia, visto che un giocatore potrebbe vincere anche solo in cinque turni, lasciando quindi quattro caselle vuote.

Eliminando queste partite impossibili (un conto per cui vi rimando ai links a fine post), ce ne rimangono 255 168. Ancora troppo alto? Naturalmente possiamo raffinare il conto tenendo presente le varie simmetrie della griglia. Ad esempio, pensiamo alle possibili mosse iniziali: giocare in uno dei quattro angoli del quadrato (in alto a sinistra, in basso a destra e cosi via) dà il via a quattro alberi di possibili partite uguali fra loro, ma semplicemente ruotati di 90°, 180° o 270°: in effetti, le possibili aperture non simmetriche fra loro non sono 9, ma tre: centro, angolo, oppure lato centrale. Eliminando anche queste simmetrie, le possibili partite si riducono (a seconda della definizione che diamo di simmetria) a 26 830 oppure 31 896. Tante, non é cosi? In effetti il Tris, nonostante la sua assoluta semplicità e compattezza, permette di passare diverse settimane di gioco prima di essere riusciti a provare tutte le diverse partite (anche se, in questo conto, permangono comunque partite sostanzialmente dementi, in cui quando il nostro avversario sta per fare Tris non facciamo nulla, oppure, viceversa, non lo facciamo noi quando ne abbiamo l’opportunità).

Ci si potrebbe chiedere cosa accade con un gioco nettamente più complicato come gli Scacchi, in cui (per esempio) solo le mosse d’apertura possibili sono 20. Fare un calcolo preciso come prima risulta essere praticamente impossibile, ma gli esperti sono riusciti a trovarne un numero minimo (nonostante molto probabilmente la realtà sia maggiore): 10120, anche chiamato Numero di Shannon: un numero addirittura maggiore degli atomi nell’Universo. Metaforicamente parlando, sembra proprio vero che gli Scacchi siano un gioco… infinito!

Fonti:

Tic-Tac-Toe su btinternet.com
Numero di Shannon su lestinto.it

Posted in Teoria dei Giochi | Contrassegnato da tag: , , , , , | 2 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 »