Impara a Programmare, Articolo Bonus 2: La Teoria dei giochi

La Teoria dei Giochi

La teoria dei giochi [1,2,3,4,5] e’ una branca della matematica applicata che studia l’interazione strategica tra agenti, detti giocatori.

Possiamo distinguere i giochi in:

• cooperativi, quando i giocatori collaborano per ottenere insieme dei benefici
• non-cooperativi quando ogni giocatore si batte singolarmente per massimizzare la sua utilita’.

Noi ci occuperemo in particolare di questi ultimi. Un gioco (che e’ quindi un modello di descrizione dell’ interazione strategica di alcuni agenti economici) µe composto da tre elementi:

• L’insieme dei giocatori: i = 1, 2,…, n.
• L’insieme delle strategie che i giocatori possono seguire:
• La funzione di payoff di ciascun giocatore: u_i().

La teoria dei giochi studia tutte quelle situazioni in cui il payoff di un individuo non dipende solo dalle sue azioni, ma anche dalle azioni degli altri giocatori. Si ipotizza che i giocatori siano razionali e che l’obiettivo di ciascuno µe quello di massimizzare il proprio payoff nei limiti dei vincoli.

Una game form G in forma strategica, a due giocatori, è una quadrupla della forma:

(X,Y,E,h)

Dove:

• X,Y,E sono insiemi
• h è una funzione definita su X×Y ed a valori in E

• X rappresenta l’insieme delle scelte disponibili per il primo giocatore (che indicherò come giocatore “I“); idem per Y rispetto al giocatore “II“
• E rappresenta un insieme che contiene tutti gli esiti possibili del gioco in considerazione
• h è la funzione che dice quale esito si otterrà, date le scelte dei giocatori. Più precisamente, se I sceglie x e II sceglie y, si otterrà l’esito h(x,y)

Per passare a un gioco, occorre conoscere le preferenze dei giocatori rispetto ai vari elementi (cioè esiti) di E. Un modo “spiccio” per descrivere tali preferenze è quello di utilizzare “funzioni di utilità“.

Ad esempio, per il giocatore I assumeremo che sia data una funzione u definita su E ed a valori in ℝ.

Interpreteremo u(e’)≥u(e”) come espressione del fatto che egli preferisce l’esito e’ all’esito e”.

Quindi, se abbiamo una game form (X,Y,E,h) e una coppia di funzioni di utilità (una per ognuno dei giocatori) (u,v), abbiamo un gioco:

(X,Y,E,h,u,v)

Definendo f=u∘h e g=v∘h, possiamo considerare la quadrupla (X,Y,f,g). Ovvero un gioco a due giocatori in forma strategica.

Un gioco a due giocatori in forma strategica è:

(X,Y,f,g)

Dove:

X,Y sono insiemi

f,g:X×Y→ℝ

Un equilibrio di Nash per G=(X,Y,f,g) è una coppia ordinata (x*,y*) ∈ X×Y tale che:

• f(x*,y*)≥f(x,y*)   ∀x∈X
• g(x*,y*)≥g(x*,y)  ∀y∈Y

Occorre aggiungere un ingrediente alla descrizione fatta finora, senza il quale non avremmo un “gioco” nel senso tecnico del termine, ma solo cio’ che viene chiamato “game form”: occorre indicare dunque, quali siano le preferenze dei giocatori rispetto agli esiti del gioco. Ovviamente gli esiti possibili di questo gioco sono due: “vince I” e “vince II”. Possiamo ritenere scontato che un giocatore razionale preferisca vincere anziche’ perdere.

Una strategia e’ dunque definibile come l’insieme delle mosse scelte da un giocatore al fine di vincere il gioco.

Il significato di quest’ultima disuguaglianza è molto semplice: se un gioco ammette almeno un equilibrio di Nash, ogni agente ha a disposizione almeno una strategia dalla quale non ha alcun interesse ad allontanarsi se tutti gli altri giocatori hanno giocato la propria strategia. Infatti, come si può desumere direttamente dalla disuguaglianza, se il giocatore i gioca una qualunque strategia a sua disposizione diversa da f(x*,y*), mentre tutti gli altri hanno giocato la propria strategia f(x,y*) può solo peggiorare il proprio guadagno o, al più, lasciarlo invariato. Se ne deduce quindi che se i giocatori raggiungono un equilibrio di Nash, nessuno può più migliorare il proprio risultato modificando solo la propria strategia, ed è quindi vincolato alle scelte degli altri. Poiché questo vale per tutti i giocatori, è evidente che se esiste un equilibrio di Nash ed è unico, esso rappresenta la soluzione del gioco, in quanto nessuno dei giocatori ha interesse a cambiare strategia.

Si suppone che l’equilibrio di Nash cosi` definito sia un vettore delle strategie di equilibrio costituite dalle risposte ottimali di tutti gli agenti, ottenute attraverso l’intersezione di set di strategie ottimali per ogni agente.

Il dilemma del prigioniero

Due criminali vengono accusati di aver compiuto una rapina. Gli investigatori li chiudono in due celle diverse impedendo loro di comunicare. A ognuno di loro vengono date due scelte: confessare l’accaduto, oppure non confessare. Viene inoltre spiegato loro che:

• se solo uno dei due confessa, chi ha confessato evita la pena; l’altro viene però condannato a 10 anni di carcere.
• se entrambi confessano, vengono condannati a 1 anni ciascuno.
• se nessuno dei due confessa, entrambi vengono condannati a 9 anni.

 Prigioniero 2

Confessa

Non Confessa

 Prigioniero 1

Confessa

(9,9)

(0,10)

Non Confessa

(10,0)

(1,1)

L’equilibrio di Nash di questo gioco e` la coppia (9,9) (e quindi confessare) e rappresenta un esito non ottimale in assoluto per entrambi i giocatori: se infatti avessero potuto comunicare e sapere cosa l’altro stava facendo, avrebbero scelto di non confessare, in quanto ciò avrebbe comportato un pay-off maggiore per entrambi.

[1]   John Nash: “Equilibrium points in n-person games”, 48-49, Proceedings of the National Academy of Sciences, 36, 1950

[2]   Martin J. Osborne (Autore), Ariel Rubinstein (Autore) “A Course in Game Theory” Publisher: The MIT Press (July 12, 1994) – pag. 9 par. “Strategic Games”

[3]   F. Patrone (Autore) “Decisori razionali interagenti” Una introduzione alla Teoria dei Giochi – Edizioni PLUS, Pisa, 2006 ISBN: 88-8492-350-6

[4]   M.O. Spata, “A scheduling algorithm based on Nash equilibrium for a Cluster Grid” Published in 16th IEEE International Workshops on Enabling Technologies: Infrastructures for Collaborative Enterprises (WETICE-2007) GET/INT Paris, France 18th-20th June 2007

[5]   M.O. Spata, G. Pappalardo, S. Rinaudo “Nash Equilibrium of the Prisoner Agents for a Cluster Grid” Published in 3rd IEEE International Conference on eScience and Grid Computing, Bangalore, India, 10th-13th December 2007.

Articoli Simili:

1. La Teoria dei Giochi al servizio delle Smart Grids
2. Impara a Programmare: Guida alla programmazione di Algoritmi e Strutture Dati Avanzate in C
3. Impara a Programmare, Articolo Bonus 1: La Teoria delle Code