Appunti di teoria dei giochi

1

Appunti di Teoria dei Giochi

per il corso di

Modelli Matematici per le Scienze Sociali

Antonio BERNARDO

1. Premessa

La teoria dei giochi si occupa di situazioni di interazione strategica fra decisori che si assume siano

‘intelligenti’ e ‘razionali’.

Intelligenti significa che capiscono la situazione in cui si trovano e sono in grado di fare ragionamenti

logici corretti. Razionali significa che hanno preferenze coerenti sugli esiti finali del processo decisionale

e che hanno l’obiettivo di massimizzare queste preferenze.

Ogni individuo ha una sua funzione di utilità sull’insieme dei beni. Per esempio, se l’insieme dei beni è

una fetta di torta, un libro, una vacanza, un diploma, ognuno è in grado di quantificare numericamente

la sua utilità per ciascuno dei beni. Non è detto che le utilità di due persone distinte per lo stesso bene

siano le stesse. La razionalità richiesta ai giocatori impone che valga la proprietà transitiva nelle

preferenze: se il diploma è preferito alla vacanza e la vacanza al libro allora il diploma deve essere

preferito al libro.

Una prima classificazione dei giochi è tra giochi cooperativi e giochi non cooperativi.

La teoria dei giochi cooperativi studia il formarsi di coalizioni con accordi sottoscritti e vincolanti che

possono essere di vantaggio ai singoli componenti. Lo studio di questo tipo di coalizioni è stato

introdotto da Neumann.

La teoria dei giochi non cooperativi si occupa dei meccanismi delle decisioni dei singoli, sulla base di

ragionamenti individuali, in assenza di alleanze vincolanti. Questa teoria è stata introdotta di Nash.

La teoria dei giochi non si occupa dei giochi contro il caso, come il lotto, la roulette, … I giochi di cui

si occupa questa teoria devono avere almeno due individui che interagiscono.

Vediamo due esempi.

Esempio 1: pari e dispari

Primo gioco. Due giocatori, Piero e Silvia, hanno un’urna ciascuno contenente 5 palline numerate da 1

a 5. Ciascuno dei due giocatori estrae una pallina dall’urna. Se la somma dei due numeri è pari, vince

Piero, se è dispari vince Silvia.

E’ un gioco contro il caso. Vi sono 25 possibilità, di cui 13 a favore del primo e 12 a favore del

secondo, il gioco non è equo ma i due giocatori non hanno né scelte né decisioni da prendere.

Secondo gioco. Piero e Silvia scelgono contemporaneamente un numero da 1 a 5 e lo indicano con la

mano. Se la somma dei numeri è pari, vince Piero, se è dispari vince Silvia.

In questo gioco i giocatori scelgono il numero da indicare.

Un gioco è a informazione completa se le regole del gioco e le funzioni di utilità di tutti i giocatori

sono conoscenza comune di tutti i giocatori.

Questo assunto non è molto realistico ma è una prima semplificazione per costruire una teoria; si

possono comunque studiare anche i giochi a informazione incompleta ma la teoria è più complessa.

Un gioco è finito se ogni giocatore ha un numero finito di mosse a disposizione e il gioco si conclude

dopo un numero finito di mosse.

Assioma di razionalità. L’ipotesi di base della teoria dei giochi è che tutti i giocatori si comportino

razionalmente, ossia nessun giocatore sceglie un’azione se ne ha a disposizione un’altra che gli permette

di ottenere risultati migliori, qualunque sia il comportamento dell’avversario.

Un’informazione è di comune conoscenza tra due o più giocatori se questi ne sono al corrente, sanno

che gli altri ne sono al corrente, sanno che gli altri sanno che i giocatori ne sono al corrente e così via.

Un gioco è a informazione perfetta se entrambi i giocatori conoscono sempre tutta la storia passata

del gioco, le possibili evoluzioni future e nessuna mossa è segreta per nessuno.

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 2

Gli scacchi e la dama sono tipici giochi a informazione perfetta, i giochi di carte solitamente non lo

sono.

Un gioco è a memoria perfetta se quando è il suo turno di muovere, ogni giocatore ricorda tutto

quanto già sapeva negli stadi precedenti del gioco e tutte le sue mosse passate.

Un gioco è descritto compiutamente quando se ne precisa lo stato iniziale, l’evoluzione, lo stato

finale e il risultato.

Esempio 2: fiammiferi

Stato iniziale: 2 mucchetti di 2 fiammiferi ciascuno

Evoluzione: 2 giocatori a turno levano almeno un fiammifero, e possono farlo da un solo mucchio

Stato finale: tutti i fiammiferi sono stati tolti

Risultato: perde chi toglie l’ultimo fiammifero.

Classificazione dei giochi

a. Le mosse di un gioco possono essere simultanee o sequenziali

Nel gioco degli scacchi le mosse sono sequenziali, nel gioco della morra cinese le mosse sono

simultanee. In una gara d’asta per un appalto le ditte fanno un’offerta simultaneamente, senza

conoscere le offerte fatte dagli altri concorrenti.

b. Gli interessi dei giocatori possono essere completamente contrapposti o parzialmente contrapposti

Nel gioco degli scacchi gli interessi sono completamente contrapposti: se un giocatore vince,

l’altro perde, oppure possono pareggiare entrambi. Nei giochi di carte, solitamente, la vittoria di

un giocatore è pari alla perdita dell’altro. I giochi economici e sociali non sono quasi mai a somma

zero: due imprese possono collaborare insieme per produrre di più di quanto riuscirebbero a

produrre separatamente; in una guerra ci possono essere solo perdenti.

Vi sono poi giochi di pura coordinazione nei quali i giocatori hanno esattamente gli stessi obiettivi

e, senza poter collaborare, cercano di arrivare alla stessa scelta. E’ il caso del dilemma dello

studente bugiardo.

c. Un gioco può essere disputato una sola volta oppure può essere ripetuto più volte.

Un meccanico d’auto si può comportare diversamente se ha a che fare con un automobilista di

passaggio o un cliente abituale. In una corsa sui cento metri non c’è possibilità di collaborazione

tra i corridori ma in una maratona o una gara di ciclismo i corridori possono ritenere utile

collaborare tra di loro.

d. I giocatori possono avere informazione perfetta del gioco o no

Nel gioco degli scacchi ciascun giocatore, nel momento in cui deve fare una mossa, conosce

esattamente la situazione attuale e tutte le mosse che hanno portato a quella situazione. Nel gioco

del poker, invece, un giocatore conosce le carte che ha in mano e quelle scartate dai giocatori ma

non sa nulla delle carte possedute dagli altri giocatori. Tutti i giochi con mosse simultanee sono

giochi a informazione incompleta.

e. I giocatori possono sottoscrivere accordi vincolanti oppure operare indipendentemente l’uno

dall’altro.

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 3

2. Giochi in forma estesa

La descrizione formale di un gioco non cooperativo si fa in due modi: in forma estesa e in forma

normale o strategica.

Nella forma estesa la descrizione del gioco è fatta con un albero.

Un albero è un grafo connesso privo di circuiti.

Esempio 2 in forma estesa: fiammiferi

Se i giocatori si comportano razionalmente il vincitore di questo gioco sarà sempre il secondo giocatore.

Esempio 3: il dilemma dell’ombrello

Piero e Silvia stanno per uscire di casa e devono decidere se portare l’ombrello.

La vincita di ciascun giocatore è

0 se affronta la pioggia senza ombrello

6 se affronta la pioggia con l’ombrello

8 se prende l’ombrello in una giornata di sole

12 se lascia l’ombrello in una giornata di sole

Piero apprende che tempo farà prima di uscire di casa. Silvia osserva che cosa fa Piero.

Esplicitare in forma estesa il gioco.

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 4

Esempio 4: evasione fiscale

Il governo intende ridurre l’evasione fiscale. Una legge consente di punir soltanto un evasore fiscale

all’anno, che dovrà pagare dieci volte la tassa dovuta. La Guardia di Finanza procede in ordine

alfabetico; se il primo ha pagato le tasse passa al secondo, se il secondo è un evasore non indaga più,

altrimenti passa al terzo.

Disegnare la forma estesa del gioco nell’ipotesi di tre contribuenti: Abate, Bianchi, Caroli.

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 5

Esempio 5: lavori in giardino

Il papà ha bisogno di fare alcuni lavori in giardino, propone ai figli Andrea ed Emanuele di aiutarlo in

cambio di un gioco per PlayStation. I ragazzi stimano che il gioco valga 3 ore di lavoro, inoltre hanno al

massimo 5 ore disponibili. Il padre propone il seguente meccanismo di decisione: Andrea, il più grande

comincia, se vuole, a offrire un’ora di lavoro, poi viene il turno di Emanuele che può aggiungere

un'altra ora di lavoro o rinunciare. Se Emanuele rilancia, tocca ad Andrea decidere se aggiungere ancora

un’ora o rinunciare. Chi rinuncia perde il premio ma deve comunque pagare la sua ultima offerta.

Questo metodo permetterà al padre di ottenere di più di quanto vale il gioco in premio?

La forma estesa del gioco è

Partiamo dalla fine del gioco.

Quando Andrea si trova nell’ultimo nodo e deve scegliere se rilanciare o rinunciare è ovvio che deciderà

di rilanciare, in questo modo perderà 2 invece di perdere 3.

Per cui, quando Emanuele si trova al penultimo nodo dovrà decidere tra le alternative (0,-2) e (-2,-4),

ossia deve decidere se perdere 2 o perdere 4, quindi sceglierà di perdere 2.

Ma quindi al nodo precedente Andrea deve scegliere tra la soluzione (-1,1) e (0,-2) perciò sceglierà (0,-

2).

Allora, al nodo precedente Emanuele dovrà scegliere tra (0,0), (0,2), se Andrea rinuncia e tra (2,0) e (0,-

2) se Andrea offre 1 ora. Nel primo caso Emanuele sceglie (0,2), nel secondo sceglie (2,0).

Al primo nodo Andrea sa che se rinuncia la soluzione sarà (0,2) se offre 1 ora la soluzione sarà (2,0).

Quindi sceglie di offrire 1 ora ed Emanuele sceglie di ritirarsi dal gioco.

Il padre quindi avrà un’ora di lavoro in cambio di un premio del valore di 3.

Questo procedimento si chiama induzione a ritroso.

Esempio 6: gioco del tris

In un quadrato 3x3 due giocatori selezionano a turno una casella, scrivendoci sopra “O” o “X”. Vince

chi per primo completa con il proprio simbolo una riga, una colonna o una diagonale.

Data la simmetria della figura l’albero è

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 6

Esempio 7: morra cinese

Due giocatori devono scegliere contemporaneamente tra Sasso, Forbice, Carta. Se i due giocatori

scelgono lo stesso segno, la partita è pari. Altrimenti, sasso vince su forbice, forbice vince su carta e

carta vince su sasso.

Il gioco della morra cinese, a differenza dei giochi precedenti, non è a informazione perfetta. Poiché i

due giocatori scelgono contemporaneamente il segno, il secondo giocatore in realtà non sa cosa ha

scelto il primo e quindi non sa in quale nodo del ramo si trova.

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 7

Esempio 8: Il dilemma del prigioniero

Due individui sospettati di un crimine vengono arrestati e interrogati separatamente. Se uno denuncia

l’altro sarà liberato e l’altro sconterà 7 anni di prigionia. Se entrambi si denunciano a vicenda saranno

condannati entrambi a 5 anni con una riduzione della pena. Se nessuno dei due parla saranno entrambi

condannati a 1 anno per reati minori.

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 8

3. Giochi in forma strategica

Nella forma normale o strategica (introdotta da Morgenstern e Nemann) si precisa il numero di

giocatori, lo spazio delle strategie e la funzione di utilità di ciascuno giocatore.

{ }

∏ → ∈

N , X , f : X , i N

DEF: Si chiama gioco in forma strategica l’insieme i i i

{ }

1, 2,...n è l’insieme dei giocatori

N =

X è l’insieme delle scelte possibili, dette strategie, del giocatore i

i

f (x ,x ,…,x ) è il guadagno del giocatore i se il giocatore 1 usa la strategia x , il giocatore 2 usa la

i 1 2 n 1

strategia x , …, il giocatore n usa la strategia x .

2 n

Esempio 2 (fiammiferi) in forma strategica

Proponiamoci ora di scrivere il gioco dei fiammiferi in forma strategica.

Elenchiamo tutte le strategie

Giocatore 1

strategia 1: sceglie 2, se si trova in 4 sceglie 9

strategia 2: sceglie 2, se si trova in 4 sceglie 10

se si trova in 5 o in 6 non ha strategie possibili da scegliere, il suo gioco è forzato dalle scelte

dell’avversario

strategia 3: sceglie 3

Giocatore 2

strategia 1: se si trova in 2, sceglie 4; se si trova in 3, sceglie 7

strategia 2: se si trova in 2, sceglie 4; se si trova in 3, sceglie 8

strategia 3: se si trova in 2, sceglie 5; se si trova in 3, sceglie 7

strategia 4: se si trova in 2, sceglie 5; se si trova in 3, sceglie 8

strategia 5: se si trova in 2, sceglie 6; se si trova in 3, sceglie 7

strategia 6: se si trova in 2, sceglie 6; se si trova in 3, sceglie 8

1 (4+7) 2 (4+8) 3 (5+7) 4 (5+8) 5 (6+7) 6 (6+8)

1 (2+9) (1,-1) (1,-1) (-1,1) (1,-1) (1,-1) (-1,1)

2 (2+10) (-1,1) (1,-1) (-1,1) (-1,1) (1,-1) (-1,1)

3 (3) (-1,1) (-1,1) (-1,1) (1,-1) (1,-1) (1,-1)

Poiché il giocatore 1 sceglie le righe non potrà mai scegliere una riga nella quale vince sempre. Il

giocatore 2, invece, indipendentemente dalla riga scelta dal primo giocatore può sempre scegliere la

colonna 3 e vincere in ogni caso.

Esempio 7 (morra cinese) in forma strategica

A differenza da quello che può far pensare l’albero del gioco, il giocatore 2 non può scegliere la

strategia in base alla scelta del giocatore 1; il giocatore 2 infatti non sa in quale nodo dell’albero si trova.

La forma strategica prevede 3 strategie per il primo e 3 strategie per il secondo giocatore:

C F S

C 0,0 -1,1 1,-1

F 1,-1 0,0 -1,1

S -1,1 1,-1 0,0

Esempio 8: dilemma del prigioniero

Anche in questo caso il secondo giocatore non sa in quale nodo si trova quando sceglie la propria

strategia C NC

C -5,-5 0,-7

NC -7,0 -1,-1

________________________________________________________________________________________________

A. Bernardo Appunti di Teoria dei Giochi per il corso di 02/02/2006

Modelli Matematici per le Scienze Sociali 9

Osservazione

Il passaggio dalla forma estesa alla forma strategica è sempre possibile nei giochi finiti, ossia si possono

sempre elencare tutte le combinazioni di strategie possibili. Il passaggio inverso invece non è sempre

possibile, e in ogni caso presenta complicazioni non semplici.

4. Giochi a somma zero o di puro antagonismo × →

f : X Y

DEF.: Un gioco a somma zero consiste in un tripla (X, Y, )

X rappresenta lo spazio delle strategie del primo giocatore

Y rappresenta lo spazio delle strategie del secondo giocatore

f è la funzione di pagamento, definita come la quantità f(x,y) (positiva o negativa) che il secondo

giocatore paga al primo quando il primo giocatore gioca la strategia x e il secondo giocatore gioca la

strategia y.

Un gioco a somma nulla tra due persone si rappresenta comunemente mediante una matrice le cui righe

sono intestate al primo giocatore e le cui colonne sono intestate al secondo giocatore. In

(i,j), perché la

corrispondenza alla riga i e alla colonna j, la matrice riporta soltanto la vincita f 1

corrispondente vincita del secondo giocatore è data da f (i,j)=-f (i,j).

2 1

Eliminazione di strategie dominate

Esempio 1

Consideriamo il gioco rappresentato dalla seguente matrice

2 3 3

0 7 1

1 0 2

L’assioma di razionalità permette di affermare che il secondo giocatore non sceglierà mai la terza

colonna, perciò la terza colonna può essere eliminata (passo 1). Analogamente il primo giocatore non

sceglierà mai l’ultima riga, perciò può essere eliminata (passo 2). A questo punto il secondo giocatore

non sceglierà più la seconda colonna, che può essere eliminata (passo 3). Il primo giocatore non

sceglierà più la seconda riga, che può essere eliminata (passo 4).

2 3 3 2 3 2 3 2 2

0 7 1 0 7 0 7 0

1 0 2 1 0

passo 1 passo 2 passo 3 passo 4

Siamo arrivati alla soluzione del gioco con il metodo detto di eliminazione successiva di strategie

dominate. Il primo giocatore vince 2, il secondo paga 2.

Il metodo è consistito nell’eliminazione di righe e/o colonne strettamente dominate, ossia nelle quali

ogni elemento della riga o colonna era più conveniente di ogni corrispondente elemento dell’atra riga o

colonna.

E’ possibile anche eliminare strategie che sono soltanto debolmente dominate. Vediamo un esempio

2 4 2 4 2 4 2

1 0 0 0 0 5 2 5 2 2

2 5 2 5 2

In questo caso, è stata preferita la riga 5,2 alla riga 4,2 sebbene 5>4 ma 2 non è maggiore di 2. La riga 2

dunque domina debolmente la riga 1. Questo tipo di eliminazione può f