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

TEORIA DEI GIOCHI = scienza dei modelli matematici di interazione strategica.

↓

GIOCO = insieme delle regole che descrivono un’interazione strategica.

↓

Le persone e gli enti coinvolti sono i GIOCATORI = decisori che operano scelte razionali per ottimizzare un

loro obiettivo.

↓

Durante il gioco ogni giocatore riceve un PAGAMENTO/PAYOFF/VINCITA = misura del valore che un giocatore

attribuisce ad un risultato del gioco e la cui entità dipende dalle strategie adottate da tutti.

↓

STRATEGIA = distribuzione di probabilità sulle mosse.

↓

I giochi di distinguono in:

↙ ↘

GIOCHI COOPERATIVI = GIOCHI COMPETITIVI =

I giocatori possono allearsi per aumentare i Ogni giocatore è in conflitto con tutti gli altri e

rispettivi pagamenti quindi sceglie le sue strategie migliori tenendo

conto di quello che possono fare gli altri

↓

I giochi si rappresentano in 3 forme:

↙ ↓ ↘

GIOCHI IN FORMA NORMALE = GIOCHI IN FORMA ESTESA = GIOCHI IN FORMA

Gioco descritto da una bimatrice Gioco rappresentato da un CARATTERISTICA =

di pagamenti e dove si suppone albero, i cui archi rappresentano Gioco descritto mediante

che tutti i giocatori effettuino scelte sequenziali dei giocatori FUNZIONE CARATTERISTICA, ossia

all’inizio del gioco tutte le loro (es. supermercati) una funzione che associa ad ogni

decisioni prevedendo tutti i coalizione di un gioco cooperativo

possibili sviluppi del gioco (es. una vincita. Tale vincita è nulla

offerte i busta chiusa) per la coalizione vuota.

(es. partiti politici)

GIOCHI IN FORMA NORMALE A SOMMA COSTANTE

= giochi in cui la somma dei pagamenti assegnati a tutti i giocatori da ogni possibile strategia ha un valore

costante

GIOCHI A SOMMA ZERO

= giochi a somma costante zero, ossia in cui la somma dei pagamenti assegnati a tutti i giocatori da ogni

possibile strategia ha valore zero.

In particolare, se il gioco è a due persone, la vincita di ciascun giocatore è l’opposto della vincita dell’altro (nella

matrice quindi troverò scritti solo i pagamenti del 1° giocatore, quelli del 2° giocatore so già che sono

l’opposto dei pagamenti dell’altro giocatore).

↓

Esempio gioco a somma zero a due persone: ii

ii 2 , 0 1 , 1 0 , 2

2 , 0 1 , 1 0 , 2 i

i Ipoteticamente i 4 , 0 1, 0, 0,

4 , 0 1 0 0 -1 0 0

pagamenti del II giocatore 3 , 1 2, 1, 0,

3 , 1 2 1 0 -2 -1 0

sarebbero i seguenti 2 , 2 1, 2, 1,

2 , 2 1 2 1 -1 -2 -1

(numeri di destra) → 1 , 3 0, 1, 2,

1 , 3 0 1 2 0 -1 -2

0 , 4 0, 0, 1,

0 , 4 0 0 1 0 0 -1

Pagamenti I e II giocatore

Pagamenti I giocatore

MOSSA = possibile scelta individuale da parte di un giocatore

DOMINANZA DI STRATEGIE/MOSSE = una mossa ne domina un’altra se porta a dei pagamenti non inferiori

all’altra in tutti i casi e in almeno un caso porta ad un pagamento maggiore.

Esempio:

ii ii

In questo caso la mossa (3,1)

2 , 0 1 , 1 0 , 2 2 , 0 1 , 1 0 , 2

i i

del I giocatore domina la

mossa (4,0).

4 , 0 1 0 0 3 , 1 2 1 0

Notiamo che non vi sono

3 , 1 2 1 0 2 , 2 1 2 1

altre mosse dominate né per

2 , 2 1 2 1 1 , 3 0 1 2

il 1° giocatore (orizzontale-

1 , 3 0 1 2 0 , 4 0 0 1

numeri di sx) né per il 2°

0 , 4 0 0 1 Pagamenti I giocatore

giocatore (verticale-numeri

Pagamenti I giocatore di dx).

Eliminando le mosse

dominate otteniamo → 1

MAX-MIN = criterio decisionale pessimistico, che sceglie l’alternativa con il più alto valore fra i più bassi

pagamenti possibili.

Esempio: In questo caso le mosse di maxmin di

ii Min di I

entrambi i giocatori ( ) puntano

,

i

entrambe alla stessa casella.

2, 6, 3, 2

-2 -6 -3

maxmin

Quindi la coppia ( ) si chiama soluzione

7, 5, 4, 4 ,

-7 -5 -4

di I

nelle STRATEGIE PURE = strategie per cui una

8, 0, 1, 0

-8 0 -1

mossa viene adottata con probabilità 1.

Min di II -8 -6 -4

maxmin di II

La posizione individuata si chiama anche PUNTO DI SELLA, perché è di minimo nella direzione orizzontale (7,5,4)

e di massimo nella direzione verticale (3,4,1).

PUNTO DI SELLA = coppia di strategie tali che il valore corrispondente al minimo pagamento per la prima,

coincide con il valore corrispondente al massimo pagamento per la seconda strategia.

Se non esiste un punto di sella nelle strategie pure, bisogna utilizzare le STRATEGIE MISTE (= distribuzioni di

probabilità sulle strategie pure) utilizzando il Teorema di von Neumann o TEOREMA DEL MINIMAX = teorema

che assicura l’esistenza di un punto di sella nei giochi in forma normale a somma zero fra due persone.

Esempio:

B Min di A

La matrice non ha un punto di sella nelle strategie pure (poiché 2 è di

A minimo sia nella direzione verticale [3,2] che orizzontale [2,6]).

3 1 1 maxmin

Quindi usiamo le strategie miste:

di A

2 6 2

Min di B -3 -6

maxmin di B

PROGRAMMAZIONE LINEARE METODO GRAFICO/FORMULE DIRETTE

Utilizzabile sempre. utilizzabile solo per i giochi a somma zero fra 2 persone con

2 sole mosse per ciascun giocatore.

Devo porre i seguenti vincoli: 3 + ≤

3 + 2 ≥ 1 2

1 2 a a

+ 6 ≥ 2 + 6 ≤ 11 12

1 2 1 2

{ { [ ]

+ = 1 + = 1 a a

1 2 1 2 21 22

, ≥ 0 , ≥ 0

1 2 1 2 D = a − a − a + a D = −

v=vincita, w=perdita (valore assoluto) 1 21 11 22 12 2 1

Per risolverle bisogna sostituire le prime due disuguaglianze a − a a − a

21 22 22 12

con uguaglianze, ignorare la quarta disuguaglianza e x = =

1 1

D D

risolvere sostituendo i valori. 1 2

Soluzioni: x = 1 − x y = 1 − y

2 1 2 1

x = 2/3 y = 5/6

1 1

x = 1/3 y = 1/6

2 2

v = 8/3 w = 8/3 = (a − )/

1 12 21 11 22 1

= −

2 1

Soluzioni:

x = 2/3 y = 5/6

1 1

x = 1/3 y = 1/6

2 2

v = 8/3 v = -8/3

1 2

+ vedi pag. 273 (casi a soluzione immediata con dominanze) 2

EQUITA’ DI UN GIOCO

= un gioco a somma costante è equo se la vincita attesa da tutti i giocatori è nulla.

Esempio: Ma può essere trasformato in un corrispondente gioco equo

B Min

I II sottraendo 23/5 a ogni elemento della matrice:

A di A

I 3 7 3 B Min

II 5 4 4 I II

A di A

Min di B -5 -7 I -8/5 12/5 -8/5

Non essendoci punto di sella risolvo con le strategie II 2/5 -3/5 -3/5

miste con programmazione lineare o formule Min di B -2/5 -12/5

dirette e ottengo: V = (1∙-8/5 + 4∙2/5)/(1+4) = 0

A

V = (1∙3+4∙5)/(1+4) = 23/5 V = 0

A B

V = - 23/5

B Volendo può essere trasformato in un gioco a pagamenti interi,

Non è quindi un gioco equo. moltiplicando ogni elemento per 5, strategicamente equivalente:

B I II

A I -8 12

II 2 -3

GIOCHI A SOMMA COSTANTE

= giochi in cui la somma dei pagamenti assegnati a tutti i giocatori da ogni possibile strategia ha un valore

costante (per questo motivo nella matrice dobbiamo scrivere i pagamenti di entrambi i giocatori).

Esempio: Se la somma costante è k, basta sottrarre k/2 a tutti i pagamenti.

ii

In questo caso sottrarre 10/2, ossia 5:

i Utilizzando la regola del

Min di I

ii

2, 8 6, 4

maxmin