Riassunto esame Teoria dei Giochi e delle Decisioni, prof. Bertini e Gambarelli, libro consigliato "Strategie: introduzione alla Teoria dei Giochi e delle Decisioni", Bertini, Gambarelli, Stach

Teoria dei giochi

Esercizio 1

Risolvere il gioco in forma normale

Ricerca degli equilibri di Nash

• Per ogni colonna, sottolineo il numero di sinistra più alto (7 e 6).
• Per ogni riga, sottolineo il numero di destra più alto (8 e 7).
• Poiché non abbiamo casi di doppia sottolineatura, allora non ci sono equilibri di Nash (o strategie di equilibrio di Nash: nessuna) nelle strategie pure.

Quindi non essendoci equilibri di Nash nelle strategie pure, alla domanda “Quali sono Pareto-ottimali?” la risposta è “nessuna”.

Ricerca di eventuali dominanze

In merito alla soluzione competitiva classica di Nash, iniziamo con le dominanze.

Osserviamo che non ci sono mosse dominate né in orizzontale (giocatore A – numeri di sx guardo le sue coppie di mosse in verticale) né in verticale (giocatore B – numeri di dx guardo le sue coppie di mosse in orizzontale).

Vedi pag. 298.

Se avessimo trovato mosse dominate, avremmo eliminato le righe/colonne dominate, arrivando velocemente alla soluzione.

Troviamo ora le soluzioni competitive classiche di Nash:

Maxmin nelle strategie pure

Punto di sella: quando il punto di convergenza delle mosse di maxmin è di massimo nella direzione verticale e di minimo nella direzione orizzontale.

Maxmin di B.

Nei giochi a somma variabile, anche se vi è un punto di convergenza/sella nelle mosse di maxmin, le strategie miste possono migliorarlo per entrambi i giocatori. Quindi procediamo:

1) Soluzione competitiva classica di Nash

a b a b D = 4-7-6+5 = -4 D = 7-3-0+8 = 12

11 11 12 12 [ ] 1 2 a b a b 21 21 22 22 x = (4-6)/(-4) = 1/2 y = (8-0)/12 = 2/3

D = a − a − a + a D = b − b − b + b 1 21 11 22 12 2 21 11 22 12 x = 1-1/2 = 1/2 y = 1-2/3 = 1/3

2 2 a − a b − b 21 22 12 22 v = 7/3+5/6+4/3+1 = 11/2

x = = 11 1 D D v = 1+4/3+7/3+0 = 14/3

1 2 2

Strategie competitive:

x = 1 − x y = 1 − y 2 1 2 1 x =1/2 x =1/2 y =2/3 y =1/3 v =11/2 v =14/3

1 2 1 2 1 2 = x a + x a + x a + x a 1 1 1 11 1 2 12 2 1 21 2 2 22

= x b + x b + x b + x b 2 1 1 11 1 2 12 2 1 21 2 2 22

Se D=0 o se fuori [0, 1], allora strategie pure.

N.B!

Se D=0 oppure se il giocatore ottiene x o y fuori dall’intervallo [0, 1], occorre passare alle strategie pure:

• Se D =0, la soluzione per il giocatore A è la sua mossa di maxmin nelle strategie pure.
• Se x risulta fuori dall’intervallo [0, 1], la soluzione per il giocatore A è la sua mossa di maxmin nelle strategie pure.
• Se D =0, la soluzione per il giocatore B è la sua mossa di maxmin nelle strategie pure.
• Se y risulta fuori dall’intervallo [0, 1], la soluzione per il giocatore B è la sua mossa di maxmin nelle strategie pure.

Maxmin di B.

2) Soluzione cooperativa di Nash (NTU – utilità non trasferibile)

5, 8

8 - Poiché il testo dell’esercizio fa riferimento alle strategie non correlate, vediamo come disegnare l’insieme dei pagamenti nelle strategie miste.

4, 7

7 - Partendo dalla matrice iniziale, su un grafico cartesiano congiungiamo con segmenti le coppie di punti che corrispondono alle righe della matrice e poi congiungiamo le coppie di punti che corrispondono alle colonne della matrice. A meno di arrotondamenti (linee curve) che non consideriamo, avremo il grafico a sinistra.

6 71 137 , 12 24

5 11 14 , 2 3

4 - I vertici corrispondono ai pagamenti raggiungibili con le strategie pure.

7, 3

3 - Una volta disegnato il grafico individuiamo la frontiera Pareto-ottimale (segmento verde).

- Posizioniamo i nuovi assi aventi origine nel punto di coordinate v =11/2; v =14/3 (dalla soluzione competitiva classica di Nash).

1 2

2 - I nuovi assi delimitano una regione ammissibile (segmenti tratteggiati gialli) in cui è rispettata la “razionalità individuale”, cioè ove i pagamenti non sono inferiori a quelli che ciascuno otterrebbe con la soluzione competitiva v =11/2; v =14/3.

1 6, 0 1 2

0 0 1 2 3 4 5 6 7 8

- Osserviamo inoltre che (agli effetti di una soluzione cooperativa del gioco) qualsiasi punto interno alla regione ammissibile è da scartare, poiché non esiste un altro punto più in alto a destra che è migliore per entrambi i giocatori.

- Dovremo quindi considerare un “sottoinsieme” della frontiera Pareto-ottimale individuato dai nuovi assi, chiamato “Negotiation Set” (segmento della frontiera Pareto-ottimale colorato in giallo).

Partendo dal Negotiation Set ci sono 3 possibilità:

• 1) Il Negotiation Set è composto da un unico punto → quello è la soluzione cooperativa di Nash NTU.
• 2) Il Negotiation Set non delimita una regione ammissibile convessa* a nord-est → non ci sono soluzioni cooperative di Nash NTU.
• 3) Il Negotiation Set delimita una regione ammissibile convessa* a nord-est → cerchiamo il punto di tangenza tra il Negotiation Set e il fascio di iperboli equilatere riferite agli assi con origine nella soluzione competitiva nelle strategie miste.

* Una figura è convessa se, comunque si prendono due punti al suo interno, il segmento che li congiunge è interamente contenuto nella figura, altrimenti è concava.

Nel nostro caso, con riferimento ai nuovi assi, notiamo che a nord-est la regione ammissibile è convessa (non ha concavità), quindi dobbiamo cercare il punto di tangenza (punto nero) tra il Negotiation Set e il fascio di iperboli equilatere riferite agli assi con origine nella soluzione competitiva nelle strategie miste.

La soluzione cooperativa di Nash NTU si calcola quindi nel modo seguente:

Soluzione cooperativa di Nash (NTU)

y − p x − p 2 1 = q − p q − p p = (p , p ) = (5, 8)

2 2 1 1 1 2

{(x )(y )− v̅ − v̅ = k q = (q , q ) = (7, 3)

1 2 1 2 v = 11/2 Δ= 0 1 v = 14/3 2

y 5 41 y−8 x−5 p , p y=− x+=1 2 2 2 3−8 7−5

11 14 11 14 (x − ) (y − ) = k (x − ) (y − ) = k 2 3 2 3 {{ Δ= 0 Δ= 0

q , q 1 2 5 41 5 41 v̅ , v̅ 1 2 y=− x+ y=− x+ 2 2 2 2

11 5 95 11 5 41 14 x (x − ) (− x + ) = k (x − ) (− x + − )=k 2 2 6 2 2 2 3 {{ Δ= 0 Δ= 0

5 41 y=− x+ 355 2 2

−b 355 71 5 71 41 137 12 considerando che Δ= 0 → x= → x = = = y=− ∙ + = 5 355 1045 2a 5 12 ∙ 5 12 2 12 2 24 2

x − x+ −k=0 2 12 12 { Δ= 0

Il punto di tangenza ha quindi coordinate 71/12, 137/24. Notiamo che è sulla frontiera Pareto-ottimale.

N.B!

Può capitare che il punto di tangenza tra il Negotiation Set e il fascio di iperboli, sia esterno al segmento del Negotiation Set (vedi figura sotto). In questo caso il punto va scartato e sostituito con il vertice più vicino.

3) Soluzione cooperativa di Nash (TU – unità trasferibile)

A è l’insieme dei vertici della frontiera Pareto-ottimale. Per calcolare S uso la coppia di numeri che mi dà la maggiore somma, in questo caso (5,8):

È un generico elemento di A a = (a , a ) 1 2 S = 5+8 = 13

v = 11/2 1

s = max (a + a ) 1 2 v = 14/3 2

11 14 13 + − 8 3 2 3 1TUC v = = 2 1 2

(a , a ) 1 2

11 14 13 − + 7 3 2 3 2TUC v = = 2 1 2

1TUC v = (s + v̅ − v̅ )/2 1 2

2TUC v = (s − v̅ + v̅ )/2 1 2

N.B!

1TUC 2TUC Se il Negotiation Set non delimita una regione v , v ammissibile convessa non ci sono soluzioni cooperative di Nash NTU, ma le soluzioni TU ci sono sempre e quindi vanno sempre trovate.

1C 2C v̅ , v̅

1TUC 2TUC v , v → soluzione cooperativa

1C 2C v̅ , v̅ → soluzione competitiva

Soluzioni con minaccia di Nash

Calcolare matrice differenza, per trasformare la matrice iniziale in gioco a somma zero.

Basta sottrarre tra loro ciascuna coppia di numeri della matrice iniziale:

A/B 4, -3, -4 3 -3, 6, 3 -6

Ricerca di eventuali dominanze

In merito alla soluzione competitiva con minaccia di Nash, iniziamo con le dominanze.

Osserviamo che non ci sono mosse dominate né in orizzontale (giocatore A-numeri sx guardo le sue coppie di mosse in verticale) né in verticale (giocatore B-numeri dx guardo le sue coppie di mosse in orizzontale).

Se avessimo trovato dominanze, avremmo eliminato le righe/colonne dominate, arrivando velocemente alla soluzione.

Troviamo ora le soluzioni competitive con minaccia di Nash:

Maxmin nelle strategie pure

Punto di sella: quando il punto di convergenza delle mosse di maxmin è di massimo nella direzione verticale e di minimo nella direzione orizzontale.

Minmax di B.

Nei giochi a somma zero, se vi è un punto di convergenza/sella nelle mosse di maxmin, allora abbiamo già trovato la soluzione del gioco a somma zero.

Non avendo trovato un punto di sella, occorre procedere:

4) Soluzione competitiva con minaccia di Nash

A/B 1 2 a a 1 11 12 a a D = -3-4-6-3 = -16 D = 16 2 21 22 1 2

x = (-3-6)/(-16) = 9/16 y = (6+3)/16 = 9/16

D = a − a − a + a D = − 1 11 21 11 22 12 2 1 x = 1-9/16 = 7/16 y = 1-9/16 = 7/16

a − a a − a 2 221 22 22 12 x = = 1 1 D D 1 2

x = 1 − x y = 1 − y 2 1 2 1

= x a + x a + x a + x a 1 1 1 11 1 2 12 2 1 21 2 2 22

= x b + x b + x b + x b 2 1 1 11 1 2 12 2 1 21 2 2 22

Ora dobbiamo riprendere la matrice iniziale per determinare i pagamenti del giocatore A e B:

9/16 7/16 Quindi le vincite competitive con minaccia saranno:

1T v = 567/256 + 315/256 + 252/256 + 294/256 = 357/64

A/B 2T v = 243/256 + 504/256 + 441/256 + 0 = 297/64

5) Soluzione cooperativa con minaccia di Nash (NTU – utilità non trasferibile)

5, 8

8 Riprendiamo il grafico del punto 2), ma questa volta:

4, 7

- Posizioniamo i nuovi assi aventi origine nel punto di coordinate v =357/64; v =297/64 (dalla soluzione competitiva con minaccia di Nash).

1 2

7 6

(Tutta la spiegazione del grafico e seguenti è uguale a quella del punto 2)),

763 1433 , 128 256

5 357 297 , 64 64

4 7, 3

3 2 1 6, 0

0 0 1 2 3 4 5 6 7 8

Anche in questo caso, con riferimento ai nuovi assi, notiamo che a nord-est la regione ammissibile è convessa (non ha concavità), quindi dobbiamo cercare il punto di tangenza (punto nero) tra il Negotiation Set e il fascio di iperboli equilatere riferite agli assi con origine nella soluzione competitiva con minaccia nelle strategie miste.

La soluzione cooperativa con minaccia di Nash NTU si calcola quindi nel modo seguente (= a punto 2):

Soluzione cooperativa con minaccia di Nash (NTU)

y − p x − p p = (p , p ) = (5, 8)

2 1 1 2 = q − p q − p q = (q , q ) = (7, 3)

1 2 2 2 1 1 { v = 357/64

(x )(y )− v̅ − v̅ = k 1 1 2 v = 297/64 Δ= 0 2

5 41 y−8 x−5 y p , p y=− x+=1 2 2 2 3−8 7−5

357 297 357 297 (x − ) (y − )=k (x − ) (y − )=k 64 64 64 64 {{ Δ= 0 Δ= 0

q , q 1 2 5 41 5 41 v̅ , v̅ 1 2 y=− x+ y=− x+ 2 2 2 2

357 5 1015 357 5 41 297 (x − ) (− x + )=k (x − ) (− x + − ) = k 64 2 64 64 2 2 64 x {{ Δ= 0 Δ= 0

5 41 y=− x+ 3815 2 2

−b 3815 763 5 763 41 1433 128 considerando che Δ= 0 → x= → x = = = y=− ∙ + = 5 3815 362355 2a 5 128 ∙ 5 128 2 128 2 256 2

x − x+ −k=0 2 128 4096 { Δ= 0

Il punto di tangenza ha quindi coordinate 763/128, 1433/256. Notiamo che è sulla frontiera Pareto-ottimale.

6) Soluzione cooperativa con minaccia di Nash (TU – unità trasferibile)

A è l’insieme dei vertici della frontiera Pareto-ottimale. Per calcolare S uso la coppia di numeri che mi dà la maggiore somma, in questo caso (5,8):

È un generico elemento di A a = (a , a ) 1 2 S = 5+8 = 13

v = 357/64 1

s = max (a + a ) 1 2 v = 297/64 2

357 297 13 + − 223 64 64 1TUC v = = 2 32

(a , a ) 1 2

357 297 13 − + 193 64 64 2TUC v = = 2 32

1TUC v = (s + v̅ − v̅ )/2 1 2

2TUC v = (s − v̅ + v̅ )/2 1 2

N.B!

1TUC 2TUC v , v Se il Negotiation Set non delimita una regione ammissibile convessa non ci sono soluzioni cooperative con minaccia di Nash NTU, ma le soluzioni TU ci sono sempre e quindi vanno sempre trovate.

1C 2C v̅ , v̅

1TUC 2TUC v , v → soluzione cooperativa

1C 2C v̅ , v̅ → soluzione competitiva

Esercizio 2

Risolvere il gioco in forma normale

Ricerca degli equilibri di Nash

• Per ogni colonna, sottolineo il numero di sinistra più alto (10 e 0).
• Per ogni riga, sottolineo il numero di destra più alto (10 e 0).
• Poiché abbiamo casi di doppia sottolineatura, allora ci sono equilibri di Nash nelle strategie pure.

Quindi

Strategie di equilibrio di Nash:

x =0 x =1 y =0 y =1 v =0 v =0 (0,0) → 1 2 1 2 1 2

x =1 x =0 y =1 y =0 v =10 v =10 (10,10) → 1 2 1 2 1 2

N.B: se la domanda mi chiede solo le vincite/pagamenti corrispondenti alle strategie di Nash equilibrio nelle strategie pure, la risposta sarà solo: (0,0) e (10,10).

Quali sono Pareto-ottimali?:

Guardo punto 2), devo verificare quale strategia appartiene alla frontiera Pareto-ottimale.

Risposta: x =1 x =0 y =1 y =0 v =10 v =10 (10,10) → 1 2 1 2 1 2

Ricerca di eventuali dominanze

In merito alla soluzione competitiva classica di Nash, iniziamo con le dominanze.

Osserviamo che non ci sono mosse dominate né in orizzontale (giocatore A – numeri di sx guardo le sue coppie di mosse in verticale) né in verticale (giocatore B – numeri di dx guardo le sue coppie di mosse in orizzontale).

Se avessimo trovato mosse dominate, avremmo eliminato le righe/colonne dominate, arrivando velocemente alla soluzione.

Troviamo ora le soluzioni competitive classiche di Nash:

Maxmin nelle strategie pure

Punto di sella: quando il punto di convergenza delle mosse di maxmin è di massimo nella direzione verticale e di minimo nella direzione orizzontale.

Maxmin di B.

Nei giochi a somma variabile, anche se vi è un punto di convergenza/sella nelle mosse di maxmin, le strategie miste possono migliorarlo per entrambi i giocatori. Quindi procediamo:

1) Soluzione competitiva classica di Nash

a b a b 11 11 12 12 [ ] a b a b D = 5-10-0-1 = -6 D = -1-10-0+5 = -6 21 21 22 22 1 2

x = (5-0)/(-6) = -5/6* y = (5-0)/(-6) = -5/6*

D = a − a − a + a D = b − b − b + b 1 11 21 11 22 12 2 21 11 22 12 x = 1+5/6 = 11/6* y = 1+5/6 = 11/6*

2 2 a − a b − b 21 22 12 22 x = = 1 1 D D 1 2

x = 1 − x y = 1 − y 2 1 2 1

= x a + x a + x a + x a 1 1 1 11 1 2 12 2 1 21 2 2 22

= x b + x b + x b + x b 2 1 1 11 1 2 12 2 1 21 2 2 22

Se D=0 o se fuori [0, 1], allora strategie pure.

N.B!

*In questo caso risulta che sia x che y sono fuori dall’intervallo [0, 1], occorre quindi passare alle strategie pure:

• Se D =0, la soluzione per il giocatore A è la sua mossa di maxmin nelle strategie pure.
• Se x risulta fuori dall’intervallo [0, 1], la soluzione per il giocatore A è la sua mossa di maxmin nelle strategie pure.
• Se D =0, la soluzione per il giocatore B è la sua mossa di maxmin nelle strategie pure.
• Se y risulta fuori dall’intervallo [0, 1], la soluzione per il giocatore B è la sua mossa di maxmin nelle strategie pure.

Maxmin di B.

Strategie competitive (dalle strategie pure):

x =0 x =1 y =0 y =1 v =0 v =0 1 2 1 2 1 2

2) Soluzione cooperativa di Nash (NTU – utilità non trasferibile)

11 - Vediamo come