Introduzione alla Teoria dei Giochi – Parte 1

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 che gli é permesso compiere. Generalmente queste vengono dette le sue strategie (e l’insieme indicato con ), 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à , 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 .
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 .
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!

Giochi da Politici

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):

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.

Piccoli Giochi Crescono

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): 10¹²⁰, 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

Cooperazione ed Equilibri

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).