Teoria 2: teorema di Nash
Il thread "teoria 1bis" si è rivelato essere molto interessante. In effetti ha portato alla luce alcuni punti nodali per la dimostrazione dell'esistenza dell'equilibrio di Nash. Questo teorema è uno dei risultati fondamentali in teoria dei giochi. Dovuto a Nash, è uno dei suoi risultati matematicamente più banali. Il suo lavoro del 1950:
è di 1 pagina (non inganni la numerazione sopra indicata). E la dimostrazione, scritta in tono semi-discorsivo, occupa poche righe!
Vediamo allora l'enunciato del teorema, tanto per cominciare. A dire il vero, il teorema di Nash propriamente detto ha delle ipotesi più specifiche, adatte per l'applicazione diretta all'estensione mista di un gioco finito. Preferisco però vedere prima questa versione, per poi analizzare in seguito il "caso particolare" della estensione mista. Anche perché l'idea di strategie mista richiede una adeguata introduzione e discussione.
Teorema Sia $G=(X,Y,f,g)$ un gioco a due giocatori in forma strategica. Supponiamo che:
- sia $X$ che $Y$ siano sottoinsiemi compatti, convessi e non vuoti di un opportuno spazio euclideo finito-dimensionale
- $f,g$ siano continue
- per ogni $y \in Y$, $x \mapsto f(x,y)$ sia quasi-concava e per ogni $x \in X$, $y \mapsto g(x,y)$ sia quasi-concava
Allora $G$ ha (almeno) un equilibrio di Nash.
Nota 1 Uno spazio euclideo (reale) finito-dimensionale è uno spazio vettoriale di dimensione finita su $RR$, su cui è definito un prodotto scalare (e quindi una noma, pertanto una metrica e quindi una topologia). Come esempio, basta prendere $RR^k$
Nota 2 La continuità di $f$ e $g$ è naturalmente intesa rispetto alla topologia citata nella Nota 1
Nota 3 Una funzione, definita su un sottoinsieme convesso di uno spazio vettoriale $Z$, è quasi-concava se:
$\forall t \in RR$, ${ z \in Z : f(z) \ge t }$ è convesso.
Prima di proseguire, attendo commenti, if any
Per chi voglia approfondire o cercare qualche consideazione in più (a parte il solito magnifico libro
) può essere utile questo:
http://www.fioravante.patrone.name/mat/ ... kutani.pdf
Nash, John F. Jr. [1950]: Equilibrium Points in n-Person Games, Proc. Nat. Acad. Sci. U.S.A., 36, 48-49
è di 1 pagina (non inganni la numerazione sopra indicata). E la dimostrazione, scritta in tono semi-discorsivo, occupa poche righe!
Vediamo allora l'enunciato del teorema, tanto per cominciare. A dire il vero, il teorema di Nash propriamente detto ha delle ipotesi più specifiche, adatte per l'applicazione diretta all'estensione mista di un gioco finito. Preferisco però vedere prima questa versione, per poi analizzare in seguito il "caso particolare" della estensione mista. Anche perché l'idea di strategie mista richiede una adeguata introduzione e discussione.
Teorema Sia $G=(X,Y,f,g)$ un gioco a due giocatori in forma strategica. Supponiamo che:
- sia $X$ che $Y$ siano sottoinsiemi compatti, convessi e non vuoti di un opportuno spazio euclideo finito-dimensionale
- $f,g$ siano continue
- per ogni $y \in Y$, $x \mapsto f(x,y)$ sia quasi-concava e per ogni $x \in X$, $y \mapsto g(x,y)$ sia quasi-concava
Allora $G$ ha (almeno) un equilibrio di Nash.
Nota 1 Uno spazio euclideo (reale) finito-dimensionale è uno spazio vettoriale di dimensione finita su $RR$, su cui è definito un prodotto scalare (e quindi una noma, pertanto una metrica e quindi una topologia). Come esempio, basta prendere $RR^k$
Nota 2 La continuità di $f$ e $g$ è naturalmente intesa rispetto alla topologia citata nella Nota 1
Nota 3 Una funzione, definita su un sottoinsieme convesso di uno spazio vettoriale $Z$, è quasi-concava se:
$\forall t \in RR$, ${ z \in Z : f(z) \ge t }$ è convesso.
Prima di proseguire, attendo commenti, if any
Per chi voglia approfondire o cercare qualche consideazione in più (a parte il solito magnifico libro
) può essere utile questo:http://www.fioravante.patrone.name/mat/ ... kutani.pdf
Risposte
Per chi voglia approfondire o cercare qualche considerazione in più (a parte il solito magnifico libro )
Scusate ma di quale libro si tratta? Mi piacerebbe leggermi un'introduzione alla teoria dei giochi, ma non conosco nè i libri che sono in commercio sull'argomento nè il loro grado di difficoltà. Qualcuno sa aiutarmi?
se mi sforzo mi viene in mente
vedi:
https://www.matematicamente.it/f/viewtop ... 753#155753
e anche il mio post successivo per una indicazione un po' più allargata
ciao
vedi:
https://www.matematicamente.it/f/viewtop ... 753#155753
e anche il mio post successivo per una indicazione un po' più allargata
ciao
Una banalità: nel caso del gioco $(X,Y,f,g)$ con $X,Ysube RR$, il ragionamento nel thread "teoria1bis", con qualche piccola modifica, funziona facilmente anche sotto queste nuove ipotesi... Giusto? 
Questo perche' l'ipotesi di quasi concavità permette, per ogni $y$, di localizzare il minimo $x$ per cui $f(x,y)=max$.
Questo perche' l'ipotesi di quasi concavità permette, per ogni $y$, di localizzare il minimo $x$ per cui $f(x,y)=max$.
"fields":
Una banalità: nel caso del gioco $(X,Y,f,g)$ con $X,Ysube RR$, il ragionamento nel thread "teoria1bis", con qualche piccola modifica, funziona facilmente anche sotto queste nuove ipotesi... Giusto?
Se capisco bene quello che intendi (
), la risposta è negativa.La tua idea mi pare sia quella di effettuare una selezione dalla "multiapplicazione di miglior risposta".
Ovvero da $R_I : Y \to X$ definita come:
$R_I(y) = $ arg $\max_{x \in X} f(x,y)$
Per poterla fare seguendo la tua idea, che è quella di prendere il più piccolo elemento in "arg max", la quasi concavità non serve (continuità e compattezza bastano).
Il guaio è che la tua "selezione" risulta essere sì una funzione, solo che non è detto che sia continua. Per cui, Brouwer o simili, nisba.
Esempio: $f(x,y) = xy$ con $x$ ed $y$ in $[0,1]$
$ arg $\max_{x \in X} f(x,y) = [0,1]$ se $y=0$
$ arg $\max_{x \in X} f(x,y) = {1}$ se $y>0$
La tua selezione risulta essere $0$ per $y=0$ e $1$ per $y \in ]0,1]$. Quindi discontinua.
La scappatoia qui sarebbe prendere il più grande elemento di "arg max", ma è ovvio che basta cambiare un segno e si ha subito un controesempio anche in questo caso.
Il problema è legato ad una difficoltà generale: multiapplicazioni semicontinue superiormente possono non ammettere selezioni continue.
Un ottimo riferimento in materia è:
Klein, E. e A. C. Thompson [1984]: Theory of correspondences, Wiley, New York.
"Fioravante Patrone":
Se capisco bene quello che intendi (
Sì, hai interpretato bene quello che volevo dire. In effetti inizialmente avevo pensato che la quasi concavità mi avrebbe reso la funzione di scelta continua, sbagliandomi. Il tuo controesempio è chiarificatore.
Devo dire che comunque sono contento che il mio tentativo di ragionamento non sia giusto: sarebbe stato troppo banale
La strada seguita da Nash per provare l'esistenza di un equilibrio consiste nel trasformare il problema di equilibrio in un problema di punto fisso e provare che questo ultimo problema ha punti fissi (usando un opportuno teorema).
In questo post descriverò questa trasformazione. Ci tengo a precisare che questa verrà fatta per un gioco $G=(X,Y,f,g)$ qualsiasi, senza cioè nessuna ipotesi su $X,Y,f,g$.
Il prezzo da pagare per questo livello di generalità è che dovremo usare le multiapplicazioni. Ma, visto che anche per problemi di equilibrio piuttosto semplici ci si imbatte comunque in multiapplicazioni, tanto vale seguire la strada generale.
La strada è già stata abbozzata prima, su sollecitazione di fields. Vediamola comunque ora in generale.
Definisco:
$R_I(y) = $ arg $\max_{x \in X} f(x,y)$
$R_{II}(x) = $ arg $\max_{y \in Y} g(x,y)$
Mi soffermo su $R_I$, data la simmetria della situazione.
Ricordo, preliminarmente, che arg $\max$ indica l'insieme dei punti di massimo della funzione cui si riferisce. In particolare, arg $\max_{x \in X} f(x,y)$ indica l'insieme dei punti di massimo su $X$ della funzione $x \mapsto f(x,y)$ (dove $y \in Y$ è un elemento dato).
Dato $y$, non c'è nessuna garanzia che la funzione $x \mapsto f(x,y)$ abbia massimo. Quindi "arg $\max_{x \in X}$" può benissimo essere l'insieme vuoto. Qualora non sia vuoto, non è detto che sia un singleton: la funzione in esame potrebbe avere più di un punto di massimo.
Per questi motivi, $R_I$ è una multiapplicazione da $Y$ in $X$. Cioè una legge che ad ogni elemento di $Y$ assegna uno ed un solo sottoinsieme di $X$ (e questo può benissimo essere vuoto).
Avendo a disposizione $R_I$ ed $R_{II}$, possiamo definire $R$, multiapplicazione da $X \times Y$ in $X \times Y$, così:
$R(x,y) = R_I(y) \times R_{II}(x)$.
Definizione. Data una multiapplicazione $F$ da $Z$ in $Z$, diremo che $\bar z \in Z$ è un punto fisso per $F$ se $\bar z \in F(\bar z)$.
Teorema. Dato un gioco $G$, $(\bar x,\bar y) \in X \times Y$ è un equilibrio di Nash se e solo se è un punto fisso per $R$
Dimostrazione. Per esercizio
In questo post descriverò questa trasformazione. Ci tengo a precisare che questa verrà fatta per un gioco $G=(X,Y,f,g)$ qualsiasi, senza cioè nessuna ipotesi su $X,Y,f,g$.
Il prezzo da pagare per questo livello di generalità è che dovremo usare le multiapplicazioni. Ma, visto che anche per problemi di equilibrio piuttosto semplici ci si imbatte comunque in multiapplicazioni, tanto vale seguire la strada generale.
La strada è già stata abbozzata prima, su sollecitazione di fields. Vediamola comunque ora in generale.
Definisco:
$R_I(y) = $ arg $\max_{x \in X} f(x,y)$
$R_{II}(x) = $ arg $\max_{y \in Y} g(x,y)$
Mi soffermo su $R_I$, data la simmetria della situazione.
Ricordo, preliminarmente, che arg $\max$ indica l'insieme dei punti di massimo della funzione cui si riferisce. In particolare, arg $\max_{x \in X} f(x,y)$ indica l'insieme dei punti di massimo su $X$ della funzione $x \mapsto f(x,y)$ (dove $y \in Y$ è un elemento dato).
Dato $y$, non c'è nessuna garanzia che la funzione $x \mapsto f(x,y)$ abbia massimo. Quindi "arg $\max_{x \in X}$" può benissimo essere l'insieme vuoto. Qualora non sia vuoto, non è detto che sia un singleton: la funzione in esame potrebbe avere più di un punto di massimo.
Per questi motivi, $R_I$ è una multiapplicazione da $Y$ in $X$. Cioè una legge che ad ogni elemento di $Y$ assegna uno ed un solo sottoinsieme di $X$ (e questo può benissimo essere vuoto).
Avendo a disposizione $R_I$ ed $R_{II}$, possiamo definire $R$, multiapplicazione da $X \times Y$ in $X \times Y$, così:
$R(x,y) = R_I(y) \times R_{II}(x)$.
Definizione. Data una multiapplicazione $F$ da $Z$ in $Z$, diremo che $\bar z \in Z$ è un punto fisso per $F$ se $\bar z \in F(\bar z)$.
Teorema. Dato un gioco $G$, $(\bar x,\bar y) \in X \times Y$ è un equilibrio di Nash se e solo se è un punto fisso per $R$
Dimostrazione. Per esercizio
"fields":
[quote="Fioravante Patrone"]Sia $G=(X,Y,f,g)$ un gioco a due giocatori in forma strategica. Supponiamo che:
- sia $X$ che $Y$ siano sottoinsiemi compatti, convessi e non vuoti di un opportuno spazio euclideo finito-dimensionale
- $f,g$ siano continue
- per ogni $y \in Y$, $x \mapsto f(x,y)$ sia quasi-concava e per ogni $x \in X$, $y \mapsto g(x,y)$ sia quasi-concava
Allora $G$ ha (almeno) un equilibrio di Nash.
Vediamo un po'... Avrei questa "congettura":
Sia $G=(X,Y,f,g)$ un gioco a due giocatori in forma strategica. Supponiamo che:
- sia $X$ che $Y$ siano sottoinsiemi compatti, convessi e non vuoti di $RR$
- $f,g$ siano continue
- per ogni $y \in Y$, l'insieme dei punti di max di $x \mapsto f(x,y)$ sia convesso e per ogni $x \in X$, l'insieme dei punti di max $y \mapsto g(x,y)$ sia convesso.
Allora $G$ ha (almeno) un equilibrio di Nash.
L'ipotesi con cui ho sostituito l'ipotesi di quasi concavità è più debole, eppure l'enunciato sembra essere vero. Può essere?[/quote]
Come detto, ho ricopiato qui per intero il tuo post che avevi messo nel thread "teoria 1bis: non esistenza di equilibri di Nash"
Hai ragione, la ipotesi che avevo messo io può essere indebolita e sostituita con la tua (e questo vale in ogni spazio euclideo finito dimensionale, non solo in $RR$).
Come vedremo, la dimostrazione del teorema regge benissimo, senza dover spostare una virgola.
Vorrei fare un commento di natura "sostanziale" (in matematica???).
Il vantaggio della "mia" formulazione consiste nell'usare una ipotesi che è "significativa". Ad esempio, in (micro-)economia si fanno spesso ipotesi sulle preferenze degli agenti (in particolare, dei consumatori) che poi vanno a riflettersi in modo naturale nella quasi-concavità delle $f$ e $g$.
Non ho mai analizzato a fondo la questione, ma aggiungo che non conosco esempi interessanti in cui si possa applicare il "tuo" teorema e non il "mio".
Ok, grazie, avevo scritto di là per non imbrattare questo thread con eventuali sciocchezze
Visto che ci sono, due parole sull'idea che ho avuto per dimostrare tale versione. In sostanza dimostro una versione adattata del teorema di punto fisso di Brouwer solo che al posto di una funzione ci sta una multiapplicazione, che si ottiene "componendo" $R_I$ e $R_(II)$. La dimostrazione e' analoga a quella per il teorema di Brouwer, solo che naturalmente e' un po' piu' critica. L'idea è che le multiapplicazioni $R_I$ e $R_(II)$ sono, in un senso tutto da precisare, "continue", e quindi si riesce a riprodurre l'argomentazione del th di Brouwer.
Naturalmente ho supposto $X,Y\sube RR$ perche' non sono abbastanza familiare con spazi vettoriali piu' sofisticati.
Visto che ci sono, due parole sull'idea che ho avuto per dimostrare tale versione. In sostanza dimostro una versione adattata del teorema di punto fisso di Brouwer solo che al posto di una funzione ci sta una multiapplicazione, che si ottiene "componendo" $R_I$ e $R_(II)$. La dimostrazione e' analoga a quella per il teorema di Brouwer, solo che naturalmente e' un po' piu' critica. L'idea è che le multiapplicazioni $R_I$ e $R_(II)$ sono, in un senso tutto da precisare, "continue", e quindi si riesce a riprodurre l'argomentazione del th di Brouwer.
Naturalmente ho supposto $X,Y\sube RR$ perche' non sono abbastanza familiare con spazi vettoriali piu' sofisticati.
se hai voglia di mettere giù i dettagli, mi piacerebbe vedere una dim "artigianale"
quanto agli spazi vettoriali più sofisticati, il teorema di Nash riguarda $RR^k$, niente di più
anche se il passaggio da $RR$ ad $RR^2$ non è indolore...
PS: se a qualcuno interessa, poi possiamo vedere il teorema di Glicksberg, che estende Nash a spazi vettoriali di dimensione infinita
quanto agli spazi vettoriali più sofisticati, il teorema di Nash riguarda $RR^k$, niente di più
anche se il passaggio da $RR$ ad $RR^2$ non è indolore...
PS: se a qualcuno interessa, poi possiamo vedere il teorema di Glicksberg, che estende Nash a spazi vettoriali di dimensione infinita
"Fioravante Patrone":
se hai voglia di mettere giù i dettagli, mi piacerebbe vedere una dim "artigianale"
Una dimostrazione artigianale..
In effetti lo è, non ho utilizzato nessun "cannone". E' un po' lunghetta, ci vorrà un po' per metterla giù come si deve. Ci provo.
Ecco la mia dimostrazione artigianale Ora sono curioso di leggere una dim un po' più sofisticata..
EDIT: typos
Ora sono curioso di leggere una dim un po' più sofisticata..
EDIT: typos
Mentre fields attende pazientemente una risposta al suo post, io vado avanti con la "strada solita". Posso dire solo, al momento, che la sua definizione iniziale mi sembra coincida con la definizione di multiapplicazione a grafico ridotto chiuso (vedi sotto). Buon segno...
Comunque, fra artigianale e sofisticato la differenza sta tutta nell'uso di un appropriato teorema di punto fisso. Insomma, il cuore della dim dell'esistenza di un equilibrio di Nash è il teorema di punto fisso. Il resto sono "esercizi". Molto più semplici, per capici, della dimostrazione artigianale di fields
Tanto per chiarire a che punto siamo, la dim dovrebbe essere conclusa nell'arco di un paio di post. Uno lo userò per il teorema di massimo (o teorema di Berge). E l'altro per "mettere assieme i pezzi".
[size=117]Teoremi di punto fisso di Brouwer e di Kakutani[/size]
Abbiamo ridotto il problema di provare l'esistenza di un equilibrio di Nash alla dimostrazione che esiste un punto fisso per la multiapplicazione di miglior risposta.
Che teorema usare? Facile, ce n'è uno già pronto alla bisogna: il teorema di Shizuo Kakutani, pubblicato nel 1941.
Questo teorema è discendente diretto del teorema di Brouwer. E', per così dire, una sua naturale generalizzazione dal contesto delle funzioni a quello delle multiapplicazioni.
Richiamo per prima cosa, allora, il teorema di Brouwer, con un enunciato "taylored for" quello che mi serve.
Teorema (Brouwer). Sia $K$ un sottoinsieme compatto, convesso e non vuoto di uno spazio euclideo di dimensione finita. Sia $f:K \to K$ una funzione continua. Allora esiste un punto fisso. Cioè, esiste $\bar k \in K$ t.c. $\bar k=f(\bar k)$.
Una interessante storia del teorema di Brouwer si trova qui:
http://www.math.uri.edu/~kulenm/mth381p ... point.html
La estensione alle multiapplicazioni è abbastanza immediata.
Teorema (Kakutani, 1941). Sia $K$ un sottoinsieme compatto, convesso e non vuoto di uno spazio euclideo di dimensione finita. Sia $F:K \to K$ una multiapplicazione a valori non vuoti e convessi ed a grafico ridotto chiuso Allora esiste un punto fisso. Cioè, esiste $\bar k \in K$ t.c. $\bar k \in F(\bar k)$.
"Grafico ridotto" (spesso chiamato semplicemente "grafico") di una multiapplizazione $H$ da $A$ a $B$ non è altro che:
${ (a,b) \in A \times B : b \in H(a) }$
In realtà, il teorema di Kakutani è stato essenzialmente anticipato da von Neumann, nel suo famoso modello di crescita. Le argomentazioni che usa in una dimostrazione costituiscono sostanzialmente la dimostrazione del risultato di Kakutani:
J. von Neumann (1937) "A Model of General Economic Equilibrium", in K. Menger, editor, Ergebnisse eines mathematischen Kolloquiums, 1935-36. 1945 Translation, Review of Economic Studies, Vol. 13 (1), p.1-9.
Per chi è curioso, segnalo:
Gale, D. (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly 86: 818-827
Ricordo che ulteriori dettagli si possono trovare in questi miei appunti in rete:
http://www.fioravante.patrone.name/mat/ ... kutani.pdf
Comunque, fra artigianale e sofisticato la differenza sta tutta nell'uso di un appropriato teorema di punto fisso. Insomma, il cuore della dim dell'esistenza di un equilibrio di Nash è il teorema di punto fisso. Il resto sono "esercizi". Molto più semplici, per capici, della dimostrazione artigianale di fields
Tanto per chiarire a che punto siamo, la dim dovrebbe essere conclusa nell'arco di un paio di post. Uno lo userò per il teorema di massimo (o teorema di Berge). E l'altro per "mettere assieme i pezzi".
[size=117]Teoremi di punto fisso di Brouwer e di Kakutani[/size]
Abbiamo ridotto il problema di provare l'esistenza di un equilibrio di Nash alla dimostrazione che esiste un punto fisso per la multiapplicazione di miglior risposta.
Che teorema usare? Facile, ce n'è uno già pronto alla bisogna: il teorema di Shizuo Kakutani, pubblicato nel 1941.
Questo teorema è discendente diretto del teorema di Brouwer. E', per così dire, una sua naturale generalizzazione dal contesto delle funzioni a quello delle multiapplicazioni.
Richiamo per prima cosa, allora, il teorema di Brouwer, con un enunciato "taylored for" quello che mi serve.
Teorema (Brouwer). Sia $K$ un sottoinsieme compatto, convesso e non vuoto di uno spazio euclideo di dimensione finita. Sia $f:K \to K$ una funzione continua. Allora esiste un punto fisso. Cioè, esiste $\bar k \in K$ t.c. $\bar k=f(\bar k)$.
Una interessante storia del teorema di Brouwer si trova qui:
http://www.math.uri.edu/~kulenm/mth381p ... point.html
La estensione alle multiapplicazioni è abbastanza immediata.
Teorema (Kakutani, 1941). Sia $K$ un sottoinsieme compatto, convesso e non vuoto di uno spazio euclideo di dimensione finita. Sia $F:K \to K$ una multiapplicazione a valori non vuoti e convessi ed a grafico ridotto chiuso Allora esiste un punto fisso. Cioè, esiste $\bar k \in K$ t.c. $\bar k \in F(\bar k)$.
"Grafico ridotto" (spesso chiamato semplicemente "grafico") di una multiapplizazione $H$ da $A$ a $B$ non è altro che:
${ (a,b) \in A \times B : b \in H(a) }$
In realtà, il teorema di Kakutani è stato essenzialmente anticipato da von Neumann, nel suo famoso modello di crescita. Le argomentazioni che usa in una dimostrazione costituiscono sostanzialmente la dimostrazione del risultato di Kakutani:
J. von Neumann (1937) "A Model of General Economic Equilibrium", in K. Menger, editor, Ergebnisse eines mathematischen Kolloquiums, 1935-36. 1945 Translation, Review of Economic Studies, Vol. 13 (1), p.1-9.
Per chi è curioso, segnalo:
Gale, D. (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly 86: 818-827
Ricordo che ulteriori dettagli si possono trovare in questi miei appunti in rete:
http://www.fioravante.patrone.name/mat/ ... kutani.pdf
Vediamo di predisporre l'ultimo tassello utile per la dimostrazione del teorema di Nash.
Poi si tratterà solo di sistemarli tutti assieme.
Il teorema, di carattere fondamentalmente elementare, affronta un problema significativo. Se ho un problema di minimo dipendente da un parametro, quale è la dipendenza della soluzione del problema di minimo da questo parametro? Ovviamente, per soluzione di un problema di minimo si possono intendere, ragionevolmente, due cose: l'insieme dei punti di minimo o il valore minimo. Io mi interesserò del primo, ma quando ci si riferisce al teorema di Berge spesso si intende lo studio di entrambi questi aspetti.
E' difficile sopravvalutare l'importanza di questo tipo di risultati. Che stanno nella famiglia cui appartengono:
- integrali dipendenti da un parametro
- dipendenza continua dai dati per un problema di Cauchy
Dal punto di vista delle applicazioni, non essendo generalmente possibile conoscere con esattezza i dati, questo tipo di risultati offre un po' di sollievo, garantendo che la soluzione del problema "vero" non sarà troppo lontana (in qualche modo) dalla soluzione che abbiamo trovato.
Teorema. (Berge)
Siano $S,T$ sottoinsiemi di un opportuno spazio euclideo finito-dimensionale. e sia $f:S \times T to RR$, continua. Allora la multiapplicazione $M$ da $S$ in $T$, definita come $M(s)= $arg$\max_{t \in T} \ f(s,t)$, ha grafico ridotto chiuso.
Dimostrazione. Ci serve dimostrare che:
( $s_n \rightarrow s_0$, $t_n \rightarrow t_0$, $t_n \in $arg$\max_{t \in T} f(s_n,t)$) implica $t_0 \in $arg$\max_{t \in T} f(s_0,t)$
Supponiamo per assurdo che non sia vero.
Allora $\exists \bar{t}$ tale che $f(s_0,t_0) < f(s_0,\bar{t})$.
Sia $\epsilon = f(s_0, \bar{t}) - f(s_0, t_0)$. Abbiamo:
$\epsilon =[f(s_0, \bar{t}) - f(s_n, \bar{t})] + [f(s_n, \bar{t}) - f(s_n, t_n)] + [f(s_n, t_n)-f(s_0, t_0)]$
Osserviamo che:
$s_n to s_0$, quindi $f(s_n, \bar{t}) to f(s_0, \bar{t})$ per la continuità di $f$,
$t_n \in $arg$\max_{t \in T} f(s_n,t)$, pertanto $f(s_n, \bar{t}) - f(s_n, t_n) \le 0$,
$(s_n,t_n) to (s_0,t_0)$ e quindi $f(s_n, t_n) to f(s_0, t_0)$, sempre per la continuità di $f$,
Allora (per $n$ sufficientemente grande):
$\epsilon =[f(s_0, \bar{t}) - f(s_n, \bar{t})] + [f(s_n, \bar{t}) - f(s_n, t_n)] + [f(s_n, t_n)-f(s_0, t_0)] \le \frac {1} {3}\epsilon + 0 + \frac {1} {3}\epsilon$
Quindi $\epsilon \le \frac {2} {3}\epsilon.$ Contraddizione.
Un paio di disegnetti illustrativi del teorema sono al solito posto, ovvero qui:
http://www.fioravante.patrone.name/mat/ ... kutani.pdf
Poi si tratterà solo di sistemarli tutti assieme.
Il teorema, di carattere fondamentalmente elementare, affronta un problema significativo. Se ho un problema di minimo dipendente da un parametro, quale è la dipendenza della soluzione del problema di minimo da questo parametro? Ovviamente, per soluzione di un problema di minimo si possono intendere, ragionevolmente, due cose: l'insieme dei punti di minimo o il valore minimo. Io mi interesserò del primo, ma quando ci si riferisce al teorema di Berge spesso si intende lo studio di entrambi questi aspetti.
E' difficile sopravvalutare l'importanza di questo tipo di risultati. Che stanno nella famiglia cui appartengono:
- integrali dipendenti da un parametro
- dipendenza continua dai dati per un problema di Cauchy
Dal punto di vista delle applicazioni, non essendo generalmente possibile conoscere con esattezza i dati, questo tipo di risultati offre un po' di sollievo, garantendo che la soluzione del problema "vero" non sarà troppo lontana (in qualche modo) dalla soluzione che abbiamo trovato.
Teorema. (Berge)
Siano $S,T$ sottoinsiemi di un opportuno spazio euclideo finito-dimensionale. e sia $f:S \times T to RR$, continua. Allora la multiapplicazione $M$ da $S$ in $T$, definita come $M(s)= $arg$\max_{t \in T} \ f(s,t)$, ha grafico ridotto chiuso.
Dimostrazione. Ci serve dimostrare che:
( $s_n \rightarrow s_0$, $t_n \rightarrow t_0$, $t_n \in $arg$\max_{t \in T} f(s_n,t)$) implica $t_0 \in $arg$\max_{t \in T} f(s_0,t)$
Supponiamo per assurdo che non sia vero.
Allora $\exists \bar{t}$ tale che $f(s_0,t_0) < f(s_0,\bar{t})$.
Sia $\epsilon = f(s_0, \bar{t}) - f(s_0, t_0)$. Abbiamo:
$\epsilon =[f(s_0, \bar{t}) - f(s_n, \bar{t})] + [f(s_n, \bar{t}) - f(s_n, t_n)] + [f(s_n, t_n)-f(s_0, t_0)]$
Osserviamo che:
$s_n to s_0$, quindi $f(s_n, \bar{t}) to f(s_0, \bar{t})$ per la continuità di $f$,
$t_n \in $arg$\max_{t \in T} f(s_n,t)$, pertanto $f(s_n, \bar{t}) - f(s_n, t_n) \le 0$,
$(s_n,t_n) to (s_0,t_0)$ e quindi $f(s_n, t_n) to f(s_0, t_0)$, sempre per la continuità di $f$,
Allora (per $n$ sufficientemente grande):
$\epsilon =[f(s_0, \bar{t}) - f(s_n, \bar{t})] + [f(s_n, \bar{t}) - f(s_n, t_n)] + [f(s_n, t_n)-f(s_0, t_0)] \le \frac {1} {3}\epsilon + 0 + \frac {1} {3}\epsilon$
Quindi $\epsilon \le \frac {2} {3}\epsilon.$ Contraddizione.
Un paio di disegnetti illustrativi del teorema sono al solito posto, ovvero qui:
http://www.fioravante.patrone.name/mat/ ... kutani.pdf
Mettiamo allora insieme i pezzi.
Dato il gioco, si tratta di vedere che le ipotesi fatte garantiscono che $R$ soddisfi le ipotesi del teorema di Kakutani.
Prima osservazione: $R(x,y) = R_I(y) \times R_{II}(x)$.
Quindi per provare che $R$ è a valori non vuoti e convessi basta provare che $R_I$ lo è (naturalmente, le stesse argomentazioni varranno per $R_{II}$). Infatti, il prodotto cartesiano di insiemi non vuoti (risp.: convessi) è non vuoto (risp: convesso).
Che $R_I$ sia a valori non vuoti è conseguenza del teorema di Weierstrass (abbiamo continuità e compattezza come serve).
Che sia a valori convessi dovrebbe essere già chiaro dalle osservazioni (proposta di generalizzazione) di fields. Comunque,:
$R_I(y) = $ arg $\max_{x \in X} f(x,y) = {x \in X : f(x,y) \ge \max_{x \in X} f(x,y)}$
E l'insieme descritto qui sopra a destra è convesso grazie alla quasi-concavità di $f$. Infatti basta ricordare la def di quasi concavità:
Resta solo da garantire che $R$ ha grafico ridotto chiuso. Anche qui (esercizio per il lettore...) sarà sufficiente provare che $R_I$ ha grafico ridotto chiuso. Ma il teorema di Berge cosa l'abbiamo visto a fare?
CVD
Dato il gioco, si tratta di vedere che le ipotesi fatte garantiscono che $R$ soddisfi le ipotesi del teorema di Kakutani.
Prima osservazione: $R(x,y) = R_I(y) \times R_{II}(x)$.
Quindi per provare che $R$ è a valori non vuoti e convessi basta provare che $R_I$ lo è (naturalmente, le stesse argomentazioni varranno per $R_{II}$). Infatti, il prodotto cartesiano di insiemi non vuoti (risp.: convessi) è non vuoto (risp: convesso).
Che $R_I$ sia a valori non vuoti è conseguenza del teorema di Weierstrass (abbiamo continuità e compattezza come serve).
Che sia a valori convessi dovrebbe essere già chiaro dalle osservazioni (proposta di generalizzazione) di fields. Comunque,:
$R_I(y) = $ arg $\max_{x \in X} f(x,y) = {x \in X : f(x,y) \ge \max_{x \in X} f(x,y)}$
E l'insieme descritto qui sopra a destra è convesso grazie alla quasi-concavità di $f$. Infatti basta ricordare la def di quasi concavità:
"Fioravante Patrone":e prendere $t = \max_{x \in X} f(x,y)$
Nota 3 Una funzione, definita su un sottoinsieme convesso di uno spazio vettoriale $Z$, è quasi-concava se:
$\forall t \in RR$, ${ z \in Z : f(z) \ge t }$ è convesso.
Resta solo da garantire che $R$ ha grafico ridotto chiuso. Anche qui (esercizio per il lettore...) sarà sufficiente provare che $R_I$ ha grafico ridotto chiuso. Ma il teorema di Berge cosa l'abbiamo visto a fare?
CVD
"Fioravante Patrone":
se hai voglia di mettere giù i dettagli, mi piacerebbe vedere una dim "artigianale"
quanto agli spazi vettoriali più sofisticati, il teorema di Nash riguarda $RR^k$, niente di più
anche se il passaggio da $RR$ ad $RR^2$ non è indolore...
PS: se a qualcuno interessa, poi possiamo vedere il teorema di Glicksberg, che estende Nash a spazi vettoriali di dimensione infinita
Mi interesserebbe particolarmente, visto che l'estensione potrebbe essere un caso molto interessante per alcune applicazioni che sto studiando.
Ciao! considerando che della teoria dei giochi so poco e niente..mi stavo documentando sull'equilibrio di nash. Solo che non capisco una cosa. In pratica ogni giocatore cerca di minimizzare la sua perdita. Ma perchè,nel dilemma del prigioniero,secondo l'equilibrio di Nash tutti e due dovrebbero parlare? Io pensavo che,minimizzando le loro perdite,entrambi non dovrebbero parlare in maniera da avere una pena più leggera. Spero non sia troppo difficile da capire per un neofilo come me! Grazie!
La risposta è che il risultato derivante da scelte individuali non necessariamente è collettivamente "buono".
Nello scegliere, fra due alternative, quella migliore per se, un giocatore trascura l'effetto che quella scelta ha sull'altro. E questo effetto (questa esternalità) può sopravvanzare il beneficio che tocca a chi fa la scelta.
Questa è la radice di ciò che avviene nel dilemma del prigioniero e in molti altri giochi in cui un equilibrio di Nash non corrisponde ad un esito efficiente.
Nello scegliere, fra due alternative, quella migliore per se, un giocatore trascura l'effetto che quella scelta ha sull'altro. E questo effetto (questa esternalità) può sopravvanzare il beneficio che tocca a chi fa la scelta.
Questa è la radice di ciò che avviene nel dilemma del prigioniero e in molti altri giochi in cui un equilibrio di Nash non corrisponde ad un esito efficiente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo