INTRODUZIONE ALLA TEORIA DEI GIOCHI - people.unica.it · 2016. 1. 22. · Riferimenti bibliogra...

INTRODUZIONE ALLA TEORIA DEI GIOCHI

ANTONIO IANNIZZOTTO

Sommario. In questi appunti intendiamo offrire una breve ma rigorosa introduzione allateoria dei giochi, utilizzabile per i corsi di laurea magistrale o di dottorato di ricercain matematica. Il corso e incentrato principalmente sugli aspetti teorici della disciplina:definizioni formali di gioco, utilita e soluzione; cenni di analisi multivoca; concetto diequilibrio di Nash; giochi statici non-cooperativi e cooperativi; giochi a somma nulla;teoremi di minimax; giochi dinamici; rappresentazione mediante grafi. Infine vengonopresentate diverse applicazioni, con particolare attenzione ai modelli economici.

Ringraziamo la Prof.ssa Ornella Naselli, del Dipartimento di Matematica e Informaticadell’Universita degli Studi di Catania, per i molti e preziosi chiarimenti che ci ha offerto suquesto argomento.

Indice

1. Introduzione: giochi, soluzioni ed equilibri 21.1. Notazioni 62. Multifunzioni 72.1. Multifunzioni fra spazi topologici 82.2. Selezioni continue 122.3. Punti fissi 142.4. Il principio KKM 173. Giochi non cooperativi ed equilibri di Nash 193.1. Strategie miste e teorema di Nash 203.2. Esempi 233.3. Equilibri approssimati 264. Giochi a somma nulla e teoria del minimax 284.1. Alcuni teoremi di minimax 315. Giochi cooperativi 355.1. Valore di Shapley 415.2. Esempi 446. Cenni sui giochi dinamici 466.1. Esempi 51Riferimenti bibliografici 54

Versione del 15 aprile 2015

1

2 A. IANNIZZOTTO

1. Introduzione: giochi, soluzioni ed equilibri

Chi in cento battaglie riporta cento vittorie, non e il piu abile in assoluto; al contrario, chinon da nemmeno battaglia, e sottomette le truppe dell’avversario, e il piu abile in assoluto.

Sun Tzu

I primi matematici ad affrontare teoricamente il problema dei giochi furono Zermelo [37] eBorel [3], con particolare anfasi sugli aspetti logici e probabilistici. Tuttavia, il maggiorcontributo verso la formalizzazione di une teoria metematica dei giochi e dovuto a VonNeumann [36]. La moderna teoria dei giochi rappresenta un tentativo di descrivere leinterazioni sociali (specialmente in campo economico) tra soggetti che, in competizione traloro, effettuano decisioni razionali cercando di ottenere il massimo vantaggio. Lo studioha finalita predittive: determinare, se possibile, la soluzione o le situazioni di equilibrio diun’interazione prima che essa abbia luogo.

Per elaborare un modello di queste interazioni si ricorre al concetto di gioco, che puo averediverse caratteristiche (statico, dinamico, non-cooperativo, cooperativo etc.): questo modellorisulta efficace in quanto permette di trascurare tutti gli gli aspetti dell’interazione nonattinenti 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 efilosofia morale (teoria della scelta razionale). Per un’ampia trattazione della materiarimandiamo alle monografie di Aubin [1], Burger [6], Colombo [10], Gibbons [14],McKinsey [23], Morgenstern [27], Morgenstern & von Neumann [28], e allaraccolta di saggi di Kuhn & Tucker [22]. Per i collegamenti con l’analisi moderna,rimandiamo a Rossi [32].

Dal punto di vista teorico, la teoria dei giochi costituisce un interessante crocevia di branchemutuamente indipendenti della matematica quali la topologia, l’analisi multivoca, il calcolodelle probabilita e la teoria dei grafi.

Introduciamo brevemente le definizioni-assiomi della teoria:

Definizione 1.1. Un gioco e un’interazione tra due o piu decisori razionali e intelligenti,detti giocatori. Un decisore e 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 sceltenello stesso momento, mentre in un gioco dinamico i giocatori scelgono secondo un certoordine temporale, adattando la strategia alle mosse degli altri giocatori. In un giocodeterministico i giocatori scelgono in condizioni di certezza, ovvero sanno che un determinatoinsieme 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 probabilita. In ungioco non-cooperativo i giocatori non possono stringere accordi vincolanti tra loro, mentrein un gioco cooperativo possono. Un gioco statico deterministico non-cooperativo tra un

TEORIA DEI GIOCHI 3

insieme finito di giocatori P1, . . . Pn (n > 2) e rappresentato da un complesso

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

dove Xi e l’insieme delle strategie del giocatore Pi, E e l’insieme degli esiti e h : Πni=1Xi → E

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:

Definizione 1.2. Una preferenza � e una relazione binaria su un insieme E con le seguentiproprieta:

(i) e � e per ogni e ∈ E (riflessiva);(ii) se e1 � e2 e e2 � e3 allora e1 � e3 per ogni e1, e2, e3 ∈ E (transitiva);

(iii) e1 � e2 o e2 � e1 per ogni e1, e2 ∈ 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 � e2 e non e2 � e1, si scrive e1 ≺ e2. Se e1 � e2 e e2 � e1, allora e1, e2 sono dettiequivalenti (e1 ∼ e2).

Osservazione 1.3. Una preferenza non e un ordinamento: manca la proprieta antisimme-trica!

L’ipotesi di razionalita implica che il giocatore Pi dispone di una preferenza �i su E. Inmolti casi (come nelle scommesse), tale preferenza puo essere quantificata.

Definizione 1.4. Un’utilita e una funzione u : E → R con le seguenti proprieta:

(i) per ogni e1, e2 ∈ E, se e1 � e2, allora u(e1) 6 u(e2);(ii) per ogni e1, e2 ∈ E, se e1 ≺ e2, allora u(e1) < u(e2).

L’esistenza di una funzione di utilita non e ovvia. Vale in merito il Teorema di Rappresenta-zione (Kreps [21]):

Teorema 1.5. Siano E un insieme non vuoto e � una preferenza su E:

(i) se |E| 6 ℵ0, allora esiste un’utilita u : E → R;(ii) se |E| 6 2ℵ0, E e uno spazio topologico e � e continua, allora esiste un’utilita

u : E → R continua.

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

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

dove fi = ui ◦ h : Πni=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 delgioco in una (bi)matrice. Questa rappresentazione e detta in forma strategica.

Esempio 1.6. Il gioco del pari o dispari prevede due giocatori P (che vince se la somma epari), Q (che vince se la somma e 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

4 A. IANNIZZOTTO

attribuisce utilita 1 alla vittoria e −1 alla sconfitta. Il gioco e rappresentato dalla tabellasimmetrica:

P\Q p dp (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 strategieX = Y = {c, p, f} e tre esiti E = {vince P , vince Q, pareggio}.Per ogni giocatore, la vittoria vale 1, il pareggio 0 e la sconfitta −1. Il gioco e rappresentatodalla tabella simmetrica:

P\Q c p fc (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 effettiva-mente le cose) usando la tabella dei pay-off mediante il metodo delle eliminazioni iterate.In particolare, se P e Q hanno strategie fortemente dominanti x e y, la soluzione del giocosara (x, y).

Definizione 1.8. Nel gioco (1.2), siano xi, yi ∈ Xi due strategie. Si dice che

(i) xi domina fortemente yi se fi(z1, . . . xi, . . . zn) > fi(z1, . . . yi, . . . zn) per ogni (z1, . . . zn) ∈Πj 6=iXj;

(ii) xi domina strettamente yi se fi(z1, . . . xi, . . . zn) > fi(z1, . . . yi, . . . zn) per ogni(z1, . . . zn) ∈ Πj 6=iXj ed esiste (z1, . . . zn) ∈ Πj 6=iXj t.c. fi(z1, . . . xi, . . . zn) >fi(z1, . . . yi, . . . zn);

(iii) xi domina debolmente yi se fi(z1, . . . xi, . . . zn) > fi(z1, . . . yi, . . . zn) per ogni (z1, . . . zn) ∈Πj 6=iXj.

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

Nei giochi considerati negli Esempi 1.6, 1.7 nessun giocatore ha strategie dominanti. Seguonoalcuni esempi di soluzione per eliminazioni iterate per giochi con due giocatori:

Esempio 1.9. Consideriamo il seguente gioco:

P\Q y1 y2x1 (1, 2) (0, 1)x2 (0, 2) (2, 1)

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

TEORIA DEI GIOCHI 5


P\Q y1 y2x1 (3, 3) (2, 2)x2 (0, 2) (1, 1)x3 (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 (x1, y1). Se Q gioca per primo si perviene alla stessa soluzione.


P\Q y1 y2x1 (3, 5) (2, 5)x2 (3, 0) (0, 2)x3 (0, 2) (2, 0)

Osserviamo che in questo gioco non esistono strategie fortemente dominanti. Sia P il primoa giocare: x1 domina strettamente x2 e x3; se P elimina x2, osserva che nel nuovo gioco(ridotto) y1 domina strettamente y2, dunque sceglie x1 e la soluzione e (x1, y1); se inveceelimina x3, un ragionamento analogo porta alla soluzione (x1, y2). Se Q gioca per primo siperviene alle stesse soluzioni.

Per risolvere queste ambiguita si introduce un concetto di equilibrio dovuto a Nash [29]:

Definizione 1.12. Nel gioco (1.2), la n-upla (x1, . . . xn) ∈ Πni=1Xi e un equilibrio di Nash

se per ogni i ∈ {1, . . . n} si ha

fi(x1, . . . xn) > fi(x1, . . . yi, . . . xn) per ogni yi ∈ Xi.

L’insieme degli equilibri di Nash di Γ si denota Ne(Γ).

Nella tabella dei pay-off, un equilibrio di Nash corrisponde a una casella in cui la primacomponente e massima tra quelle della stessa colonna e la seconda e massima tra quelledella stessa riga. I giochi degli Esempi 1.6, 1.7 non presentano equilibri di Nash. L’unicoequilibrio di Nash nell’Esempio 1.9 e (x1, y1), nell’Esempio 1.10 e (x1, y1). Nell’Esempio 1.11ve ne sono due: (x1, y1) e (x1, y2). Ne deduciamo che

• un gioco puo non avere alcun equilibrio di Nash;• un gioco puo avere piu di un equilibrio di Nash;• una strategia fortemente dominata non puo essere componente di un equilibrio di

Nash;• una strategia debolmente dominata puo essere componente di un equilibrio di Nash.

Dunque, la risoluzione di un gioco per eliminazione delle strategie fortemente dominatepreserva gli equilibri di Nash (se ve ne sono), mentre la risoluzione per eliminazione dellestrategie debolmente dominate puo sopprimerne alcuni.

Esempio 1.13. Nel gioco noto come battaglia dei sessi, una coppia deve decidere se andareallo stadio (s) o a teatro (t); l’uomo (P ) preferisce andare allo stadio in compagnia che

6 A. IANNIZZOTTO

a teatro in compagnia, ma questo e pur sempre meglio che andare allo stadio da solo; ladonna (Q) ha preferenze analoghe. Il gioco e rappresentato dalla seguente tabella:

P\Q s ts (10, 5) (0, 0)t (0, 0) (5, 10)

Dunque gli equilibri di Nash sono (s, s) e (t, t) (l’esperienza insegna, tuttavia, che la coppiaandra a teatro).

Altri equilibri si possono determinare cambiando paradigma, cioe consentendo a ciascungiocatore di ripartire la sua scelta tra le varie strategie (come uno speculatore che investeparti 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.

Il problema dell’esistenza (e, in subordine, dell’unicita) dell’equilibrio di Nash richiede, peressere risolto, un armamentario matematico alquanto avanzato, che presenteremo nella suaforma piu generale.

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

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 ogniA ⊆ X denotiamo int(A) l’interno, cl(A) la chiusura, ∂A la frontiera di A, rispettivamente,e τA la topologia indotta da τ su A; per ogni x ∈ X denotiamo U(x) la famiglia degli intornidi 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},

dH(S, T ) = max{

supx∈S

d(x, T ), supy∈T

d(y, S)},

e per ogni r > 0

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

Spazi vettoriali: in uno spazio vettoriale X, per ogni S ⊆ X denotiamo

span(S) ={ n∑

i=1

λixi : n ∈ N, λ1, . . . λn ∈ R, x1, . . . xn ∈ S},

aff(S) ={ n∑

i=1

λixi : n ∈ N, λ1, . . . λn ∈ R,n∑i=1

λi = 1, x1, . . . xn ∈ S},

conv(S) ={ n∑

i=1

λixi : n ∈ N, λ1, . . . λn ∈ [0, 1],n∑i=1

λi = 1, x1, . . . xn ∈ S}.

TEORIA DEI GIOCHI 7

Spazi vettoriali-topologici: in uno spazio vettoriale-topologico (X, τ), denotiamo X∗ il dualetopologico di X, per ogni S ⊆ X denotiamo

cc(S) = cl(conv(S)

).

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 dellefunzioni non sono singoli elementi di un insieme bensı suoi sottoinsiemi: questa sceltacorrisponde all’esigenza di studiare con i mezzi dell’analisi matematica fenomeni caratterizzatida un alto grado di incertezza (come nella teoria dei controlli). Un altro contesto in cuile multifunzioni risultano utili e lo studio di problemi differenziali con discontinuita (ved.Chang [8] e Filippov [13]), con applicazioni in meccanica. In questa sezione introduciamole 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 [20].

Definizione 2.1. Siano X, Y insiemi non vuoti. Una multifunzione F : X → 2Y e unafunzione 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 ∈ 2Y ,

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

IF (y) = {x ∈ X : y ∈ F (x)}.

Osservazione 2.2. Il concetto di multifunzione e, a rigore, identico a quello di relazionebinaria. A differenza da quanto avviene per le funzioni (univoche), ogni sottoinsieme di X×Ye il grafico di una multifunzione. Spesso, tuttavia, si restringe lo studio alle multifunzioni avalori non vuoti (dom(F ) = X).

Alcune proprieta insiemistiche delle multifunzioni:

Lemma 2.3. Se F : X → 2Y e una multifunzione, allora:

(i) F−(T ) = X \ F+(Y \ T ) per ogni T ∈ 2Y ;(ii) F+(T ) = X \ F−(Y \ T ) per ogni T ∈ 2Y ;

(iii) F−(∪i∈ITi) = ∪i∈IF−(Ti) per ogni (Ti)i∈I ⊆ 2Y ;(iv) F+(∩i∈ITi) = ∩i∈IF−(Ti) per ogni (Ti)i∈I ⊆ 2Y ;(v) IF (y) = F−({y}) per ogni y ∈ Y .

8 A. IANNIZZOTTO

2.1. Multifunzioni fra spazi topologici. Per le multifunzioni fra spazi topologici lanozione di continuita ha diverse possibili estensioni:

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

(i) F e semi-continua inferiormente (s.c.i.) in x se per ogni A ∈ τX t.c. F (x) ∩A 6= ∅esiste U ∈ UX(x) t.c. F (z) ∩ A 6= ∅ per ogni z ∈ U ;

(ii) F e semi-continua superiormente (s.c.s.) in x se per ogni A ∈ τX t.c. F (x) ⊆ Aesiste U ∈ UX(x) t.c. F (z) ⊆ A per ogni z ∈ U ;

(iii) F e semi-continua in x se per ogni A ∈ τX t.c. F (x) ⊆ A esiste U ∈ UX(x) t.c.F (z) ∩ A 6= ∅ per ogni z ∈ 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) ∈ τY per ogni A ∈ τX ;

(vii) F e chiusa se F (C) ∈ σY per ogni C ∈ σX .

Caratterizzazioni della semi-continuita inferiore:

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

(i) F e s.c.i.;(ii) F−(A) ∈ τX per ogni A ∈ τY ;

(iii) F+(C) ∈ σX per ogni C ∈ σY ;(iv) IF e aperta.

Caratterizzazioni della semi-continuita superiore:

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

(i) F e s.c.s.;(ii) F+(A) ∈ τX per ogni A ∈ τY ;

(iii) F−(C) ∈ σX per ogni C ∈ σY ;(iv) IF e chiusa.

Tutte le nozioni di continuita introdotte per le multifunzioni sono equivalenti all’usualecontinuita nel caso univoco. Un caso speciale e quello delle multifunzioni i cui valori sonointervalli 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 → 2R e definita da F (x) = [a(x), b(x)] per ogni x ∈ X, allora leseguenti sono equivalenti:

(i) F e s.c.i.;(ii) a e s.c.s. e b e s.c.i.

Dimostrazione. Dimostriamo solo 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.

TEORIA DEI GIOCHI 9

a(x) < y < b(x). Poiche a e s.c.s. e b e s.c.i. abbiamo ay, by ∈ τ e x ∈ ay ∩ by. Dunqueesiste U ∈ U(x) t.c. U ⊆ ay ∩ by. Abbiamo infine y ∈ F (z) per ogni z ∈ 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 → 2R e definita da F (x) = [a(x), b(x)] per ogni x ∈ X, allora leseguenti 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 contenutia:

Esempio 2.9. La multifunzione F : R→ 2R 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.

Esempio 2.10. La multifunzione F : R→ 2R 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.

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

∂g(x) = {y ∈ R : y(v − x) 6 g(v)− g(x) per ogni v ∈ R}.La multifunzione ∂g : R→ 2R e s.c.s.

La semi-continuita e a nozione piu debole:

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

La semi-continuita superiore e legata alla chiusura e alla compattezza degli insiemi.

Lemma 2.13. Se (X, τX) e uno spazio topologico, (Y, τY ) e uno spazio normale, F : X → 2Y

e s.c.s. a valori chiusi, allora gr(F ) ⊆ X × Y e chiuso.

Dimostrazione. Proviamo che A = (X × Y ) \ gr(F ) e aperto. Per ogni (x, y) ∈ A, esistonoV,W ∈ τY t.c. y ∈ V , F (x) ⊆ W e V ∩W = ∅. Poiche F e s.c.s. esiste U ∈ UX(x) t.c.F (U) ⊆ W . Dunque U × V ∈ U(x, y) e U × V ⊆ A. �

L’implicazione non si inverte, fuorche in casi particolari:

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

10 A. IANNIZZOTTO

Estensione del Teorema di Weierstraß:

Teorema 2.15. Se (X, τX) e uno spazio compatto, (Y, τY ) uno spazio topologico, F : X →2X 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 ∈ Xesiste Jx ⊆ I finito t.c. F (x) ⊆ ∪i∈JxAi. Posto J = ∪x∈XJx, la famiglia (F+(Ai))i∈J eun ricoprimento aperto di X, dunque esiste H ⊆ J finito t.c. X = ∪i∈HF+(Ai), da cuiF (X) ⊆ ∪i∈HAi. Percio, F (X) e compatto. �

Soffermiamoci sul caso particolare delle multifunzioni fra spazi metrici:

Definizione 2.16. Siano (X, dX), (Y, dY ) spazi metrici, dYH denoti la distanza di Hausdorffsu Y , F : X → 2Y : F e lipschitziana se esiste L > 0 t.c.

dYH(F (x), F (z)) 6 LdX(x, z) per ogni x, z ∈ X.

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

Lemma 2.17. Se (X, dX), (Y, dY ) sono spazi metrici e F : X → 2Y e lipschitziana, alloraF 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. BY

r (y) ⊆ A. Dunque, posto δ = r/L, per ogni z ∈ BXδ (x)

hodYH(F (z), F (x)) 6 LdX(x, z) < r,

da cui dY (y, F (z)) < r, che implica F (z) ∩ A 6= ∅. Pertanto, BXδ (x) ⊆ F−(A) e F risulta

s.c.i. (Lemma 2.5). �

Estensione del Teorema di Darboux:

Teorema 2.18. Se (X, τX) e uno spazio connesso, (Y, τY ) uno spazio topologico, F : X → 2X

semi-continua a valori non vuoti e connessi, allora F (X) e connesso.

Dimostrazione. Procediamo per assurdo: siano A,B ∈ τY 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 apertiin X: infatti, per ogni x ∈ F−(A) si ha in effetti F (x) ⊆ A, quindi esiste U ∈ UX(x) t.c.F (z) ⊆ A per ogni z ∈ 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:

Definizione 2.19. Siano X, Y , Z insiemi non vuoti, F : X → 2Y , G : X → 2Z : il prodottocartesiano di F e G e la multifunzione F ×G : X → 2Y×Z definita per ogni x ∈ X da

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

Lemma 2.20. Se (X, τX), (Y, τY ), (Z, τZ) sono spazi topologici e F : X → 2Y , G : X → 2Z ,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.;

TEORIA DEI GIOCHI 11

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

Dimostrazione. Dimostriamo solo (i): siano (Ai)i∈I , (Bi)i∈I sottofamiglie di τY , τZ rispetti-vamente. Si ha

(F ×G)−(∪i∈IAi ×Bi) = ∪i∈I(F−(Ai) ∩G−(Bi)

),

e il secondo insieme e aperto. Dalla Definizione 2.19 segue che F ×G e s.c.i. �

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

Teorema 2.21. Se (X, τX) e uno spazio connesso, (Y, τY ) uno spazio topologico, F : X → 2Y

s.c.i. a valori non vuoti e connessi, allora gr(F ) e connesso.

Dimostrazione. Segue dal Lemma 2.20 e dal Teorema 2.18, una volta osservato che gr(F ) =(idX × F )(X). �

Un’applicazione:

Lemma 2.22. Se (X, τX), (Y, τY ) sono spazi topologici, S ⊆ X × Y e una delle seguenticondizioni e verificata:

(i) X e connesso, Sx 6= ∅ e connesso per ogni x ∈ X, Sy e aperto per ogni y ∈ Y ;(ii) Y e connesso, Sy 6= ∅ e connesso per ogni y ∈ Y , Sx e aperto per ogni x ∈ X,

allora S e connesso.

Dimostrazione. Sia verificata (i): definiamo F : X → 2Y ponendo F (x) = Sx per ognix ∈ 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∈ASy,e aperto, quindi F e s.c.i. La tesi segue dalla Proposizione 2.21, poiche gr(F ) = S. �

Un lemma di stabilita che sara utile in seguito:

Lemma 2.23. Se (X, τ) e uno spazio topologico, (Y, d) uno spazio metrico, F,G : X → 2Y

s.c.i. a valori non vuoti, r ∈ R+0 e

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

allora la multifunzione H : X → 2Y definita da H(x) = F (x) ∩Br(G(x)) per ogni x ∈ X es.c.i.

Dimostrazione. Sia A ⊆ Y aperto. L’insieme

A = {(y, z) ∈ Y × Y : y ∈ A, d(y, z) < r}e aperto in Y × Y . Ho

(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)) ∩ A cosı che x ∈ (F ×G)−(A). E viceversa.

12 A. IANNIZZOTTO

Per la Proposizione 2.20, la multifunzione F ×G e s.c.i., dunque (F ×G)−(A) e aperto inX (Proposizione 2.5). Da (2.1) segue la tesi. �

2.2. Selezioni continue. Il legame tra analisi multivoca e univoca e dato dalla seguentenozione:

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

Ovviamente ogni multifunzione a valori non vuoti ammette selezioni. Tuttavia, questepossono in generale essere irregolari: la multifunzione dell’Esempio 2.9 non ha alcunaselezione continua. Si deve a Michael [24–26] il principale risultato di esistenza di selezionicontinue per una multifunzione. Questo richiede alcune premesse topologiche:

Definizione 2.25. Sia (X, τ) uno spazio di Hausdorff. Esso e detto paracompatto se ogniricoprimento aperto A di X ammette un raffinamento localmente finito, ovvero un altroricoprimento aperto B di X con le seguenti propriea

(i) per ogni A ∈ A esiste B ∈ B t.c. B ⊆ A;(ii) per ogni x ∈ X esistono U ∈ U(x), Bx ⊆ B finita t.c. U∩B = ∅ per ogni B ∈ B\Bx.

Ogni spazio paracompatto e normale (T4). Ogni spazio metrico e paracompatto. Si hainoltre il seguente teorema (di partizione dell’unita):

Teorema 2.26. Se (X, τ) e uno spazio normale e {Ai}i∈I e un ricoprimento aperto local-mente finito di X, allora esistono una famiglia {ϕi}i∈I di funzioni continue ϕi : X → [0, 1]e una famiglia {Ci}i∈I di chiusi t.c.

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

(iii)∑

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

In particolare, se (X, τ) e uno spazio paracompatto e (Ai)i∈I e un ricoprimento aperto diX, allora esiste una partizione continua dell’unita (ϕi)i∈I subordinata ad (Ai)i∈I (su questaparte, si veda Checcucci, Tognoli & Vesentini [9, p. 157 e p. 223]).

Un lemma preparatorio:

Lemma 2.27. Se (X, τ) e uno spazio topologico paracompatto, (Y, ‖ ·‖) uno spazio normato,F : X → 2Y s.c.i. a valori non vuoti e convessi, allora per ogni ε > 0 esiste fε : X → Ycontinua 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 e un ricoprimentoaperto di X, che ammette un raffinamento localmente finito (Ey)y∈Y (Definizione 2.25), cuie subordinata una partizione continua dell’unita (ϕy)y∈Y (Teorema 2.26). Per ogni x ∈ Xponiamo

fε(x) =∑y∈Y

ϕy(x)y.


E definita una funzione fε : X → Y . Proviamo che fε e continua: per ogni x ∈ X esistonoU ∈ U(x), y1, . . . yn ∈ Y t.c. U ∩ Ey = ∅ per ogni y ∈ Y \ {yi}ni=1; dunque, per ogni z ∈ Uabbiamo

fε(z) =n∑i=1

ϕyi(z)yi,

dunque fε e continua in x. Proviamo infine la formula metrica: procedendo come sopra,assumiamo che per ogni i ∈ {1, . . . n} sia ϕyi(x) > 0, da cui x ∈ Ayi ; pertanto esistewi ∈ F (x) t.c. ‖wi − yi‖ < ε; sia

w =n∑i=1

ϕyi(x)wi,

allora (per convessita di F (x)) abbiamo w ∈ F (x) e anche

‖fε(x)− w‖ 6n∑i=1

ϕyi(x)‖wi − yi‖ < ε,

da cui d(fε(x), F (x)) < ε. �

Il teorema di Michael:

Teorema 2.28. Se (X, τ) e uno spazio topologico paracompatto, (Y, ‖ · ‖) uno spazio diBanach, F : X → 2Y s.c.i. a valori non vuoti, chiusi e convessi, allora F ammette unaselezione continua.

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

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

2n, d(fn(x), fn+1(x)) <

1

2n−1.

Procediamo per induzione. Per n = 1, dalla Proposizione 2.27 segue l’esistenza di f1 : X → Ycontinua t.c. d(f1(x), F (x)) < 1/2 per ogni x ∈ X, n ∈ N. Fissato n ∈ N0, se esistonof1, . . . fn verificanti (2.2), definiamo Fn : X → 2Y ponendo per ogni x ∈ X

Fn(x) = F (x) ∩B1/2n(fn(x)),

cosı che Fn e s.c.i. (Proposizione 2.23) e ha valori non vuoti (per (2.2)) e convessi. Per laProposizione 2.27 esiste fn+1 : X → Y continua t.c. per ogni x ∈ X

d(fn+1(x), Fn(x)) <1

2n+1.

In particolare, per ogni x ∈ X esiste yx ∈ Fn(x) t.c. ‖fn+1(x)− yx‖ < 1/2n+1, da cui

‖fn+1(x)− fn(x)‖ 6 ‖fn+1(x)− yx‖+ ‖yx − fn(x)‖ < 1

2n+

1

2n+1<

1

2n−1.

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

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

14 A. IANNIZZOTTO

Poiche F ha valori chiusi, f e una selezione continua di F . �

Una conseguenza importante e il seguente teorema di estensione-selezione:

Teorema 2.29. Se (X, τ) e uno spazio topologico paracompatto, (Y, ‖ · ‖) uno spazio diBanach, F : X → 2Y s.c.i. a valori non vuoti, chiusi e convessi, C ⊆ X chiuso, g : C → Ycontinua t.c. g(x) ∈ F (x) per ogni x ∈ C, allora F ammette una selezione continuaf : X → Y t.c. f |C = g.

Dimostrazione. Sia F : X → 2Y definita ponendo per ogni x ∈ X

F (x) =

{{g(x)} se x ∈ CF (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(z) ∈ A per ogni z ∈ U ∩C;inoltre F (x) ∩ A 6= ∅, quindi esiste V ∈ U(x) t.c. F (z) ∩ A 6= ∅ per ogni x ∈ V ;posto W = U ∩ V , abbiamo W ∈ U(x) e F (z) ∩ A 6= ∅ per ogni z ∈ W ;

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

Inoltre, F ha valori chiusi e convessi. Per il Teorema 2.28, F ha una selezione continuaf : X → Y , e ovviamente f(x) = g(x) per ogni x ∈ C. �

Di seguito presentiamo alcune applicazioni del Teorema 2.28. La prima e un teorema diestensione continua per funzioni definite su insiemi chiusi (che generalizza, in un certo senso,il Teorema di Tietze):

Corollario 2.30. Se (X, τ) e uno spazio topologico paracompatto, (Y, ‖ · ‖) e uno spaziodi Banach, C ⊂ X e non vuoto e chiuso, g : C → Y e continua, allora esiste f : X → Ycontinua t.c. f(x) = g(x) per ogni x ∈ C.

Dimostrazione. Applichiamo il Teorema 2.29 alla multifunzione costante F (x) = Y per ognix ∈ X. �

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

Corollario 2.31. Se (X, ‖·‖X), (Y, ‖·‖Y ) sono spazi di Banach e ϕ ∈ hom(Y,X) e continuoe suriettivo, allora esiste f : X → Y continua t.c. ϕ ◦ f = idX .

Dimostrazione. Applichiamo il Teorema 2.29 alla multifunzione F = ϕ−1, che ha valori nonvuoti, chiusi e convessi per le ipotesi su ϕ ed e s.c.i. perche ϕ e aperta (ved. Proposizione2.5), come segue dal teorema della mappa aperta (si veda Rudin [33, p. 47]). �

2.3. Punti fissi. Nella teoria dei punti fissi per applicazioni univoche, si distinguono duefamiglie di risultati: i teoremi ’metrici’ di punto fisso dovuti a Banach, Caccioppoli, e quelli’algebrico-topologici’ dovuti a Brouwer, Schauder, Cauty (si veda Granas & Dugundji [16]).Anche il caso multivoco rispecchia questa distinzione.


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

Il teorema di Nadler estende il teorema di Banach & Caccioppoli rispetto all’esistenza dipunti fissi, ma si perde l’unicita:

Teorema 2.33. Se (X, d) e uno spazio metrico completo e F : X → 2X una contrazionemultivoca a valori chiusi, allora fix(F ) 6= ∅.

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

(2.3) xn ∈ F (xn−1), d(xn−1, xn) < βLn−1d(x0, F (x0)) per ogni n ∈ N0.

Procediamo per induzione. L’esistenza di x1 verificante (2.3) e ovvia. Sia n > 1 e sianox0, . . . xn ∈ X verificanti (2.33): in particolare,

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

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

d(xm, xn) 6m∑

i=n+1

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

i=n+1

Li−1;

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, xn) < ε. Poiche X ecompleto, abbiamo xn → x. Da (2.3) ho 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. Poiche F (x) e chiuso, abbiamo infine x ∈fix(F ). �

Il primo, basilare risultato:

Teorema 2.34. Se (X, ‖ · ‖) e uno spazio di Banach, K ⊂ X e compatto e convesso eF : K → 2K e s.c.i. a valori non vuoti, chiusi e convessi, allora fix(F ) 6= ∅.

Dimostrazione. Per il Teorema 2.28, F ammette una selezione continua f : K → K. Per ilTeorema di Schauder [16, p. 119], esiste x ∈ K t.c. f(x) = x. Dunque x ∈ fix(F ). �

Per studiare le multifunzioni s.c.s. occorre richiamare un lemma di approssimazione dovutoa Cellina [7]:

Lemma 2.35. Se K,H ⊂ Rn (n ∈ N0) sono compatti, r > 0 e F : K → 2H e s.c.s. avalori non vuoti, chiusi e convessi, allora esiste g : K → H continua t.c.

gr(g) ⊆ Br(gr(F )).

Il piu noto teorema di punto fisso per le multifunzioni e il seguente, dovuto a Kakutani [19]:

16 A. IANNIZZOTTO

Teorema 2.36. Se K ⊆ Rn (n ∈ N0) e compatto e convesso e F : K → 2K e s.c.s. a valorinon vuoti, chiusi e convessi, allora fix(F ) 6= ∅.

Dimostrazione. Per ogni k ∈ N0, dal Lemma 2.35 segue l’esistenza di gk : K → K continuat.c. gr(gk) ⊆ B1/k(gr(F )). Per il Teorema di Brouwer [16, p. 95] esiste xk ∈ fix(gk). A menodi estratte, abbiamo xk → x per qualche x ∈ K, da cui (xk, xk)→ (x, x), quindi

d((x, x), gr(F )) = limkd((xk, xk), gr(F )) 6 lim

k

1

k= 0.

Poiche gr(F ) e chiuso (Lemma 2.13), abbiamo infine x ∈ fix(F ). �

Il Teorema 2.36 e stato esteso agli spazi vettoriali-topoligici da Glicksberg [15]:

Teorema 2.37. Se (X, τ) e uno spazio vettoriale-topologico localmente convesso di Hausdorff,K ⊂ X compatto e convesso, F : K → 2K a valori chiusi e convessi t.c. gr(F ) e chiuso,allora fix(F ) 6= ∅.

Il seguente risultato dovuto a Browder [5] garantisce l’esistenza di punti fissi per unamultifunzione a fibre aperte:

Teorema 2.38. Se (X, τ) e uno spazio vettoriale-topologico localmente convesso di Haudorff,K ⊂ X e compatto e convesso, F : K → 2K a valori non vuoti e convessi t.c. F−(y) ∈ τper ogni y ∈ K, allora fix(F ) 6= ∅.

Dimostrazione. La famiglia (F−(y))y∈K e un ricoprimento aperto di K, che e compatto,quindi esistono n ∈ N, y1, . . . yn ∈ K t.c. K ⊂ ∪ni=1F

−(yi). Per il Teorema 2.26 esistonoϕ1, . . . ϕn : K → [0, 1] continue t.c.

n∑i=1

ϕi(x) = 1 per ogni x ∈ K

e per ogni i ∈ {1, . . . n} si ha ϕi(x) = 0 per ogni x ∈ K \ F−(yi). Sia

f(x) =n∑i=1

ϕi(x)yi per ogni x ∈ K.

Poiche K e convesso, f : K → K, inoltre f e continua. Osserviamo che f e una selezionedi F : infatti, per ogni x ∈ K, posto Ix = {i ∈ {1, . . . n} : ϕi(x) 6= 0}, per ogni i ∈ Ixotteniamo x ∈ F−(yi), ovvero yi ∈ F (x), da cui per convessita di F (x)

f(x) =∑i∈Ix

ϕi(x)yi ∈ F (x).

Sia C = conv(y1, . . . yn), Y = span(y1, . . . yn). Chiaramente dim(Y ) < ∞, dunque Y eisomorfo a uno spazio euclideo, inoltre f(C) ⊆ C. Possiamo dunque applicare il teorema diBrouwer [16, p. 95] a f |C , trovando x ∈ C ∩ fix(f). Ne segue x ∈ fix(F ). �

In uno spazio di Banach di dimensione infinita, tutti questi teoremi di punto fisso hannoapplicazioni limitate per l’estrema ’rarita’ dei compatti in tali spazi. Si ricorre dunque aipunti fissi approssimati (si veda Branzei et Al. [4]).


Definizione 2.39. Siano (X, d) uno spazio metrico, F : X → 2X , ε > 0 un numero reale,x ∈ X: x e detto ε-punto fisso di F se d(x, F (x)) < ε. L’insieme degli ε-punti fissi di F edenotato fixε(F ).

Vale in merito il seguente risultato:

Teorema 2.40. Se (X, ‖ · ‖) e uno spazio di Banach riflessivo, S ⊆ X limitato, convessot.c. int(S) 6= ∅, F : S → 2S a valori non vuoti e convessi, t.c. gr(F ) e debolmente chiuso,allora per ogni ε > 0 si ha fixε(F ) 6= ∅.

Dimostrazione. L’ultima ipotesi significa che gr(F ) e chiuso rispetto alla topologia prodottodella topologia σ(X∗, X) per se stessa, relativizzata a S × S (leggere due volte aiuta).Supponiamo S = B1(0) (il caso generale si tratta con aggiustamenti minori). Fissato ε > 0,trovo δ ∈ R t.c. 0 < δ < min{1, ε} e poniamo K = (1 − δ)cl(S) = B1−δ(0), e per ognix ∈ K

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

Dunque, K e un insieme chiuso, convesso, limitato in X, quindi debolmente compatto (siveda Fabian et Al. [11]) e G : K → 2K ha valori convessi e grafico debolmente chiuso.Per il Teorema 2.37 esiste x ∈ fix(G), ovvero esiste y ∈ F (x) t.c. x = (1− δ)y, da cui

d(x, F (x)) 6 ‖x− y‖ = δ‖x‖ < ε.

In conclusione x ∈ fixε(F ). �

2.4. Il principio KKM. Concludiamo questa sezione con un celebre risultato di Knaster,Kuratowski & Mazurkiewicz [18], in base al quale la famiglia dei valori di unamultifunzione (soggetta a una peculiare ipotesi geometrica) ha la proprieta dell’intersezionefinita (si veda anche [16, p. 37]).

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

conv(x1, . . . xn) ⊆ ∪ni=1F (xi).

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

Teorema 2.42. Se X e uno spazio vettoriale, S ⊂ X e non vuoto, F : S → 2X soddisfaKKM e F (x) e finitamente chiuso1 per ogni x ∈ S, allora per ogni n ∈ N0, x1, . . . xn ∈ Ssi ha

∩ni=1F (xi) 6= ∅.

Dimostrazione. Procediamo per assurdo: sia dunque

(2.4) ∩ni=1 F (xi) = ∅.

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

18 A. IANNIZZOTTO

Denotiamo X = span(x1, . . . xn), C = conv(x1, . . . xn). Su X definiamo una topologiavettoriale di Hausdorff, rendendo X omeomorfo a uno spazio euclideo: in tale spazio, C echiuso 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 ∈ ∩ni=1F (xi) (rammentiamo che gli insiemi F (xi) ∩ X sono chiusi),contro (2.4). 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) =n∑i=1

λi(x)∑nj=1 λj(x)

xi per ogni x ∈ X.

La funzione f e continua e si ha f(x) ∈ C per ogni x ∈ X. Dunque, per il teorema diBrouwer [16, p. 95], esiste x0 ∈ fix(f |C). Applicando la condizione KKM otteniamo

x0 = f(x0) ∈ conv ({xi : i ∈ Ix0}) ⊆ ∪i∈Ix0F (xi),

cosı che esiste i ∈ Ix0 t.c. x0 ∈ F (xi), da cui λi(x0) = 0, contro la definizione di λi. Questoconclude la dimostrazione. �

Come conseguenza, si puo provare che esiste un punto comune a tutti i valori di unamultifunzione:

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

∩x∈SF (x) 6= ∅.

Dimostrazione. Si vede facilmente che F (x) e finitamente chiuso per ogni x ∈ S. SiaF : S → 2F (x0) definita ponendo per ogni x ∈ S

F (x) = F (x) ∩ F (x0).

Per il Teorema 2.42, dom(F ) = S. Per ogni n ∈ N, x1, . . . xn ∈ S si ha

∩ni=1F (xi) = ∩ni=0F (xi) 6= ∅,

dunque (F (x))x∈S e una famiglia di sottoinsiemi chiusi del compatto F (x0) soddisfacentela proprieta dell’intersezione finita. Dunque esiste x ∈ ∩x∈SF (x) (si veda [9, p. 135]), inparticolare x ∈ ∩x∈SF (x). �


3. Giochi non cooperativi ed equilibri di Nash

Ciascuno deve impostare la propria strategia di vita sul presupposto dell’ostilita altrui.

E. Limonov

In questa sezione riprendiamo il concetto di equilibrio di Nash: usando gli strumentimatematici introdotti nelle sezioni precedenti, dimostreremo l’esistenza di (almeno) unequilibrio di Nash per un gioco statico non cooperativo deterministico con due giocatori,rappresentato in forma strategica da Γ = (X, Y, f, g) (alcune nozioni qui introdotte sipossono estendere al caso di piu giocatori). Per approfondimenti rimandiamo ai testi diAubin [1], Colombo [10] e Gibbons [14].

Specializziamo la Definizione 1.12:

Definizione 3.1. Un equilibrio (di Nash) per Γ e una coppia (x, y) ∈ X × Y t.c.

(i) f(x, y) = supXf(·, y);

(ii) g(x, y) = supYg(x, ·).

L’insieme degli equilibri per Γ si denota Ne(Γ).

Una nozione collegata a quella di equilibrio e la seguente:

Definizione 3.2. Nel gioco Γ = (X, Y, f, g), la coppia (x, y) ∈ X × Y e un ottimo (diPareto) se non esiste un’altra coppia (x, y) ∈ X×Y verificante una delle seguenti condizioni:

(i) f(x, y) > f(x, y), g(x, y) > g(x, y);(ii) f(x, y) > f(x, y), g(x, y) > g(x, y).

L’insieme degli ottimi per Γ si denota Po(Γ).

Queste due nozioni sono indipendenti, come dimostra il piu celebre problema della teoriadei giochi, noto come dilemma del prigioniero:

Esempio 3.3. Due individui vengono arrestati con l’accusa di omicidio e richiusi in celleseparate. Il commissario fa a ogni prigioniero la seguente proposta: ’Se confessi (accusandoil tuo complice) vi incriminero entrambi e sarete condannati a 10 anni di prigione, ma tusarai liberato per aver collaborato; se confessate entrambi avrete uno sconto di pena e sareteliberi in 5 anni; se nessuno di voi confessa, resterete in galera solo per il tempo del processo,cioe 1 anno.’ Ogni prigioniero sa che la stessa offerta e stata fatta anche all’altro, e devedecidere cercando di ridurre al minimo gli anni che deve passare in cella. Denotati P , Qi prigionieri, X = Y = {c, t} le strategie (confessare e tacere) ed eguagliati i pay-off agliopposti delle durate delle condanne, si ottiene la seguente tabella:

P\Q c tc (−5,−5) (0,−10)t (−10, 0) (−1,−1)

Si vede che Ne(Γ) = {(c, c)}, mentre Po(Γ) = {(t, t)}. Non potendo comunicare, i dueprigionieri sceglieranno di confessare, raggiungendo cosı un equilibrio inefficiente. Questo

20 A. IANNIZZOTTO

esito e tipico dei giochi non cooperativi, nei quali la competizione esasperata preclude lapossibilita di accordi.

Un equilibrio e, di solito, la miglior soluzione raggiungibile nei giochi non cooperativi. Sipone pertanto il problema di individuare condizioni sufficienti per l’esistenza di (almeno) unequilibrio. Per ottenere questo risultato occorre estendere il concetto di strategia utilizzatonella Sezione , introducendo il concetto di tipo probabilistico di strategia mista.

3.1. Strategie miste e teorema di Nash. Richiamiamo un’elementare nozione dal calcolodelle probabilita (si veda Scozzafava [34]):

Definizione 3.4. Sia X = {x1, . . . xn} un insieme finito (n ∈ N0, xi 6= xj per ogni i 6= j):una distribuzione di probabilita su X e una funzione p : X → [0, 1] t.c.

n∑i=1

p(xi) = 1.

Le strategie miste si possono rappresentare geometricamente: sia ϕ : X → Rn definita daϕ(xi) = ei per ogni i ∈ {1, . . . n} (in particolare, ϕ e iniettiva). Sia Π(X) l’insieme di tuttele distribuzioni di probabilita su X, e sia ϕ : Π(X)→ Rn definita da

ϕ(p) =n∑i=1

p(xi)ϕ(xi) per ogni p ∈ Π(X).

Chiaramente si ha ϕ(Π(X)) = conv(ϕ(X)), ovvero ϕ(Π(X)) e il simplesso (n − 1)-dimensionale di vertici e1, . . . en (in particolare, esso e un insieme compatto e convesso), e ϕe un isomorfismo tra Π(X) (con le operazioni formali) e ϕ(Π(X)). Identificando, per ognii ∈ {1, . . . n}, xi con la distribuzione p ∈ Π(X) definita da p(xj) = δi,j per ogni j ∈ {1, . . . n},possiamo considerare ϕ come un’estensione di ϕ (unica a meno di isomorfismi).

Osservazione 3.5. La Definizione 3.4 si puo estendere al caso in cui X e infinito: allorauna distribuzione di probabilita su X e una misura p su X, t.c. p(X) = 1. Per chiarire: seX rappresenta l’insieme dei possibili esiti di un evento aleatorio (ad esempio una corsa dicavalli), la funzione p associa a ogni esito (rappresentato da un elemento o da un sottoinsiemedi X) la somma che uno scommettitore punta su tale esito con la prospettiva di vincere 1 seil pronostico si rivela esatto.

Introduciamo la seguente nozione:

Definizione 3.6. Nel gioco Γ, una strategia mista per il giocatore P (Q) e una distribuzionedi probablilita sull’insieme delle strategie X (Y ). Gli elementi di X (Y ) sono detti strategiepure.

L’impiego di strategie miste corrisponde al seguente schema: P e visto come uno speculatoreche dispone di un capitale pari a 1, da investire in un insieme X di attivita; scegliereuna strategia mista p equivale allora a investire la somma p(xi) nell’attivita xi, per ognii ∈ {1, . . . n} (si puo formulare lo stesso concetto utilizzando lo schema delle scommesse). Si evisto come l’insieme Π(X) si puo identificare con un sottoinsieme convesso e compatto di uno


spazio euclideo: e quindi ragionevole ipotizzare, come faremo in seguito, che l’insieme dellestrategie (miste) di ciascun giocatore goda di queste proprieta geometriche e topologiche.

Esempio 3.7. Nel gioco considerato nell’Esempio 1.6, esteso alle strategie miste, si poneX = Y = [0, 1]: per ogni (x, y) ∈ [0, 1]2 (che rappresenta la valutazione da parte di Pche l’evento p abbia probabilita x e d invece probabilita (1− x), mentre Q attribuisce a pprobabilita y e a d probabilita (1− y)) i pay-off dei due giocatori sono rispettivamente

f(x, y) = xy − x(1− y)− (1− x)y + (1− x)(1− y) = 4xy − 2x− 2y + 1,

g(x, y) = −xy + x(1− y) + (1− x)y − (1− x)(1− y) = −4xy + 2x+ 2y − 1

(si noti che f(x, y) = −g(x, y)).

Per determinare gli equilibri di un gioco Γ si fa uso delle multifunzioni di miglior rispostaper i singoli giocatori e globale, RP : Y → 2X , RQ : X → 2Y , R : X × Y → 2X×Y , definiteper ogni (x, y) ∈ X × Y da

RP (y) ={x ∈ X : f(x, y) = sup

Xf(·, y)

},

RQ(x) ={y ∈ Y : g(x, y) = sup

Yg(x, ·)

},

R(x, y) = RP (y)×RQ(x).

Le multifunzioni ora introdotte permettono di rappresentare gli equilibri di Γ:

Lemma 3.8. Si ha Ne(Γ) = fix(R).

Dimostrazione. Sia (x, y) ∈ Ne(Γ), allora per la Definizione 3.1

f(x, y) = supXf(·, y), g(x, y) = sup

Yg(x, ·),

da cui (x, y) ∈ R(x, y). E viceversa. �

Il seguente teorema di esistenza di un equilibrio e il piu celebre risultato della teoria deigiochi, ed e dovuto a Nash [29]:

Teorema 3.9. Se X ⊂ Rn, Y ⊂ Rm (n,m ∈ N0) sono convessi e compatti, f, g : X×Y → Rsono continue e

(i) f(·, y) e quasi-concava2 per ogni y ∈ Y ;(ii) g(x, ·) e quasi-concava per ogni x ∈ X,

allora Ne(Γ) 6= ∅.

Dimostrazione. Adottiamo su X e su Y le rispettive topologie euclidee, e su X × Y latopologia prodotto. Intendiamo applicare alla multifunzione R : X × Y → 2X×Y il Teorema2.36.

2Se X e un insieme convesso in uno spazio vettoriale e f : X → R, allora f e detta quasi-concava (risp.

quasi-convessa se f c (risp. fc) e convesso per ogni c ∈ R.

22 A. IANNIZZOTTO

La multifunzione RP : Y → 2X ha valori non vuoti, chiusi e convessi. Infatti, per ogniy ∈ Y , la f(·, y) : X → R e continua su un compatto, quindi Teorema di Weierstraß esistex ∈ X t.c.

f(x, y) = supXf(·, y) = c,

da cui x ∈ RP (y); inoltre l’insieme RP (y) = f(·, y)c e chiuso e convesso per (i) (in effetti,RP (y) e compatto perche X e compatto).

Proviamo ora che gr(RP ) e chiuso in Y ×X, procedendo per assurdo: sia (yn, xn) ∈ gr(RP )per ogni n ∈ N e (yn, xn) → (y, x), ma (y, x) /∈ gr(RP ). Allora f(x, y) < supX f(·, y). Siaε ∈ R t.c.

0 < ε < supXf(·, y)− f(x, y).

Esiste x ∈ X t.c.

f(x, y) > f(x, y) + ε.

per continuita di f per n ∈ N abbastanza grande abbiamo

|f(xn, yn)− f(x, y)| < ε

3,

|f(x, yn)− f(x, y)| < ε

3.

Usando le precedenti diseguaglianze, per n ∈ N abbastanza grande otteniamo

f(xn, yn) < f(x, y) +ε

3< f(x, y)− 2ε

3< f(x, yn),

contro l’ipotesi che xn ∈ RP (yn). Pertanto gr(RP ) e chiuso, quindi RP e s.c.s. (Lemma2.14).

Similmente si prova che RQ : X → 2Y e s.c.s. a valori non vuoti, compatti e convessi.

Ne segue che R : X × Y → 2X×Y e s.c.s. (Lemma 2.20) a valori non vuoti, compatti econvessi. Sono pertanto soddisfatte le ipotesi del Teorema 2.36, da cui segue che fix(R) 6= ∅.Per il Lemma 3.8 ho Ne(Γ) 6= ∅. �

Osservazione 3.10. Usando un’attrezzatura matematica piu sofisticata, e possibile provareversioni generalizzate del Teorema 3.9 (per esempio, in cui X e Y sono sottoinsiemi compattie convessi di uno spazio di Banach di dimensione infinita).

Oltre al risultato di esistenza, il metodo sopra illustrato fornisce un algoritmo per individuaregli equilibri, che descriviamo limitandoci al caso semplice in cui X = Y = [0, 1]. I graficidelle multifunzioni RP e RQ si possono rappresentare come curve inscritte nel quadrato[0, 1]× [0, 1] (in generale, queste curve potranno contenere tratti verticali). Si ha allora, peril Lemma 3.8,

(3.1) Ne(Γ) = gr(RP ) ∩ gr(RQ).

Nella Fig. 1, questi punti sono (0, 0) e (1, 1).


Figura 1. Il metodo dell’intersezione.

3.2. Esempi. In questa sezione presentiamo alcuni esempi e applicazioni: alcuni di questisono veri ’giochi’ o esercizi matematici, altri sono modelli realmente usati nelle scienzesociali. Tutti possono essere risolti utilizzando il Teorema 3.9 per provare l’esistenza degliequilibri, e la formula (3.1) per determinarli esplicitamente.

Esempio 3.11. Nel gioco della battaglia dei sessi, come abbiamo visto nell’Esempio 1.13,(s, s) e (t, t) sono equilibri di Nash. Passando dalle strategie pure a quelle miste, definiamoX = Y = [0, 1] e f, g : [0, 1]2 → R ponendo per ogni (x, y) ∈ [0, 1]

f(x, y) = 10xy + 0x(1− y) + 0(1− x)y + 5(1− x)(1− y) = 15xy − 5x− 5y + 5

(si puo pensare a x e a (1− x) come al tempo passato allo stadio e a teatro, rispettivamente,da P ). Analogamente, per ogni (x, y) ∈ [0, 1] abbiamo

g(x, y) = 15xy − 10x− 10y + 10.

Il Teorema 3.9 garantisce l’esistenza di almeno un equilibrio. In effetti, ve ne sono tre.Semplici calcoli forniscono le multifunzioni di miglior risposta:

RP (y) =

{0} se y ∈ [0, 1/3)

[0, 1] se y = 1/3

{1} se y ∈ (1/3, 1]

,

RQ(x) =

{0} se x ∈ [0, 2/3)

[0, 1] se x = 2/3

{1} se x ∈ (2/3, 1]

.

Gli equilibri si ottengono mediante (3.1):

Ne(Γ) =

{(0, 0),

(2

3,1

3

), (1, 1)

}(due di essi corrispondono a strategie pure).

Osserviamo che gli equilibri in strategie miste dipendono dai valori dei pay-off, mentre quelliin strategie pure solo dalle preferenze (Definizione 1.2).

24 A. IANNIZZOTTO

Esempio 3.12. Nel gioco noto come caccia al cinghiale, due cacciatori P , Q devono sceglierese andare a caccia di cinghiale o di lepri (X = Y = {c, l}), sapendo che per catturare uncinghiale bisogna essere in due, mentre per catturare molte lepri e meglio separarsi. Si ha laseguente tabella dei pay-off:

P\Q c lc (10, 10) (0, 8)l (8, 0) (4, 4)

Si ha Ne(Γ) = {(c, c), (l, l)} ma Po(Γ) = {(c, c)}. Passando alle strategie miste si trova unterzo equilibrio (2/3, 2/3).

Esempio 3.13. Nel gioco dei fumatori, due fumatori P , Q si trovano in una piccola stanza:entrambi hanno voglia di fumare, ma sono infastiditi dall’aria viziata, pertanto ognuno deidue vorrebbe fumare da solo, ma preferisce comunque fumare insieme all’altro piuttosto cheastenersi. Si ha la seguente tabella dei pay-off:

P\Q f nf (1, 1) (2, 0)n (0, 2) (0, 0)

Studiamo Γ direttamente in strategie miste: poniamoo X = Y = [0, 1] e ricaviamo

f(x, y) = 2x− xy, g(x, y) = 2y − xy per ogni (x, y) ∈ [0, 1]2.

Ne segue che RP (y) = RQ(x) = {1} per ogni (x, y) ∈ [0, 1]2, cosı che Ne(Γ) = {(1, 1)},ovvero P e Q scelgono entrambi di fumare. Si noti che Po(Γ) = ∅. Questo gioco e un casoparticolare del cosiddetto paradosso liberale, secondo il quale in assenza di divieti ognunotende a fare come gli pare senza curarsi del bene comune.

Esempio 3.14. Nel gioco del pollo, reso celebre dal film ’Rebel without a cause’ di NicholasRay (1955), due personaggi P , Q si sfidano a correre in macchina verso un burrone: perdechi sterza per primo. Ogni giocatore dispone di due strategie, sterzare (s) e tirare dritto (d);i pay-off sono, rispettivamente, 10 per la vittoria, 5 per il pareggio, 1 per la sconfitta e 0 perla morte:

P\Q s ds (5, 5) (1, 10)d (10, 1) (0, 0)

Come si vede, Ne(Γ) = {(s, d), (d, s)} e Po(Γ) = ∅. Passando alle strategie miste si trovaun altro equilibrio, (1/6, 1/6). Questo gioco e un utile schema delle competizioni in cui ladeterrenza riveste un ruolo importante (per esempio, la corsa agli armamenti).

Esempio 3.15. Nel gioco dei ragni, due ragni P e Q (di una specie che produce parecchieuova ma poche ragnatele) competono per il possesso di una ragnatela: ciascun ragno puolottare (l) o arrendersi (a); se entrambi lottano, i pay-off assegnati (che rappresentano lepropensioni dei ragni a lottare) sono p, q > 0, in generale la situazione e descritta dalla


tabellaP\Q l al (p, q) (10, 0)a (0, 10) (5, 5)

Gli equilibri dipendono dai valori dei parametri:

• se p, q > 0 si ha Ne(Γ) = {(l, l)};• se p > 0 = q si ha Ne(Γ) = {(l, l), (l, a)};• se p = 0 < q si ha Ne(Γ) = {(l, l), (a, l)};• se p = q = 0 si ha Ne(Γ) = {(l, l), (l, a), (a, l)}.

Esempio 3.16. Nel gioco dei candidati, le proposte programmatiche in vista di un’elezionesono rappresentate dai numeri reali compresi tra 0 (estrema sinistra) e 1 (estrema destra)e si suppone che gli elettori siano uniformemente distribuiti lungo questo intervallo escelgano il candidato col programma piu vicino alle loro idee: due candidati P e Q devonoformulare i loro programmi, col vincolo che quello di P si collochi ’piu a sinistra’ di quellodi Q, e ovviamente puntano entrambi a ottenere la maggioranza dei voti. Il gioco Γ, nonrappresentabile in una tabella, presenta X = Y = [0, 1] e le multifunzioni di miglior risposta

RP (y) ={x ∈ [0, 1] :

x+ y

2>

1

2

}= [1− y, 1],

RQ(x) ={y ∈ [0, 1] :

x+ y

26

1

2

}= [0, 1− x].

Si ottieneNe(Γ) =

{(x, 1− x) : x ∈ [0, 1]

}(in questo caso RP , RQ hanno infiniti valori non degeneri).

Esempio 3.17. Riprendiamo il gioco considerato nell’Esempio 3.16, ambientandolo in unPaese di orientamento politico non neutrale: sia ϕ : [0, 1] → [0, 1] la densita con cui glielettori si distribuiscono da ’sinistra’ a ’destra’, supponiamo ϕ continua e poniamo

Φ(t) =

∫ t

0

ϕ(τ)dτ per ogni t ∈ [0, 1],

chiaramente sotto il vincolo Φ(1) = 1. In questo caso, le funzioni di miglior risposta sono

RP (y) ={x ∈ [0, 1] : Φ

(x+ y

2

)>

1

2

},

RQ(x) ={y ∈ [0, 1] : Φ

(x+ y

2

)6

1

2

}.

In particolare, se ϕ(t) = 2t per ogni t ∈ [0, 1] (cioe se l’elettorato e prevalentementeconservatore), si ha

RP (y) =

{∅ se y ∈ [0,

√2− 1)[√

2− y, 1]

se y ∈ [√

2− 1, 1],

RQ(x) =

{[0, 1] se x ∈ [0,

√2− 1)[

0,√

2− x]

se x ∈ [√

2− 1, 1]..

26 A. IANNIZZOTTO

Dunque,

Ne(Γ) ={

(x,√

2− x) : x ∈ [√

2− 1, 1]}.

Si puo concludere che al candidato di sinistra non conviene adottare posizioni estreme.

Esempio 3.18. Il duopolio di Cournot e un classico modello economico: due produttori Pe Q si contendono l’intero mercato di un bene: i dati fissi sono la soglia di esaurimento delmercato a > 0 e il costo unitario di produzione c > 0; le strategie rappresentano le quantitaprodotte, cosı che X = Y = [0, a]. Si introduce una funzione di domanda (identificata colprezzo) p : [0, a]2 → R definita da

p(x, y) =

{a− (x+ y) se x+ y < a0 se x+ y > a

,

da cui i rispettivi pay-off

f(x, y) =

{x(p(x, y)− c) = −x2 − xy + (a− c)x se x+ y < a

−c se x+ y > a,

g(x, y) =

{y(p(x, y)− c) = −y2 − xy + (a− c)y se x+ y < a

−c se x+ y > a.

Le ipotesi del Teorema 3.9 sono verificate, quindi Ne(Γ) 6= ∅. In effetti, massimizzando ipay-off si ottiene il sistema misto

−2x− y + a− c = 0

−2y − x+ a− c = 0

0 6 x 6 a− c0 6 y 6 a− c,

da cui l’unico equilibrio

x =a− c

3, y =

a− c3

.

3.3. Equilibri approssimati. Quando gli insiemi X, Y non sono compatti, e impossibileapplicare il Teorema 3.9. Per questo Branzei et Al. [4] hanno introdotto la nozione diequilibrio approssimato:

Definizione 3.19. Siano Γ = (X, Y, f, g) un gioco, ε > 0: un ε-equilibrio di Nash per Γ euna coppia (x, y) ∈ X × Y t.c.

(i) f(x, y) ≥ supXf(·, y)− ε;

(ii) g(x, y) ≥ supYg(x, ·)− ε.

L’insieme degli ε-equilibri di Nash di Γ si denota Neε(Γ).

Anche in questo caso gli equilibri si possono caratterizzare come punti fissi di una multifun-zione: poniamo per ogni (x, y) ∈ X × Y

RεP (y) =

{x ∈ X : f(x, y) ≥ sup

Xf(·, y)− ε

},


RεQ(x) =

{y ∈ Y : g(x, y) ≥ sup

Yg(x, ·)− ε

},

Rε(x, y) = RεP (y)×Rε

Q(x).

Come nel Lemma 3.8, si ha

(3.2) Neε(Γ) = fix(Rε)

L’esistenza di ε-equilibri si puo dimostrare sotto ipotesi piu blande riguardo X, Y (compen-sate da condizioni piu restrittive su f , g) rispetto a quelle del Teorema 3.9:

Teorema 3.20. Se (X, dX), (Y, dY ) sono spazi metrici e

(i) f, g : X × Y → R sono uniformemente continue rispetto alla metrica

d((x, y), (z, w)

)= dX(x, z) + dY (y, w) per ogni (x, y), (z, w) ∈ X × Y ;

(ii) fixδ(Rρ) 6= ∅ per ogni ρ, δ > 0,

allora per ogni ε > 0 si ha Neε(Γ) 6= ∅.

Dimostrazione. Fissiamo ε > 0. Per (i) esiste η > 0 t.c. per ogni (x, y), (z, w) ∈ X × Y t.c.

d((x, y), (z, w)

)<η

2

si ha

(3.3) max {|f(x, y)− f(z, w)| , |g(x, y)− g(z, w)|} < ε

2.

Per (ii) esiste (x, y) ∈ fixη/2(Rε/2), cioe (Definizione 2.39) esistono z ∈ Rε/2P (y) e w ∈ Rε/2

Q (x)t.c.

d((x, y), (z, w)) ≤ η

2< η.

Per (3.3) ne segue

supXf(·, y)− ε ≤ f(z, y)− ε

2< f(x, y),

supYg(x, ·)− ε ≤ g(x,w)− ε

2< g(x, y),

quindi (x, y) ∈ Neε(Γ). �

L’ipotesi (i) e difficile da verificare. Possiamo ricorrere alla teoria dei punti fissi approssimati:

Corollario 3.21. Se X, Y sono sottoinsiemi limitati convessi di spazi di Banach riflessivit.c. int(X), int(Y ) 6= ∅ e

(i) f, g : X × Y → R sono uniformemente continue rispetto alla metrica

d((x, y), (z, w)

)= ‖x− z‖X + ‖y − w‖Y per ogni (x.y), (z, w) ∈ X × Y ;

(ii) Rρ : X × Y → 2X×Y ha valori non vuoti e convessi per ogni ρ > 0;(iii) gr(Rρ) e debolmente chiuso per ogni ρ > 0,

allora per ogni ε > 0 si ha Neε(Γ) 6= ∅.

28 A. IANNIZZOTTO

Dimostrazione. Da (ii) e (iii) segue, per il Teorema 2.40, che per ogni δ, ρ > 0

fixδ(Rρ) 6= ∅.

Rammentando anche (i), vediamo che sono verificate tutte le ipotesi del Teorema 3.20,dunque Neε(Γ) 6= ∅ per ogni ε > 0. �

Ovviamente, la tecnica degli equilibri approssimati e usata in contesti piuttosto astratti.Concludiamo questa sezione mostrando un’applicazione del Teorema 3.20:

Esempio 3.22. Siano (X, ‖ · ‖) uno spazio normato, v ∈ X \ {0} e f, g : X × X → Rdefinite da

f(x, y) = −‖x− y‖, g(x, y) = −∥∥∥x− y − v

1 + ‖x‖

∥∥∥ per ogni (x, y) ∈ X ×X.

Studiamo il gioco Γ = (X,X, f, g). Si vede facilmente che la multifunzione di migliorrisposta (congiunta) e data da

R(x, y) ={(y, x− v

1 + ‖x‖

)}per ogni (x, y) ∈ X ×X,

pertanto fix(R) = ∅, ovvero Ne(Γ) = ∅. Cerchiamo dunque equilibri approssimati, appli-cando il Teorema 3.20. Le funzioni f, g : X × X → R sono lipschitziane (in particolare,uniformemente continue). Per f la cosa e ovvia. Per g, si dimostra come segue: fissati(x1, y1), (x2, y2) ∈ X ×X, abbiamo∣∣g(x1, y1)− g(x2, y2)

∣∣ 6 ∥∥∥x1 − y1 − v

1 + ‖x1‖− x2 + y2 +

v

1 + ‖x2‖

∥∥∥6 ‖x1 − x2‖+ ‖y1 − y2‖+ ‖v‖

∣∣‖x1‖ − ‖x2‖∣∣(1 + ‖x1‖)(1 + ‖x2‖)

6 (1 + ‖v‖)d((x1, y1), (x2, y2)

).

Inoltre, fissato δ > 0, per ogni x ∈ X t.c. ‖x‖ > ‖v‖/δ abbiamo

d((x, x), R(x, x)

)=

‖v‖1 + ‖x‖

< δ,

da cui (x, x) ∈ fixδ(R). In particolare, per ogni ρ, δ > 0 abbiamo fixδ(Rρ) 6= ∅. Cosı leipotesi (i) e (ii) del Teorema 3.20 sono verificate. Dunque, per ogni ε > 0 si ha Neε(Γ) 6= ∅(in effetti si dimostra che (x, x) ∈ Neε(Γ) per ogni x ∈ X con ‖x‖ abbastanza grande).

4. Giochi a somma nulla e teoria del minimax

Mors tua, vita mea.

Anonimo

In questa sezione, dedicata ai giochi a somma nulla, il concetto di equilibrio di Nash vienemesso in relazione con quello di minimax, che e piu generale. Per la teoria del minimax,rimandiamo a Ricceri & Simons [31].


Definizione 4.1. Un gioco Γ = (X, Y, f, g) e detto a somma nulla se

f(x, y) + g(x, y) = 0 per ogni (x, y) ∈ X × Y .

In questo caso il gioco si denota Γ = (X, Y, f).

I giochi a somma nulla corrispondono alle interazioni in cui due (o piu) soggetti si contendonoun capitale fissato: i guadagni di uno equivalgono alle perdite dell’altro. Prendiamo dapprimain esame il caso finito, ovvero X = {x1, . . . xn}, Y = {y1, . . . ym} (n,m ∈ N0). Se il giocatoreP (che gioca per primo) sceglie la strategia xi (1 ≤ i ≤ n), allora Q minimizza la sua perditascegliendo yj (1 ≤ j ≤ m) t.c.

f(xi, yj) = minYf(xi, ·).

Sapendo cio, P sceglie una strategia xi t.c.

minYf(xi, ·) = max

XminYf.

Similmente, se Q gioca per primo, la sua scelta ricade su yj t.c.

maxX

f(·, yj) = minY

maxX

f.

Questo ragionamento conduce a un concetto di equilibrio diverso da (in effetti, come sivedra, piu generale di) quello formulato da Nash: una coppia (xi, yj) ∈ X × Y verificantel’eguaglianza di minimax

(4.1) maxX

minYf = min

YmaxX

f.


P\Q y1 y2x1 1 2x2 0 1x3 −1 0

Osservando la tabella (i cui numeri rappresentano i pay-off di P e contemporaneamentegli opposti dei pay-off di Q), si ricava Ne(Γ) = {(x1, y1)}; all’unico equilibrio di Nash di Γcorrisponde il valore 1. D’altra parte si ha

maxX

minYf = min

YmaxX

f = 1,

in particolare vale (4.1).

Se X, Y sono infiniti, l’esistenza di massimi e minimi non e garantita e le definizioni vannoriformulate:

Definizione 4.3. Sia Γ = (X, Y, f) un gioco a somma nulla: sono definiti i valori inferioree superiore di Γ

f∗ = supX

infYf, f ∗ = inf

YsupXf

(entrambi in R ∪ {±∞}). Se vale l’eguaglianza di minimax

(4.2) f∗ = f ∗ (= f),

30 A. IANNIZZOTTO

Figura 2. (0, 0) e un punto di sella per la funzione f(x, y) = y2 − x2.

il gioco Γ ha valore f . Un punto di sella e una coppia (x, y) ∈ X × Y t.c.

supXf(·, y) = f(x, y) = inf

Yf(x, ·).

L’insieme dei punti di sella di f si denota sp(f).

L’idea geometrica di ’sella’ e esemplificata dalla Fig. 2. Alcune precisazioni:

Lemma 4.4. Se Γ e un gioco a somma nulla, allora si ha

f∗ ≤ f ∗.

Dimostrazione. Per ogni (x, y) ∈ X × Y abbiamo

infYf(x, ·) ≤ f(x, y) ≤ sup

Xf(·, y),

da cui la tesi. �

Lemma 4.5. Se Γ e un gioco a somma nulla e (x, y) ∈ sp(f), allora si ha (4.2) e

f(x, y) = f .

Dimostrazione. Si ha

f ∗ ≤ supXf(·, y) = f(x, y) = inf

Yf(x, ·) ≤ f∗.

Dalla Proposizione 4.4 segue (4.2), da quanto sopra segue f(x, y) = f . �

L’implicazione non si inverte:

Esempio 4.6. Siano X = [0, 1], Y =]0, 1] e f : X × Y → R definita da f(x, y) = xy perogni (x, y) ∈ X × Y . L’eguaglianza (4.2) e verificata in quanto

f∗ = sup0≤x≤1

inf0<y≤1

xy = sup0≤x≤1

0 = 0,

f ∗ = inf0<y≤1

sup0≤x≤1

xy = inf0<y≤1

y = 0.


In particolare, f = 0. Tuttavia il gioco in questione non ammette punti di sella. Ragionandoper assurdo, suppongo che (x, y) ∈ sp(f): allora

x y = sup0≤x≤1

xy = y > 0,

mentrex y = inf

0<y≤1xy = 0,

assurdo.

Ovviamente (tenendo conto del fatto che −f esprime i pay-off di Q) si ha:

Teorema 4.7. Se Γ e un gioco a somma nulla, allora si ha

Ne(Γ) = sp(f).

Dal Lemma 4.5 e dal Teorema 4.7 segue che, se Γ ammette un equilibrio di Nash, allora vale(4.2). Pertanto, si considera l’eguaglianza di minimax come una forma debole di equilibrio delgioco e acquistano interesse nell’ottica della teoria dei giochi i risultati che, sotto opprtuneipotesi, assicurano il verificarsi di (4.2): i teoremi di minimax.

4.1. Alcuni teoremi di minimax. Il primo e dovuto a Von Neumann [36]:

Teorema 4.8. Se X ⊂ Rn, Y ⊂ Rm (n,m ∈ N0) sono compatti e convessi, f : X × Y → Re bilineare, allora sp(f) 6= ∅.

Dimostrazione. Sia F : X → 2Y definita da

F (x) ={y ∈ Y : f(x, y) = inf

Yf(x, ·)

}per ogni x ∈ X.

Per ogni x ∈ X l’insieme F (x) 6= ∅ e chiuso e convesso. Sia α : X → R definita da

α(x) = infYf(x, ·) per ogni x ∈ X.

Proviamo che α e uniformemente continua: per ogni ε > 0, per il Teorema di Cantor-Heineesiste δ > 0 t.c.

(4.3) |f(x, y)− f(z, w)| < ε

2per ogni (x, y), (z, w) ∈ X × Y , d((x, y), (z, w)) < δ.

Siano x, z ∈ X t.c. ‖x− z‖Rn < δ: per ogni y ∈ Y ho

α(x) ≤ f(x, y) ≤ supY|f(x, ·)− f(z, ·)|+ f(z, y),

da cuiα(x)− α(z) ≤ sup

Y|f(x, ·)− f(z, ·)| .

Ragionando analogamente otteniamo

α(z)− α(x) ≤ supY|f(x, ·)− f(z, ·)| .

In conclusione, applicando (4.3),

|α(x)− α(z)| ≤ supY|f(x, ·)− f(z, ·)| ≤ ε

2< ε.

32 A. IANNIZZOTTO

Proviamo ora che gr(F ) ⊆ X × Y e chiuso: siano (xn, yn) ∈ gr(F ) per ogni n ∈ N,(x, y) ∈ X × Y t.c. (xn, yn)→ (x, y); per ogni n ∈ N abbiamo

f(xn, yn) = α(xn),

da cui, passando al limite per n→∞,

f(x, y) = α(x)

ovvero (x, y) ∈ gr(F ). Per la Proposizione 2.14, F e s.c.s. Sia ora G : Y → 2X definita da

G(y) ={x ∈ X : f(x, y) = sup

Xf(·, y)

}per ogni y ∈ Y .

Come sopra dimostro che G e s.c.s. a valori non vuoti, chiusi e convessi. Per il Lemma2.20, G× F : X × Y → 2X×Y e s.c.s. a valori compatti. Dunque il Teorema 2.36 assicural’esistenza di (x, y) ∈ fix(G× F ): chiaramente si ha (x, y) ∈ sp(f). �

Il seguente risultato di Fan [12] estende l’eguaglianza di minimax a classi piu ampie difunzioni e di spazi:

Teorema 4.9. Se (X, τX), (Y, τY ) sono spazi vettoriali-topologici localmente convessi diHausdorff, S ⊂ X, T ⊂ Y insiemi non vuoti, compatti e convessi, f : S × T → R t.c.

(i) f(·, y) e s.c.s. e quasi-concava per ogni y ∈ T ;(ii) f(x, ·) e s.c.i. e quasi-convessa per ogni x ∈ S,

allora si ha

supS

infTf = inf

TsupSf.

Dimostrazione. Procediamo per assurdo, supponendo che esista c ∈ R t.c.

(4.4) f∗ < c < f ∗.

L’insieme K = S × T e compatto e convesso nello spazio vettoriale-topologico localmenteconvesso di Hausdorff X × Y . Sia F : K → 2K definita da

F (x, y) ={

(z, w) ∈ K : min{f(x,w)− c, c− f(z, y)} ≤ 0}

per ogni (x, y) ∈ K.

Dimostriamo che

(4.5) ∩(x,y)∈K F (x, y) 6= ∅.

Per ogni (x, y) ∈ K gli insiemi f(x, ·)c, f(·, y)c (non vuoti per (4.4)) sono chiusi per le

ipotesi (i), (ii), quindi

F (x, y) = f(·, y)c × f(x, ·)c

e un sottoinsieme chiuso del compatto K; dunque F ha valori compatti. Inoltre F verificaKKM (ved. Definizione 2.41): lo proviamo per assurdo, supponendo che esistano n ∈ N0,(x1, y1), . . . (xn, yn) ∈ K, (z0, w0) ∈ conv((x1, y1), . . . (xn, yn)) t.c.

(z0, w0) /∈ ∪ni=1F (xi, yi).

Questo significa che, per ogni i ∈ {1, . . . n}, si ha

f(z0, yi) < c < f(xi, w0),


ovvero yi ∈ f(z0, ·)c e xi ∈ f(·, w0)c, insiemi entrambi convessi (ancora (i), (ii)). Pertantow0 ∈ f(z0, ·)c e z0 ∈ f(·, w0)c, ovvero

c < f(z0, w0) < c,

una contraddizione. Applicando il Corollario 2.43 si ottiene (4.5). Sia dunque (z, w) ∈∩(x,y)∈KF (x, y): si ha per ogni (x, y) ∈ K

min{f(x,w)− c, c− f(z, y)} ≤ 0.

Possono presentarsi due casi:

• se f(x,w) ≤ c per ogni x ∈ S, si ha

f ∗ ≤ supSf(·, w) ≤ c,

contro (4.4);• se esiste x ∈ S t.c. f(x,w) > c, allora f(z, y) ≥ c per ogni y ∈ T , da cui

f∗ ≥ infTf(z, ·) ≥ c,

contro (4.4).

In ogni caso, (4.4) conduce a una contraddizione. Tenendo conto della Proposizione 4.4,posso concludere che f∗ = f ∗. �

Osservazione 4.10. Dalla dimostrazione del Teorema 4.9 segue che esiste (x, y) ∈ S × Tt.c.

f(x, y) = f .

Tuttavia, questo non implica che (x, y) sia un punto di sella per f .

Per studiare il problema del minimax in assenza di una struttura vettoriale, tipicamente sitende a sostituire la convessita con la connessione. Uno dei risultati piu raffinati in questocontesto e dovuto a Konig [19]:

Teorema 4.11. Se (X, τX) e uno spazio topologico, (Y, τY ) uno spazio compatto, f : X×Y →R t.c.

(i) ∩x∈Hf(x, ·)c

e connesso per ogni c > f∗, H ⊂ X non vuoto e finito;(ii) ∩y∈Kf(·, y)c e connesso per ogni c < f ∗, K ⊂ Y non vuoto;

(iii) f(·, y) e s.c.s. per ogni y ∈ Y ;(iv) f(x, ·) e s.c.i. per ogni x ∈ X,

allora si ha (4.2).

Il limite del Teorema 4.11 consiste nel fatto che (a differenza dalla convessita) la proprietadi connessione non e stabile rispetto all’intersezione. I seguenti esempi chiariscono alcuniaspetti del problema.

Esempio 4.12. Nello spazio euclideo R2 siano X = B1(0), Y = ∂B1(0), e sia f : X×Y → Rdefinita da

f(x, y) = 〈x, y〉 per ogni (x, y) ∈ X × Y .

34 A. IANNIZZOTTO

La funzione f verifica le ipotesi (iii), (iv) del Teorema 4.11. Inoltre, f(x, ·)c

e connesso perogni c > f∗, x ∈ X e f(·, y)c e connesso per ogni c < f ∗, y ∈ Y , anche se le condizioni (i),(ii) non sono verificate. Nondimeno si ha f∗ = 0, f ∗ = 1.

Esempio 4.13. Siano (Z, ‖ · ‖) uno spazio di Hilbert t.c. dim(Z) =∞ e

X ={x ∈ Z : ‖x‖ ≥ 1

}, Y =

{y ∈ Z : ‖y‖ ≤ 1

}.

Su X adottiamo la topologia forte, su Y quella debole (cosı che Y e compatto). Siaf : X × Y → R definita da

f(x, y) = 〈x, y〉 per ogni (x, y) ∈ X × Y .

La funzione f verifica le ipotesi (i), (iii), (iv) del Teorema 4.11. Inoltre essa verifica’quasi’ l’ipotesi (ii), in quanto ∩y∈Kf(·, y)c e connesso per ogni c ∈ R e ogni K ⊂ Y finito.Nondimeno si ha f∗ = 0, f ∗ = 1.

Nel caso particolare in cui X e un intervallo compatto in R, le ipotesi di connessione possonoessere alleggerite, riferendole a singoli sotto- e sopra-livelli di f (ved. Ricceri [32]). Lostrumento fondamentale per questo studio e il seguente risultato di coincidenza per lemultifunzioni:

Lemma 4.14. Se a, b ∈ R, a < b, (Z, τ) e uno spazio connesso, F,G : Z → 2[a,b] sono s.c.i.a valori non vuoti e connessi, t.c. F (Z) = [a, b], allora esiste z ∈ Z t.c.

F (z) ∩G(z) 6= ∅.

Dimostrazione. Procediamo per assurdo, supponendo

(4.6) F (z) ∩G(z) = ∅ per ogni z ∈ Z.

Sia H = F ×G, allora H : Z → 2[a,b]2 e s.c.i. a valori non vuoti e connessi. Per il Teorema2.18, H(Z) e connesso. Siano

A = {(p, q) ∈ [a, b]2 : p < q}, B = {(p, q) ∈ [a, b]2 : p > q},insiemi aperti in [a, b]2 t.c. H(Z) ⊆ A ∪B (per (4.6)). Poiche F (Z) = [a, b], esiste z0 ∈ Zt.c. a ∈ F (z0): scelto q ∈ G(z0), sempre per (4.6) ho a < q ovvero (a, q) ∈ H(z0) ∩ A, cosıche H(Z) ∩ A 6= ∅. Similmente dimostriamo che H(Z) ∩ B 6= ∅, contro la connessione diH(Z). �

Ne segue un teorema di minimax assai generale:

Teorema 4.15. Se a, b ∈ R, a < b, (Y, τ) e uno spazio topologico, f : [a, b]×Y → R verificale seguenti condizioni:

(i) f(x, ·)c e non vuoto e connesso per ogni x ∈ [a, b], c > f∗;(ii) f(·, y)c e non vuoto e connesso per ogni y ∈ Y , c > f∗;

(iii) f(x, ·) e s.c.i. per ogni x ∈ [a, b];(iv) f(·, y) e s.c.s. per ogni y ∈ Y ,

allora si hasup[a,b]

infYf = inf

Ysup[a,b]

f.


Dimostrazione. Procediamo per assurdo, supponendo che esista c ∈ R t.c.

(4.7) f∗ < c < f ∗.

Su [a, b] adottiamo la topologia euclidea. Siano

S ={

(x, y) ∈ [a, b]× Y : f(x, y) < c}, T =

{(x, y) ∈ [a, b]× Y : f(x, y) > c

}.

Proviamo che S e connesso. Ovviamente [a, b] e connesso; inoltre, per ogni x ∈ [a, b], da

c > f∗ ≥ infYf(x, ·)

segue che Sx 6= ∅, e tale insieme e connesso (i); per ogni y ∈ Y , Sy e aperto (iv). Dunque,l’asserto segue dal Lemma 2.22.

Siano F,G : S → 2[a,b] definite da F (x, y) = {x}, G(x, y) = T y per ogni (x, y) ∈ S. Perogni (x, y) ∈ S, chiaramente F (x, y) 6= ∅ e connesso; F e s.c.i.; inoltre, per ogni x ∈ [a, b],esiste y ∈ Y t.c. x ∈ F (x, y) (come visto sopra), quindi F (S) = [a, b]. D’altra parte,per ogni (x, y) ∈ S l’insieme G(x, y) 6= ∅ e connesso (ii); infine, per ogni z ∈ [a, b] e ogni(x, y) ∈ G−(z) abbiamo

f(z, y) > c,

quindi (iii) esiste W ∈ UY (y) t.c.

f(z, w) > c per ogni w ∈ W ,

cosı che (u,w) ∈ G−(z) per ogni (u,w) ∈ S t.c. w ∈ W ovvero G−(z) e aperto, in particolareG e s.c.i. Per la Proposizione 4.14 esiste (x, y) ∈ S t.c.

F (x, y) ∩G(x, y) 6= ∅.

Si ha dunque x ∈ T y, ovvero (x, y) ∈ S ∩ T , assurdo. �

5. Giochi cooperativi

Hey you, don’t tell me there’s no hope at all.Together we stand, divided we fall.

R. Waters

In questa sezione introduciamo i giochi cooperativi, caratterizzati dalla possibilita che i gioca-tori si associno in coalizioni per perseguire una maggiore utilita: presupposto fondamentaleperche cio avvenga e che i giocatori possano comunicare tra loro stabilendo degli accordi.Per semplicita esamineremo il caso dei giochi cooperativi statici. Per approfondimentirimandiamo a Colombo [10], Morgenstern [27].

Definizione 5.1. Siano P un insieme, v : 2P → R+ una funzione verificante le proprieta

(i) v(∅) = 0;(ii) se S, T ∈ 2P , S ∩ T = ∅, allora v(S ∪ T ) ≥ v(S) + v(T ).

La coppia Γ = (P, v) e detta gioco (cooperativo); gli elementi di P sono detti giocatori, isottoinsiemi di P coalizioni, v(S) utilita corrispondente alla coalizione S ∈ 2P , v funzionecaratteristica del gioco.

36 A. IANNIZZOTTO

La proprieta (ii) della Definizione 5.1 e detta super-additivita ed esprime il fatto checoalizzarsi ’conviene’ ai singoli giocatori (essa non e richiesta in tutte le versioni dellateoria dei giochi cooperativi). In particolare, alla grande coalizione P corrisponde il valoremassimo della funzione caratteristica: questo rappresenta l’utilita totale del gioco, e ilproblema principale consiste nel trovare una coalizione che distribuisca tale utilita in modosoddisfacente per tutti i giocatori che la formano. Nel seguito adotteremo la notazioneP = {1, . . . n} (n ∈ N0).

Definizione 5.2. Due giochi Γ = (P, v), Γ′ = (P, v′) si dicono strategicamente equivalenti(Γ ∼ Γ′) se esistono r > 0, a1, . . . an ∈ R t.c.

v′(S) = rv(S) +∑i∈S

ai per ogni S ∈ 2P .

Si dimostra facilmente che l’equivalenza strategica e effettivamente una relazione di equiva-lenza (riflessiva, simmetrica, transitiva) sull’insieme dei giochi con insieme dei giocatori P .Segnaliamo ora alcune importanti classi di giochi cooperativi.

Definizione 5.3. Un gioco Γ = (P, v) e detto

(i) essenziale se

v(P ) >n∑i=1

v(i);

(ii) normale se v(P ) = 1 e v(i) = 0 per ogni i ∈ P ;(iii) semplice se v(S) ∈ {0, 1} per ogni S ∈ 2P ;(iv) a somma costante se v(S) + v(P \ S) = v(P ) per ogni S ∈ 2P .

Chiaramente ogni gioco essenziale e semplice e normale. Inoltre, ogni gioco essenziale puoessere normalizzato:

Lemma 5.4. Se Γ = (P, v) e un gioco essenziale, allora esiste un unico gioco normaleΓ′ = (P, v′) tale che Γ ∼ Γ′.

Dimostrazione. Sia

v′(S) =v(S)−

∑i∈S v(i)

v(P )−∑n

j=1 v(j)per ogni S ∈ 2P .

Il gioco Γ′ = (P, v′) e normale. Inoltre, posto

r =[v(P )−

n∑j=1

v(j)]−1

, ai = −rv(i) per ogni i ∈ P ,

si ha

v′(S) = rv(S) +∑i∈S

ai per ogni S ∈ 2P ,

ovvero Γ ∼ Γ′. L’unicita e provata facilmente. �

Una nozione che sara richiamata in seguito e quella di giocatore fantoccio (dummy player):


Definizione 5.5. In un gioco Γ = (P, v), i ∈ P e detto giocatore fantoccio se

v(S ∪ {i}) = v(S) + v(i) per ogni S ∈ 2P .

Esempio 5.6. Nel gioco delle pertiche, tre esploratori devono attraversare un fiume dilarghezza l > 0 e ognuno di essi possiede una pertica di lunghezza 2l/3. Si ha P = {1, 2, 3}e, posta 1 l’utilita di attraversare il fiume, possiamo enumerare tutti i valori della funzionecaratteristica v : 2P → R:

v(p1) = v(p2) = v(p3) = 0, v({p1, p2}) = v({p1, p3}) = v({p2, p3}) = v({p1, p2, p3}) = 1.

Il gioco Γ = (P, v) e semplice e a somma costante.

Esempio 5.7. Nel gioco della produzione, tre imprenditori P = {p1, p2, p3} dispongono ditre materie prime, per esempio ferro, gomma e legno, nelle quantita indicate dalla seguentetabella:

f g lp1 2 3 3p2 3 0 3p3 1 3 0

Per produrre un’unita di prodotto finito (che si vende al prezzo 1) serve un’unita diciascuna materia prima. La funzione caratteristica determina il ricavo ottenibile da ciascunacoalizione:

v(p1) = 2, v(p2) = v(p3) = 0,

v({p1, p2}) = v({p1, p3}) = v({p2, p3}) = 3,

v({p1, p2, p3}) = 6.

Il gioco Γ = (P, v) non e a somma costante (v(p1) + v({p2, p3}) = 5) e neanche normale. Ilgioco normalizzato Γ′ = (P, v′) si ottiene ponendo

r =1

4, a1 = −1

2, a2 = a3 = 0.

Esempio 5.8. Nel gioco della maggioranza pesata, i partiti P = {p1, . . . pn} (n ∈ N0)dispongono ciascuno di si seggi in parlamento (si ∈ N per ogni i ∈ {1, . . . n}) e il quorumper approvare una legge e q ∈ N. La situazione configura un gioco semplice Γ = (P, v) con

v(S) =

{0 se

∑i∈S si < q

1 se∑

i∈S si ≥ q.

Le nozioni introdotte di seguito servono a definire un concetto ragionevole di soluzione per igiochi cooperativi.

Definizione 5.9. Un’imputazione per il gioco Γ = (P, v) e un vettore x ∈ Rn t.c.

(i)n∑i=1

xi = v(P ) (efficienza);

(ii) xi ≥ v(i) per ogni i ∈ {1, . . . n} (razionalita individuale).

L’insieme delle imputazioni di Γ si denota i(Γ).

38 A. IANNIZZOTTO

Figura 3. Un 2-simplesso in R3.

L’insieme i(Γ) si puo rappresentare graficamente mediante un simplesso (n−1)-dimensionalein Rn (come nella Fig. 3). Introduciamo ora la nozione di nucleo, che esprime il sottoinsiemedi i(Γ) contenente le imputazioni vantaggiose non solo per i singoli giocatori, ma anche perciascuna coalizione:

Definizione 5.10. Il nucleo del gioco Γ = (P, v) e l’insieme delle imputazioni x ∈ i(Γ) t.c.∑i∈S

xi ≥ v(S) per ogni S ∈ 2P .

Il nucleo di Γ si denota c(Γ).

L’insieme c(Γ) ⊂ Rn e chiuso e convesso. Il problema di determinare il nucleo di Γ rientranella programmazione lineare (una branca dell’ottimizzazione): si definiscono un insieme

X ={

(x1, . . . xn) ∈ Rn :∑i∈S

xi ≥ v(S) per ogni S ∈ 2P}

e una funzione f : X → R definita da

f(x1, . . . xn) =n∑i=1

xi;

per il Teorema di Weierstraß e per la definizione di X, esiste (x1, . . . xn) ∈ X t.c.

f(x1, . . . xn) = infXf = f ≥ v(P ).

A questo punto occorre distinguere due casi:

• se f = v(P ), allora (x1, . . . xn) ∈ c(Γ);• se f > v(P ), allora c(Γ) = ∅.


Nell’Esempio 5.6 si ha c(Γ) = ∅, nell’Esempio 5.7 si ha

c(Γ) ={

(x1, x2, 6− x1 − x2) ∈ R3 : 2 ≤ x1 ≤ 3, 0 ≤ x2 ≤ 3, x1 + x2 ≤ 3}.

Esempio 5.11. Nel gioco dei musicisti, tre suonatori P = {p1, p2, p3} si esibiscono da soli,in duo o in trio percependo i seguenti salari:

v(p1) = 100, v(p2) = 150, v(p3) = 200,

v({p1, p2}) = 400, v({p1, p3}) = 300, v({p2, p3}) = 400,

v({p1, p2, p3}) = 600.

Attraverso un procedimento grafico, si ottiene

c(Γ) ={

(x1, 400− x1, 200) : 100 ≤ x1 ≤ 200}.

Esempio 5.12. Nel gioco dei guanti, 10 persone hanno ciascuna un guanto sinistro e 11persone hanno ciascuna un guanto destro; ovviamente un guanto solo e inservibile, comepure due guanti uguali, mentre un paio di guanti (diversi) vale 1. Il gioco Γ = (P, v) ha laseguente struttura: P = L ∪R, dove L = {1, . . . 10} e l’insieme di persone con un guantosinistro e R = {11, . . . 21} l’insieme di persone con un guanto destro, e per ogni S ∈ 2P si ha

v(S) = min{|S ∩ L|, |S ∩R|}.

Chiaramente

i(Γ) ={x ∈ R21 :

21∑i=1

xi = 10, xi ≥ 0 per ogni i ∈ {1, . . . 21}}.

Detta x ∈ i(Γ) l’imputazione che ha le prime 10 componenti pari a 1 e le altre 11 pari a 0,si ha

c(Γ) = {x}.Prima dimostriamo che x ∈ c(Γ). Per ogni S ∈ 2P ho∑

i∈S

xi = |S ∩ L| ≥ v(S).

Poi proviamo che x e l’unica imputazione di c(Γ), per assurdo: sia z ∈ c(Γ) \ {x}. Distinguodue casi:

• se esiste 11 ≤ h ≤ 21 t.c. zh = a > 0, allora, posto S = P \ {ph}, si ha

10 = v(S) ≤∑i∈S

zi =∑i 6=h

zi = 10− a < 10,

assurdo;• se zi = 0 per ogni i ∈ {11, . . . 21}, da z 6= x segue che esiste 1 ≤ j ≤ 10 t.c.zj = b < 1, da cui, per T = {j, 11}, si ha

1 = v(T ) ≤∑i∈T

zi = zj + z11 = b < 1,

assurdo.

40 A. IANNIZZOTTO

Questo esempio suggerisce l’idea di un forte vantaggio per i possessori di guanti sinistri,ovvero del bene piu raro.

In alcuni casi, il nucleo si determina facilmente:

Proposizione 5.13. Se Γ = (P, v) e un gioco essenziale a somma costante, allora c(Γ) = ∅.

Dimostrazione. Per assurdo: sia x ∈ c(Γ). Allora, per ogni j ∈ {1, . . . n} si ha

v(P )− v(j) = v(P \ {j}) ≤∑i 6=j

xi = v(P )− xj,

cioe xj = v(j), da cui

v(P ) =n∑i=1

xi =n∑i=1

v(i),

assurdo. �

Nei giochi semplici (Definizione 5.3 (iii)) si definisce una classe particolare di giocatori:

Definizione 5.14. Sia Γ = (P, v) un gioco semplice: i e detto giocatore di veto se v(P \{i}) = 0.

Chiaramente, in un gioco semplice ogni coalizione ’vincente’ deve contenere tutti gli eventualigiocatori di veto: se S ∈ 2P e i /∈ S e un giocatore di veto, si ha S ⊆ P \ {i}, da cui

v(S) ≤ v(P \ {i}) = 0.

Questa nozione si collega a quella di nucleo:

Proposizione 5.15. Se Γ = (P, v) e un gioco semplice, le seguenti sono equivalenti:

(i) c(Γ) 6= ∅;(ii) Γ ha almeno un giocatore di veto.

Dimostrazione. Proviamo che (i) implica (ii), per assurdo: sia v(P \ {i}) = 1 per ognii ∈ {1, . . . n} e sia x ∈ c(Γ); allora per ogni j ∈ {1, . . . n} si ha

0 ≤ xj = 1−∑i 6=j

xi ≤ 1− v(P \ {xj}) = 0,

contro l’ipotesi che x sia un’imputazione. Proviamo che (ii) implica (i): sia S la coalizioneformata da tutti i giocatori di veto (S 6= ∅). Definiamo x ∈ Rn ponendo

xi =

{0 se i /∈ S1/|S| se i ∈ S .

Ottengo cosın∑i=1

xi = 1.

Inoltre, se T ∈ 2P , distinguiamo due casi:


• se v(T ) = 0, allora banalmente∑i∈T

xi ≥ v(T );

• se v(T ) = 1, per quanto sopra S ⊆ T , da cui∑i∈T

xi ≥∑i∈S

xi = 1.

Dunque, x ∈ c(Γ). �

5.1. Valore di Shapley. Definiamo adesso il piu comune (non l’unico) concetto di soluzioneper un gioco cooperativo Γ = (P, v), introdotto da Shapley [35]. Per semplicita adotto lanotazione P = {1, . . . n} (n ∈ N0). Introduco l’insieme delle permutazioni di P

P ! ={σ : P → P : σ biunivoca

}.

Per ogni i ∈ P , σ ∈ P ! sia

S(i, σ) ={j ∈ P : σ(j) < σ(i)

}la coalizione formata dai giocatori che precedono i nell’ordine stabilito da σ, e sia

M(i, σ) = v(S(i, σ) ∪ {i})− v(S(i, σ))

il contributo marginale di i (ovvero l’incremento di utilita offerto dal giocatore i alla coalizioneS(i, σ)). Per la (ii) della Definizione 5.1 si ha

(5.1) M(i, σ) ≥ v(i) per ogni i ∈ P , σ ∈ P !.

Facendo variare σ ∈ P !, la media dei contributi marginali di i ne misura il valore:

Definizione 5.16. Il valore di Shapley del gioco Γ e il vettore φ = (φ1, . . . φn) definito da

φi =1

n!

∑σ∈P !

M(i, σ) per ogni i ∈ P .

Il valore di Shapley di Γ si denota Sv(Γ).

L’interpretazione della Definizione 5.16 e la seguente: per ogni i ∈ P , φi rappresenta laricompensa corrisposta al giocatore i, tanto maggiore quanto piu rilevante e il contributodato da i alle varie coalizioni che si possono formare. Per esempio, se si vuole organizzareun torneo di calcio avendo a disposizione molti bravi attaccanti ma pochi bravi difensori, il’valore’ di questi ultimi (cioe la loro quota del premio in caso di vittoria) sara maggiore diquello degli attaccanti.

Osservazione 5.17. La formula della Definizione 5.16 puo risultare di difficile computazione(n! addendi). In tal caso si puo usare la formula equivalente

φi =1

n!

∑i/∈S

|S|!(n− |S| − 1)! (v(S ∪ {i})− v(S)) per ogni i ∈ P .

Infatti, per ogni σ ∈ P !, M(i, σ) non dipende da σ bensı solo da S(i, σ). D’altra parte,il numero delle permutazioni che producono una fissata coalizione S e |S|!(n − |S| − 1)!.

42 A. IANNIZZOTTO

In questa formula, gli addendi sono 2n−1 (sottoinsiemi di P \ {i}), il che rende la formulaapprezzabile per valori grandi di n, in quanto

limn

2n−1

n!= 0.

Esempio 5.18. Sia Γ = (P, v) il gioco con P = {1, 2, 3} e

v(1) = v(2) = v(3) = 0,

v({1, 2}) = v({1, 3}) = 4, v({2, 3}) = 6,

v({1, 2, 3}) = 20.

I contributi marginali possono essere raccolti nella seguente tabella:

σ\i 1 2 3123 0 4 16132 0 16 4213 4 0 16231 14 0 6312 4 16 0321 14 6 0

Dunque si ha Sv(Γ) = (6, 7, 7).

I seguenti risultati mostrano che il valore di Shapley rappresenta una soluzione del gioco:

Teorema 5.19. Si ha Sv(Γ) ∈ i(Γ).

Dimostrazione. Innanzitutto osserviamo chen∑i=1

φi =n∑i=1

1

n!

∑σ∈P !

M(i, σ)

=1

n!

∑σ∈P !

n∑i=1

M(i, σ)

=1

n!

∑σ∈P !

[v(P )− v(∅)]

= v(P ).

Inoltre, per ogni i ∈ P , da (5.1) segue

φi ≥1

n!

∑σ∈P !

v(i) = v(i).

Dunque, φ e un’imputazione. �

Inoltre si hanno altre proprieta, riassunte nel seguente Teorema di Shapley:

Teorema 5.20. Siano Γ = (P, v), Γ′ = (P, v′) giochi con Sv(Γ) = φ, Sv(Γ′) = φ′

(i) detto Γ + Γ′ = (P, v + v′), allora Sv(Γ + Γ′) = φ+ φ′ (additivita);


(ii) se esistono r > 0, a1, . . . an ∈ R t.c. v′(S) = rv(S) +∑

i∈S ai per ogni S ∈ 2P ,allora φ′ = rφ+ (a1, . . . an) (invarianza per equivalenza strategica);

(iii) se esiste σ ∈ P ! t.c. v′(S) = v(σ(S)) per ogni S ∈ 2P , allora φ′i = φσ(i) (simmetria);(iv) se i ∈ P e un giocatore fantoccio, allora φi = v(i).

Dimostrazione. Dimostriamo (i): per ogni i ∈ P si ha

Svi(Γ + Γ′) =1

n!

∑σ∈P !

[(v + v′)(S(i, σ) ∪ {i})− (v + v′)(S(i, σ))]

= φi + φ′i.

Dimostriamo (ii): per ogni i ∈ P si ha

φ′i =1

n!

∑σ∈P !

[v′(S(i, σ) ∪ {i})− v′(S(i, σ))]

=1

n!

∑σ∈P !

[rv(S(i, σ) ∪ {i}) +

∑j∈S(i,σ)

aj + ai − rv(S(i, σ))−∑

j∈S(i,σ)

aj

]=

1

n!

∑σ∈P !

[rM(i, σ) + ai]

= rφi + ai.

Dimostriamo (iii): per ogni i ∈ P si ha

φ′i =1

n!

∑ρ∈P !

[v′(S(i, ρ) ∪ {i})− v′(S(i, ρ))]

=1

n!

∑ρ∈P !

[v(σ(S(i, ρ)) ∪ {σ(i)})− v(σ(S(i, ρ)))]

= φσ(i).

Dimostriamo (iv): si ha

φi =1

n!

∑σ∈P !

[v(S(i, σ) ∪ {i})− v(S(i, σ))]

=1

n!

∑σ∈P !

v(i)

= v(i).

Questo conclude la dimostrazione. �

Osservazione 5.21. Le proprieta (i)-(iv) sono caratteristiche del valore di Shapley (altredefinizioni di soluzione di un gioco possiedono alcune di queste proprieta, ma non tutte).

Introduciamo una nuova classe di giochi:

Definizione 5.22. Un gioco Γ = (P, v) e detto convesso se

v(S ∩ T ) + v(S ∪ T ) ≥ v(S) + v(T ) per ogni S, T ∈ 2P .

44 A. IANNIZZOTTO

L’interpretazione della Definizione 5.22 e la seguente: siano A,B,C ∈ 2P t.c. A ⊆ B,B ∩ C = ∅; posto S = A ∪ C, T = B, si ha

v(B ∪ C)− v(B) ≥ v(A ∪ C)− v(A),

ovvero il contributo marginale offerto da C a una coalizione e tanto maggiore, quanto piugrande e la coalizione stessa. Nei giochi convessi il valore di Shapley assume un’importanzaancora piu spiccata:

Teorema 5.23. Se Γ = (P, v) e un gioco convesso, allora Sv(Γ) ∈ c(Γ).

Dimostrazione. Fissata σ ∈ P !, sia ψi = M(i, σ). Dimostriamo che ψ ∈ c(Γ): per ogniT ∈ 2P , dalla convessita di Γ segue che per ogni i ∈ T

ψi = v({j ∈ P : σ(j) ≤ σ(i)})− v({j ∈ P : σ(j) < σ(i)})≥ v({j ∈ T : σ(j) ≤ σ(i)})− v({j ∈ T : σ(j) < σ(i)}),

da cui ∑i∈T

ψi ≥∑i∈T

v({j ∈ T : σ(j) ≤ σ(i)})−∑i∈T

v({j ∈ T : σ(j) < σ(i)})

= v(T ).

Rammentando che c(Γ) e convesso e che

Sv(Γ) =1

n!

∑σ∈P !

ψ,

si ha infine φ ∈ c(Γ). �

Di conseguenza, i giochi convessi hanno nucleo non vuoto. Ma, anche se c(Γ) = ∅, il valoredi Shapley fornisce una soluzione di Γ.

5.2. Esempi. Presentiamo qui alcuni esempi di giochi cooperativi, studiati mediante ilvalore di Shapley.

Esempio 5.24. Quattro azionisti possiedono rispettivamente il 10%, 20%, 30%, 40% diun’azienda; in una riunione dell’assemblea degli azionisti, una proposta viene approvata seottiene i voti dei titolari di piu del 50% dell’azienda. Questa situazione si puo rappresentarecon un gioco semplice Γ = (P, v), dove P = {1, 2, 3, 4} e

v(1) = v(2) = v(3) = v(4) = 0,

v({1, 2}) = v({1, 3}) = v({1, 4}) = v({2, 3}) = 0, v({2, 4}) = v({3, 4}) = 1,

v({1, 2, 3}) = v({1, 2, 4}) = v({1, 3, 4}) = v({2, 3, 4}) = 1,

v({1, 2, 3, 4}) = 1.

Poiche Γ e semplice e non ha alcun giocatore di veto, si ha c(Γ) = ∅ (Proposizione 5.15).Per calcolare Sv(Γ) usiamo l’Osservazione 5.17:

φi =1

4!

∑i/∈S

|S|!(3− |S|)!.


Ricavo φ = (2/24, 6/24, 6/24, 10/24), con il sorprendente esito che la ricompensa di 2 euguale a quella di 3, benche quest’ultimo possieda piu titoli.

Esempio 5.25. Il Consiglio di Sicurezza dell’ONU e formato da 5 membri permanenti(con diritto di veto) e da 10 membri transitori (senza diritto di veto); una proposta alConsiglio viene approvata se ottiene almeno 9 voti favorevoli, tra i quali tutti i voti deimembri permanenti. Nasce un gioco semplice Γ = (P, v) con P = {1, . . . 15}, V = {1, . . . 5}(giocatori di veto) e funzione caratteristica definita per ogni S ∈ 2P da

v(S) =

{1 se |S| ≥ 9 e V ⊂ S0 altrimenti

.

Questo e uno dei casi in cui l’Osservazione 5.17 risulta utile (15! ∼ 1300 · 109, 214 = 16384):

(5.2) φi =1

15!

∑i/∈S

|S|!(14− |S|)! [v(S ∪ {i})− v(S)] per ogni i ∈ P .

Fissato i ∈ P \ V , per ogni S ∈ 2P , i /∈ S esaminiamo tre casi speciali:

• se |S| ≤ 7 si ha v(S ∪ {i})− v(S) = 0;• se |S| ≥ 9 si ha v(S ∪ {i})− v(S) = 0;• se V \ S 6= ∅ si ha v(S ∪ {i})− v(S) = 0.

Dunque in (5.2) vanno contate solo le coalizioni S ⊆ P \ {i} t.c. |S| = 8, V ⊂ S: il loronumero e 9!/(3!6!), sicche

φi =9!8!6!

15!3!6!=

4

2145.

Se invece i ∈ V , osserviamo che

• se |S| ≤ 7 si ha v(S ∪ {i})− v(S) = 0;• se V \ (S ∪ {i}) 6= ∅ si ha v(S ∪ {i})− v(S) = 0.

Dunque in (5.2) vanno contate solo le coalizioni S ⊆ P \ {i} t.c. |S| ≥ 8, V \ {i} ⊂ S e siricava

φi =1

15!

14∑k=8

k!(14− k)!10!

(k − 4)!(14− k)!=

421

2145.

Dal confronto tra i due risultati si puo dedurre che un membro permanente del Consiglio emolto piu importante di uno transitorio, indipendentemente dalla durata.

Per concludere, presentiamo un esempio di gioco subadditivo (la differenza, rispetto allaDefinizione 5.1, e che puo aversi v(S ∪ T ) < v(S) + v(T ) per una coppia di coalizioniS, T ∈ 2P , S ∩ T = ∅). Per tali giochi, i concetti di imputazione e di nucleo come sono statifin qui definiti non hanno senso, mentre e ancora possibile calcolare il valore di Shapley.

Esempio 5.26. Nel gioco dell’aeroporto, si considera un aeroporto in cui atterrano aereidiversi, che richiedono piste di lunghezza diversa; il costo di manutenzione di ciascuna pistava ripartito tra gli aerei che ne fanno uso, tenendo conto che ognuno di essi usura una partediversa della pista. I giocatori (gli aerei) siano P = {p1, . . . pn}, raggruppati in k classi

P1 = {p1, . . . pm1}, . . . Pk = {pmk−1+1, . . . pmk} (1 ≤ m1 ≤ . . . ≤ mk = n)

46 A. IANNIZZOTTO

in modo che gli aerei della classe Pj abbiano bisogno di una pista di costo (lunghezza) cj(0 < c1 < . . . < ck). Detta S ∈ 2P una coalizione (per esempio, una compagnia aerea),assegno ad essa un’utilita pari al costo della pista piu lunga di cui necessita:

v(S) = max {cj : S ∩ Pj 6= ∅} .

Cosı e definito un gioco Γ = (P, v) (la funzione caratteristica v non e super-additiva). Il

valore di Shapley e alquanto difficile da calcolare in base alla Definizione 5.16. E piu sempliceprocedere come segue:

• il costo c1 del primo tratto di pista e diviso tra tutti gli aerei di P ;• il costo c2 − c1 del secondo tratto e diviso tra gli aerei del sottoinsieme ∪kj=2Pj;• . . .• il costo ck − ck−1 dell’ultimo tratto e diviso tra gli aerei del sottoinsieme Pk.

Si dimostra che la ripartizione di costi cosı ottenuta corrisponde a φ. Per esempio, seP = {1, 2, 3} con P1 = {1, 2}, P2 = {3} e c1 = 1, c2 = 4, la tabella dei contributi marginalie la seguente:

σ\i 1 2 3123 1 0 3132 1 0 3213 0 1 3231 0 1 3312 0 0 4321 0 0 4

Si ricava Sv(Γ) = (1/3, 1/3, 10/3).

6. Cenni sui giochi dinamici

Non si puo discendere due volte nel medesimo fiume.

Eraclito

In questa sezione esponiamo alcuni elementi di teoria dei giochi dinamici, che sono caratteriz-zati dalla sequenzialita delle scelte dei vari giocatori (ved. Gibbons [14], Morgenstern &von Neumann [28]). Questi giochi sono efficacemente rappresentati tramite grafi, pertantoe utile richiamare alcune nozioni elementari relative a questi oggetti geometrici.

Definizione 6.1. Un grafo (semplice) e una coppia G = (V,E) dove V = {v1, . . . vn}(n ∈ N0) e un insieme non vuoto e

E ⊆ {e ∈ 2V : |e| = 2}

e un insieme di coppie non ordinate di elementi di V . Gli elementi di V sono detti verticidi G, quelli di E sono detti lati. Se e = {v, w} e un lato, v e w ne sono gli estremi; see, f ∈ E, e 6= f , e ∩ f 6= ∅, e e f sono consecutivi. Se v, w ∈ V e {v, w} ∈ E, v e w sonoadiacenti.

Alcune nozioni relative ai grafi:


Figura 4. Un albero.

Definizione 6.2. Siano G = (V,E) un grafo, v ∈ V : il grado di v e

deg(v) =∣∣{e ∈ E : v ∈ e}

∣∣.Se deg(v) = 0, v e detto vertice isolato. Una catena di estremi v, w ∈ V e un insiemeordinato C = (e1, . . . em), dove m ∈ N0, ei ∈ E, per ogni i ∈ {1, . . .m}, ei, ei+1 consecutiviper ogni i ∈ {1, . . .m− 1}, v estremo di e1, w estremo di em; se v = w e i vertici intermedisono distinti a due a due, C e un ciclo; G e detto aciclico se non contiene cicli; G e connessose per ogni v, w ∈ V esiste una catena C che congiunge v e w. Un sotto-grafo di G e unacoppia G ′ = (V ′, E ′) dove V ′ ⊆ V ed E ′ e l’insieme dei lati di G con gli estremi in V ′.

Piu sofisticata e la nozione di grafo orientato, in cui si adotta un ordine tra gli estremi diun lato:

Definizione 6.3. Un grafo orientato e una coppia G = (V,E) dove V = {v1, . . . vn} (n ∈ N0)e un insieme non vuoto e E ⊆ V ×V . Una catena di estremi v, w ∈ V e un insieme ordinatoC = (e1, . . . em), dove m ∈ N0, ei ∈ E, per ogni i ∈ {1, . . .m}, ei, ei+1 consecutivi perogni i ∈ {1, . . .m− 1}, v primo estremo di e1, w secondo estremo di em. Se G e un grafoorientato, su V e definita una relazione d’ordine � mediante la legge

v � w se esiste una catena C di estremi v e w..

La classe piu studiata di grafi (ved. Fig. 4):

Definizione 6.4. Un albero e un grafo orientato, connesso, aciclico. Se G e un albero, unsotto-albero e un sotto-grafo G ′ = (V ′, E ′) t.c.

V ′ = {v0} ∪ {v ∈ V : v0 � v},dove v0 ∈ V .

Richiamando la Definizione 1.1 e la susseguente discussione, definiamo un gioco dinamico(deterministico, non-cooperativo) come l’interazione tra due o piu decisori razionali eintelligenti (giocatori), che effettuano le loro scelte (mosse) in una sequenza temporale

48 A. IANNIZZOTTO

prefissata; ogni giocatore, quando effettua ogni sua mossa, e informato di tutte le mosseprecedenti sue e degli altri giocatori e delle loro conseguenze (informazione completa); aigiocatori e vietato stringere accordi vincolanti. Una strategia, per un giocatore, e unasequenza di mosse condizionate dalle mosse degli altri giocatori.Un gioco di questo genere si suole rappresentare in forma estesa (ved. Kuhn & Tucker [22]):denotiamo il gioco con Γ e definiamo l’insieme dei giocatori P = {P1, . . . Pn} (n ∈ N0) equello degli stati del gioco S = {s1, . . . sm} (m ∈ N0). Sull’insieme degli stati e definito unordine parziale � (relazione transitiva e antisimmetrica). Uno stato s ∈ S e detto inizialese non esiste t ∈ S t.c. t� s (l’insieme degli stati iniziali e denotato Si) e finale (o esito) senon esiste t ∈ S t.c. s� t (l’insieme degli stati finali e denotato Se), altrimenti e un turno.Ogni giocatore Pi (1 ≤ i ≤ n) dispone di una preferenza sull’insieme Se (ved. Definizione1.2), e per il Teorema 1.5 anche di una funzione di utilita ui : Se → R. Una mossa e unacoppia ordinata (s, t) ∈ S × S t.c.

(i) s� t;(ii) non esiste u ∈ S t.c. s� u� t.

Una storia e una sequenza finita di stati (s1, . . . sk) (k ∈ N0 e detto lunghezza) t.c.

s1 � s2 � . . .� sk.

Una storia e detta conclusa se sk ∈ Se. Elenchiamo di seguito gli assiomi che sarannoadottati nella presente discussione:

• lo stato iniziale s0 e unico;• per ogni stato finale s ∈ Se esiste un’unica storia che congiunge s0 con s (la lunghezza

di questa storia e detta altezza di s);• esiste una regola di turno, ovvero una funzione τ : S \ Se → P che associa a ogni

stato il giocatore a cui spetta muovere.

Sotto queste ipotesi, un gioco si puo rappresentare mediante un grafo G = (S,E), dove E el’insieme delle mosse consentite.

Proposizione 6.5. Se Γ e un gioco e G il grafo che lo rappresenta, allora G e un albero.

Esempio 6.6. Nel gioco dei fiammiferi due giocatori P , Q tolgono a turno quanti fiammiferivogliono da uno di due gruppi originariamente di 2 fiammiferi ciascuno, posti su un tavolo;vince il primo che lascia il tavolo vuoto. Sia P il primo a muovere. L’albero che rappresentaquesto gioco ha 6 foglie, cioe vi sono 6 esiti, 3 dei quali favorevoli a P e 3 a Q.

Il concetto di equilibrio di Nash si puo applicare anche ai giochi dinamici, ma risultainsoddisfacente:

Esempio 6.7. Il gioco dell’entrata e un modello molto generale che abbraccia il seguente caso:un produttore P deve decidere se introdursi (i) oppure no (o) in un mercato monopolizzatoda un altro produttore Q; questi puo reagire aggressivamente (a), abbassando i prezzi einfliggendo una perdita a se oltre che al concorrente, oppure pacificamente (p), dividendo ilmercato con P . Rappresentando questo gioco Γ in forma strategica, otteniamo la seguente


tabella dei pay-off:

P\Q a pi (−2, 5) (6, 6)o (0, 8) (0, 12)

Si ha Ne(Γ) = {(i, p), (o, p)}, conclusione insoddisfacente perche (o, a) corrisponde a uncomportamento irrazionale di Q. L’intuizione suggerisce che si dovrebbe avere solo (i, p)come equilibrio.

Il modo piu semplice per ’risolvere’ un gioco dinamico e quello basato sul metodo di induzionea ritroso (o algoritmo di Zermelo-Kuhn): si tratta di un procedimento finalizzato a eliminare,in un numero finito di passi, tutte le mosse irrazionali di tutti i giocatori; quello che resta el’unione delle storie razionali, che conduce alle soluzioni del gioco.Sia Γ un gioco:

• scegliamo uno stato finale s di altezza massima;• determiniamo lo stato immediatamente precedente t ∈ S e l’insieme T degli stati

immediatamente successivi a t (tra cui s);• detto Pi (1 ≤ i ≤ n) il giocatore che muove in t, determiniamo s′ ∈ T t.c.

ui(s′) = max

Tui;

• definiamo un nuovo gioco Γ′ eliminando tutti gli stati di T e attribuendo a t un’utilitaper Pi uguale a ui(s

′);• ripetiamo il procedimento partendo da t (che e uno stato finale di Γ′);• . . .• raggiungiamo lo stato iniziale s0.

Attraverso questo procedimento si determina una storia soddisfacente la seguente definizione:

Definizione 6.8. Un equilibrio perfetto nei sottogiochi per il gioco Γ e una storia completaC = (s0, s1, . . . sp) (p ∈ N0) t.c. per ogni 0 ≤ j ≤ p− 1 la mossa migliore per il giocatoreche gioca in sj e (sj, sj+1). L’insieme degli equilibri perfetti nei sottogiochi di Γ e indicatocon spe(Γ).

Il procedimento di induzione a ritroso fornisce una dimostrazione costruttiva del seguenteTeorema di Selten:

Teorema 6.9. Se Γ e un gioco dinamico a informazione completa con un insieme finito distati, allora spe(Γ) 6= ∅.

In generale tale soluzione non e unica, poiche in qualche stato possono darsi due o piu mosseottimali equivalenti per un giocatore. Nel gioco dell’Esempio 6.6, vi sono 2 equilibri perfettinei sottogiochi, entrambi favorevoli a Q. Nel gioco dell’Esempio 6.7, si ha spe(Γ) = {(i, p)}.Se nell’Esempio 3.3 stabiliamo un turno e aggiungiamo l’ipotesi di informazione completa,otteniamo spe(Γ) = {(t, t)}.

50 A. IANNIZZOTTO

Esempio 6.10. Sia Γ un gioco con 2 giocatori P , Q e due mosse, rappresentato dallaseguente tabella dei pay-off:

P\Q y1 y2x1 (2, 1) (0, 0)x2 (1, 2) (1, 2)

Si ha Ne(Γ) = {(x1, y1), (x2, y2)}. Supponendo che P giochi per primo, si puo procedereper induzione a ritroso e ricavare spe(Γ) = {(x1, y1)}. L’altro equilibrio (x2, y2) si puointerpretare come effetto di una ’minaccia di ritorsione’ da parte di Q: esso comporta unascelta, da parte di P , non ottimale (ma solo perche la minaccia gli preclude l’esito migliore).Dal punto di vista della razionalita individuale, questa minaccia non e credibile, in quantoimplica la disponibilita da parte di Q a danneggiare se stesso (nella realta la faccenda ediversa, come provano i terroristi suicidi).

Si noti che un equilibrio perfetto nei sottogiochi non sempre e un equilibrio di Nash per laversione ’statica’ del gioco:

Esempio 6.11. Sia Γ un gioco con 2 giocatori P , Q e due mosse, rappresentato dallaseguente tabella dei pay-off:

P\Q y1 y2x1 (2, 1) (0, 0)x2 (3, 0) (1, 1)

Si vede facilmente che Ne(Γ) = {(x2, y2)}. Se inseriamo una regola di turno per cui P giocaper primo, otteniamo spe(Γ) = {(x1, y1)}.

Il modello dei giochi dinamici si puo generalizzare indebolendo l’ipotesi di informazionecompleta. Puo verificarsi che alcuni stati del gioco s1, . . . sk (k ∈ N0), nei quali e di turnosempre lo stesso giocatore Pi (1 ≤ i ≤ n), siano per tale giocatore indistinguibili: siparla allora di informazione incompleta e l’insieme {s1, . . . sk} e detto insieme informativo.Coerentemente, le mosse a disposizione di Pi in ognuno degli stati che formano lo statoinformativo sono le stesse (esse pero conducono a esiti diversi a causa di quelle informazioniche Pi ignora).

L’impasse si risolve introducendo una distribuzione di probabilita sull’insieme informativo(ved. Definizione 3.4): se la probabilita di sj secondo Pi e xj, con 0 ≤ xj ≤ 1 per ognij ∈ {1, . . . k} e

k∑j=1

xj = 1,

e se uj (definita sull’insieme degli stati finali raggiungibili da sj) e l’utilita per Pi subordinataallo stato sj, allora Pi fa la sua scelta in modo da massimizzare l’utilita mista

u =k∑j=1

xjuj.


Esempio 6.12. Considero un gioco con due giocatori P , Q: P gioca per primo scegliendotra due mosse {a, b}; se sceglie a raggiunge uno stato finale con utilita (1, 3); se sceglie b, Pdeve fare un’altra mossa da scegliere in {c, d}, ma all’oscuro di Q; quindi gioca Q, che puoscegliere in {e, f} con la seguente tabella dei pay-off:

P\Q e fc (3, 2) (0, 0)d (2, 2) (−1, 1)

Sia 0 ≤ x ≤ 1 la probabilita, secondo Q, che P abbia scelto c al secondo stadio (dunque1− x e la probabilita che abbia scelto d). Allora Q deve massimizzare l’utilita v data da

v(e) = 2x+ 2(1− x) = 2,

v(f) = 0x+ 1(1− x) = 1− x.Qualunque sia x, Q sceglie e. Dunque P , alla sua seconda mossa, puo attribuire le utilitau(c) = 3, u(d) = 2 e sceglie c. Risalendo allo stato iniziale del gioco, P sceglie b e i pay-offfinali sono (3, 2).

Quando si introducono le probabilita, pero, bisogna tenere conto delle valutazioni di tutti igiocatori: infatti, in base alla propria intelligenza e alla razionalita degli altri, ogni giocatoremodifica le sue valutazioni in base alle mosse che ha osservato. Per studiare questo tipodi giochi si adopera l’approccio bayesiano, che e basato sulle probabilita condizionate e sulmetodo di induzione a ritroso. Tale approccio non sara qui trattato, ma il seguente Esempio6.19 ne fornisce un assaggio.

6.1. Esempi. Presentiamo infine alcuni esempi di giochi dinamici, sia in regime di informa-zione completa che di informazione incompleta.

Esempio 6.13. Nel gioco dell’ultimatum, su un tavolo ci sono 100 monete; il giocatore Pfa una proposta di spartizione al giocatore Q (in cui ognuno riceva almeno una moneta,cioe da 1 a 99); se questi accetta (a), si procede secondo la proposta; se rifiuta (r), nessunoprende monete. Si ha spe(Γ) = {(99, 1)}, il che dimostra come il concetto di equilibrio siaspesso in contrasto con l’esperienza.

Esempio 6.14. Nel gioco dei pirati, 5 pirati devono dividere un bottino di 1000 doblonisecondo il seguente procedimento: il pirata P1 fa la sua proposta e la mette ai voti, seottiene la maggioranza il bottino viene diviso secondo la sua proposta, altrimenti P1 vieneucciso; P2 fa la sua proposta... Questo enigma si risolve per induzione a ritroso:

• P5, rimasto solo, prende i 1000 dobloni per se;• P4 non puo garantirsi il voto di P5 e muore;• P3 offre 1 doblone a P4 e ne conserva 999;• P2 offre 2 dobloni a P4 e 1 a P5 e ne conserva 997;• P1 offre 2 dobloni a P5 e 1 a P3 e ne conserva 997.

Inaspettatamente, P1 puo risolvere il problema in modo molto vantaggioso.

52 A. IANNIZZOTTO

Esempio 6.15. Il modello di Stackelberg e quasi identico a quello dell’Esempio 3.18, la soladifferenza essendo che P ha una posizione dominante, cioe ’gioca per primo’. Dunque Psceglie la sua strategia x sapendo che Q rispondera con la strategia condizionata

y(x) =a− c− x

2.

Dunque P opera in modo tale da massimizzare il proprio pay-off f : [0, a]→ R, definito da

f(x) = f(x, y(x)) =(a− c)x− x2

2.

L’equilibrio raggiunto e

x =a− c

2, y =

a− c4

.

Osserviamo che la posizione dominante di P distorce il mercato, consentendogli un maggiorprofitto a danno di Q, ma a vantaggio dei consumatori (il prezzo e piu basso).

Esempio 6.16. La corsa agli sportelli e un modello usato per interpretare le crisi di fiduciache talvolta colpiscono il mercato finanziario. Siano 0 < s < d < r numeri reali. Dueinvestitori P , Q hanno depositato in banca ciascuno una somma d, che la banca ha investitoin parte; al tempo I, la banca dispone di una somma 2s, mentre al tempo II, giunto amaturazione l’investimento, essa dispone di una somma 2r. Gli investitori possono sceglierese prelevare (p) o lasciare (l) al tempo I, con i seguenti pay-off:

P\Q p lp (s, s) (d, 2s− d)l (2s− d, d) (rinvio)

oppure al tempo II, con i seguenti pay-off:

P\Q p lp (r, r) (2r − d, d)l (d, 2r − d) (r, r)

Il gioco al tempo II ha un solo equilibrio di Nash (p, p), quindi al tempo I attribuisco (r, r)come pay-off della coppia di strategie (l, l) che pertanto diventa anch’essa equilibrio di Nash.Procedendo per induzione a ritroso, si ha lo stesso risultato: l’unico equilibrio perfetto neisottogiochi e la storia in cui P e Q lasciano al tempo I e prelevano al tempo II.

Esempio 6.17. Nel gioco del ’prendere o lasciare’ (detto anche gioco del millepiedi per lacaratteristica forma del grafo associato), due giocatori P , Q scelgono a turno se prendere(p) o lasciare (l) un premio che inizialmente vale 1 e poi cresce di 1 a ogni turno fino a unvalore k (k ∈ N0 pari); se dopo k turni il premio e ancora intatto, viene diviso in parti eguali.Comincia P . L’induzione a ritroso fornisce un unico equilibrio perfetto nei sottogiochi,corrispondente alla scelta da parte di P di prendere al primo turno. Tuttavia questoequilibrio e lungi dall’essere ottimale. Questo esempio mostra come il metodo dell’induzionea ritroso possa anche condurre a dei paradossi.


Esempio 6.18. Riprendiamo in esame il gioco dell’Esempio 3.3, supponendo che P giochiper primo e Q giochi ignaro della scelta di P . Sia 0 ≤ x ≤ 1 la probabilita che P abbiataciuto secondo Q, allora Q confronta le utilita

v(t) = −1x− 10(1− x) = 9x− 10,

v(c) = 0x− 5(1− x) = 5x− 5

e sceglie sempre c in quanto v(c) > v(t) per ogni x ∈ [0, 1]. P , al momento di scegliere, lo sa:quindi deduce le proprie utilita che sono u(t) = −10, u(c) = −5 e sceglie c. Si noti che lasoluzione e identica a quella dell’Esempio 3.3: infatti, l’incertezza rende irrilevante l’ordinedelle mosse.

Esempio 6.19. Esaminiamo un semplice gioco di carte con due giocatori P , Q. All’inizioentrambi puntano 1; poi P pesca una carta da un mazzo ordinario e la guarda; P sceglietra due opzioni, f (fold) e r (raise): se sceglie f , mostra la carta e prende il banco se lacarta e rossa, mentre se e nera lo prende Q; se sceglie r, aggiunge 1 e lascia la carta coperta;ora gioca Q, che ha pure due scelte, m (meet) e p (pass): se sceglie p rinuncia e P prende ilbanco, se sceglie m punta 1 e scopre la carta, e anche in questo caso il banco va a P se lacarta e rossa e a Q se e nera. Gli stati che seguono alla scelta f da parte di P formano uninsieme informativo per Q, che deve scegliere in condizioni di incertezza.

Secondo Q, la probabilita che la carta coperta sia rossa e x ∈ [0, 1] (quindi la probabilita chesia nera e 1− x). Allora le utilita ponderate di Q sono date dalla funzione v : {m, p} → Rdefinita da

v(m) = −2x+ 2(1− x) = 2− 4x,

v(p) = −x− (1− x) = −1.

A questo punto e chiaro che Q sceglie m se 0 ≤ x < 3/4, e indifferente se x = 3/4 e scegliep se 3/4 < x ≤ 1. In particolare, se x = 1/2, la scelta di Q e sempre m. In questo caso sipuo procedere per induzione a ritroso: le utilita di P al momento della sua mossa sono

u(r) = 2, u(f) = 1 se la carta e rossa,

u(r) = −2, u(f) = 1 se la carta e nera.

Dunque, P sceglie r se la carta e rossa e f se e nera. Si potrebbe osservare che, a questopunto, Q, che gioca dopo P , puo dedurre il colore della carta dalla mossa di P : se P sceglier la carta e rossa e a Q conviene scegliere p; se P sceglie f la carta e nera e a Q convienescegliere m.

54 A. IANNIZZOTTO

Riferimenti bibliografici

[1] J.P. Aubin, Mathematical methods of game and economic theory, North-Holland (1979). 2, 19[2] J.P. Aubin, H. Frankowska, Set-valued analysis, Birkhauser (2008). 7

[3] E. Borel, La theorie du jeu et le equations integrales a noyau symetrique, C.R. Hebdomadaires desSeances de l’Academie des Sciences 173 (1921) 1304-1308. 2

[4] R. Branzei, J. Morgan, V. Scalzo, S. Tijs, Approximate fixed point theorems in Banach spaceswith applications in game theory, J. Math. Anal. Appl. 285 (2003) 619-628. 16, 26

[5] F. Browder, On a new generalization of the Schauder fixed point theorem, Math. Ann. 174 (1967)285-290. 16

[6] E. Burger, Introduzione alla teoria dei giochi, Franco Angeli (1967). 2[7] A. Cellina, Approximation of set valued functions and fixed point theorems, Ann. Mat. Pura Appl.

82 (1969) 17–24. 15[8] K.C. Chang, Variational methods for nondifferentiable functionals and their applications to partial

differential equations, J. Math. Anal. Appl. 80 (1981) 102-129. 7[9] V. Checcucci, A. Tognoli, E. Vesentini, Lezioni di topologia generale, Feltrinelli (1982). 12, 18

[10] F. Colombo, Introduzione alla teoria dei giochi, Carocci (2008). 2, 19, 35[11] M. Fabian, P. Hamala, P. Hajek, V. Montesinos, V. Zizler, Banach space theory, Springer

(2011). 17[12] K. Fan, Applications of a theorem concerning sets with convex sections, Math. Ann. 163 (1966)

189-203. 32[13] A.F. Filippov, A differential equation with discontinuous right hand side, Math. Sbornik 54 (1960)

99–128. 7[14] R. Gibbons, Teoria dei giochi, Il Mulino (1992). 2, 19, 46[15] I.L. Glicksberg, A further generalization of the Kakutani fixed point theorem, with applications to

Nash equilibrium points, Proc. Amer. Math. Soc. 3 (1952) 170-174. 16[16] A. Granas, J. Dugundji, Fixed point theory, Springer (2003). 14, 15, 16, 17, 18[17] S. Kakutani, A generalization of Brouwer’s fixed point theorem, Duke Math. J. 8 (1941) 457-459. 15,

33[18] B. Knaster, C. Kuratowski, S. Mazurkiewicz, Ein Beweis des Fixpunktsatzes fur n-dimensionale

Simplexe, Fund. Math. 14 (1926). 17[19] H. Konig, A general minimax theorem based on connectedness, Arch. Math. (Basel) 59 (1992) 55-64.

15, 33[20] E. Krein, A.C. Thompson, Theory of correspondences, Wiley (1984). 7[21] D.M. Kreps, Notes on the theory of choice, Westview Press (1988). 3[22] H.W. Kuhn, A.W. Tucker (Eds.), Contributions to the theory of games, Princeton University

Press (1953). 2, 48, 55[23] J.C.C. McKinsey, Introduction to the theory of games, Rand (1952). 2[24] E. Michael, Continuous selections I, Ann. of Math. 63 (1956) 361–382. 12[25] E. Michael, Continuous selections II, Ann. of Math. 64 (1956) 562–580. 12[26] E. Michael, Continuous selections III, Ann. of Math. 65 (1956) 375–390. 12[27] O. Morgenstern, Teoria dei giochi, Bollati Boringhieri (1969). 2, 35[28] O. Morgenstern, J. von Neumann, Theory of games and economic behavior, Princeton (1953). 2,

46[29] J. Nash, Non-cooperative games, Ann. Math. 54 (1951) 286–295. 5, 21[30] B. Ricceri, Some topological mini-max theorems via an alternative principle for multifunctions, Arch.

Math. (Basel) 60 (1993) 367–377. 2, 34[31] B. Ricceri, S. Simons (eds.), Minimax theory and applications, Kluwer (1998). 28[32] J.D. Rossi, Tug-of-war games and PDEs, Proc. Roy. Soc. Edinburgh Sect. A 141 (2011) 319–369. 2, 34[33] W. Rudin, Functional analysis, McGraw-Hill (1991). 14


[34] R. Scozzafava, Incertezza e probabilita, Zanichelli (2001). 20[35] L.S. Shapley, A value for n-person games, in [22]. 41[36] J. von Neumann, Zur Theorie der Gesellschaftsspiele, Math. Ann. 100 (1928) 295-320. 2, 31[37] E. Zermelo, Uber die Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proceedings of

the Fifth International Congress of Mathematicians (1913) 501-504. 2

Dipartimento di Matematica e InformaticaUniversita degli Studi di CagliariViale L. Merello 92, 09123 Cagliari, ItalyE-mail address: [email protected]

Date post:	24-Jan-2021
Category:	Documents
Upload:	others
View:	4 times
Download:	0 times

INTRODUZIONE ALLA TEORIA DEI GIOCHI - people.unica.it · 2016. 1. 22. · Riferimenti bibliogra...

Documents