INTRODUZIONE ALLA TEORIA DEI GIOCHI ANTONIO IANNIZZOTTO Sommario.

(1)

ANTONIO IANNIZZOTTO

Sommario. In questi appunti intendiamo offrire una breve ma rigorosa introduzione alla teoria dei giochi, utilizzabile per i corsi di laurea magistrale o di dottorato di ricerca in matematica. Il corso

`

e incentrato principalmente sugli aspetti teorici della disciplina: definizioni formali di gioco, utilit`a e soluzione; cenni di analisi multivoca; concetto di equilibrio di Nash; giochi statici non-cooperativi e cooperativi; giochi a somma nulla; teoremi di minimax; giochi dinamici; rappresentazione mediante grafi. Infine vengono presentate diverse applicazioni, con particolare attenzione ai modelli economici.

Ringraziamo la Prof.ssa Ornella Naselli, dell’Universit`a degli Studi di Catania, per i molti e preziosi chiarimenti che ci ha offerto su questo argomento.

Indice

Notazioni 2

1. Introduzione: giochi, soluzioni ed equilibri 3

2. Multifunzioni 7

2.1. Multifunzioni fra spazi topologici 8

2.2. Selezioni continue 12

2.3. Punti fissi 15

2.4. Il principio KKM 18

3. Giochi non-cooperativi ed equilibri di Nash 20 3.1. Strategie miste e teorema di Nash 21

3.2. Esempi 24

3.3. Equilibri approssimati 27

4. Giochi a somma nulla e teoria del minimax 29

4.1. Alcuni teoremi di minimax 32

5. Giochi cooperativi 35

5.1. Valore di Shapley 41

5.2. Esempi 45

6. Cenni sui giochi dinamici 47

6.1. Esempi 52

Riferimenti bibliografici 55

Versione del 10 giugno 2017

Dipartimento di Matematica e Informatica Universit`a degli Studi di Cagliari Viale L. Merello 92, 09123 Cagliari, Italy

[email protected]

1

(2)

Notazioni

Introduciamo qui alcuni simboli e notazioni che saranno usati nel seguito:

Insiemi: se X `e un insieme, la sua cardinalit`a si denota |X|. Se X, Y sono insiemi e S ⊆ X × Y , denotiamo per ogni x ∈ X, y ∈ Y

Sx= {y⁰∈ Y : (x, y⁰) ∈ S}, S^y = {x⁰∈ X : (x⁰, y) ∈ S}, inoltre poniamo

S^T = {(y, x) ∈ Y × X : (x, y) ∈ S}.

Sotto- e sopralivelli: se X `e un insieme e f : X → R, denotiamo

f^c = {x ∈ X : f (x) < c}, f^c= {x ∈ X : f (x) 6 c}, fc= {x ∈ X : f (x) > c}, f_c= {x ∈ X : f (x) > c}.

Spazi topologici: in uno spazio topologico (X, τ ), denotiamo σ la famiglia dei chiusi; per ogni A ⊆ X denotiamo int(A) l’interno, cl(A) la chiusura, ∂A la frontiera di A, rispettivamente, e τAla topologia indotta da τ su A; per ogni x ∈ X denotiamo U (x) la famiglia degli intorni di x.

Spazi metrici: in uno spazio metrico (X, d) denotiamo per ogni x ∈ X, S, T ⊆ X d(x, S) = inf{d(x, y) : y ∈ S}, d(S, T ) = inf{d(x, y) : x ∈ S, y ∈ T }, e introduciamo la distanza di Hausdorff

d_H(S, T ) = maxn sup

x∈S

d(x, T ), sup

y∈T

d(y, S)o , e per ogni r > 0

B_r(S) = {x ∈ X : d(x, S) < r}.

Spazi vettoriali: in uno spazio vettoriale (reale) X, per ogni S ⊆ X denotiamo span(S) =nXⁿ

i=1

λixi: n ∈ N, λ¹, . . . λn ∈ R, x1, . . . xn∈ So ,

aff(S) =nXⁿ

i=1

λ_ix_i: n ∈ N, λ1, . . . λ_n∈ R,

n

X

i=1

λ_i= 1, x₁, . . . x_n∈ So ,

conv(S) =nXⁿ

i=1

λixi: n ∈ N, λ¹, . . . λn∈ [0, 1],

n

X

i=1

λi= 1, x1, . . . xn∈ So .

Spazi vettoriali-topologici: ricordiamo che uno spazio vettoriale-topologico è uno spazio vettoriale X, sul quale è definita una topologia tale che le funzioni (x, y) 7→ x + y, (λ, x) 7→ λx sono continue (su R si adotta tacitamente la topologia euclidea); in particolare, ogni spazio normato (X, k · k) è uno spazio vettoriale- topologico; in uno spazio vettoriale-topologico (X, τ ), denotiamo X^∗ il duale topologico di X, per ogni S ⊆ X denotiamo

cc(S) = cl conv(S).

(3)

1. Introduzione: giochi, soluzioni ed equilibri

Chi in cento battaglie riporta cento vittorie, non è il più abile in assoluto; al contrario, chi non dà nemmeno battaglia, e sottomette le truppe dell’avversario, è il più abile in assoluto.

Sun Tzu I primi matematici ad affrontare teoricamente il problema dei giochi furono Zermelo [45] e Borel [3], con particolare enfasi sugli aspetti logici e probabilistici. Tuttavia, il maggior contributo verso la formalizzazione di una teoria matematica dei giochi `e dovuto a Von Neumann [44] (ved.

anche Israel & Mill´an Gasca [18]). La moderna teoria dei giochi rappresenta un tentativo di descrivere le interazioni sociali (specialmente in campo economico) tra soggetti che, in competizione tra loro, effettuano decisioni razionali cercando di ottenere il massimo vantaggio. Lo studio ha finalit`a predittive: determinare, se possibile, la soluzione o le situazioni di equilibrio di un’interazione prima che essa abbia luogo.

Per elaborare un modello di queste interazioni si ricorre al concetto di gioco, che pu`o avere diverse caratteristiche (statico, dinamico, non-cooperativo, cooperativo etc.): questo modello risulta efficace in quanto permette di trascurare tutti gli aspetti dell’interazione non attinenti alla strategia.

La teoria `e stata applicata con successo, oltre che nelle scienze sociali, anche in biologia (evoluzione di popolazioni di microorganismi), elettronica, scienze militari, psicologia e filosofia morale (teoria della scelta razionale). Per un’ampia trattazione della materia rimandiamo alle monografie di Aubin [1], Burger [6], Colombo [12], Gibbons [16], McKinsey [26], Morgenstern [30], Morgenstern

& von Neumann [31], e alla raccolta di saggi di Kuhn & Tucker [25]. Per i collegamenti con l’analisi moderna, rimandiamo a Caffarelli [7], Mot¸, Petrus¸el & Petrus¸el [32], Rossi [39].

Dal punto di vista astratto, la teoria dei giochi costituisce un interessante crocevia di branche mutuamente indipendenti della matematica quali la topologia, l’analisi multivoca, il calcolo delle probabilit`a e la teoria dei grafi.

Introduciamo brevemente le definizioni-assiomi della teoria:

Definizione 1.1. Un gioco è un’interazione tra due o più decisori razionali e intelligenti, detti giocatori. Un decisore è detto

(i) razionale se dispone di una preferenza sull’insieme degli esiti (vedi Definizione 1.2);

(ii) intelligente se persegue senza commettere errori la massima soddisfazione.

Un gioco statico rappresenta una situazione in cui tutti i giocatori effettuano le loro scelte nello stesso momento, mentre in un gioco dinamico i giocatori scelgono secondo un certo ordine temporale, adattando la strategia alle mosse degli altri giocatori. In un gioco deterministico i giocatori scelgono in condizioni di certezza, ovvero sanno che un determinato insieme di strategie conduce invariabilmente a un certo esito, mentre in un gioco stocastico, dato un insieme di strategie, vi sono diversi esiti ciascuno con la sua probabilit`a. In un gioco non-cooperativo i giocatori non possono stringere accordi vincolanti tra loro, mentre in un gioco cooperativo possono. Un gioco statico deterministico non-cooperativo tra un insieme finito di giocatori P₁, . . . P_n(n > 2) `e rappresentato da un complesso

(1.1) Γ = (X1, . . . Xn, E, h),

dove Xi è l’insieme delle strategie del giocatore Pi, E è l’insieme degli esiti e h : Πⁿ_i=1Xi → E è la funzione che associa a ogni n-upla di strategie l’esito corrispondente.

Per compiere le proprie scelte, i giocatori hanno bisogno di un criterio:

(4)

Definizione 1.2. Una preferenza `e una relazione binaria su un insieme E con le seguenti propriet`a:

(i) e e per ogni e ∈ E (riflessiva);

(ii) se e₁ e₂ e e₂ e₃ allora e₁ e₃ per ogni e₁, e₂, e₃∈ E (transitiva);

(iii) e₁ e₂ o e₂ e₁ per ogni e₁, e₂ ∈ E (completa);

(iv) se E `e uno spazio topologico, allora l’insieme {e ∈ E : e e} `e chiuso per ogni e ∈ E (continua).

Se e1 e₂ e non e2 e₁, si scrive e1 ≺ e₂. Se e1 e₂ e e2 e₁, allora e1, e2 sono detti equivalenti (e1 ∼ e₂).

Osservazione 1.3. Una preferenza non `e un ordinamento: manca la propriet`a antisimmetrica!

L’ipotesi di razionalit`a implica che il giocatore Pi dispone di una preferenza i su E. In molti casi (come nelle scommesse), tale preferenza pu`o essere quantificata.

Definizione 1.4. Un’utilità è una funzione u : E → R con le seguenti proprietà:

(i) per ogni e1, e2∈ E, se e₁ e₂, allora u(e1) 6 u(e2);

(ii) per ogni e1, e2∈ E, se e₁ ≺ e₂, allora u(e1) < u(e2).

L’esistenza di una funzione di utilit`a non `e ovvia. Vale in merito il seguente Teorema di Rappresentazione:

Teorema 1.5. (Kreps [24]) Siano E un insieme non vuoto e una preferenza su E:

(i) se |E| 6 ℵ0, allora esiste un’utilit`a u : E → R;

(ii) se |E| 6 2^ℵ⁰, E è uno spazio topologico e è continua, allora esiste un’utilità u : E → R continua.

Assumeremo sempre l’esistenza di un’utilit`a per ogni giocatore. Dunque il complesso (1.1) si riformula come

(1.2) Γ = (X1, . . . Xn, f1, . . . fn),

dove fi = ui ◦ h : Πⁿ_i=1Xi → R `e detta pay-off del giocatore Pi. Nel caso n = 2, usualmente denoteremo P , Q i giocatori e Γ = (X, Y, f, g) e rappresenteremo i possibili risultati del gioco in una (bi)matrice. Questa rappresentazione `e detta in forma strategica (ved. Borel [3]).

Esempio 1.6. Il gioco del pari o dispari prevede due giocatori P (che vince se la somma è pari), Q (che vince se la somma è dispari) con lo stesso insieme di strategie X = Y = {p, d} e due esiti E = {vince P , vince Q}. Ovviamente ogni giocatore preferisce vincere, ergo attribuisce utilità 1 alla vittoria e −1 alla sconfitta. Il gioco è rappresentato dalla tabella simmetrica:

P \Q p d

p (1, −1) (−1, 1) d (−1, 1) (1, −1)

Esempio 1.7. Il gioco della morra cinese (o carta, pietra e forbice) prevede due giocatori P , Q con lo stesso insieme di strategie X = Y = {c, p, f } e tre esiti

E = {vince P , vince Q, pareggio}.

(5)

Per ogni giocatore, la vittoria vale 1, il pareggio 0 e la sconfitta −1. Il gioco `e rappresentato dalla tabella simmetrica:

P \Q c p f

c (0, 0) (1, −1) (−1, 1) p (−1, 1) (0, 0) (1, −1) f (1, −1) (−1, 1) (0, 0)

In casi semplici, possiamo risolvere un gioco (ovvero, determinare come andranno effettivamente le cose) usando la tabella dei pay-off e il seguente concetto di dominazione:

Definizione 1.8. Nel gioco (1.2), siano x_i, y_i ∈ X_i due strategie. Si dice che (i) x_i domina fortemente y_i se per ogni (z₁, . . . z_n) ∈ Π_j6=iX_j si ha

f_i(z₁, . . . x_i, . . . z_n) > f_i(z₁, . . . y_i, . . . z_n);

(ii) xi domina strettamente yi se per ogni (z1, . . . zn) ∈ Πj6=iXj si ha f_i(z₁, . . . x_i, . . . z_n) > fi(z₁, . . . y_i, . . . z_n), ed esiste (z₁, . . . z_n) ∈ Π_j6=iX_j t.c.

fi(z1, . . . xi, . . . zn) > fi(z1, . . . yi, . . . zn);

(iii) x_i domina debolmente y_i se per ogni (z₁, . . . z_n) ∈ Π_j6=iX_j si ha f_i(z₁, . . . x_i, . . . z_n) > fi(z₁, . . . y_i, . . . z_n).

Inoltre, xi `e detta fortemente (strettamente, debolmente) dominante se domina fortemente (strettamente, debolmente) ogni altra strategia di Xi.

Si procede con il metodo delle eliminazioni iterate: ogni giocatore che abbia una strategia fortemente (o strettamente) dominata la elimina, e ciò che resta è la soluzione. In particolare, se P , Q hanno ciascuno una strategia fortemente dominante x, y, la soluzione del gioco sarà la coppia (x, y). Nei giochi considerati negli Esempi1.6,1.7 nessun giocatore ha strategie dominanti. Seguono alcuni esempi di soluzione per eliminazioni iterate per giochi con due giocatori:

Esempio 1.9. Consideriamo il seguente gioco:

P \Q y₁ y₂ x1 (1, 2) (0, 1) x2 (0, 2) (2, 1)

Sia P il primo a giocare: egli osserva che y₁ è per Q una strategia fortemente dominante, quindi sceglie x1 (che gli permette la massima utilità). La soluzione del gioco è pertanto (x1, y1). La stessa soluzione è raggiunta se Q gioca per primo.

P \Q y1 y2

x1 (3, 3) (2, 2) x₂ (0, 2) (1, 1) x₃ (1, 2) (0, 1)

Sia P il primo a giocare: egli osserva che y2 `e fortemente dominata da y1, dunque sceglie x1; la soluzione `e (x₁, y₁). Se Q gioca per primo si perviene alla stessa soluzione.

(6)

P \Q y1 y2

x₁ (3, 5) (2, 5) x₂ (3, 0) (0, 2) x₃ (0, 2) (2, 0)

Osserviamo che in questo gioco non esistono strategie fortemente dominanti. Sia P il primo a giocare: x1 domina strettamente x2 e x3; se P elimina x2, osserva che nel nuovo gioco (ridotto) y₁ domina strettamente y₂, dunque sceglie x₁ e la soluzione `e (x₁, y₁); se invece elimina x₃, un ragionamento analogo porta alla soluzione (x₁, y₂). Se Q gioca per primo si perviene alle stesse soluzioni.

Per risolvere queste ambiguit`a si introduce un concetto di equilibrio analogo a quello in uso in meccanica:

Definizione 1.12. (Nash [34]) Nel gioco (1.2), la n-upla (x1, . . . xn) ∈ Πⁿ_i=1Xi `e un equilibrio di Nash se per ogni i ∈ {1, . . . n} si ha

f_i(x₁, . . . x_n) > fi(x₁, . . . x⁰_i, . . . x_n) per ogni x⁰_i∈ X_i. L’insieme degli equilibri di Nash di Γ si denota Ne(Γ).

Consideriamo il caso n = 2. Nella tabella dei pay-off, un equilibrio di Nash corrisponde a una casella in cui la prima componente è massima tra quelle della stessa colonna e la seconda è massima tra quelle della stessa riga. I giochi degli Esempi1.6, 1.7 non presentano equilibri di Nash. L’unico equilibrio di Nash nell’Esempio1.9 è (x1, y1), nell’Esempio1.10è (x1, y1). Nell’Esempio1.11ve ne sono due: (x1, y1) e (x1, y2). Ne deduciamo che

• un gioco pu`o non avere alcun equilibrio di Nash;

• un gioco pu`o avere pi`u di un equilibrio di Nash;

• una strategia fortemente dominata non pu`o essere componente di un equilibrio di Nash;

• una strategia debolmente dominata pu`o essere componente di un equilibrio di Nash.

Dunque, la risoluzione di un gioco per eliminazione delle strategie fortemente dominate preserva gli equilibri di Nash (se ve ne sono), mentre la risoluzione per eliminazione delle strategie debolmente dominate pu`o sopprimerne alcuni.

Esempio 1.13. Nel gioco noto come battaglia dei sessi, una coppia deve decidere se andare allo stadio (s) o a teatro (t); l’uomo (P ) preferisce andare allo stadio in compagnia che a teatro in compagnia, ma questo `e pur sempre meglio che andare allo stadio da solo; la donna (Q) ha preferenze analoghe. Il gioco `e rappresentato dalla seguente tabella:

P \Q s t

s (10, 5) (0, 0) t (0, 0) (5, 10)

Non vi sono strategie dominanti. Invece gli equilibri di Nash sono (s, s) e (t, t)¹.

Altri equilibri si possono determinare cambiando paradigma, cio`e consentendo a ciascun giocatore di ripartire la sua scelta tra le varie strategie (come uno speculatore che investe parti del suo capitale su diversi titoli, variando gli investimenti secondo le sue aspettative): questa `e la teoria delle strategie miste, su cui torneremo in seguito.

1L’esperienza insegna, tuttavia, che la coppia andr`a a teatro.

(7)

Il problema dell’esistenza (e, in subordine, dell’unicit`a) dell’equilibrio di Nash richiede, per essere risolto, un armamentario matematico alquanto avanzato, che presenteremo nella sua forma pi`u generale.

2. Multifunzioni

Who needs set-valued analysis?

J.P. Aubin & H. Frankowska L’analisi multivoca estende la tradizionale analisi matematica al caso in cui i valori delle funzioni non sono singoli elementi di un insieme bens`ı suoi sottoinsiemi: questa scelta corrisponde all’esigenza di studiare con i mezzi dell’analisi matematica fenomeni caratterizzati da un alto grado di incertezza (come nella teoria dei controlli). Un altro contesto in cui le multifunzioni risultano utili `e lo studio di problemi differenziali con discontinuit`a (ved. Chang [9], Clarke [11] e Filippov [15]), con applicazioni in meccanica. In questa sezione introduciamo le definizioni di base dell’analisi multivoca e alcuni teoremi di selezione e di punto fisso. Per approfondimenti rimandiamo ai testi di Aubin & Frankowska [2] e di Krein & Thompson [23]².

Definizione 2.1. Siano X, Y insiemi non vuoti. Una multifunzione F : X → 2^Y `e una funzione i cui valori sono sottoinsiemi di Y . Si denota

dom(F ) = {x ∈ X : F (x) 6= ∅}, F (S) = ∪_x∈SF (x) per ogni S ⊆ X,

F⁻(T ) = {x ∈ X : F (x) ∩ T 6= ∅}, F⁺(T ) = {x ∈ X : F (x) ⊆ T } per ogni T ∈ 2^Y, gr(F ) = {(x, y) ∈ X × Y : y ∈ F (x)}.

La multifunzione inversa IF : Y → 2^X `e definita per ogni y ∈ Y da I_F(y) = {x ∈ X : y ∈ F (x)}.

Osservazione 2.2. Il concetto di multifunzione `e, a rigore, identico a quello di relazione binaria.

A differenza da quanto avviene per le funzioni (univoche), ogni sottoinsieme di X × Y `e il grafico di una multifunzione. Spesso, tuttavia, si restringe lo studio alle multifunzioni a valori non vuoti (dom(F ) = X).

Alcune propriet`a insiemistiche delle multifunzioni³: Lemma 2.3. Se F : X → 2^Y `e una multifunzione, allora:

(i) X \ F⁻(T ) = F⁺(Y \ T ) per ogni T ∈ 2^Y; (ii) X \ F⁺(T ) = F⁻(Y \ T ) per ogni T ∈ 2^Y; (iii) F⁻(∪_i∈IT_i) = ∪_i∈IF⁻(T_i) per ogni (T_i)_i∈I ⊆ 2^Y;

(iv) F⁺(∩i∈ITi) = ∩i∈IF⁺(Ti) per ogni (Ti)i∈I ⊆ 2^Y; (v) IF(y) = F⁻({y}) per ogni y ∈ Y .

Chiaramente, ogni funzione (univoca) f : X → Y si identifica con la multifunzione F : X → 2^Y definita per ogni x ∈ X da F (x) = {f (x)}.

2Per conseguire la massima generalit`a abbiamo considerato multifunzioni operanti fra spazi topologici astratti, ma nella maggior parte delle applicazioni alla teoria dei giochi `e sufficiente usare multifunzioni fra spazi euclidei.

3In questa sezione riporteremo solo le dimostrazioni pi`u significative, lasciando quelle elementari al lettore.

(8)

2.1. Multifunzioni fra spazi topologici. Ci concentriamo ora sulle multifunzioni operanti fra spazi topologici, rimandando per le nozioni e i risultati di topologia generale a Checcucci, Tognoli & Vesentini [10]. Nel caso multivoco, la nozione di continuit`a ha diverse possibili versioni:

Definizione 2.4. Siano (X, τX), (Y, τY) spazi topologici, x ∈ X, F : X → 2^Y:

(i) F `e semi-continua inferiormente (s.c.i.) in x se per ogni A ⊆ Y aperto t.c. F (x) ∩ A 6= ∅ esiste U ∈ UX(x) t.c. F (x⁰) ∩ A 6= ∅ per ogni x⁰ ∈ U ;

(ii) F `e semi-continua superiormente (s.c.s.) in x se per ogni A ⊆ Y aperto t.c. F (x) ⊆ A esiste U ∈ U_X(x) t.c. F (x⁰) ⊆ A per ogni x⁰ ∈ U ;

(iii) F `e semi-continua in x se per ogni A ⊆ Y aperto t.c. F (x) ⊆ A esiste U ∈ U_X(x) t.c.

F (x⁰) ∩ A 6= ∅ per ogni x⁰∈ U ;

(iv) F `e continua in x se `e s.c.i. e s.c.s. in x;

(v) F `e s.c.i. (s.c.s., semi-continua, continua) in X se `e s.c.i. (s.c.s., semi-continua, continua) in ogni punto di X;

(vi) F `e aperta se F (A) `e aperto per ogni A ⊆ X aperto;

(vii) F `e chiusa se F (C) `e chiuso per ogni C ⊆ X chiuso.

Nel caso univoco, le proprietà(i) - (iii) sono tutte equivalenti alla continuità. Nel caso multivoco, d’altra parte, nessuna di esse implica l’altra in generale, e ciascuna estende alcune particolari proprietà delle funzioni continue. Ricordiamo alcune caratterizzazioni della semi-continuità inferiore (di dimostrazione immediata):

Lemma 2.5. Se (X, τ_X), (Y, τ_Y) sono spazi topologici, F : X → 2^Y, allora le seguenti sono equivalenti:

(i) F `e s.c.i.;

(ii) F⁻(A) `e aperto per ogni A ⊆ Y aperto;

(iii) F⁺(C) `e chiuso per ogni C ⊆ Y chiuso;

(iv) IF `e aperta.

Valgono le analoghe caratterizzazioni della semi-continuit`a superiore:

Lemma 2.6. Se (X, τ_X), (Y, τ_Y) sono spazi topologici, F : X → 2^Y, allora le seguenti sono equivalenti:

(i) F `e s.c.s.;

(ii) F⁺(A) `e aperto per ogni A ⊆ Y aperto;

(iii) F⁻(C) `e chiuso per ogni C ⊆ Y chiuso;

(iv) I_F `e chiusa.

Un caso speciale `e quello delle multifunzioni i cui valori sono intervalli reali:

Lemma 2.7. Se (X, τ ) `e uno spazio topologico, a, b : X → R sono funzioni t.c. a(x) 6 b(x) per ogni x ∈ X e F : X → 2^R `e definita da F (x) = [a(x), b(x)] per ogni x ∈ X, allora le seguenti sono equivalenti:

(i) F `e s.c.i.;

(ii) a `e s.c.s. e b `e s.c.i.⁴

4Una funzione ϕ : X → R è detta s.c.i. se ϕcè aperto per ogni c ∈ R, s.c.s. se ϕ^cè aperto per ogni c ∈ R.

(9)

Dimostrazione. Dimostriamo che (i)implica (ii). Siano c ∈ R, x ∈ a^c, allora F (x)∩]c, +∞[6= ∅.

Poiché F è s.c.s. esiste un intorno U ∈ U (x) t.c. per ogni x⁰∈ U si ha F (x)∩]c, +∞[6= ∅. Dunque a^c è aperto e a è s.c.s. Similmente si dimostra che b è s.c.i.

Dimostriamo che (ii)implica (i). Siano x ∈ X t.c. a(x) < b(x) (per evitare casi banali) e A ⊂ R aperto t.c. F (x) ∩ A 6= ∅. Allora esiste y ∈ A t.c. a(x) < y < b(x). Poiché a è s.c.s. e b è s.c.i. gli insiemi a^y, b_y sono aperti e x ∈ a^y∩ b_y. Dunque esiste U ∈ U (x) t.c. U ⊆ a^y∩ b_y. Abbiamo infine

y ∈ F (x⁰) per ogni x⁰ ∈ U .

Analogamente:

Lemma 2.8. Se (X, τ ) `e uno spazio topologico, a, b : X → R sono funzioni t.c. a(x) 6 b(x) per ogni x ∈ X e F : X → 2^R `e definita da F (x) = [a(x), b(x)] per ogni x ∈ X, allora le seguenti sono equivalenti:

(i) F `e s.c.s.;

(ii) a `e s.c.i. e b `e s.c.s.

Alcuni esempi illustrano le differenze tra le varie nozioni di continuit`a:

Esempio 2.9. La multifunzione F : R → 2^R definita da

F (x) =







{0} se x < 0 [0, 1] se x = 0 {1} se x > 0.

`e s.c.s. ma non s.c.i. Infatti la funzione a : R → R definita da a(x) =

(0 se x 6 0 1 se x > 0

`e s.c.i. ma non s.c.s., mentre b : R → R definita da b(x) =

(0 se x < 0 1 se x > 0

`e s.c.s. ma non s.c.i. (ved. Lemmi2.7,2.8).

Esempio 2.10. La multifunzione F : R → 2^R definita da

F (x) =







[0, 1] se x < 0 {1/2} se x = 0 [0, 1] se x > 0.

`e s.c.i. ma non s.c.s. La dimostrazione `e analoga alla precedente.

Esempio 2.11. Sia g : Rⁿ→ R convessa. `E definito per ogni x ∈ Rⁿ il sub-differenziale

∂g(x) = {y ∈ Rⁿ: y · (z − x) 6 g(z) − g(x) per ogni v ∈ Rⁿ}.

La multifunzione ∂g : Rⁿ → 2^Rⁿ `e s.c.s. Questa multifunzione, insieme alle sue varianti, `e largamente usata nella teoria dell’ottimizzazione per funzioni non derivabili (ved. Clarke [11]).

La semi-continuità è la nozione più debole:

Lemma 2.12. Se (X, τX), (Y, τY) sono spazi topologici, F : X → 2^Y `e s.c.i. o s.c.s. e dom(F ) = X, allora F `e semi-continua.

(10)

Dimostrazione. Supponiamo che F sia s.c.i. (l’altro caso `e simile). Per ogni x ∈ X, A ⊂ Y aperto t.c. F (x) ⊆ A, si ha F (x) ∩ A = F (x) 6= ∅, dunque esiste U ∈ U (x) t.c. per ogni x⁰ ∈ U si ha

F (x⁰) ∩ A 6= ∅.

La semi-continuit`a superiore `e legata alla chiusura e alla compattezza degli insiemi.

Lemma 2.13. Se (X, τ_X) è uno spazio topologico, (Y, τ_Y) è uno spazio normale⁵, F : X → 2^Y è s.c.s. a valori chiusi, allora gr(F ) ⊆ X × Y è chiuso.

Dimostrazione. Proviamo che A = (X × Y ) \ gr(F ) è aperto. Per ogni (x, y) ∈ A, esistono V, W ⊂ Y aperti t.c. y ∈ V , F (x) ⊆ W e V ∩ W = ∅. Poiché F è s.c.s. esiste U ∈ U_X(x) t.c.

F (U ) ⊆ W . Dunque U × V ∈ U (x, y) e U × V ⊆ A.

L’implicazione non si inverte, fuorch´e in casi particolari:

Lemma 2.14. Se (X, τX) è uno spazio topologico, (Y, τY) è uno spazio compatto e F : X → 2^Y ha grafico chiuso, allora F è s.c.s.

Dimostrazione. Sia C ⊆ Y chiuso, dimostriamo che F⁻(C) è chiuso in X. Per ogni x ∈ cl(F⁻(C)) esiste una successione generalizzata (xα) in F⁻(C) convergente a x⁶. Per ogni indice α esiste y_α∈ F (x_α) ∩ C. Poiché C è compatto, (y_α) ammette un punto limite y ∈ C. Si ha (x_α, y_α) ∈ gr(F ) per ogni α, quindi (x, y) ∈ gr(F ) cioè y ∈ F (x) ∩ C, da cui x ∈ F⁻(C). Estensione del Teorema di Weierstraß (per questa proprietà l’analogo della continuità univoca è la semi-continuità superiore):

Teorema 2.15. Se (X, τ_X) `e uno spazio compatto, (Y, τ_Y) uno spazio topologico, F : X → 2^X s.c.s. a valori compatti, allora F (X) `e compatto.

Dimostrazione. Sia (Ai)i∈I una famiglia di aperti in Y t.c. F (X) ⊆ ∪i∈IAi. Per ogni x ∈ X esiste J_x⊆ I finito t.c. F (x) ⊆ ∪_i∈J_xA_i. Poniamo B_x= ∪_i∈J_xA_i, cos`ı che

X ⊆ ∪x∈XF⁺(Bx).

Poiché F è s.c.s. e X è compatto, esistono n ∈ N e x1, . . . xn∈ X t.c. X ⊆ ∪ⁿ_k=1F⁺(Bxk), da cui F (X) ⊆ ∪ⁿ_k=1Bxk = ∪ⁿ_k=1∪_i∈J_xk Ai,

cioè abbiamo estratto da (A_i)_i∈I un sotto-ricoprimento finito di F (X). Estensione del Teorema dei valori intermedi (qui è sufficiente la semi-continuità):

Teorema 2.16. Se (X, τX) `e uno spazio connesso, (Y, τY) uno spazio topologico, F : X → 2^X semi-continua a valori non vuoti e connessi, allora F (X) `e connesso.

Dimostrazione. Procediamo per assurdo: siano A, B ⊂ Y aperti t.c. F (X) ⊆ A ∪ B, F (X) ∩ A 6= ∅, F (X) ∩ B 6= ∅ e F (X) ∩ A ∩ B = ∅. Gli insiemi F⁻(A), F⁻(B) sono non vuoti e aperti in X: infatti, per ogni x ∈ F⁻(A) si ha in effetti F (x) ⊆ A, quindi esiste U ∈ UX(x) t.c. F (x⁰) ⊆ A per ogni x⁰ ∈ U , da cui U ⊆ F⁻(A) (similmente si prova che F⁻(B) `e aperto). Inoltre F⁻(A) ∪ F⁻(B) = X,

F⁻(A) ∩ F⁻(B) = ∅, contro l’ipotesi che X `e connesso.

In vista delle applicazioni, definiamo il prodotto cartesiano di multifunzioni:

5Uno spazio normale, o T4, `e uno spazio di Hausdorff in cui, dati due chiusi C1, C2 t.c. C1∩ C2= ∅, esistono due aperti A1, A2 t.c. Ci⊂ Ai (i = 1, 2) e A1∩ A2= ∅, ved. [10].

6Se X `e uno spazio metrico si pu`o usare una successione ordinaria (xn).

(11)

Definizione 2.17. Siano X, Y , Z insiemi non vuoti, F : X → 2^Y, G : X → 2^Z: il prodotto cartesiano di F e G `e la multifunzione F × G : X → 2^{Y ×Z} definita per ogni x ∈ X da

(F × G)(x) = F (x) × G(x).

Lemma 2.18. Se (X, τ_X), (Y, τ_Y), (Z, τ_Z) sono spazi topologici e F : X → 2^Y, G : X → 2^Z, allora:

(i) se F , G sono s.c.i., F × G `e s.c.i.;

(ii) se F , G sono s.c.s. a valori compatti, F × G `e s.c.s.;

(iii) se F , G sono semi-continue a valori compatti, F × G `e semi-continua.

Dimostrazione. Dimostriamo solo (i): siano A ⊆ Y , B ⊆ Z aperti, allora si ha

(F × G)⁻(A × B) =x ∈ X : (F (x) × G(x)) ∩ (A × B) 6= ∅ = F⁻(A) ∩ G⁻(B),

e tale insieme è aperto. La proprietà si estende facilmente a unioni arbitrarie e intersezioni finite di insiemi del tipo A × B, che formano una base di aperti della topologia di Y × Z. Dunque F × G è

s.c.i.

Una funzione (univoca) continua, definita su un connesso, ha grafico connesso. Questo principio si estende alle multifunzioni, e inaugura una serie di risultati che legano multifunzioni e connessione:

Teorema 2.19. Se (X, τ_X) `e uno spazio connesso, (Y, τ_Y) uno spazio topologico, F : X → 2^Y s.c.i. a valori non vuoti e connessi, allora gr(F ) `e connesso.

Dimostrazione. Segue dal Lemma 2.18 e dal Teorema 2.16, una volta osservato che gr(F ) =

(id_X × F )(X).

Come gi`a osservato, ogni insieme S ⊆ X × Y si pu`o vedere come il grafico di una multifunzione da X in Y o viceversa. Dunque i risultati precedenti ammettono una versione topologica:

Lemma 2.20. Se (X, τX), (Y, τY) sono spazi topologici, S ⊆ X × Y e una delle seguenti condizioni

`e verificata:

(i) X è connesso, S_x6= ∅ è connesso per ogni x ∈ X, S^y è aperto per ogni y ∈ Y ; (ii) Y è connesso, S^y 6= ∅ è connesso per ogni y ∈ Y , S_x è aperto per ogni x ∈ X, allora S è connesso.

Dimostrazione. Sia verificata (i): definiamo F : X → 2^Y ponendo F (x) = Sx per ogni x ∈ X.

Allora F ha valori non vuoti e connessi. Inoltre, per ogni A ∈ τY l’insieme F⁻(A) = {x ∈ X : (x, y) ∈ S per qualche y ∈ A} = ∪_y∈AS^y,

è aperto, quindi F è s.c.i. La tesi segue dal Teorema 2.19, poiché gr(F ) = S. In generale, l’intersezione di multifunzioni s.c.i. non è s.c.i. Tuttavia vale il seguente risultato, in cui una delle due viene ’dilatata’:

Lemma 2.21. Se (X, τ ) `e uno spazio topologico, (Y, d) uno spazio metrico, F, G : X → 2^Y s.c.i.

a valori non vuoti, r ∈ R⁺₀ e

Br(G(x)) = {y ∈ Y : d(y, G(x)) < r} per ogni x ∈ X,

allora la multifunzione H : X → 2^Y definita da H(x) = F (x) ∩ B_r(G(x)) per ogni x ∈ X `e s.c.i.

(12)

Dimostrazione. Sia A ⊆ Y aperto. L’insieme

A = {(y, z) ∈ Y × Y : y ∈ A, d(y, z) < r}˜

`e aperto in Y × Y . Si ha

(2.1) H⁻(A) = (F × G)⁻( ˜A).

Infatti, per ogni x ∈ H⁻(A) esiste y ∈ F (x) ∩ A t.c. d(y, G(x)) < r, quindi esiste z ∈ G(x) t.c.

d(y, z) < r. Allora (y, z) ∈ (F (x) × G(x)) ∩ Ã cos`ı che x ∈ (F × G)⁻( Ã). E viceversa. Per il Lemma2.18, la multifunzione F × G è s.c.i., dunque (F × G)⁻( Ã) è aperto in X (Lemma 2.5). Da

(2.1) segue la tesi.

Soffermiamoci sul caso particolare delle multifunzioni fra spazi metrici:

Definizione 2.22. Siano (X, dX), (Y, dY) spazi metrici, d^Y_H denoti la distanza di Hausdorff su Y , F : X → 2^Y: F `e lipschitziana se esiste L > 0 t.c.

d^Y_H(F (x), F (x⁰)) 6 LdX(x, x⁰) per ogni x, x⁰ ∈ X.

Se L = 1, F `e detta non-espansiva. Se L < 1, F `e detta contrazione multivoca.

La distanza d^Y_H stabilisce una metrica su (un conveniente sottoinsieme di) 2^Y, cos`ı che la Definizione 2.22introduce una specie di continuit`a di F come funzione (univoca) fra X e 2^Y. Questa nozione, estremamente delicata, ha con la semi-continuit`a inferiore la seguente relazione:

Lemma 2.23. Se (X, d_X), (Y, d_Y) sono spazi metrici e F : X → 2^Y `e lipschitziana, allora F `e s.c.i.

Dimostrazione. Siano L > 0 una costante di Lipschitz per F , A ⊆ Y aperto, x ∈ F⁻(A). Esistono y ∈ F (x) ∩ A e r > 0 t.c. B_r^Y(y) ⊆ A. Dunque, posto δ = r/L, per ogni x⁰ ∈ B^X_δ (x) abbiamo

d^Y_H(F (x), F (x⁰)) 6 LdX(x, x⁰) < r,

da cui dY(y, F (x⁰)) < r, che implica F (x⁰) ∩ A 6= ∅. Pertanto, B_δ^X(x) ⊆ F⁻(A) e F risulta s.c.i.

(Lemma 2.5).

2.2. Selezioni continue. Il legame tra analisi multivoca e univoca `e dato dalla seguente nozione:

Definizione 2.24. Siano X, Y insiemi non vuoti, F : X → 2^Y, f : X → Y : f `e una selezione di F se f (x) ∈ F (x) per ogni x ∈ X.

Ovviamente ogni multifunzione a valori non vuoti ammette selezioni. Tuttavia, queste possono in generale essere irregolari: nella fig. 1 `e mostrata una selezione continua, la multifunzione dell’Esempio2.9invece non ha alcuna selezione continua. Si deve a Michael [27–29] il principale risultato di esistenza di selezioni continue per una multifunzione. Questo richiede alcune premesse topologiche:

Definizione 2.25. Sia (X, τ ) uno spazio di Hausdorff. Esso `e detto paracompatto se ogni ricoprimento aperto (Ai)i∈I di X ammette un raffinamento localmente finito, ovvero un altro ricoprimento aperto (Bi)i∈I di X⁷ con le seguenti proprie`a

(i) per ogni i ∈ I si ha Bi⊆ A_i;

(ii) per ogni x ∈ X esistono U ∈ U (x), Jx ⊆ I finito t.c. U ∩ B_i= ∅ per ogni i ∈ I \ Jx.

7Si vede facilmente che il raffinamento pu`o essere indicizzato rispeto allo stesso insieme di indici I del ricoprimento originario.

(13)

Figura 1. La curva evidenziata `e il grafico di una selezione continua della multifunzione.

Ogni spazio paracompatto è normale. Ogni spazio metrico è paracompatto. Si ha inoltre il seguente teorema di partizione dell’unità:

Teorema 2.26. Se (X, τ ) `e uno spazio normale e (Ai)i∈I `e un ricoprimento aperto localmente finito di X, allora esistono una famiglia (ϕi)_i∈I di funzioni continue ϕi : X → [0, 1] e una famiglia (C_i)_i∈I di chiusi t.c.

(i) Ci⊆ A_i per ogni i ∈ I;

(ii) ϕi(x) = 0 per ogni x ∈ X \ Ci, i ∈ I;

(iii) P

i∈Iϕ_i(x) = 1 per ogni x ∈ X.

Osserviamo che, poiché (Ci)i∈I è un ricoprimento localmente finito, la somma in (iii)è estesa a un numero finito di vertici in un conveniente intorno di x, e pertanto non pone problemi di convergenza. In particolare, se (X, τ ) è uno spazio paracompatto e (A_i)_i∈I è un ricoprimento aperto di X, allora esiste una partizione continua dell’unità (ϕ_i)_i∈I subordinata ad (A_i)_i∈I (su questa parte, ved. [10, p. 157 e p. 223]).

Prepariamo il terreno con un lemma di approssimazione:

Lemma 2.27. Se (X, τ ) `e uno spazio topologico paracompatto, (Y, k · k) uno spazio normato, F : X → 2^Y s.c.i. a valori non vuoti e convessi, allora per ogni ε > 0 esiste fε: X → Y continua t.c.

d(f_ε(x), F (x)) < ε per ogni x ∈ X.

Dimostrazione. Per ogni y ∈ Y sia Ay = F⁻(Bε(y)). La famiglia (Ay)y∈Y è un ricoprimento aperto di X, che ammette un raffinamento localmente finito (Ey)y∈Y (Definizione2.25), cui è subordinata una partizione continua dell’unità (ϕ_y)_y∈Y (Teorema 2.26). Per ogni x ∈ X poniamo

fε(x) =X

y∈Y

ϕy(x)y.

E definita una funzione f` ε : X → Y . Proviamo che fε `e continua: per ogni x ∈ X esistono U ∈ U (x), y1, . . . yn∈ Y t.c. U ∩ E_y = ∅ per ogni y ∈ Y \ {yi}ⁿ_i=1; dunque, per ogni x⁰ ∈ U abbiamo

fε(x⁰) =

n

X

i=1

ϕyi(x⁰)yi,

cos`ı che fε`e continua in x. Proviamo infine la formula metrica: procedendo come sopra, assumiamo che per ogni i ∈ {1, . . . n} sia ϕ_y_i(x) > 0, da cui x ∈ A_y_i; pertanto esiste w_i ∈ F (x) t.c. kw_i−y_ik < ε;

(14)

sia

w =

n

X

i=1

ϕ_y_i(x)w_i, allora (per convessit`a di F (x)) abbiamo w ∈ F (x) e anche

kf_ε(x) − wk 6

n

X

i=1

ϕyi(x)kwi− y_ik < ε,

da cui d(f_ε(x), F (x)) < ε.

Introduciamo adesso il risultato principale, in cui gioca un ruolo importante la completezza dei valori di F :

Teorema 2.28. (Michael [27]) Se (X, τ ) `e uno spazio topologico paracompatto, (Y, k · k) uno spazio di Banach, F : X → 2^Y s.c.i. a valori non vuoti, chiusi e convessi, allora F ammette una selezione continua.

Dimostrazione. Costruiamo una successione (f_n) di funzioni f_n: X → Y continue t.c. per ogni x ∈ X, n ∈ N

(2.2) d(f_n(x), F (x)) < 1

2ⁿ, d(f_n(x), f_n+1(x)) < 1 2ⁿ⁻¹.

Procediamo per induzione. Per n = 1, dal Lemma2.27segue l’esistenza di f1 : X → Y continua t.c. d(f₁(x), F (x)) < 1/2 per ogni x ∈ X. Fissato n ∈ N, se esistono f1, . . . f_n verificanti (2.2), definiamo F_n: X → 2^Y ponendo per ogni x ∈ X

F_n(x) = F (x) ∩ B_1/2ⁿ(f_n(x)),

cos`ı che Fn `e s.c.i. (Lemma 2.21) e ha valori non vuoti (per (2.2)) e convessi. Per il Lemma 2.27 esiste f_n+1: X → Y continua t.c. per ogni x ∈ X

d(f_n+1(x), F_n(x)) < 1 2ⁿ⁺¹.

In particolare, per ogni x ∈ X esiste y_x ∈ F_n(x) t.c. kf_n+1(x) − y_xk < 1/2ⁿ⁺¹, da cui kf_n+1(x) − f_n(x)k 6 kfn+1(x) − y_xk + ky_x− f_n(x)k < 1

2ⁿ⁺¹ + 1 2ⁿ < 1

2ⁿ⁻¹.

Dunque fn+1 verifica (2.2). La successione (fn) `e di Cauchy uniformemente in X: per completezza di Y , si ha fn→ f uniformemente in X per qualche f : X → Y continua, per la quale si ha da (2.2)

d(f (x), F (x)) = 0 per ogni x ∈ X.

Poiché F ha valori chiusi, abbiamo f (x) ∈ F (x). Dunque f è una selezione continua di F . Una conseguenza importante è il seguente teorema di estensione-selezione:

Corollario 2.29. Se (X, τ ) `e uno spazio topologico paracompatto, (Y, k · k) uno spazio di Banach, F : X → 2^Y s.c.i. a valori non vuoti, chiusi e convessi, C ⊆ X chiuso, g : C → Y continua t.c.

g(x) ∈ F (x) per ogni x ∈ C, allora F ammette una selezione continua f : X → Y t.c. f |_C = g.

(15)

Dimostrazione. Sia ˜F : X → 2^Y definita ponendo per ogni x ∈ X F (x) =˜

({g(x)} se x ∈ C F (x) se x /∈ C.

Proviamo che ˜F `e s.c.i. Per ogni A ⊆ Y aperto e ogni x ∈ ˜F⁻(A), possono darsi due casi:

(a) se x ∈ C, allora g(x) ∈ A, quindi esiste U ∈ U (x) t.c. g(x⁰) ∈ A per ogni x⁰∈ U ∩ C; inoltre F (x) ∩ A 6= ∅, quindi esiste V ∈ U (x) t.c. F (x⁰) ∩ A 6= ∅ per ogni x⁰ ∈ V ; posto W = U ∩ V , abbiamo W ∈ U (x) e ˜F (x⁰) ∩ A 6= ∅ per ogni x⁰ ∈ W ;

(b) se x /∈ C, esiste U ∈ U (x) t.c. ˜F (x⁰) ∩ A = F (x⁰) ∩ A 6= ∅ per ogni x⁰∈ U .

Inoltre, ˜F ha valori chiusi e convessi. Per il Teorema2.28, ˜F ha una selezione continua f : X → Y ,

e ovviamente f (x) = g(x) per ogni x ∈ C.

Di seguito presentiamo alcune applicazioni del Teorema2.28. La prima `e un risultato di estensione continua per funzioni definite su insiemi chiusi (che generalizza, in un certo senso, il Teorema di Tietze):

Corollario 2.30. Se (X, τ ) è uno spazio topologico paracompatto, (Y, k · k) è uno spazio di Banach, C ⊂ X è non vuoto e chiuso, g : C → Y è continua, allora esiste f : X → Y continua t.c.

f (x) = g(x) per ogni x ∈ C.

Dimostrazione. Applichiamo il Corollario2.29alla multifunzione costante definita ponendo F (x) =

Y per ogni x ∈ X.

La seconda `e un risultato di esistenza di un’inversa continua per operatori lineari continui (che trova applicazione nella teoria delle equazioni differenziali lineari):

Corollario 2.31. Se (X, k · k_X), (Y, k · k_Y) sono spazi di Banach e ϕ : X → Y `e un operatore lineare continuo e suriettivo, allora esiste f : X → Y continua t.c. ϕ ◦ f = id_Y.

Dimostrazione. Per il teorema della mappa aperta (ved. Rudin [40, p. 47]), la funzione ϕ : X → Y trasforma aperti in aperti. Per il Lemma2.5, ne segue che la multifunzione F = ϕ⁻¹: Y → 2^X

`e s.c.i. Inoltre F ha valori non vuoti, chiusi e convessi. Per il Teorema 2.28 esiste f : Y → X continua t.c. per ogni y ∈ Y si ha f (y) ∈ F (y), ovvero ϕ(f (y)) = y. 2.3. Punti fissi. Nella teoria dei punti fissi per applicazioni univoche, si distinguono due famiglie di risultati: i teoremi ’metrici’ di punto fisso dovuti a Banach, Caccioppoli, e quelli ’algebrico- topologici’ dovuti a Brouwer, Schauder, Cauty (ved. Granas & Dugundji [19]). Anche il caso multivoco rispecchia questa distinzione.

Definizione 2.32. Siano X un insieme non vuoto, F : X → 2^X, x ∈ X: x `e un punto fisso di F se x ∈ F (x). L’insieme dei punti fissi di F `e denotato fix(F ).

Il seguente teorema di punto fisso per le contrazioni multivoche estende il teorema di Banach &

Caccioppoli rispetto all’esistenza di punti fissi, ma si perde l’unicit`a:

Teorema 2.33. (Nadler [33]) Se (X, d) `e uno spazio metrico completo e F : X → 2^X una contrazione multivoca a valori chiusi, allora fix(F ) 6= ∅.

Dimostrazione. Siano L ∈ (0, 1) una costante di Lipschitz per F , β > 1 un numero reale e x0 ∈ X. Scartando casi banali, supponiamo x₀ ∈ F (x/ ₀), da cui d(x0, F (x0)) > 0. Costruiamo una successione (xn) in X t.c.

(2.3) x_n∈ F (x_n−1), d(x_n−1, x_n) < βLⁿ⁻¹d(x₀, F (x₀)) per ogni n ∈ N.

(16)

Procediamo per induzione. L’esistenza di x₁ verificante (2.3) `e ovvia. Sia n > 1 e siano x₀, . . . x_n∈ X verificanti (2.3): in particolare,

d(xn, F (xn)) 6 dH(F (xn−1), F (xn)) 6 Ld(xn−1, xn) < βLⁿd(x0, F (x0)),

da cui segue l’esistenza di xn+1∈ F (x_n) verificante (2.3). Proviamo ora che (xn) `e una successione di Cauchy in X: per ogni n, m ∈ N, n < m, abbiamo

d(xm, xn) 6

m

X

i=n+1

d(xi, xi−1) 6 βd(x0, F (x0))

m

X

i=n+1

Lⁱ⁻¹;

dal Criterio di Cauchy per le serie (e dalla convergenza della serie geometrica di ragione L) segue che, per ogni ε > 0, esiste ν ∈ N t.c. se ν < n < m allora d(xm, x_n) < ε. Poich´e X `e completo, abbiamo xn→ x. Da (2.3) abbiamo per ogni n ∈ N

d(xn, F (x)) 6 dH(F (xn−1), F (x)) 6 Ld(xn−1, x),

da cui, passando al limite, d(x, F (x)) = 0. Poich´e F (x) `e chiuso, abbiamo infine x ∈ fix(F ). Esaminiamo ora i teoremi di punto fisso ’topologici’, cominciando con l’estensione del teorema di Schauder [19, p. 119] al caso multivoco (per la teoria degli spazi di Banach rimandiamo a Fabian et Al. [13]):

Teorema 2.34. Se (X, k · k) `e uno spazio di Banach, K ⊂ X `e compatto e convesso e F : K → 2^K

`e s.c.i. a valori non vuoti, chiusi e convessi, allora fix(F ) 6= ∅.

Dimostrazione. Per il Teorema2.28, F ammette una selezione continua f : K → K. Per il citato teorema di Schauder, esiste x ∈ K t.c. f (x) = x. Dunque x ∈ fix(F ). In vista delle applicazioni, tuttavia, `e importante dimostrare un teorema di punto fisso per multifunzioni s.c.s. A questo fine occorre richiamare un lemma di approssimazione:

Lemma 2.35. (Cellina [8]) Se (X, d) `e uno spazio metrico compatto, (Y, k · k) uno spazio normato, F : X → 2^Y s.c.s. a valori non vuoti e convessi, allora per ogni r > 0 esiste gr : X → Y continua t.c. per ogni x ∈ X

d((x, g_r(x)), gr(F )) 6 r.

Dimostrazione. Sia fissato r > 0. Per il Lemma 2.6, per ogni x ∈ X esiste ρ > 0 t.c.

(2.4) F (B_ρ(x)) ⊆ B_r/2(F (x)).

Per ogni x ∈ X poniamo ρ(x) = sup

n ρ ∈

0,r

2 i

: F (Bρ(x)) ⊆ B_r/2(F (x⁰)) per qualche x⁰∈ B_ρ(x) o

. Dimostriamo che

(2.5) inf

x∈Xρ(x) = ρ₀> 0.

Procediamo per assurdo: sia (x_n) una successione in X t.c. ρ(x_n) = ρ_n→ 0. Passando a un’estratta, abbiamo xn→ x in X. Sia ρ > 0 come in (2.4) per x. Definitivamente, si ha

maxρ_n, d(xn, x) < ρ 3, da cui x ∈ B_ρ/3(xn) e

F (B_ρ/3(xn))F (Bρ(x)) ⊆ B_r/2(F (x)),

(17)

contro la relazione ρ_n< ρ/3.

Poniamo per ogni x ∈ X

G(x) = F (B_ρ₀_/2(x)).

Proviamo che G⁻(y) `e aperto in X per ogni y ∈ F (X). Infatti, per ogni x ∈ G⁻(y) esiste x⁰ ∈ B_ρ₀_/2(x) t.c. y ∈ F (x⁰). Posto σ = 1/2(ρ₀/2 − d(x, x⁰)), si ricava B_σ(x) ⊆ G⁻(y). Infatti, per ogni x⁰⁰ ∈ B_σ(x) si ha

d(x⁰, x⁰⁰) 6 d(x⁰, x) + d(x, x⁰⁰) < d(x, x⁰) 2 +ρ₀

4 < ρ₀ 2 , da cui y ∈ F (B_ρ₀_/2(x⁰⁰)), ovvero x⁰⁰ ∈ G⁻(y).

Dunque (G⁻(y))_{y∈F (X)} `e un ricoprimento aperto di X, da cui si estrae un sotto-ricoprimento finito (G⁻(yi))^m_i=1 (y1, . . . ym ∈ F (X)). Per il Teorema 2.26, ad esso `e subordinata una partizione (finita)

continua dell’unit`a (ϕi)^m_i=1. Poniamo per ogni x ∈ X gr(x) =

m

X

i=1

ϕi(x)yi.

La funzione g_r: X → Y `e ovviamente continua. Fissiamo x ∈ X. Per (2.5) esistono ρ ∈ [ρ₀/2, r/2], x⁰ ∈ B_ρ(x) t.c. F (B_ρ(x)) ⊆ B_r/2(F (x⁰)), da cui

G(x) ⊆ B_r/2(F (x⁰)) ∩ conv(F (X))

(l’ultimo essendo un insieme convesso). Per semplicit`a supponiamo ϕi(x) > 0 se e solo se 1 6 i 6 l (l 6 m), allora si ha

y_i ∈ B_r/2(F (x⁰)) ∩ conv(F (X)), i = 1, . . . l.

Poich´e gr(x) `e una combinazione convessa di y1, . . . yl, ne segue g_r(x) ∈ B_r/2(F (x⁰)) ∩ conv(F (X)).

Per la diseguaglianza triangolare e le relazioni precedenti, si ha infine

d((x, gr(x)), gr(F )) 6 d((x, gr(x)), (x⁰, gr(x))) + d((x⁰, gr(x)), gr(F )) 6 d(x, x⁰) + d(g_r(x), F (x⁰))

6 ρ + r 2 6 r,

il che conclude la dimostrazione.

Il pi`u noto teorema di punto fisso per le multifunzioni `e il seguente:

Teorema 2.36. (Kakutani [22]) Se K ⊆ Rⁿ (n ∈ N) `e compatto e convesso e F : K → 2^K `e s.c.s. a valori non vuoti, chiusi e convessi, allora fix(F ) 6= ∅.

Dimostrazione. Per ogni k ∈ N, dal Lemma2.35segue l’esistenza di g_k : K → K continua t.c. per ogni x ∈ K

d((x, g_k(x)), gr(F )) < 1 k.

Per il teorema di Brouwer [19, p. 95] esiste x_k∈ fix(g_k). A meno di estratte, abbiamo x_k→ x per qualche x ∈ K, da cui (x_k, x_k) → (x, x), quindi

d((x, x), gr(F )) = lim

k d((x_k, x_k), gr(F )) 6 lim

k

1 k = 0.

Poich´e gr(F ) `e chiuso (Lemma2.13), abbiamo infine x ∈ fix(F ).

(18)

Se nel Teorema 2.36 sostituiamo Rⁿ con uno spazio normato di dimensione infinita, le ipotesi diventano troppo restrittive in quanto gli insiemi compatti in un tale spazio sono pochi (per esempio, un insieme con interno non vuoto in uno spazio di Banach di dimensione infinita non

`e mai compatto). Per questo sono state introdotte alcune estensioni improprie (le dimostrazioni sono simili a quella del Teorema2.36). In una di esse, si ammette l’uso di topologie vettoriali localmente convesse, permettendo applicazioni agli spazi di Banach riflessivi⁸:

Teorema 2.37. (Glicksberg [17]) Se (X, τ ) `e uno spazio vettoriale-topologico localmente convesso di Hausdorff, K ⊂ X compatto e convesso, F : K → 2^K a valori chiusi e convessi t.c. gr(F )

`e chiuso, allora fix(F ) 6= ∅.

Teorema 2.38. (Browder [5]) Se (X, τ ) `e uno spazio vettoriale-topologico localmente convesso di Haudorff, K ⊂ X `e compatto e convesso, F : K → 2^K a valori non vuoti e convessi t.c. F⁻(y)

`e aperto per ogni y ∈ K, allora fix(F ) 6= ∅.

Un’altra strategia comporta l’uso di punti fissi approssimati:

Definizione 2.39. Siano (X, d) uno spazio metrico, F : X → 2^X, ε > 0 un numero reale, x ∈ X:

x `e detto ε-punto fisso di F se d(x, F (x)) 6 ε. L’insieme degli ε-punti fissi di F `e denotato fix^ε(F ).

Vale in merito il seguente risultato:

Teorema 2.40. (Brânzei et Al. [4]) Se (X, k · k) è uno spazio di Banach riflessivo, S ⊆ X limitato, convesso t.c. int(S) 6= ∅, F : S → 2^S a valori non vuoti e convessi, t.c. gr(F ) è debolmente chiuso⁹, allora per ogni ε > 0 si ha fix^ε(F ) 6= ∅.

Dimostrazione. Supponiamo S = B1(0) (il caso generale si tratta con aggiustamenti minori).

Fissato ε > 0, troviamo δ ∈ R t.c. 0 < δ < min{1, ε} e poniamo K = (1 − δ)cl(S) = B1−δ(0), e per ogni x ∈ K

G(x) = (1 − δ)cl(F (x)).

Dunque, K `e un insieme chiuso, convesso, limitato in X, quindi debolmente compatto, e G : K → 2^K ha valori convessi e grafico debolmente chiuso. Per il Teorema2.37esiste x ∈ fix(G), ovvero esiste y ∈ F (x) t.c. x = (1 − δ)y, da cui

d(x, F (x)) 6 kx − yk = δkxk < ε.

In conclusione x ∈ fix^ε(F ).

2.4. Il principio KKM. Concludiamo questa sezione con un celebre teorema di coincidenza, in base al quale la famiglia dei valori di una multifunzione (soggetta a una peculiare ipotesi geometrica) ha la propriet`a dell’intersezione finita (ved. anche [19, p. 37]).

Definizione 2.41. Siano X uno spazio vettoriale, S ⊂ X non vuoto, F : S → 2^S: F soddisfa KKM se, per ogni n ∈ N, x1, . . . x_n∈ S, si ha

conv(x₁, . . . x_n) ⊆ ∪ⁿ_i=1F (x_i).

Chiaramente, se F soddisfa KKM, allora fix(F ) = S. Inoltre, l’unione di due valori F (x₁) e F (x₂) contiene il segmento congiungente x₁ e x₂, e cos`ı via.

8Uno spazio vettoriale-topologico è detto localmente convesso se ogni punto ha una base di intorni convessi; uno spazio di Banach con la topologia debole è localmente convesso, e se lo spazio è riflessivo gli insiemi debolmente chiusi e limitati sono debolmente compatti (ved. [13]).

9L’ultima ipotesi significa che gr(F ) `e chiuso rispetto alla topologia prodotto della topologia debole σ(X^∗, X) per se stessa, relativizzata a S × S (leggere due volte aiuta).

(19)

Teorema 2.42. (Knaster et Al. [21]) Se X è uno spazio vettoriale, S ⊂ X è non vuoto, F : S → 2^X soddisfa KKM e F (x) è finitamente chiuso¹⁰per ogni x ∈ S, allora per ogni n ∈ N, x1, . . . xn∈ S si ha

∩ⁿ_i=1F (xi) 6= ∅.

Dimostrazione. Procediamo per assurdo: sia dunque

(2.6) ∩ⁿ_i=1F (xi) = ∅.

Denotiamo ˜X = span(x₁, . . . x_n), C = conv(x₁, . . . x_n). Su ˜X definiamo una topologia vettoriale di Hausdorff, rendendo ˜X omeomorfo a uno spazio euclideo: in tale spazio, C `e chiuso e limitato, quindi compatto. Per ogni i ∈ {1, . . . n} definiamo λ_i : ˜X → R ponendo

λi(x) = d(x, F (xi) ∩ ˜X) per ogni x ∈ ˜X.

La funzione λi `e continua. Per ogni x ∈ ˜X esiste i ∈ {1, . . . n} t.c. λi(x) > 0: altrimenti, infatti, si avrebbe x ∈ ∩ⁿ_i=1F (x_i) (rammentiamo che gli insiemi F (x_i) ∩ ˜X sono chiusi), contro (2.6). Dunque, per ogni x ∈ ˜X `e definito un insieme non vuoto

Ix = {i ∈ {1, . . . n} : λi(x) > 0}.

Definiamo f : ˜X → ˜X ponendo f (x) =

Pn

i=1λi(x)xi

Pn

j=1λj(x) per ogni x ∈ ˜X.

La funzione f `e continua e si ha f (x) ∈ C per ogni x ∈ ˜X. Dunque, per il teorema di Brouwer [19, p.

95], esiste x0∈ fix( f |_C). Applicando la condizione KKM otteniamo x₀ = f (x₀) ∈ conv (x_i)_i∈I_x0 ⊆ ∪_i∈I_x0F (x_i),

cos`ı che esiste i ∈ Ix0 t.c. x0 ∈ F (x_i), da cui λi(x0) = 0, contro la definizione di λi. Questo

conclude la dimostrazione.

Come conseguenza, si pu`o provare che esiste un punto comune a tutti i valori di una multifunzione:

Corollario 2.43. Se (X, τ ) è uno spazio vettoriale-topologico di Hausdorff, S ⊆ X è non vuoto, F : S → 2^X soddisfa KKM e ha valori chiusi, ed esiste x0 ∈ S t.c. F (x₀) è compatto, allora

∩_x∈SF (x) 6= ∅.

Dimostrazione. Si vede facilmente che F (x) `e finitamente chiuso per ogni x ∈ S. Sia ˜F : S → 2^{F (x}⁰⁾ definita ponendo per ogni x ∈ S

F (x) = F (x) ∩ F (x˜ 0).

Per il Teorema2.42, dom( ˜F ) = S. Per ogni n ∈ N, x1, . . . xn∈ S si ha

∩ⁿ_i=1F (x˜ _i) = ∩ⁿ_i=0F (x_i) 6= ∅,

dunque ( ˜F (x))_x∈S `e una famiglia di sottoinsiemi chiusi del compatto F (x₀) soddisfacente la propriet`a dell’intersezione finita. Dunque esiste x ∈ ∩x∈SF (x) (ved. [10, p. 135]), in particolare˜

x ∈ ∩x∈SF (x).

10In uno spazio vettoriale X, si dice che S ⊆ X `e finitamente chiuso se, per ogni sottospazio Y di X di dimensione finita, l’insieme S ∩ Y `e chiuso in Y (rispetto alla topologia euclidea).