1

TEORIA DEI GIOCHI SU RETI

Molti problemi reali di tipo tecnico-economico si risolvono mediante una ottimizzazione associata

ai flussi su una rete. In queste lezioni vedremo una particolare forma di ottimizzazione, la teoria dei

giochi.

In un normale problema di ottimizzazione, il decisore vuole massimizzare o minimizzare una certa

funzione (detta funzione obiettivo), agendo sulle variabili che ne determinano il valore. Un gioco è

un problema di ottimizzazione più complesso, in cui l’esito per ciascun decisore (giocatore)

dipende, oltre che dalle sue scelte, da quelle degli altri giocatori, ciascuno dei quali sta a sua volta

cercando di ottimizzare la propria funzione obiettivo. Per esempio, il giocatore i cerca di

massimizzare la funzione:

zi = fi(x1, x2,…, xi, …, xn)

ma controlla solo la variabile xi, mentre le rimanenti variabili appartengono rispettivamente al

giocatore 1, al giocatore 2 e così via. La teoria dei giochi è un settore di ricerca relativamente

giovane (si è formata a partire dagli anni ’40, grazie al contributo di due dei più brillanti matematici

del ‘900, Janos Neumann e John Nash). Ancora più recente è l’idea di applicare la teoria dei giochi

alle reti: il primo convegno su GameNets (game theory for networks) si è tenuto a Pisa nel 2006.

Formalmente, un gioco G è dato da:

G = {N; S1, S2, … Sn; z1, z2, … zn}

dove

N = {1, 2, …, n} è l’insieme dei giocatori

Si è l’insieme delle strategie a disposizione del giocatore i

zi è la funzione obiettivo del giocatore i (se non diversamente specificato, supporremo che si tratti

sempre di un guadagno, da massimizzare).

Si dicono giochi finiti i giochi con un numero finito di strategie e di giocatori. In particolare, un

gioco finito con due soli giocatori, in cui il giocatore I ha a disposizione le m strategie a1,…, am e il

giocatore II ha a disposizione le n strategie s1,…, sn, può essere rappresentato dalla seguente

bimatrice:

II

I s1 … sj … sn

a1

…

ai v(ai, sj)

z(ai, sj)

…

am

dove z(ai, sj) è il guadagno di I e v(ai, sj) il guadagno di II.

Assumiamo le seguenti ipotesi:

- le decisioni sono simultanee o comunque indipendenti (nessuno sa cosa sceglie l’altro);

- conoscenza perfetta (ciascun giocatore conosce l'insieme delle strategie possibili e la funzione

obiettivo e gli obiettivi degli altri, gli altri sanno che lo sa, e così via).

2

Consideriamo per esempio due reti televisive che si spartiscano un pubblico di 100 milioni di

spettatori fra le 20 e le 21 di una certa serata, annunciando simultaneamente la programmazione

(film, partita di calcio o varietà).

II

I s1 s2

a1 65

35

85

15

a2 12

85

42

58

a3 62

38

76

24

Si tratta di un gioco a somma costante (o perfettamente antagonistico o di puro conflitto):

z(ai, sj) + v(ai, sj) = c per ogni i e j.

Un caso particolare di un gioco a somma costante è il gioco a somma nulla:

z(ai, sj) + v(ai, sj) = 0 per ogni i e j ⇔ v(ai, sj) = - z(ai, sj) per ogni i e j.

Soluzione di un gioco

Per soluzione si intende l’esito del gioco, in base a un qualche criterio di ottimalità che indichi a

ciascun giocatore quale strategia scegliere.

1) Massimo vettoriale. Dato il gioco:

II

I s1 s2

a1 2

1

0

0

a2 0

0

0

-1

vale

(a1, s1) : max z(ai, sj) e max v(ai, sj).

Ma il fatto che due funzioni distinte assumano il massimo nello stesso punto è del tutto accidentale

(non accade mai, in particolare, nei giochi di puro conflitto). Inoltre, se il punto di massimo non

fosse unico, il raggiungimento del massimo potrebbe risultare problematico, come, per esempio, nel

seguente gioco.

II

I s1 s2

a1 2

1

1

0

a2 0

0

2

1

2) Criterio di dominanza

3

II

I s1 s2 s3

a1 0

5

1

1

2

0

a2 3

3

5

1

1

-2

Qualsiasi strategia scelga il giocatore II, a2 dà al giocatore I un guadagno maggiore o uguale a

quello fornito da a1 (a2 domina a1 in senso debole). Considerando il giocatore II, qualsiasi strategia

scelga I, s2 gli dà un guadagno maggiore di s1 (s2 domina s1 in senso stretto); le coppie di strategie

s2, s3 e s, s3 sono efficienti (nessuna delle due domina l’altra). Eliminando le strategie dominate (in

senso forte o in senso debole), si ottiene il gioco ridotto:

II

I s'2 s'3

a'1 1

1

2

0

In questo caso, il criterio di dominanza non fornisce una soluzione unica, anche se permette di

ridurre il numero di possibili soluzioni. In altri casi, non ci sono strategie dominate, come nel gioco:

II

I s1 s2

a1 2

1

0

0

a2 0

0

1

2

2') Dominanza iterata

Applicando di nuovo il criterio di dominanza (dominanza iterata) al precedente gioco ridotto:

II

I s'2 s'3

a'1 1

1

2

0

si ottiene, in termini del gioco iniziale, la soluzione (a1, s3). L’iterazione è resa possibile dall’ipotesi

di conoscenza perfetta: entrambi i giocatori eliminano non solo le proprie strategie dominate, ma

anche quelle altrui, quindi entrambi si trovano di fronte al gioco ridotto.In questo caso il criterio di

dominanza iterata ha fornito un’unica soluzione. Purtroppo tale soluzione può risultare, come in

questo caso, inefficiente, poiché (a1, s1) darebbe un guadagno maggiore a entrambi i giocatori.

Nel seguente gioco:

II

I s1 s2

a1 3

3

5

0

a2 0

1

1

1

4

la strategia s2 domina s1, ma a1 e a2 non sono confrontabili. Tuttavia, dopo aver eliminato s1, a2

risulta preferibile ad a1. La soluzione ottenuta con il criterio della dominanza iterata è pertanto (a2,

s2).

3) Equilibrio di Nash

II

I s1 s2

a1 0

0

-3

3

a2 -1

1

2

-2

II

I s1 s2 s3

a1 -2

2

-1

1

-3

3

a2 -4

4

2

-2

3

-3

Nel primo gioco non esiste un equilibrio, mentre nel secondo gioco esiste ed è dato da (a1, s2)

(l’esito non dipende dal punto di partenza).

Un equilibrio di Nash è una situazione in cui a nessuno dei due giocatori conviene modificare la

propria scelta, data quella dell'altro giocatore. Si può anche dire che in equilibrio deviazioni

unilaterali dall'equilibrio sono svantaggiose, ovvero ogni strategia è la reazione ottima all’altra.

Formalmente, la coppia di strategie (ai*, sj*) è un equilibrio (di Nash) se:

z(ai*, sj*) ≥ z(ai, sj*) per ogni i

v(ai*, sj*) ≥ v(ai*, sj) per ogni j

ossia se è contemporaneamente il massimo di colonna per z e il massimo di riga per v. Applicando

quest’ultima regola direttamente alla tabella, si ottiene:

a1 a2

s1 s2

a1

s3 s2

a2

5

II

I s1 s2 s3

a1 0

5*

1

1*

2*

0*

a2 3

3

5*

1*

1

-2

Gli eventuali equilibri corrispondono alle caselle in cui entrambi gli esiti sono segnati con

l’asterisco, in questo caso due: (a1, s3) e (a2, s2). Si possono confermare con questo metodo i

risultati già ottenuti nei due giochi precedenti: nel primo non c’è equilibrio, nel secondo ce n’è uno

solo. In conclusione, l’equilibrio di Nash non sempre esiste, e se esiste non sempre è unico. Inoltre,

quando non è unico, non sempre le preferenze dei giocatori riguardo “quale equilibrio scegliere”

concordano, come nel seguente gioco:

II

I s1 s2

a1 2

1

0

0

a2 0

0

1

2

con due equilibri, (a1, s1) e (a2, s2).

Per quanto riguarda il problema dell’esistenza, è almeno in parte risolto dal teorema di Nash (1950):

esiste sempre almeno un equilibrio in strategie miste (ottenute assegnando una distribuzione di

probabilità sull’insieme delle strategie di ciascun giocatore).

L’equilibrio di Nash però, come già il criterio di dominanza, non garantisce l’efficienza.

Dilemma degli “inoltratori”

Consideriamo due trasmettitori A e B, ciascuno dei quali vuole trasmettere alla rispettiva

destinazione C e D un pacchetto di dati per ogni unità di tempo, utilizzando l’altro giocatore come

inoltratore. Per ciascun giocatore il costo di inoltro è 0,3, il beneficio se l’altro inoltra è pari a 1.

Questa situazione può essere rappresentata dal seguente gioco:

II

I s1 s2

a1 0,7

0,7

1

- 0,3

a2 - 0,3

1

0

0

6

L’equilibrio di Nash (a2, s2) è inefficiente. L’ottimo sociale sarebbe dato da (a1, s1), con un

guadagno totale pari a 1,4 (mentre l’equilibrio dà guadagno totale nullo).

Questo tipo di gioco è noto in letteratura come il “dilemma dei prigionieri”. Un esempio tratto dalla

vita reale è dato nel seguente articolo, pubblicato dal Sole 24 Ore nel 2004. Riguarda la

“bancarotta” del governo argentino, non più in grado di rimborsare interamente i titoli di stato, e si

riferisce alla conseguente Opa (offerta pubblica di acquisto) con cui il governo offriva ai creditori

un rimborso pari al 30% del valore iniziale dei titoli.

7

Un problema di traffico

Quando il tempo di percorrenza dipende anche dalla decisione degli altri, per la presenza di effetti

di congestione, il traffico su reti può essere rappresentato come un gioco. Consideriamo una rete

orientata con un nodo iniziale A e un nodo finale B, in cui a ogni ramo ij è associato un tempo di

percorrenza:

Tij(x) = aijx + bij aij, bij ≥ 0

dove x è il numero delle auto che lo percorrono. Indichiamo tale tempo di precorrenza direttamente

sul rispettivo arco (notiamo che AD e CB sono insensibili alla congestione).

Questo problema può essere interpretato come un gioco, in cui ogni auto è un giocatore, le sue

strategie sono i cammini possibili e l’esito (da minimizzare) è il tempo totale di percorrenza.

Supponiamo che il flusso da A a B sia di 4000 auto. I cammini possibili sono ACB e ADB; se tutti

scelgono ACB, ciascuno impiega:

4000/100 + 45 = 85

(lo stesso vale per ADB). Se le auto si dividono a metà, ciascuno impiega:

2000/100 + 45 = 65.

L’equilibrio di Nash è dato dal vettore di n strategie (una per ogni giocatore) tali che ciascuna è la

reazione ottima alle altre, ossia (s1*,…, si -1*, si*, si +1*,…, sn*) tale che:

zi(s1*,…, si-1*, si*, si+1*,…, sn*) ≥ zi(s1*,…, si-1*, si, si+1*,…, sn*)

per ogni i e per ogni si. Tutti e solo gli equilibri di Nash sono i vettori di strategie con

equiripartizione fra i due cammini (per dimostrare che ogni equiripartizione è un equilibrio, basta

osservare che nessun guidatore ha convenienza a deviare; per dimostrare che ogni equilibrio è

l’equiripartizione, basta considerare che altrimenti i due cammini avrebbero tempi di percorrenza

diversi e converrebbe deviare da quello più lento).

8

Consideriamo ora un “miglioramento” della rete, in particolare un nuovo collegamento da C a D,

talmente veloce (e insensibile alla congestione) da avere tempo di percorrenza “nullo”. Ora c’è un

solo equilibrio di Nash, in cui ogni guidatore usa il cammino ACDB, con tempo di percorrenza:

4000/100 + 0 + 4000/100 = 80

con un peggioramento rispetto all’equilibrio precedente. Si tratta di un esempio del seguente

paradosso.

Paradosso di Braess (del traffico). Data una rete di trasporti, il suo ampliamento può peggiorare i

tempi di percorrenza.

Questo paradosso è una conseguenza del fatto che, in un gioco, aggiungere una strategia ad almeno

uno dei giocatori può peggiorare il risultato (dare un equilibrio peggiore per entrambi). Basta

confrontare per esempio gli equilibri ottenuti nei due giochi:

II

I s1 s2

a1 0

-1

1*

0

a2 3*

3*

1

1*

II

I s1 s2 s3

a1 0

-1

1

0

2*

2*

a2 3

3*

1

1*

4*

1