Introduzione alla Teoria dei Giochi

Marcello Mastroleo

Homo Ludens – 5° incontro

18 Novembre 2009

La Teoria dei Giochi.

La teoria dei giochi studia i giochi e le loro soluzioni.

Un gioco è una descrizione di una interazione strategica tra dei giocatori.

La soluzione di un gioco è una descrizione dei possibili esiti che possono emergere a partire da esso.

Giochi e giochi.

Tutti i giochi noti (es. dama, scacchi, tris, morra cinese…) sono analizzabili nella teoria dei giochi.

Solitamente però, qui con gioco si indica qualcosa di molto semplice che non ha interesse in quanto tale (es. dama), ma quando estrema astrazione di un fenomeno naturale o sociale.

Vi sono varie famiglie di giochi e ognuna di esse ha caratteristiche proprie che determinano differenti tipi di soluzioni.

In quest’ottica, l’obiettivo della Teoria dei Giochi è quello di parlare di cose complicate con strumenti semplici.

Giochi e giochi.

La prima differenza, che si nota, è a livello procedurale (modo di giocare). Le principali tipologie sono:

1.Giochi in forma strategica: sono dei giochi in cui tutti i giocatori agiscono simultaneamente e indipendentemente (es. Morra Cinese);

2.Giochi in forma estesa: sono giochi in cui si alternano le mosse dei giocatori finché non si raggiunge uno stato di fine (es. Scacchi), questi giochi possono essere visti come una sequenza di problemi decisionali.

Alcuni giochi in forma estesa possono essere rappresentati come giochi in forma strategica.

Giochi e giochi.

Una seconda differenza è legata allo stato informativo che posseggono i giocatori, ovvero:

1. Completa informazione Giochi a informazione perfetta (es. tris);

2. Informazione parziale (incertezza) Giochi a informazione imperfetta (es. asta al secondo prezzo).

I giochi in forma strategica a informazione imperfetta (es. ) sono noti come giochi Bayesiani.

Giochi e giochi.

Un’ulteriore differenza è rappresentata dal concetto di cooperazione:

1. Ogni azione è associata a uno e un solo giocatore Giochi competitivi;

2. Esistono azioni congiunte tra i giocatori Giochi cooperativi.

Ma chi è il giocatore?

La Teoria dei Giochi trova le sue radici nella Teoria delle Decisioni, che generalizza.

Il perno della Teoria delle decisioni (quindi della Teoria dei giochi) è il decisore razionale.

Giocatore Decisore Razionale

Il decisore razionale è colui che sceglie “massimizzando” una relazione di preferenza, che spesso si rappresenta con una funzione di utilità*.

*il passaggio da una relazione di preferenza a una utilità può generare paradossi.

Giochi in forma Strategica.

Un Gioco in forma Strategia è composto da:

1. Un insieme finito di giocatori {1, 2, …, N};

2. Per ogni giocatore i, un insieme non vuoto Ai di azioni possibili;

3. Per ogni giocatore i, una relazione di preferenza ≥i tra i possibili “profili” del gioco.

Un profilo e’ una qualunque N-upla di azioni (a1, a2, …, aN) in A1 × A2 × … × AN.

Esempio.

Esempio di gioco a somma nulla.

La strategia.

Per strategia si intende ciò che il giocatore farà durante il gioco.

Una strategia è quindi composta, a seconda del gioco, da una o più azioni in sequenza.

Si chiama strategia per sottolineare che è frutto di un ragionamento “strategico” ovvero razionale (ricordate il decisore?).

La Dominanza.

L’azione ai del giocatore A domina l’azione aj se, indipendentemente da quello che fanno gli altri giocatori, A preferisce ciò che otterrebbe giocando ai.

Ui(ai,bk) ≥ Ui(aj,bk)

Se ogni giocatore ha una azione che domina tutte le altre, la soluzione del gioco è univocamente

determinata.

Esempio di soluzione.

Cosa succede qui?

Il dilemma del prigioniero.

Simulazione 1

Ogni gruppo sceglie un’azione (Confessa / Non Confessa) e si gioca al Dilemma del Prigioniero.

Vince il gruppo che fa più punti (meno anni di carcere) su 20 partite “secche”.

Cosa è emerso?

…

Simulazione 2

Ogni gruppo deve preparare un elenco di 20 azioni (Confessa / Non Confessa) da confrontarsi simultaneamente in maniera ordinata (l’i-esima azione del Gruppo 1 con l’i-esima del Gruppo 2).

Vince il gruppo che fa più punti (meno anni di carcere) al Dilemma del Prigioniero.

Cosa è cambiato?

…

È stabile l’ottimo?

Equilibrio di Nash

Un equilibrio di Nash è un esito del gioco da cui nessun giocatore ha interesse a spostarsi.

E* = (a1*, a2*, …, aN*) è un equilibrio di Nash se per ogni giocatore i risulta:

Ui(ai*,a-i*) ≥ Ui(ai,a-i*)

per ogni ai diversa da ai*.

Cosa succede con Nash?

Il salto.

L’equilibrio di Nash è dato dalle strategie che minimizzano la massima perdita, piuttosto che il massimo utile.

Ci si riferisce a tale proprietà degli equilibri di Nash come principio del Max/Min.

€

maxa imina− iU i(ai,a−i)

Boxe vs Balletto.

Simulazione 3

Ogni gruppo deve preparare un elenco di 20 azioni (Boxe / Balletto) da confrontarsi simultaneamente in maniera ordinata (l’i-esima azione del Gruppo 1 con l’i-esima del Gruppo 2).

Vince il gruppo che fa più punti al gioco Boxe vs Balletto.

Cos’è cambiato qui?

…

La coordinazione

Boxe vs Balletto è il classico esempio di gioco in cui, sebbene i giocatori sono in competizione, c’è interesse a collaborare in qualche modo. C’è interesse a coordinarsi.

La coordinazione presuppone comunicazione, ma nella teoria dei giochi competitivi è bandita ogni forma di comunicazione.

Come ci si può coordinare senza comunicare?

Equilibrio Correlato.

Gli elementi dell’equilibrio correlato sono 2:

1.Una distribuzione di probabilità P sugli esiti del gioco;

2.Una persona di cui tutti i giocatori si fidano che: Seleziona, in accordo con P, un esito del gioco E; Invia a ogni giocatore i solo ed esclusivamente la

strategia si che determina l’esito E.

Si parla di equilibrio correlato se l’utilità che ogni giocatore si aspetta giocando la strategia raccomandata dalla persona di fiducia è maggiore a quella di deviare da essa.

Equilibrio Correlato.

Ma come si gioca a Morra Cinese?

Il gioco della Morra Cinese la relazione di preferenza data dalla dominanza è contraddittoria, in più non esiste un equilibrio di Nash.

Con gli strumenti visti non è possibile individuare un equilibrio, quindi risolvere il gioco.

Bisogna generalizzare il concetto di strategia per carpire l’essenza del gioco.

Mixed Strategies

Un giocatore usa una mixed strategy se al posto di definire un’azione, definisce una distribuzione di probabilità P tra le possibili azioni con la quale sceglierà a caso l’azione da fare.

Esempio

P(Sasso) = 0.2, P(Carta) = 0.5, P(Forbici) = 0.3

Equilibrio di Nash.

Un equilibrio di Nash, nel caso delle mixed strategies, è sempre una strategia dalla quale i singoli giocatori non anno interesse a deviare.

Quello che cambia ora, è che la strategia non è più una azione ma, una distribuzione di probabilità.

Soluzione: P(Sasso)=P(Carta)=P(Forbici)=1/3

I giochi ripetuti.

Fino ad ora abbiamo analizzato i giochi in forma strategica, in cui non vi è dipendenza dal tempo.

Molto più interessante è il caso in cui lo stesso gioco “istantaneo” si ripete un certo numero di volte avendo la possibilità di osservare ciò che succede (Come si è fatto nella Simulaizone 2 del Dilemma del Prigioniero).

Giochi Ripetuti.

Se si vede un gioco come una interazione tra 2 o più parti, un gioco ripetuto rappresenta una interazione nel tempo.

Qui, non è detto che l’equilibrio istantaneo (l’equilibrio sulla singola istanza) sia preservato per tutta la durata del gioco.

In realtà, la situazione è un po’ più complessa.

Folk Theorems

Se un gioco viene ripetuto, ogni payoff possibile può essere un equilibrio, a patto che i giocatori siano sufficientemente pazienti.

Questo dicono i Folk Theorems che sono stati chiamati così perché, prima di essere dimostrati, sono stati creduti veri per anni.

Tutto è un equilibrio!

Cos’è quindi la reputazione?

La reputazione è legata alla fiducia, in Teoria dei Giochi, la fiducia è associata alla razionalità dei giocatori.

La reputazione è quindi legata al fatto che non sia razionale per un giocatore deviare dall’equilibrio dinamico.

C’è una buona reputazione quando il guadagno futuro che si otterrebbe cambiando strategia (tradendo) è minore di quello generato dall’equilibrio.

Come vi suona?

…