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.

Tipi di giochi

I giochi si distinguono in:

• ↙ Giochi cooperativi = i giocatori possono allearsi per aumentare i rispettivi pagamenti.
• ↘ Giochi competitivi = ogni giocatore è in conflitto con tutti gli altri e 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 = gioco descritto da una bimatrice di pagamenti e dove si suppone che tutti i giocatori effettuino all’inizio del gioco tutte le loro decisioni prevedendo tutti i possibili sviluppi del gioco (es. offerte in busta chiusa).
• ↓ Giochi in forma estesa = gioco rappresentato da un albero, i cui archi rappresentano scelte sequenziali dei giocatori (es. supermercati).
• ↘ Giochi in forma caratteristica = gioco descritto mediante funzione caratteristica, ossia una funzione che associa ad ogni coalizione di un gioco cooperativo una vincita. Tale vincita è nulla per la coalizione vuota. (es. partiti politici).

Giochi a somma costante e a somma zero

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: iiii 2, 0 1, 1 0, 2 2, 0 1, 1 0, 2 ii 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.

Mosse e dominanza

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.

Criterio max-min e punto di sella

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 e metodo grafico/formule dirette

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 21 2 a a + 6 ≥ 2 + 6 ≤ 11 121 2 1 2 { { [ ] + = 1 + = 1 a a1 2 1 2 21 22, ≥ 0, ≥ 01 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 − a21 22 22 12 con uguaglianze, ignorare la quarta disuguaglianza e x = = 1 1D D risolvere sostituendo i valori. 1 2.

Soluzioni: x = 1 − x y = 1 − y2 1 2 1 x = 2/3 y = 5/61 1 x = 1/3 y = 1/62 2 v = 8/3 w = 8/3 = (a − )/1 12 21 11 22 1 = −2 1.

Soluzioni: x = 2/3 y = 5/61 1 x = 1/3 y = 1/62 2 v = 8/3 v = -8/31 2 + vedi pag. 273 (casi a soluzione immediata con dominanze) 2.

Equità di un gioco

Equità 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 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.