teoria 2: teorema di Nash

[Fioravante Patrone]

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:

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

[yurifrey]

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?

[Fioravante Patrone]

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

[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? Questo perche' l'ipotesi di quasi concavità permette, per ogni $y$, di localizzare il minimo $x$ per cui $f(x,y)=max$.

[Fioravante Patrone]

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

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.

[fields]

Se capisco bene quello che intendi ( ), la risposta è negativa.

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

[Fioravante Patrone]

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

[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?

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

[fields]

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.

[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