Giochi a somma zero

 Pietro Bonfigli

 

In questo articolo andremo ad analizzare i giochi con due competitori e a somma zero. Vedremo che si possono ottenere risultati convincenti e molto eleganti; infatti non sussistono quei paradossi che possono verificarsi nei giochi non a somma zero.
Cominciamo dai giochi finiti, descritti da una matrice in cui il primo giocatore sceglie le righe e il secondo le colonne. Questo va a determinare un elemento aij della matrice che determina quanto il secondo giocatore paga al primo, in senso algebrico ovviamente.

 
Esempio 1
234
071
105

In questo caso se il primo giocatore sceglie la terza riga e il secondo giocatore sceglie la terza colonna si ottiene che il secondo dovrà pagare 5 al primo.
Diamo adesso una definizione precisa di giochi a somma zero.
Definizione 1 ... Un gioco a somma zero consiste in una tripla:

(X, Y, f: X % Y D Å)
dove X rappresenta lo spazio delle strategie del primo giocatore, Y lo spazio delle strategie del secondo giocatore ed f è la funzione di pagamento così definita: Se il primo giocatore gioca x ed il secondo gioca y, f(x,y) è quanto paga il secondo giocatore al primo.
Nel caso dei giochi finiti, scritti in forma di matrice, la scelta di una riga rappresenta una strategia x e quella di una colonna una strategia y.
Analizzando il gioco, se il primo giocatore applica la strategia x si aspetta di ottenere almeno:

infy f(x,y)
Questo numero dipende chiaramente da x, cioè dalla strategia che sceglierà.
Quindi chiaramente cercherà di ottenere:

supx infy f(x,y)

Dualmente, il secondo giocatore ottiene :

infy supx f(x,y)

Che risulta il valore "massimo" che egli si aspetta di dover pagare.
Introduciamo adesso un teorema molto utile.

Teorema 1.

infy supx f(x,y) <= supx infy f(x,y)

DIMOSTRAZIONE.
Infatti

infy f(x,y) <= f(x,y) <= supx f(x,y)

Quindi passando al sup su x a sinistra e all' inf su y a destra si ottiene la tesi.
Analizziamo adesso alcuni esempi.

 
Esempio 1
234
071
105

Ci chiediamo adesso quali siano le possibili strategie per i due giocatori. Iniziamo dicendo che il secondo giocatore è portato ad eliminare la terza colonna della matrice; infatti la prima colonna rappresenta, a parità di strategie del primo giocatore, una strategia che porta ad avere una perdita minore.
Quindi si ottiene la seguente matrice ridotta
 
23
07
10

Ragionando in maniera simmetrica si ha che il primo giocatore non sceglierà la terza riga. Otteniamo ancora una riduzione della matrice.
 
23
07

Iterando il ragionamento eliminiamo la seconda colonna e abbiamo
 
2
0

Chiaramente in questa situazione il primo giocatore sceglierà il 2 e questo è una soluzione del nostro gioco.
Questo metodo di lavoro è detto ad eliminazione delle strategie dominate.

Consideriamo adesso la matrice

 
Esempio 2
14125
81413
71612
1324

Con la prima eliminazione otteniamo
 
14125
81413
71612

Iterando si arriva ad avere
 
145
813
712

E successivamente
 
145
813

A questo punto ci fermiamo perché non abbiamo più strategie dominate e quindi non possiamo trovare soluzione.
Analizzando la prima matrice ci rendiamo conto che il valore 2 soddisfa l'equazione

maxx miny f(x,y) = miny maxx f(x,y)

Infatti in caso di giochi finiti si ha che la coppia (x,y) è soluzione se soddisfa l'equazione precedente.
Vi possono essere situazioni, come nell'esempio due, in cui non si arriva ad avere un punto di equilibrio, ci chiediamo come ci si possa comportare in questi casi. Il seguente esempio ci chiarirà meglio le idee.

 
Es.3
-11
1-1

Chiaramente il gioco non ha equilibrio, si può allora ricorrere ad una distribuzione di probabilità.
Con distribuzione di probabilità intendiamo una n-upla x, ..., xn con xi >0 tale che
In questo caso il problema diventa
 
 q1-q
p-11
1-p1-1

Il gioco può essere descritto in questo modo

 p in [0,1]
q in [0,1]
F(p,q) = pq (-1) + p(1-q)(1) + (1-p)q(1)+(1-p)(1-q)(-1)

Questo nuovo gioco è detto estensione del gioco precedente.
Grazie a Von Neumann abbiamo il seguente utile teorema.
Teorema 2.

Ogni gioco finito a somma zero a due giocatori ammette equilibrio in strategie miste.
Vediamo una applicazione di questo teorema

 
Esempio 4
1356
4532

Consideriamo i quattro punti

(1,4)
(3,5)
(5,3)
(6,2)

Consideriamo l'insieme C che rappresenta il più piccolo convesso che contiene i quattro punti, questo rappresenta l'insieme dei possibili pagamenti quando il secondo giocatore usa strategie miste.
Per esempio il punto (2, 9/2) appartiene a C ed è ottenuto assegnando probabilità alla prima ed alla seconda colonna e zero alle altre.
In questo caso il primo giocatore dovrà scegliere p in modo da massimizzare

2p + 9/2 (1-p)

e chiaramente sceglierà p=0. Quindi il secondo giocatore dovrà cercare di trovare un punto avente coordinate piccole sapendo che il primo giocatore potrà sempre garantirsi il pagamento della maggiore.
Definiamo adesso

Qt ={ (x,y) : x <= t, y <= t}

Von Neumann afferma che esiste t* tale che

Qt* Ç c ¹ 0
e
Qt* Ç c = 0 " t<t*
e che t* è il valore di equilibrio del gioco e che quindi determina la strategia del secondo giocatore.

Applichiamo questa teoria all'esempio precedente

 
1-1
-11

L'estensione del gioco considera i punti

(1,-1)
(-1,1)

e quindi si ottiene che il convesso C è il segmento congiungente i due punti.
Si verifica banalmente che t* = 0 soddisfa le condizioni del teorema, infatti

Qt* Ç c ¹ 0

grazie al punto (0,0) e

Qt* Ç c = 0 " t<t*

Dal teorema otteniamo che il punto t*=0 è il valore di equilibrio del gioco e che la strategia del secondo giocatore è determinata dalla equazione

(1)q + (-1) (1-q) = 0

da cui si ottiene q = , che tradotto significa scegliere tra le due strategie con uguale probabilità.
Da questo otteniamo che

 F(p,q) = pq (-1) + p(1-q)(1) + (1-p)q(1)+(1-p)(1-q)(-1)

con q = implica

 F(p,q) = 0 " p

Questo determina che il primo giocatore mediamente avrà guadagno nullo indipendentemente dalla strategia usata.
Infatti questa semplice matrice rappresenta il gioco del "pari e dispari" che si giocava da bambini ed ora abbiamo dimostrato che non esistono strategie vincenti se uno dei due giocatori gioca pari o dispari in modo totalmente casuale.