teoria 2: teorema di Nash

[fields]

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.

[fields]

Ecco la mia dimostrazione artigianale Ora sono curioso di leggere una dim un po' più sofisticata..

Testo nascosto, fai click qui per vederlo

Siano $X,Y\sube RR$ compatti e convessi. Chiamiamo una funzione $h: X\to P(Y)$ pseudo continua se

1)- data una successione $b_n$ di elementi di $X$ convergente ad $a$
- data una successione di funzioni $C_n: P(Y) to Y$ tale che la successione $C_n(h(b_n))$ converge a $k$

allora $k\in h(a)$.

2) per ogni $x\in X$, $h(x)$ e' convesso e compatto.

Proposizione (Valori Intermedi). Siano $X,Y\sube RR$ compatti convessi, $h: X\to P(Y)$ pseudo continua e $a,b\in X$. Siano inoltre $a'\in h(a),b'\in h(b)$, con $a'<b'$. Allora per ogni $c\in Y$ tale che $a'<c<b'$, esiste $x\in [a,b]$ o $x\in[b,a]$ tale che $c\in h(x)$.

Prova. Se $c\in h(a)$ oppure $c\in h(b)$ abbiamo ipso facto la tesi. Possiamo allora supporre senza perdita di generalita' che $max h(a)<c<min h(b)$. Sia $x\in X$ l'estremo superiore dell'insieme $I={y\in [a,b]| max(h(y))<c}$.

Se $x\in I$, consideriamo una successione $b_n$ di elementi di $[a,b]$ maggiori di $x$ e convergente a $x$. Consideriamo inoltre la successione dei $min h(b_n)$ e dei $max h(b_n)$, che senza perdita di generalita' convergono rispettivamente a $k_(min)$ e $k_(max)$. Poiche' $h$ e' pseudo continua, abbiamo che $k_(min)\in h(x)$ e $k_(max)\in h(x)$. Ma allora $k_(min)<c$, e dunque per la convessita' di $h(x)$ e per il fatto che $k_(max)>=c$, vale che $c\in h(x)$.

Se invece $x\notin I$, allora $max h(x)>=c$. Inoltre esiste una successione $b_n$ di elementi di $[a,b]$ minori di $x$ e convergente a $x$ tale che la successione dei $max h(b_n)$ converge ad un elemento $k<=c$. Per la pseudo continuita' di $h$, abbiamo che $k\in h(x)$ e per la convessita' di $h(x)$, $c\in h(x)$.


Corollario Sia $X\sube RR$ compatto convesso e $h: X\to P(X)$ pseudo continua. Allora esiste $bar x \in X$ tale che $\bar x\in h(\bar x)$.

Prova. Abbiamo che $X=[a,b]$. Consideriamo la funzione $g: X to P(X)$ tale che $g(x)=h(x)-x$. (con l'espressione $h(x)-x$ s'intende ${y\in X|\exists k\in h(x) \mbox{tale che} y=k-x$). E' immediato vedere che $g$ è psuedo continua.

Se $a\in h(a)$ o $b\in h(b)$, abbiamo la tesi. Se $a\notin h(a)$ e $b\notin h(b)$, allora certamente esiste $a'\in g(a)$ tale che $a'>0$ e inoltre esiste $b'\in g(b)$ tale che $b'<0$. Per la proposizione sui valori intermedi, $0\in g(x)$ per qualche $x\in X$. Ma questo significa che esiste $bar x \in X$ tale che $\bar x\in h(\bar x)$.


Proposizione. Siano $X,Y,Z\sube RR$ compatti e convessi e $f: X to P(Y)$, $g: Y to P(Z)$ pseudo continue. Definiamo $g\circ f(x)=g(f(x))$ stando attenti a definire $g(A)$ quando $A$ e' un insieme ($g(A)=uu{g(a)| a\in A}$). Allora $g\circ f: X to P(Z)$ e' pseudo continua.

Prova. Dimostriamo innanzitutto che, in generale, se $W,U\sube RR$ sono compatti e convessi e se inoltre $h: W to P(U)$ e' pseudo continua, allora $uuh(W)$ e' compatto e convesso.
Una successione in $uuh(W)$ e' della forma $C_n(h(b_n))$, con (a patto di restringerci a una sottosuccessione della successione di partenza) $b_n$ senza perdita di generalita' convergente ad $a\in W$, $C_n: P(U)\to U$ e $C_n(h(b_n))$ convergente a $k\in U$. Per la pseudo continuita' di $h$, abbiamo che $k\in h(a)$ e dunque $k\in uuh(W)$. Quindi $uu h(W)$ e' compatto.
Siano ora $a'\in h(a)$, $b'\in h(b)$, con $a,b\in W$ e $a'<b'$. Per la proposizione sui valori intermedi, se $a'<c<b'$, esiste $x\in W$ tale che $c\in h(x)$ e dunque $c\in uuh(W)$, dimostrando cosi' la convessita' di $uuh(W)$.

Da questo segue che per ogni $x\in X$, $g\circ f(x)$ e' compatto e convesso, essendo $f(x)$ compatto e convesso.

Sia ora data una successione $b_n$ di elementi di $X$ convergente ad $a$ e sia data anche una successione di funzioni $C_n: P(Z) to Z$ tale che la successione $C_n(g\circ f(b_n))$ converge ad $k$. Chiaramente esiste una successione di funzioni $D_n: P(Y) to Y$ tale che la successione $C_n(g\circ f(b_n))$ e' uguale alla successione $C_n(g(D_n(f(b_n))))$. Possiamo supporre, senza perdita di generalità, che la successione $D_n(f(b_n))$ converga a $k'\in Y$. Per la pseudo continuita' di $f$, $k'\in f(a)$. Infine, per la pseudo continuita' di $g$, $k\in g(k')$, e dunque effettivamente $k\in g\circ f(a)$.

In conclusione, $g\circ f$ e' pseudo continua.


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 $RR$
- $f,g$ siano continue
- per ogni $y \in Y$, l'insieme dei punti della funzione $x \mapsto f(x,y)$ sia convesso e per ogni $x \in X$, l'insieme dei punti di max della funzione $y \mapsto g(x,y)$ sia convesso.
Allora $G$ ha (almeno) un equilibrio di Nash.

Prova. Definiamo per ogni $y \in Y$, $F(y)$ come l'insieme dei punti di max della funzione $x \mapsto f(x,y)$ e analogamente per ogni $x \in X$, $G(x)$ come l'insieme dei punti di max della funzione $y \mapsto g(x,y)$. Per la continuita' di $f$ e $g$ certamente $F(y)$ e $G(x)$ sono compatti (e convessi per ipotesi).

Sia data ora una successione $b_n$ di elementi di $Y$ convergente ad $a$ e sia data una successione di funzioni $C_n: P(X) to X$ tale che la successione $C_n(F(b_n))$ converge a $k$. Sia $k'\in F(a)$. Abbiamo che $f(C_n(F(b_n)),b_n)>=f(k',b_n)$ per definizione. Inoltre $f(k',b_n)$ converge a $f(k',a)$. Ma per continuita' di $f$, abbiamo che $f(C_n(F(b_n)),b_n)$ converge a $f(k,a)$. Segue allora che $f(k,a)>=f(k',a)$, e dunque per definizione $k\in F(a)$.

Concludiamo quindi che $F,G$ sono pseudo continue, e che lo e' pure $F\circ G$, la quale ha un punto fisso $\bar x$. la coppia $(\bar x, \bar y)$, dove $bar y\in G(\bar x)$, e' un equilibrio di Nash per costruzione.

Fine

Dannazione, che fatica scrivere tutta questa roba!

EDIT: typos

[Fioravante Patrone]

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".


Teoremi di punto fisso di Brouwer e di Kakutani


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

[Fioravante Patrone]

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

[Fioravante Patrone]

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à:

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.

e prendere $t = \max_{x \in X} f(x,y)$

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

[Lord K]

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.

[kekko89]

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!

[Fioravante Patrone]

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.