Giochi non cooperativi con più obiettivi

Se non ci fossero conflitti fra le funzioni obiettivo, una soluzione banale
sarebbe quella ottenibile risolvendo separatamente n problemi di ottimiz-
zazione ``standard. Ma ciò, come appena osservato, non rispecchierebbe la
realtà.
In questa tesi si affronterà, come principale tecnica di soluzione di un proble-
ma di ottimizzazione vettoriale, la ricerca degli ottimi paretiani per applicarla
poi ai giochi multicriteria.
Il motivo per cui si studiano i giochi multicriteria risiede nel fatto che nel-
la vita quotidiana si valutano le situazioni tenendo conto di diversi aspetti
spesso in contrasto tra loro e quindi difficilmente paragonabili.
Ad esempio si può supporre che ci sia un'azienda che deve costruire una
nuova fabbrica: la decisione dovrà tenere conto di molteplici aspetti quali il
costo di costruzione, il costo di manutenzione, problemi di locazione, effetti
sul traffico, inquinamento etc. Si può anche supporre che un'azienda rivale
abbia le stesse intenzioni. In questo modo nasce un conflitto non solo fra gli
obiettivi che entrambe vogliono raggiungere, ma anche tra le due aziende in
quanto alcuni degli obiettivi citati sono legati alla reciproca posizione delle
due fabbriche.
Formalmente un gioco non-cooperativo multicriteria con un numero n finito
di giocatori e un numero finito m di obiettivi è una 2n-upla
G = (X1, . . . , Xn, u1, . . . , un) dove per ogni i ∈ N
• Xi è un insieme non vuoto e rappresenta lo spazio delle strategie pure
del giocatore i;
• ui : X :=
∏
i∈N Xi → Rm è la funzione di utilità del giocatore i.
Supporremo per semplicità che ogni giocatore abbia lo stesso numero m di
obiettivi.
Il problema sarà dunque trovare una soluzione per questo tipo di giochi: in-
fatti il concetto di equilibrio di Nash per i giochi non cooperativi con un unico
obiettivo era definito senza ambiguità come punto fisso di una corrisponden-
za di miglior risposta. Invece nel caso di giochi multicriteria la selezione di
un buon esito è definita in modo meno chiaro.
iv
La tesi si occuperà di tre soluzioni per i giochi multicriteria non cooperativi:
• Gli equilibri di Pareto forti;
• Gli equilibri di Pareto deboli;
• Gli equilibri di Pareto approssimati.
La tesi è divisa in quattro capitoli:
1) Nel primo capitolo vengono richiamati i concetti fondamentali dei giochi
non cooperativi con un obiettivo, che poi verranno estesi al caso di più
obiettivi nei capitoli successivi. Per ulteriori approfondimenti vedere
[10], [12], [13] e [23].
Il capitolo è diviso in cinque paragrafi, il primo dei quali si occupa di dare
la definizione di equilibrio di Nash, evidenziando il fatto che non è garantita
l'esistenza e l'unicità di tale soluzione sulla classe dei giochi finiti e ricordan-
do il fondamentale teorema di esistenza dell'equilibrio di Nash per la classe
delle estensioni miste dei giochi finiti.
Nel secondo paragrafo vengono studiate alcune assiomatizzazioni dell'equi-
librio di Nash per i giochi finiti e per le loro estensioni miste. La strada
assiomatica è un modo di introdurre l'equilibrio di Nash: ci chiediamo quali
ragionevoli proprietà deve soddisfare una soluzione per essere considerata
valida.
Nel paragrafo successivo si definisce un altro tipo di soluzione per i giochi
a un criterio: l'equilibro di Nash approssimato che riveste un ruolo fonda-
mentale nella buona posizione Tikhonov a cui si fa riferimento nel quarto
paragrafo.
Infine, il capitolo si chiude con un cenno ai giochi con potenziale esatto, for-
nendo teoremi di esistenza degli equilibri di Nash e degli equilibri di Nash
approssimati.
v
2) Il secondo capitolo affronta il problema dell'ottimizzazione vettoriale,
vedi, ad esempio, [1], [7] e [20].
Il capitolo è diviso in due paragrafi, il primo dei quali fornisce una breve
descrizione dei principali metodi di ottimizzazione vettoriale, che sono stati
discussi principalmente in [25], [26] e [27].
La ricerca degli ottimi paretiani è la tecnica di ottimizzazione vettoriale af-
frontata in questa tesi e discussa nel secondo paragrafo.
3) Col terzo capitolo, suddiviso in due paragrafi, si entra nel vivo della tesi.
Esso infatti studia i giochi multicriteria, e fornisce due tipi di soluzione
per tali giochi: gli equilibri di Pareto forti e deboli. Vedi anche [18] e
[24] per maggiori dettagli.
Gli equilibri di Pareto sono stati introdotti per la prima volta da Shapley in
[21] nel contesto dei giochi con due giocatori a somma zero con funzioni di
utilità a valori vettoriali. La definizione può essere estesa a classi più generali
di giochi multicriteria, vedi [2]: ed è questo l'argomento del primo paragrafo.
Nel secondo paragrafo alcune assiomatizzazioni dell'equilibrio di Nash per i
giochi finiti a un obiettivo affrontate in [16] e [17] sono estese agli equilibri di
Pareto deboli per i giochi multicriteria finiti. Inoltre si vedrà che gli assiomi
usati in [11], per caratterizzare gli equilibri di Nash per le estensioni miste dei
giochi finiti, non sono sufficienti per identificare univocamente l'equilibrio di
Pareto debole sulla classe delle estensioni miste dei giochi multicriteria finiti:
sarà necessario l'utilizzo di un ulteriore assioma.
4) Infine, col quarto capitolo, suddiviso in quattro paragrafi, si estendono
i giochi con potenziale esatto al caso di più obiettivi e si introduce il
concetto di equilibrio di Pareto approssimato, vedi [15].
In particolare, il primo paragrafo mostra che, nel caso in cui gli spazi di
strategie dei giocatori sono finiti, la classe dei giochi multicriteria con poten-
ziale esatto, possiede almeno un equilibrio di Pareto forte in strategie pure.
vi
vii
Il secondo paragrafo garantisce l'esistenza degli equilibri di Pareto approssi-
mati per i giochi multicriteria con potenziale quando le funzioni potenziale
sono superiormente limitate.
Il paragrafo successivo si occupa dei giochi multicriteria di congestione, in-
trodotti in [19] e successivamente studiati in [8] e [24], evidenziandone il
legame con i giochi con potenziale.
Infine, l'ultimo paragrafo estende l'esempio del duopolio di Cournot al caso
di più obiettivi.
Capitolo 1
Richiami al caso di giochi con un
obiettivo
Lo scopo di questo capitolo è ricordare i concetti noti per i giochi a un obiet-
tivo per vedere poi, nei capitoli successivi, come estenderli al caso di più
obiettivi.
Per ulteriori approfondimenti confronta con [10], [12], [13] e [23].
1.1 Equilibri di Nash
Denotiamo con N = {1, . . . , n} l'insieme finito dei giocatori di cardinalità n.
Definizione 1.1 Un gioco non cooperativo con un numero n finito di gio-
catori e un unico obiettivo è una 2n-upla G = (X1, . . . , Xn, u1, . . . , un) dove
per ogni i ∈ N
• Xi è un insieme non vuoto e rappresenta lo spazio delle strategie pure
del giocatore i ;
• ui : X :=
∏
i∈N Xi → R rappresenta la funzione di utilità
del giocatore i .
1
CAPITOLO 1. RICHIAMI AL CASO DI GIOCHI CON UN OBIETTIVO2
Per alleggerire le notazioni ometteremo di precisare ogni volta che si sta par-
lando di giochi non cooperativi in quanto nel seguito della tesi si prenderanno
in considerazione soltanto questo tipo di giochi, ossia quei giochi nei quali i
giocatori non possono sottoscrivere accordi vincolanti.
Se, oltre ad assumere che N sia un insieme finito, assumiamo anche che
∀i ∈ N , Xi sia un insieme finito si dirà che G è un gioco finito.
Poichè nel seguito si prenderanno in esame diverse classi di giochi, per evitare
confusione denotiamo con Γ1finito la classe dei giochi finiti con un unico obiet-
tivo (dove l'apice indica il numero di obiettivi).
Notazione 1.1 Sia i ∈ N , denotiamo con (xi, x−i) l'elemento appartenente
a X tale che:
• xi ∈ Xi;
• x−i ∈
∏
j∈N\{i} Xj =: X−i.
Le soluzioni più accreditate per questo tipo di giochi sono gli equilibri di
Nash (NE).
Definizione 1.2 Sia G = (X1, . . . , Xn, u1, . . . , un) un gioco. Allora la
n-upla (x˜1, . . . , x˜n) ∈ X è un equilibrio di Nash (NE per brevità) per G se
per ogni i ∈ N si ha:
ui(x˜i, x˜−i) ≥ ui(xi, x˜−i) ∀xi ∈ Xi. (1.1)
Denoteremo con NE(G) l'insieme degli equilibri di Nash per G.
Notiamo che la condizione 1.1 equivale a dire che per ogni i ∈ N si ha:
ui(x˜i, x˜−i) ≥ sup
xi∈Xi
ui(xi, x˜−i). (1.2)
CAPITOLO 1. RICHIAMI AL CASO DI GIOCHI CON UN OBIETTIVO3
Gli equilibri di Nash possono essere caratterizzati come i punti fissi di parti-
colari multiapplicazioni dette ``miglior risposte''.
In generale dati due insiemi X, Y una multiapplicazione da X in Y è una
legge che associa ad ogni elemento di X un sottoinsieme di Y.
Si può esplicitamente osservare che una multiapplicazione può essere a valori
vuoti. Chiameremo corrispondenze le multiapplicazioni a valori non vuoti.
Per trovare i punti fissi delle multiapplicazioni è importante studiarne le
proprietà di continuità. Tuttavia basterà definire i concetti di semicontinuità.
Definizione 1.3 Siano X, Y spazi topologici, F : X ⇒ Y una corrisponden-
za. Si dice che:
• F è superiormente semicontinua (u.s.c.) in x ∈ X se per ogni intorno
aperto V di F (x), esiste un intorno aperto U di x tale che F (x′) ⊆ V
∀x′ ∈ U ;
• F è inferiormente semicontinua (l.s.c.) in x ∈ X se ∀y ∈ F (x) e per
ogni intorno aperto V di y in Y, esiste un intorno aperto U di x in X
tale che F (x′) ∩ V 6= ∅ ∀x′ ∈ U ;
• F è superiormente semicontinua in X se lo è per ogni x ∈ X;
• F è inferiormente semicontinua in X se lo è per ogni x ∈ X;
• F è continua in x ∈ X se è superiormente semicontinua e inferiormen-
te semicontinua in x ∈ X;
• F è continua in X se è superiormente semicontinua e inferiormente
semicontinua in X.
Vediamo alcuni esempi che chiariscono meglio la definizione precedente.
La Figura 1.1 è il grafico di una multiapplicazione superiormente semicon-
tinua, ma non inferiormente semicontinua.
CAPITOLO 1. RICHIAMI AL CASO DI GIOCHI CON UN OBIETTIVO4
Figura 1.1: multiapplicazione u.s.c.
Un esempio, invece, di multiapplicazione inferiormente semicontinua, ma non
superiormente semicontinua (perchè non lo è in x = 0) è il seguente:
F (x) =



[
0, sen 1x
]
se sen 1x ≥ 0
[
sen 1x , 0
]
se sen 1x < 0
{0} se x = 0
Ricordiamo, infine, che data una multiapplicazione F : X ⇒ Y, diciamo che
k ∈ X è un punto fisso per F se k ∈ F (k).
Per ulteriori precisazioni sulla teoria delle corrispondenze rimandiamo a [5].
Definizione 1.4 Sia G = (X1, . . . , Xn, u1, . . . , un) definiamo per ogni i ∈ N
la multiapplicazione Ri : X−i ⇒ Xi dove
Ri(x˜−i) = arg max
xi∈Xi
ui(xi, x˜−i) = {x˜i ∈ Xi : ui(x˜i, x˜−i) ≥ ui(xi, x˜−i) ∀xi ∈ Xi} ,
CAPITOLO 1. RICHIAMI AL CASO DI GIOCHI CON UN OBIETTIVO5
cioè la miglior risposta del giocatore i fissata la strategia x˜−i degli altri gio-
catori.
Chiamiamo
R : X ⇒ X
la multiapplicazione tale che
R = (R1, . . . , Rn).
Allora R è detta `` miglior risposta'' per gli equilibri di Nash del gioco G.
Il seguente teorema afferma quanto precedentemente osservato.
Teorema 1.1 Sia G = (X1, . . . , Xn, u1, . . . , un) un gioco con n giocatori e
sia x˜ ∈ X un profilo di strategie. Allora
• x˜ ∈ NE(G) se e solo se x˜ ∈ R(x¯).
Dimostrazione La tesi segue immediatamente dalla definizione di equilibrio
di Nash e dalla definizione di corrispondenza di miglior risposta per gli equili-
bri di Nash. 
Il seguente esempio vuole essere un'applicazione delle definizioni precedenti.
Esempio 1.1 Consideriamo il gioco G = (X1, X2, u1, u2) ∈ Γ1finito con due
giocatori con matrice dei payoffs data da Tabella 1.1 nella quale
X1 = X2 = {T,B} sono gli spazi di strategie (finiti) del giocatore I e del
giocatore II rispettivamente. Le funzioni di utilità u1, u2 : X1×X2 −→ R del
giocatore I e II rispettivamente sono definite nel seguente modo:
CAPITOLO 1. RICHIAMI AL CASO DI GIOCHI CON UN OBIETTIVO6
u1(T, T ) = 2 u1(T,B) = 0 u1(B, T ) = 4 u1(B,B) = 1
u2(T, T ) = 2 u2(T,B) = 4 u2(B, T ) = 0 u2(B,B) = 1
Quando scriviamo, ad esempio, che u1(T, T ) = 2 significa che se il giocatore
I sceglie T e il giocatore II sceglie T , il giocatore I ottiene un'utilità di 2. Se
scriviamo invece u2(B, T ) = 0 significa che se il giocatore I sceglie B e il
giocatore II sceglie T , il giocatore II ottiene un'utilità di 0.
I \ II T B
T 2 2 0 4
B 4 0 1 1
Tabella 1.1: Dilemma del prigioniero
Si ottiene che: NE(G) = {(B,B)}.
Nell'esempio 1.1 abbiamo visto che esiste un unico equilibrio di Nash, tut-
tavia le proprietà di esistenza e unicità per questo tipo di soluzione non sono
garantite per ogni gioco come mostrano i seguenti esempi.
In particolare vedremo che tali proprietà non sono assicurate per i giochi in
Γ1finito.
Esempio 1.2 Consideriamo il gioco G = (X1, X2, u1, u2) ∈ Γ1finito con due
giocatori con matrice dei payoffs data da Tabella 1.2 nella quale
X1 = X2 = {P,D} sono gli spazi di strategie (finiti) del giocatore I e del
giocatore II rispettivamente. Le funzioni di utilità u1, u2 : X1×X2 −→ R del
giocatore I e II rispettivamente sono definite nel seguente modo: