6 x 9 = 42

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

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!

Annunci

4 Risposte to “Introduzione alla Teoria dei Giochi – Parte 1”

  1. Dato lo spazio, direi sintesi non male.

    Faccio due commenti, uno tecnico e un più di fondo:
    – forse è prematuro e magari saresti intervenuto sul tema in post successivi, comunque lo faccio lo stesso… Attenzione che l’uso delle strategie miste richiede (per dare un senso a quello che si fa, ovviamente matematicamente ci si può giocare a piacimento) che i decisori siano rappresentabili come decisori di von Neumann e Morgenstern. Non ci si può “accontentare” delle comode utilità “ordinali”.
    – la teoria dei giochi come “insieme di strumenti”. Sì, per lo meno ciò è vero se si vuole sottolineare il suo aspetto come “apparato matematico”. Ma, domanda: cosa è TdG e cosa è equazioni differenziali o “calcolo delle probabilità”? Intendo dire che la TdG è un insieme distrumenti che si è sviluppato avendo in mente un certo reticolo interpretativo (decisori razionali ed intelligenti, oltre che ovviamente intelligenti). In effetti, il piccolo set di problemi che hai indicato è bene o male (rilassando opportunamente queste ipotesi di razionalità ed intelligenza) riconducibile a questo ambito interpretativo: l’aspetto più problematico è l’intelligenza (penso ai moduli cerebrali o ad animali che non hanno neanche un sistema nervoso…). Anche di razionalità si può discutere, e può in qualche modo essere recuperata (fitness). Ciò che è interessante è che la TdG (come set di insiemi matematici) si applica anche laddove razionalità ed intelligenza sembrano essere del tutto assenti. Ho discusso di questi temi in un paio di conferenze (a Levico Terme e a Sanlucar de Barrameda), per introdurre applicazioni della TdG in biologia molecolare nelle quali sono stato coinvolto.

    Ciao. Ti leggo sempre volentieri

  2. scardax said

    La ringrazio come sempre del commento e degli interessanti spunti.

    Non ho ancora deciso come sviluppare il seguito degli articoli, pero’ pensavo di farne uno di approfondimento su alcuni aspetti particolari, fra i quali le assunzioni alla base della teoria (e quindi ricondurmi al primo punto che indica), eventualmente con qualche cenno storico partendo dai probabilisti francesi.

    Il secondo punto é intrigante: attraverso la (poca) esperienza che mi sono fatto delle sue varie applicazioni, la TdG é applicabile ovunque vi siano degli “agenti” (che possono essere fisici, software, od altre entità astratte) che agiscono sempre per massimizzare una qualche utilità che puo’ essere definita matematicamente. Che poi lo facciano consciamente (umani), attraverso meccanismi fisici, con un programma in Java (un software che “cerca” di ottenere più memoria possibile sulla RAM) od un qualche meccanismo di tipo più alto (TdG ed evoluzionismo) é indifferente.

    La biologia molecare insieme alla TdG sembra interessante, si puo’ trovare qualche materiale online?

  3. Sì, un po’ di cose ci sono in rete.

    Note divulgative:
    http://www.diptem.unige.it/patrone/24ore_sanit_articolo.pdf

    http://www.diptem.unige.it/patrone/game_practice_TdG_applicata_sul_serio_2_handout.pdf

    http://www.diptem.unige.it/patrone/pag_4_La_Stampa_9_mag_07.pdf

    Contributi scientifici:
    vedi la parte “Methods” di questo lavoro:
    http://www.biomedcentral.com/1471-2105/9/361

    e questo è il lavoro di origine (ma non è liberamente scaricabile):
    http://www.springerlink.com/content/m3816572506u15x6/

  4. Scardax said

    La ringrazio moltissimo, appena riesco passo in rassegna il materiale!

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

 
%d blogger hanno fatto clic su Mi Piace per questo: