Archivio mensile:Luglio 2017

Teoria dei giochi

Teoria dei giochi – Introduzione, equilibrio di Nash e primi esempi

Che cos’è un gioco? Un gioco, in termini matematici, non è niente di diverso da un gioco come siamo abitualmente soliti definirli. Tuttavia i giochi matematici racchiudono una classe di situazioni molto più ampie dei comuni giochi cooperativi e non, a cui abbiamo giocato tutti qualche volta.

Prima di passare alla definizione più teorica, preferisco che tu abbia in testa almeno un esempio di gioco, così da riportare ciò che scriverò al tuo caso. Alcuni giochi sono il pari e dispari, una partita di scacchi, una decisione tra andare al teatro o allo stadio (magari tra marito e moglie), la scelta del gusto del gelato e tutte situazioni ad esse simili.

Si può andare anche più nel complesso come nel caso delle strategie applicate in guerra, ci sono molte trattazioni a riguardo, ma molto più avanzate rispetto alle basi che vedremo qui di seguito.

Si definisce gioco qualsiasi interazione tra due o più oggetti/partecipanti le cui sorti dipendono dalle scelte di questi.

E’ quindi un gioco una qualsiasi situazione in cui va effettuata una decisione, va eseguita un’azione e ciò che accade al termine dell’interazione tra i partecipanti dipende dalle scelte fatte da essi.

Per incuriosirti un po’ ecco uno spezzone di un film che secondo me tutti devono vedere almeno una volta:

Possiamo categorizzare i giochi in funzione delle loro proprietà e modalità di sviluppo. Intanto partiamo con una prima distinzione: giochi in forma normale e giochi in forma estesa.

Non voglio appesantire fin da subito questo articolo, quindi direi che è il momento di un esempio, così da inquadrare un po’ ciò di cui stiamo parlando.

Pari e dispari

Il pari e dispari è un gioco a cui tutti, almeno una volta, hanno giocato. Vediamo come sia possibile descrivere questo gioco:

  1. I partecipanti sono 2
  2. Ogni giocatore ha 6 possibili mosse. Deve scegliere uno tra i seguenti numeri: 0,1,2,3,4,5.
  3. Ogni giocatore, prima di iniziare a giocare, ha deciso se “preferisce” Pari o Dispari e le due scelte devono essere l’una diversa dall’altra (se io scelgo pari, tu per forza avrai dispari) .

L’esito della partita dipende dal risultato della somma dei numeri scelti, in contemporanea, dai due giocatori. Supponiamo per comodità, che il Giocatore 1 vince in caso esca Pari e il 2 in caso esca Dispari.

Una volta determinate queste caratteristiche, seguono immediatamente alcune conseguenze. Per esempio, questo è un gioco in cui non esiste il pareggio. Infatti non esistono altre possibilità, ogni numero naturale è Pari o Dispari, per cui uno dei due partecipanti necessariamente vince.

Hanno entrambi la stessa probabilità di vittoria, infatti ciascuno vince in 2 casi su 4 (indicando con P e D la scelta pari e dispari, le coppie ordinate di possibili esiti sono infatti queste 4 PP,PD,DD,DP).

Bene, per ora non approfondiamo oltre l’esempio. Lo riprenderemo più avanti parlando di Equilibrio di Nash. Detto ciò, notiamo come in questo gioco particolare, i giocatori muovono contemporaneamente, è quindi un gioco in forma NORMALE.

Altra caratteristica di questi giochi, è che i giocatori non possono stringere accordi vincolanti nel corso della partita. Possono però comunicare prima che essa inizi.

Per vincolanti intendo che non si può condizionare la scelta dell’avversario con accordi più o meno vantaggiosi, facendo sì che se l’avversario non seguisse l’accordo verrebbe punito per questo. Ogni tipo di comunicazione deve precedere la partita, come se si telefonassero i giocatori prima di iniziare a giocare per decidere le regole e le modalità con cui il gioco si svilupperà.

Giochi in forma normale e giochi in forma estesa

Queste due categorie di giochi, fanno parte della classe dei giochi non cooperativi. Ossia giochi durante i quali non è possibile dialogare e contrattare. Tutto ciò che regola il gioco viene modellizzato prima che esso inizi (regole, turni e quant’altro).

Nei giochi in forma normale, i giocatori muovono simultaneamente, lo stesso numero di volte. I giochi in forma estesa, invece, si sviluppano nel tempo. In essi non tutti i giocatori muovono necessariamente insieme e lo stesso numero di volte.

Nei giochi in forma normale, quindi, i giocatori non possono muovere conoscendo ciò che gli altri hanno fatto, diversamente dai giochi in forma estesa, come gli scacchi.

Come abbiamo visto con l’esempio precedente, ogni giocatore ha alcune preferenze. Esse possono essere precisate con dei Payoff, dei premi che variano in valore in funzione delle preferenze dei giocatori stessi.

Nell’esempio del pari e dispari, se io scelgo Pari si può supporre che lo faccia perchè ha la possibilità di vincere più soldi in caso di vittoria. Diciamo quindi Payoff il premio che io vinco in caso si verifichi una data sequenza di scelte da parte dei giocatori.

Segue che ogni gioco in forma normale/estesa può essere descritto definendo i partecipanti, le mosse che hanno a disposizione (le modalità in cui esse vanno fatte, nel caso dei giochi in forma estesa) e i Payoff.

Per rappresentare un gioco in forma normale si utilizzano solitamente le tabelle a doppia entrata, mentre per rappresentare i giochi estesi si è soliti utilizzare degli alberi.

Si potrebbe dire molto di più riguardo a queste due branche di giochi, ma per il momento preferisco lasciare solo due immagini in cui penso vengano chiariti molti dettagli. Magari in separata sede, dedicherò un articolo più dettagliato a questa parte.

Gioco in forma estesa (albero)

Gioco in forma normale (tabella doppia entrata)

Cos’è un equilibrio di Nash

La teoria dei giochi deve moltissimo a John Nash, grande matematico a cui è stato anche dedicato un film negli ultimi anni (‘A beautiful mind’). Se ti interessano i film sulla matematica ecco qui un articolo che fa per te: I 5 migliori film sulla matematica

A lui è dovuto il concetto di equilibrio all’interno di un gioco. In parole povere, per equilibrio si intende una situazione in cui nessuno dei giocatori ha interesse a cambiare la scelta fatta.

Se hai osservato con attenzione le immagini qui sopra, avrai senz’altro notato che per giungere ad ogni payoff, è necessaria una specifica sequenza di mosse, di scelte dei giocatori. Bene, se quando si è giunti ad un payoff, tutti i giocatori non hanno motivi per pentirsi della sequenza di scelte fatte, allora siamo in un equilibrio.

In quali situazioni un giocatore potrebbe ‘pentirsi’ delle scelte fatte e volerle cambiare? Quando è consapevole che ha ‘vinto’ meno di ciò che potenzialmente avrebbe potuto vincere.

Supponiamo quindi di arrivare ad un punto in cui il gioco si conclude, io ho effettuato due mosse che chiamo M1 e M2. Il mio avversario ha fatto L1 e L2. Mi rendo conto che in tali circostanze vincerei 10€. Supponiamo per un momento che il mio avversario faccia le stesse esatte mosse, ora mi chiedo: avrei potuto vincere di più di 10 se avessi fatto mosse diverse da M1 e M2?

In caso di risposta affermativa, allora non sono in una situazione di equilibrio, altrimenti dovrei fare la stessa verifica anche nella direzione opposta, così da verificare se esso sarebbe solo un equilibrio per me o anche per il mio avversario.

Prima di proseguire alla ricerca di un equilibrio in un esempio molto famoso, vorrei tornare un attimo sul pari e dispari. Esso è infatti un gioco senza equilibri di Nash se si gioca solo con strategie pure.

Specifichiamo quindi due cose: cosa si intende per strategie pure e perchè in quel caso non ci sono equilibri?

Per strategie pure si intende che le scelte vengono effettuate sulle possibilità a disposizione, non vengono lasciate al caso. Si parla invece di strategie miste in situazioni dove per esempio si lancia un dado che ha probabilità P che esca la faccia ‘6’, se uscisse un 6 allora sceglierei pari, altrimenti dispari.

In tal caso si può dimostrare che se P=1/2, ed entrambi i giocatori scegliessero tra Pari e Dispari con lo stesso metodo, allora saremmo in un equilibrio. Comunque ho già programmato di scrivere un articolo interamente dedicato all’interazione dei questi giochi con la probabilità, così da avanzare nella conoscenza della teoria dei giochi con casistiche più interessanti.

Perchè non ci sono quindi equilibri puri nel pari e dispari? Beh, è molto intuitivo, infatti in ogni possibile Payoff in cui mi posso trovare al termine del gioco, supponendo che ogni giocatore giochi per vincere, uno dei due giocatori avrà sempre interesse a cambiare la scelta perchè solo in tal caso potrebbe vincere. Non ci troveremmo quindi mai in una situazione di equilibrio.

Vediamo qui sotto un gioco molto famoso, lo utilizzeremo per comprendere meglio il concetto di equilibrio.

Il dilemma dei prigionieri

Il dilemma del prigioniero è un gioco proposto negli anni cinquanta del XX secolo da Albert Tucker come problema di teoria dei giochi. Oltre ad essere stato approfonditamente studiato in questo contesto, il “dilemma” è anche piuttosto noto al pubblico non tecnico come esempio di paradosso.

Il dilemma in sé, anche se usa l’esempio dei due prigionieri per spiegare il fenomeno, può descrivere altrettanto bene la corsa agli armamenti, proprio degli anni cinquanta, da parte di USA e URSS (i due prigionieri) durante la guerra fredda.

Ecco qui la tabella a doppia entrata in cui può essere sintetizzato il gioco.

 

 

In breve, la situazione è questa:

Ci sono due prigionieri a cui viene data la possibilità di confessare. Se entrambi lo fanno, trascorreranno 5 anni a testa in prigione. Se solo uno dei due lo farà, l’altro ne trascorrerà 10 in prigione. Se nessuno dei due confessasse, trascorrerebbero solamente 2 anni a testa in prigione. (gli anni possono variare, l’importante è il concetto dietro a questa trattazione)

E’ chiaro che se mettessero il proprio interesse prima di tutto, senza valutare bene la situazione, finirebbero entrambi a farsi 5 anni in prigione. Confessando infatti avrebbero la possibilità di essere liberati. Peccato che ciò accadrebbe solo se non lo facessero entrambi.

Qual è quindi secondo te l’equilibrio di Nash di questo gioco?

Apparentemente quindi converrebbe ad entrambi non confessare, dato che il totale degli anni trascorsi in prigione sarebbero soltanto 4. Tuttavia se analizzi il tutto dal punto di vista del singolo giocatore, confessare risulta senz’altro la scelta da essi preferita.

Infatti se il giocatore 1 confessa, allora anche al 2 conviene confessarlo dato che altrimenti si beccherebbe 10 anni di prigione.

Se invece il giocatore 1 non confessasse, comunque al giocatore 2 converrebbe confessare dato che, in tali circostanze, uscirebbe indenne dalla prigione.

Lo stesso ragionamento può essere ripetuto supponendo fissata la scelta del giocatore 2 e verificando come, in qualsiasi caso convenga scegliere di confessare anche al giocatore 1.

Infatti si può notare come confessare è strategia dominante per entrambi, è la scelta preferita da entrambi i giocatori indipendentemente da ciò che accade nel gioco stesso.

L’equilibrio è quindi (confessa,confessa) ed è qui che nasce un paradosso, infatti nelle loro migliori scelte vanno a trascorrere in galera più anni di quanti ne avrebbero potuti trascorrere se avessero potuto accordarsi.

Se infatti fossero entrambi certi che l’altro giocatore avesse scelto di non confessare, avrebbero potuto trascorrere solo 2 anni in prigione a testa. Ora invece ne trascorreranno 5 a testa, ma saranno comunque “contenti” delle loro scelte in quanto esse, indipendentemente dalle scelte dell’altro giocatore, garantivano il miglior risultato.

Conclusione di questa introduzione alla teoria dei giochi

Per questa introduzione è tutto, spero di essere riuscito a descrivere i fondamenti della teoria dei giochi in maniera abbastanza chiara. Se non altro, spero di averti incuriosito e di averti fatto venir voglia di cercare altre informazioni online a riguardo.

Infatti ci sono interi corsi, video online gratuiti, ti rimane solo da trovarli ed imparare, detto ciò ho già anticipato che questo non sarà l’ultimo articolo relativo a questa tematica. Infatti la teoria dei giochi mi interessa parecchio e quando ho del tempo ne approfitto per continuare ad esplorarla. Quindi aspettati nuovi articoli in futuro 😉

Al prossimo articolo

Davide

Il commesso viaggiatore… Alla scoperta della Programmazione Lineare

Amazon riceve decine di milioni di nuovi ordini ogni giorno. Un numero che solo a pensarlo può dare un senso di stordimento.

Mettiamoci nei panni di uno dei servizi di spedizione a cui questa grande compagnia si appoggia. Il flusso di pacchi da gestire è enorme e per aumentare al massimo il profitto bisogna trovare un modo per ridurre al minimo il percorso di ogni spedizioniere.

Qui salta fuori il famoso problema del “Commesso viaggiatore”, ossia come trovare il tragitto più breve che passi per un insieme finito di punti nello spazio.

In questo post cercheremo di cogliere la reale complessità del problema e di risolverlo andando così… alla scoperta della Programmazione Lineare.

Cos’è il Travelling Salesman Problem?

Nell’introduzione abbiamo visto come il problema che stiamo analizzando nasca da un contesto prettamente concreto. Per cercare di capire come risolverlo la prima cosa da fare è sempre la stessa: fare conoscenza con il problema. Per fare questo, solitamente, i matematici non seguono alla lettera le regole del galateo, ma si mettono a dividere tutto in pezzi e a dare un nome ad ogni componente.

Noi da aspiranti matematici faremo lo stesso!

Definiamo quindi un insieme contenente tutti i punti da raggiungere, e un insieme T che rappresenti i possibili tragitti con la loro lunghezza: se esiste un percorso che va da a   di lunghezza .

Utilizzando il vettore , di cui ogni componente rappresenta un tragitto all’interno del percorso considerato (vedremo poi meglio come è fatto), definiamo una funzione che assegna ad ogni percorso la sua lunghezza.

Il problema si può ora vedere in modo più formale come: trovare il vettore   tale per cui  sia minimo.

Forse tutto questo matematichese ti ha confuso un po’, ma se provi a rileggere il tutto con attenzione ti accorgerai che non abbiamo fatto altro che riscrivere in formula il problema di prima.

Ora puoi dire che come era scritto inizialmente era molto più semplice (e ti daremmo ragione), ma questa nuova veste dà al quesito un aspetto più trattabile da un punto di vista matematico/computazionale.

Per trovare una soluzione al problema del commesso viaggiatore andiamo a scoprire uno degli strumenti più potenti nel campo dell’ottimizzazione lineare: la Programmazione Lineare.

Preliminari alla Programmazione Lineare

Prima di riuscire a riscrivere il problema dobbiamo introdurre il concetto di funzione lineare.

Diciamo funzione lineare una funzione del tipo dove .

Guardandola bene possiamo capire che il termine lineare significa semplicemente che l’argomento della funzione è di primo grado.

Analogamente diciamo che un vincolo è lineare se è nella forma  dove e .

Ricerchiamo l’ottimo con la PL

A questo punto vogliamo esprimere un percorso tramite il vettore . Come facciamo?

Una possibile soluzione è la seguente: definiamo una variabile per ogni possibile tragitto. Ad esempio identifica il tragitto dal punto  al punto . Ora poniamo  uguale a 1 se il tragitto è compreso nel percorso considerato, 0 altrimenti.

Ricordandoci del significato di  possiamo finalmente costruire la nostra tanto sudata funzione lineare .

Ci resta soltanto da porre delle condizioni che obblighino il percorso analizzato a passare per tutti i punti.

Ne servono 3!

, ossia ogni punto ha solo un percorso “entrante” …

, ossia ogni punto ha solo un percorso “uscente”….

e

, ossia le uniche possibilità sono utilizzare un tragitto (1) o non considerarlo (0).

(Per correttezza si dovrebbe utilizzare una quarta condizione per evitare la presenza di sottocircuiti non connessi che però qui tralasciamo per semplicità).

Formalizzazione del problema del commesso viaggiatore

Riassumendo tutto quello che abbiamo detto il Travelling Salesman Problem diventa:

sotto le condizioni

Molto bene… E ora?

Abbiamo dato una veste molto elegante al nostro problema, ma come lo risolviamo?

Il bello della programmazione lineare è proprio questo, “non ci interessa”!

Una volta scritto il problema secondo questo formalismo è sufficiente delegarlo ad un buon risolutore.

Qui trovate una spiegazione di come risolvere problemi del genere utilizzando Excel.

Per capire cosa succede all’interno di questi applicativi bisognerebbe aprire una lunghissima e complessa parentesi sul metodo del simplesso. Lascio ai più curiosi l’occasione di approfondire (poi se serve un aiuto scriveteci pure 🙂 ).

Il lato oscuro del commesso viaggiatore

Siamo quasi alla fine e sembra ormai che per i servizi di spedizione il problema delle consegne sia stato risolto. Tutto va bene finché il numero di punti di consegna non aumenta e il nostro metodo non riesce più a fornire una soluzione.

La modellizzazione che abbiamo fatto è infatti NP-completa e quindi il tempo di esecuzione del nostro metodo cresce in modo non polinomiale (e quindi MOLTO velocemente) al crescere del numero di punti analizzati.

E’ proprio questa difficoltà che apre lo scenario ad altre tecniche di risoluzione. L’ideale sarebbe trovare un algoritmo polinomiale, ma non sappiamo ancora se questo è possibile (l’argomento della NP vs P è stato accennato recentemente qui).

Per ora sembra che, nel caso in cui il percorso debba passare per un numero elevato di punti, non si possa trovare la soluzione ottima al problema del commesso viaggiatore in tempi ragionevoli. In pratica quindi si deve abbandonare la speranza di trovare l’ottimo ed accontentarsi di una sua approssimazione.

Futuri viaggi del commesso

Entriamo così nel mondo dell’euristica dove si va a cercare di trovare dei buoni candidati per ottenere l’ottimo utilizzando tecniche di tipo probabilistico/stocastico.

Queste metodologie sono molto interessanti e suggestive. Nel futuro andremo quindi a richiamare il nostro commesso per partire con lui in un nuovo viaggio… alla scoperta del Calcolo Stocastico!

Come abbiamo visto in questo articolo spesso molti problemi della vita quotidiana vengono affrontati facendo uso del sapere matematico.

Questo mi fa pensare che chi dedica la vita allo studio della matematica non sia poi così folle!

Spero che l’articolo ti sia piaciuto, a presto 😉

Marco