Giochi a somma zero

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 a_ij della matrice che determina quanto il secondo giocatore paga al primo, in senso algebrico ovviamente.

Esempio 1
2	3	4
0	7	1
1	0	5

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:

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

sup_x inf_y f(x,y)

Dualmente, il secondo giocatore ottiene :

inf_y sup_x f(x,y)

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

Teorema 1.

inf_y sup_x f(x,y) <= sup_x inf_y f(x,y)

DIMOSTRAZIONE.
Infatti

inf_y f(x,y) <= f(x,y) <= sup_x 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
2	3	4
0	7	1
1	0	5

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

2	3
0	7
1	0

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

2	3
0	7

Iterando il ragionamento eliminiamo la seconda colonna e abbiamo

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
14	12	5
8	14	13
7	16	12
13	2	4

Con la prima eliminazione otteniamo

14	12	5
8	14	13
7	16	12

Iterando si arriva ad avere

14	5
8	13
7	12

E successivamente

14	5
8	13

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

max_x min_y f(x,y) = min_y max_x 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
-1	1
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, ..., x_n con x_i >0 tale che

In questo caso il problema diventa

	q	1-q
p	-1	1
1-p	1	-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
1	3	5	6
4	5	3	2

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

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

Von Neumann afferma che esiste t* tale che

Q_t* Ç c ¹ 0
e
Q_t* Ç 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
-1	1

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

Q_t* Ç c ¹ 0

grazie al punto (0,0) e

Q_t* Ç 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.