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

A/B

(7, 3) (5, 8)

(4, 7) (6, 0)

Ricerca degli equilibri di Nash - Per ogni colonna, sottolineo il numero di sinistra più alto (7 e 6)

A/B - Per ogni riga, sottolineo il numero di destra più alto (8 e 7)

- Poiché non abbiamo casi di doppia sottolineatura, allora non ci sono

(7, 3) (5, 8)

equilibri di Nash (o strategie di equilibrio di Nash: NESSUNA) nelle strategie

pure.

Quindi non essendoci equilibri di Nash nelle strategie pure, alla domanda

(4, 7) (6, 0) “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 è

A/B min di A

di massimo nella direzione verticale e di minimo nella direzione

orizzontale

(7, 3) (5, 8) 5

Maxmin di A

Nei giochi a somma variabile, anche se vi è un punto di

(4, 7) (6, 0) 4 convergenza/sella nelle mosse di maxmin, le strategie miste

possono migliorarlo per entrambi i giocatori. Quindi

min di B 3 0 procediamo:

Maxmin di B

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

1 1

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 = = 1

1 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 1

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

A/B min di A

1

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

(7, 3) (5, 8) 5

Maxmin di A

strategie pure

- Se D =0, la soluzione per il giocatore B è la sua mossa

2

di maxmin nelle strategie pure

(4, 7) (6, 0) 4

- Se y risulta fuori dall’intervallo [0, 1], la soluzione

per il giocatore B è la sua mossa di maxmin nelle

min di B 3 0 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

4, 7 strategie NON correlate, vediamo come disegnare

7 l’insieme dei pagamenti nelle strategie miste.

- Partendo dalla matrice inziale, su un grafico cartesiano

congiungiamo con segmenti le coppie di punti che

6 corrispondono alle righe della matrice e poi

71 137 congiungiamo le coppie di punti che corrispondono alle

,

12 24 colonne della matrice. A meno di arrotondamenti (linee

5 curve) che non consideriamo, avremo il grafico a

sinistra.

11 14

, - I vertici corrispondono ai pagamenti raggiungibili con

2 3 le strategie pure.

4 - Una volta disegnato il grafico individuiamo la frontiera

Pareto-ottimale (segmento verde).

7, 3

3 - Posizioniamo i nuovi assi aventi origine nel punto di

coordinate v =11/2; v =14/3 (dalla soluzione competitiva

1 2

classica di Nash).

2 - I nuovi assi delimitano una regione ammissibile

(segmenti tratteggiati gialli) in cui è rispettata la

“razionalità individuale”, cioè ove i pagamenti non sono

1 inferiori a quelli che ciascuno otterrebbe con la

soluzione competitiva v =11/2; v =14/3.

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 2

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

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 da 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 + − 83

2 3

1TUC

v = =

2 12

(a , a )

1 2 11 14

13 − + 73

2 3

2TUC

v = =

2 12

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 inziale:

A/B A/B

(5-8=-3)

(7-3=4)

4, -3,

-4 3

(4-7=-3) (6-0=6)

-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 è

A/B min di A

di massimo nella direzione verticale e di minimo nella direzione

orizzontale

4 -3

Maxmin di A

-3

Nei giochi a somma zero, se vi è un punto di convergenza/sella

-3 6 -3 nelle mosse di maxmin, allora abbiamo già trovato la soluzione

del gioco a somma zero.

max di B 4 6 Non avendo trovato un punto di sella, occorre procedere:

Minmax di B 4

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 1

1 21 11 22 12 2 1 x = 1-9/16 = 7/16 y = 1-9/16 = 7/16

a − a a − a 2 2

21 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 inziale 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

9/16 (7, 3) (5, 8)

7/16 (4, 7) (6, 0)

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

7 coordinate v =357/64; v =297/64 (dalla soluzione

1 2

competitiva con minaccia di Nash).

6 (tutta la spiegazione del grafico e seguenti è uguale a

763 1433 quella del punto 2))

,

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. 5

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 da 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 6

ESERCIZIO 2

Risolvere il gioco in forma normale

A/B

(10, 10) (-1, 5)

(5, -1) (0, 0)

Ricerca degli equilibri di Nash - Per ogni colonna, sottolineo il numero di sinistra più alto (10 e 0)

A/B - Per ogni riga, sottolineo il numero di destra più alto (10 e 0)

- Poiché abbiamo casi di doppia sottolineatura, allora ci sono equilibri di

(10, 10) (-1, 5)

Nash nelle strategie pure.

(5, -1) (0, 0)

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 è

A/B min di A

di massimo nella direzione verticale e di minimo nella direzione

orizzontale

(10, 10) (-1, 5) -1

Maxmin di A

Nei giochi a somma variabile, anche se vi è un punto di

(5, -1) (0, 0) 0 convergenza/sella nelle mosse di maxmin, le strategie miste

possono migliorarlo per entrambi i giocatori. Quindi

min di B -1 0 procediamo:

Maxmin di B

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 1

1 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 7

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

1

A/B min di A

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

(10, 10) (-1, 5) -1

Maxmin di A strategie pure

- Se D =0, la soluzione per il giocatore B è la sua mossa

2

di maxmin nelle strategie pure

(5, -1) (0, 0) 0

- Se y risulta fuori dall’intervallo [0, 1], la soluzione

per il giocatore B è la sua mossa di maxmin nelle

min di B -1 0 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