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.
| 2 | 3 | 4 |
| 0 | 7 | 1 |
| 1 | 0 | 5 |
(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.
| 2 | 3 | 4 |
| 0 | 7 | 1 |
| 1 | 0 | 5 |
| 2 | 3 |
| 0 | 7 |
| 1 | 0 |
| 2 | 3 |
| 0 | 7 |
| 2 |
| 0 |
Consideriamo adesso la matrice
| 14 | 12 | 5 |
| 8 | 14 | 13 |
| 7 | 16 | 12 |
| 13 | 2 | 4 |
| 14 | 12 | 5 |
| 8 | 14 | 13 |
| 7 | 16 | 12 |
| 14 | 5 |
| 8 | 13 |
| 7 | 12 |
| 14 | 5 |
| 8 | 13 |
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.
| -1 | 1 |
| 1 | -1 |
| Con distribuzione di probabilità intendiamo una n-upla x, ..., xn con xi >0 tale che |
| q | 1-q | |
| p | -1 | 1 |
| 1-p | 1 | -1 |
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
| 1 | 3 | 5 | 6 |
| 4 | 5 | 3 | 2 |
(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 |
| -1 | 1 |
(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.