File per prepararsi all’esame orale di teoria dei giochi e delle decisioni (con domande frequenti)

Teoria dei giochi

Ci sono diversi decisori le cui decisioni interagiscono tra loro, si elaborano strategie in una situazione di interazione.

Storia

Von Neumann (1928, ungherese) scrive un articolo per una rivista tedesca che riguarda il teorema del minmax da cui nasce la teoria dei giochi. Durante la seconda guerra mondiale, vari personaggi (tra cui Von Neumann, Turing e Zuse) in ambito matematico studiano il computer.

Turing (inglese) crea la macchina di Turing che in seguito decifrerà i codici tedeschi. Zuse (industriale tedesco) studia una macchina Relè, viene mandato al fronte. Von Neumann e Zuse si incontrano negli Stati Uniti e nasce l'ENIAC, ovvero il primo computer sotto segreto militare:

• Risoluzione del problema di Enigma (codici segreti tedeschi)
• Applicazioni militari della teoria dei giochi, esempio per il problema dei convogli nell’oceano Atlantico (problema di strategie e percorsi)

Nel 1944 nasce la teoria dei giochi applicata all’economia. Von Neumann si trasferisce all’università di Pristol dove incontra l’economista Morgenstern e nasce il libro "Theory of Games and Economic Behavior" che rivoluziona le scienze economiche di quegli anni. Sempre in quest’anno, Von Neuman e Morgenstern inventano gli stable set, che diedero dei problemi in quanto esistevano dei giochi con insiemi degli instale set vuoti (non danno sicurezza per trovare un’imputazione stabile, qualsiasi imputazione può essere messa in crisi da altri giocatori).

Nash nasce in West Virginia, studia a Pristol dove nel 1950 conosce Von Neumann. Giochi a somma zero (che insieme a Morgenstern aveva risolto il problema dei ma non i giochi a somma variabile), giochi inizia a pubblicare articoli dove dà la soluzione ai somma variabile. Giochi a N persone. Nel 1953 non si aveva ancora una soluzione ai (più giocatori), sempre in questi anni viene introdotto il core dalla tesi di laurea di Gilles, Nash introduce la soluzione cooperativa per unità non trasferibile e Shapley introduce il valore a unità trasferibile a N persone. Nascono vari concetti e soluzioni che però sono insoddisfacenti perché non danno una risposta di esistenza e unicità della soluzione.

"Fase Gutemberg", Owen è conosciuto come della teoria dei giochi perché il suo libro è stato tradotto in molte lingue promuovendo molti sviluppi in diverse discipline.

Valore di Shapley

Introduce il concetto di valore del gioco che garantisce un’imputazione nei giochi a unità trasferibile, valore dotato di esistenza e unicità. Assiomi di Shapley: simmetria (la non dipende dalle etichette), efficienza, additività e dummy player (giocatore “manichino”, non conta niente e per ogni coalizione la vincita della coalizione è uguale alla vincita della stessa coalizione privata del dummy player, gli viene assegnata solo la vincita che avrebbe se giocasse da solo).

Proprietà del valore di Shapley: imputazione per giochi superadditivi, core per giochi convessi, monotonicità.

Valore di Nash - Harsanyi

A ogni giocatore viene assegnata la sua vincita da singolo + una costante (k), è un gioco che ha esistenza e unicità della soluzione (la soluzione esiste sempre ed è una), è un gioco poco significativo perché non tiene conto delle vincite intermedie (delle coalizioni). Per calcolare la costante k sommo le vincite eguaglio la somma delle vincite alla vincita della coalizione globale.

Contributo marginale: contributo che un giocatore dà a una coalizione, differenza tra la vincita di un insieme di giocatori e la vincita dello stesso insieme di giocatori privato di un giocatore. Studiando il concetto di contributo marginale si può studiare una ripartizione basata sul contributo marginale.

Valore di Banzhaf (1965)

Presenza di un coefficiente di normalizzazione k (k è esterno) (per far tornare i conti) per la sommatoria dei contributi marginali. Somma di tutti i contributi marginali che l’i-esimo giocatore fornisce a tutte le possibili coalizioni.

Calcolo il totale dei totali dei contributi marginali, si fa una ripartizione dividendo per la stessa cifra, si moltiplica il totale di ciascun giocatore per la vincita della coalizione globale fratto il totale dei totali. Proprietà: imputazione in giochi superadditivi.

Invece di avere il k fuori dalla sommatoria Shapley lo mette all’interno; (S-1)! (n-S)!/n. Il valore di Banzhaf ha gli stessi assiomi di Shapley tranne l’assioma dell’additività che cambia in concordanza con i contributi marginali.

Il valore di Shapley è il più usato per le previsioni, il valore di Banzhaf è invece usato a livello normativo (es. per la ripartizione dei beni). In alcuni casi il valore di Shapley può coincidere con quello di Banzhaf.

Valore di Schmeidler (1969), o nucleulus

È particolarmente adatto per applicazioni di carattere sociale (es. scontentando il meno possibile nelle ripartizioni chi otterrebbe meno), ripartizione che minimizza il massimo rimpianto. Schmeidler era un israeliano.

Giochi

• Competitivi: uno contro gli altri
• Cooperativi: presenza di collaborazioni e problema di ripartizione della vincita. Una soluzione verosimile deve essere tale che ogni singolo giocatore non riceva meno di ciò che riceverebbe giocando da solo

Forme dei giochi

• Normale o strategica: la mossa di ognuno dipende dalle mosse scelte dall’altro, le scelte avvengono in contemporanea, sono rappresentati da una tabella a doppia entrata che rappresenta la matrice delle vincite (righe: mosse giocatore A; colonne: mosse giocatore B). A e B non possono scegliere un esito, possono solo scegliere una strategia che permetterà di ottenere un esito, ogni esito si può dividere in 2 payoff
• Estesa o ad albero: il primo giocatore fa una scelta, poi sceglie il secondo creando così una ramificazione, le scelte sono sequenziali e alla fine della ramificazione troviamo le coppie di vincita
• Caratteristica: tutti i giocatori in un’ipotesi di coalizione globale si mettono insieme, si ha il problema di ripartizione della vincita in base ai contributi che ciascun giocatore ha dato. Solitamente sono cooperativi

Strategie

• Pure: scelta delle mosse. Se la probabilità è 1 per una mossa di conseguenza sarà 0 per l’altra, altrimenti si dice che la strategia è mista. Se maxmin e minmax non puntano allo stesso numero vuol dire che non c’è un punto di sella nelle strategie pure e si passa alle strategie miste
• Miste: scelta delle probabilità sulle strategie pure

Se nei giochi non si ha una mossa di maxmin immediata si fa ricorso alle strategie pure.

Matrici

• Matrice: giochi a somma zero, un solo numero all’interno
• Bimatrice (matrice 2x2): 2 giocatori con 2 mosse ciascuno, 2 coppie di numeri
• Uncorrelated strategies: x1+x2=1 ; y1+y2=1
• Correlated strategies: x1+x2+y1+y2=1

Gioco a somma zero: la vincita di uno è l’opposto della vincita dell’altro, la somma delle due vincite equivale a zero. (quando ci si trova davanti a un gioco a somma zero la prima cosa da fare è calcolare il maxmin)

Fair games: giochi equi, si può intuire che un gioco non è equo se tutti i numeri della matrice sono positivi. Se invece ci fossero numeri positivi e negativi bisogna calcolare la vincita attesa del primo e se non è 0 vuol dire che il gioco non è equo. Da un gioco non equo si può costruire il gioco equo togliendo da ogni numero la vincita attesa.

Gioco a somma costante (constant sum game): la somma delle vincite in tutti i casi è una costante (è sempre lo stesso numero). Per risolvere i giochi a somma costante li trasformo in un gioco equivalente a somma zero, si calcolano le strategie legate ai giochi a somma zero, si calcolano i pagamenti e poi il pagamento viene riportato al pagamento del gioco originale.

Dilemma del terrorista (gioco a somma variabile, la somma dei numeri di ciascuna coppia non è più costante): 2 terroristi sono ospitati in due prigioni diverse e il giudice deve capire come agire. Se un giocatore è pentito e confessa ma l’altro non confessa, la pena scende; se confessano entrambe c’è meno sgravio di pena; se nessuno dei due confessa il giudice non è in grado di risolvere il caso e non vengono incarcerati.

Giochi a forma estesa

Le decisioni vengono prese dai giocatori in sequenza (nei giochi a forma normale le decisioni vengono prese contemporaneamente dai giocatori). Esistono due tipologie:

• Giochi a informazione completa e perfetta (es. centipede game)
• Giochi a informazione incompleta e imperfetta: i giocatori non sanno che gioco stanno giocando, il giocatore 2 non sa che cosa ha scelto il giocatore 1 (e quindi se è andato a destra o a sinistra ma deve comunque prendere una decisione), il giocatore 2 non sa in che posizione del gioco si trova ma deve comunque prendere una decisione -> la soluzione era già stata proposta da Von Neumann e Morgenstern nel libro "The theory of games and economic behavior" (1944) ovvero trasformare questo gioco in un gioco corrispondente in forma normale (nel quale va poi trovata la soluzione competitiva)
• Giochi a memoria imperfetta: il giocatore non sa le mosse che lui ha fatto in precedenza (gioco abbastanza raro)

Giochi dinamici: giochi in cui si tiene i...