Teoria 1bis: non esistenza di equilibri di Nash
Abbiamo visto che cosa è un gioco in forma strategica, a due giocatori.
E abbiamo visto un esempio (da wedge) di un gioco privo di equilibri di Nash.
Uno potrebbe dire: ovvio! wedge ha preso spazi non compatti!
In realtà, la compattezza di $X$ ed $Y$ non è sufficiente.
Attendo esempi in poposito...
E abbiamo visto un esempio (da wedge) di un gioco privo di equilibri di Nash.
Uno potrebbe dire: ovvio! wedge ha preso spazi non compatti!
In realtà, la compattezza di $X$ ed $Y$ non è sufficiente.
Attendo esempi in poposito...
Risposte
"Fioravante Patrone":
In realtà, la compattezza di $X$ ed $Y$ non è sufficiente.
Occorre che le funzioni $f$ e $g$ siano continue?
$f$ e $g$ possono essere prese continue, se si vuole
Intendo dire che si può fare un esempio di gioco senza equilibrio di Nash, anche se gli spazi delle strategie (gli $X$ ed $Y$) ed sono compatti ed i payoff (le $f$ e $g$) sono funzioni continue
Intendo dire che si può fare un esempio di gioco senza equilibrio di Nash, anche se gli spazi delle strategie (gli $X$ ed $Y$) ed sono compatti ed i payoff (le $f$ e $g$) sono funzioni continue
Qui urge un chiarimento 
In $RR^n$ euclideo un insieme è compatto se e solo se è chiuso e limitato. Ma allora un insieme formato da due punti isolati, essendo unione finita di chiusi, è un chiuso e in aggiunta è limitato. Quindi un insieme formato da due punti isolati è un compatto vero? Se è così credo sia facile poi trovare l'esempio cercato...
In $RR^n$ euclideo un insieme è compatto se e solo se è chiuso e limitato. Ma allora un insieme formato da due punti isolati, essendo unione finita di chiusi, è un chiuso e in aggiunta è limitato. Quindi un insieme formato da due punti isolati è un compatto vero? Se è così credo sia facile poi trovare l'esempio cercato...
come si diceva una volta? fuochino? fuoco! bruci!!
però l'appetito vien mangiando!
dopo che avrai spiattellato l'esempio che già hai in mente, ne voglio anche uno in cui $X=Y=[0,1]$ (ed $f,g$ continue, s'intende!)
però l'appetito vien mangiando!
dopo che avrai spiattellato l'esempio che già hai in mente, ne voglio anche uno in cui $X=Y=[0,1]$ (ed $f,g$ continue, s'intende!)
Chi vuole giocare al "pari e dispari"? 
$X=Y={0} uu {1}
$X=Y={0} uu {1}
0 1
0 (1,-1) (-1,1)
1 (-1,1) (1,-1)
"Fioravante Patrone":
ne voglio anche uno in cui $X=Y=[0,1]$ (ed $f,g$ continue, s'intende!)
Essendo altruista, lascio la possibilità di fare quell'esempio a qualcun altro. Hai ragione, sono troppo magnanimo. Ma che ci vuoi fare
con le funzioni continue non mi viene ancora in mente nulla
ma almeno in questa gli intervalli sono compatti (un po' alla volta magari ci arrivo):
X=Y=[0,1]
f=g=Mant[x]+Mant[y]
ma almeno in questa gli intervalli sono compatti (un po' alla volta magari ci arrivo):
X=Y=[0,1]
f=g=Mant[x]+Mant[y]
Rimango sempre in attesa di un esempio con funzioni continue. Anche perché, senza la continuità dei payoff, avere l'ipotesi di compattezza sugli spazi di strategie è inutile (Bourbaki docet).
Ciò detto, tre considerazioni sull'esempio di wedge.
1.
Se $(\bar x, \bar y)$ è un equilibrio di Nash, allora $\bar x$ è un punto di massimo per la funzione $ x \mapsto f(x,\bar y)$. Allora, per avere un esempio privo di equilibri di Nash basta fare in modo che $ x \mapsto f(x,y)$ non abbia massimo, per qualsiasi valore di $y$.
Mi sembra di capire che questa sia l'idea dietro all'esempio di wedge. Infatti, la funzione che lui propone non ha mai massimo in $x$, comunque sia fissato $y$.
A questa idea se ne aggiunge un'altra: quella di prendere un payoff separabile in $x$ ed $y$. Essendo $f(x,y)= \phi(x) + \psi(y)$, per ottenere quanto detto sopra basta avere una $\phi$ che non ha massimo su $X$.
2.
Ovviamente basta far vedere che non è soddisfatta una delle due condizioni dell'equilibrio di Nash. Quindi wedge come $g$ poteva prendere una funzione qualsiasi. Anche se un esempio "simmetrico" piace di più (non solo ai fisici).
3.
Vi sono interessanti situazioni reali in cui una ragionevole modellizzazione porta a dei payoff come quelli indicati da wedge. Payoff che hanno uno "scalino", un salto. Ne cito due (che poi sono la stessa cosa...).
- duopolio di Bertrand. Le imprese usano il prezzo come variabile strategica. L'idea è che chi ha un prezzo di vendita minore [edit: "minore" era rimasto nella "penna"] si impossessa di tutto il mercato. Allora, dato $p_0$, la funzione $p \mapsto f(p,p_0)$ ha, ragionevolmente, una discontinuità in $p_0$.
- guerra d'attrito. Tipica nel "mating". Spesso nelle esibizioni dei maschi il fattore durata è rilevante. Di nuovo, per valori del parametro rilevante (in questo caso, il tempo) uguali, abbiamo una discontinuità.
Ricordo un fenomeno simile nelle aste in busta chiusa.
La guerra d'attrito è strettamente imparentata col gioco dei polli (chicken).
Un riferimento utile mi sembra:
http://www.puc-rio.br/marco.ind/pdf/dia ... -games.pdf
Ciò detto, tre considerazioni sull'esempio di wedge.
1.
Se $(\bar x, \bar y)$ è un equilibrio di Nash, allora $\bar x$ è un punto di massimo per la funzione $ x \mapsto f(x,\bar y)$. Allora, per avere un esempio privo di equilibri di Nash basta fare in modo che $ x \mapsto f(x,y)$ non abbia massimo, per qualsiasi valore di $y$.
Mi sembra di capire che questa sia l'idea dietro all'esempio di wedge. Infatti, la funzione che lui propone non ha mai massimo in $x$, comunque sia fissato $y$.
A questa idea se ne aggiunge un'altra: quella di prendere un payoff separabile in $x$ ed $y$. Essendo $f(x,y)= \phi(x) + \psi(y)$, per ottenere quanto detto sopra basta avere una $\phi$ che non ha massimo su $X$.
2.
Ovviamente basta far vedere che non è soddisfatta una delle due condizioni dell'equilibrio di Nash. Quindi wedge come $g$ poteva prendere una funzione qualsiasi. Anche se un esempio "simmetrico" piace di più (non solo ai fisici).
3.
Vi sono interessanti situazioni reali in cui una ragionevole modellizzazione porta a dei payoff come quelli indicati da wedge. Payoff che hanno uno "scalino", un salto. Ne cito due (che poi sono la stessa cosa...).
- duopolio di Bertrand. Le imprese usano il prezzo come variabile strategica. L'idea è che chi ha un prezzo di vendita minore [edit: "minore" era rimasto nella "penna"] si impossessa di tutto il mercato. Allora, dato $p_0$, la funzione $p \mapsto f(p,p_0)$ ha, ragionevolmente, una discontinuità in $p_0$.
- guerra d'attrito. Tipica nel "mating". Spesso nelle esibizioni dei maschi il fattore durata è rilevante. Di nuovo, per valori del parametro rilevante (in questo caso, il tempo) uguali, abbiamo una discontinuità.
Ricordo un fenomeno simile nelle aste in busta chiusa.
La guerra d'attrito è strettamente imparentata col gioco dei polli (chicken).
Un riferimento utile mi sembra:
http://www.puc-rio.br/marco.ind/pdf/dia ... -games.pdf
"Fioravante Patrone":
Se $(\bar x, \bar y)$ è un equilibrio di Nash, allora $\bar x$ è un punto di massimo per la funzione $ x \mapsto f(x,\bar y)$. Allora, per avere un esempio privo di equilibri di Nash basta fare in modo che $ x \mapsto f(x,y)$ non abbia massimo, per qualsiasi valore di $y$.
Io però sapevo che una funzione continua su un compatto ammette sempre massimo.
Ora, fissato $y$, la funzione $x \mapsto f(x,y)$ avrà sempre massimo assoluto
"Kroldar":
[quote="Fioravante Patrone"]
Se $(\bar x, \bar y)$ è un equilibrio di Nash, allora $\bar x$ è un punto di massimo per la funzione $ x \mapsto f(x,\bar y)$. Allora, per avere un esempio privo di equilibri di Nash basta fare in modo che $ x \mapsto f(x,y)$ non abbia massimo, per qualsiasi valore di $y$.
Io però sapevo che una funzione continua su un compatto ammette sempre massimo.
Ora, fissato $y$, la funzione $x \mapsto f(x,y)$ avrà sempre massimo assoluto
[/quote]Corretto, naturalmente.
Io mi stavo muovendo fuori dall'assunzione di continuità per i payoff, in quanto stavo commentando l'esempio di wedge.
Quello che ricordi tu mostra come l'ipotesi di compattezza più continuità impedisca che simili mezzucci (funzioni "prive di massimo") possano essere usati.
"Fioravante Patrone":
Io mi stavo muovendo fuori dall'assunzione di continuità per i payoff, in quanto stavo commentando l'esempio di wedge.
Ah ecco... avevo frainteso
Io in verità stavo pensando a un esempio sempre sulla falsariga dei giochi a somma zero, cioè con funzioni $f$ e $g$ continue magari (come suggerivi) in $[0,1]$ e tali che $f(x,y) + g(x,y) = 0$, in modo che $f$ abbia massimo dove $g$ ha minimo e viceversa.
Aspetto. Dopotutto non è una "mission impossible"
Il problema è trovare esempi semplice... Vediamo... Per $f$ un piano inclinato che passa per i punti $(0,0,0)$ e $(1,1,1)$ e con gradiente che giace sulla bisettrice del primo e terzo quadrante del piano $OXY$. Per $g$ la stessa funzione col segno cambiato.
$f$ e $g$ lineari?
no
Il teorema di Nash mi garantisce che c'è equilibrio...
E, se non prendo cantonate, mi pare che $(1,0)$ sia equilibrio di Nash.
Le espessioni analitiche per $f$ e $g$ direi siano le seguenti:
$f(x,y)= (1/2) (x+y)$
$g(x,y)= - (1/2) (x+y)$
no
Il teorema di Nash mi garantisce che c'è equilibrio...
E, se non prendo cantonate, mi pare che $(1,0)$ sia equilibrio di Nash.
Le espessioni analitiche per $f$ e $g$ direi siano le seguenti:
$f(x,y)= (1/2) (x+y)$
$g(x,y)= - (1/2) (x+y)$
"Fioravante Patrone":
E, se non prendo cantonate, mi pare che $(1,0)$ sia equilibrio di Nash.
Esatto! E anche $(0,1)$ lo è a questo punto.
"Kroldar":
Esatto! E anche $(0,1)$ lo è a questo punto.
no
"Fioravante Patrone":
[quote="Kroldar"]
Esatto! E anche $(0,1)$ lo è a questo punto.
no
[/quote]Vero, scusa. Se $I$ gioca $0$, la miglior risposta di $II$ è $0$.
Domandina ...
é vero che se tutte le sezioni orizzontali di $f$ e quelle verticali di $g$ hanno un unico massimo, allora esiste un equilibrio di Nash? (sempre sotto hp di $f,g : [0,1]\rightarrow RR$ continue)
é vero che se tutte le sezioni orizzontali di $f$ e quelle verticali di $g$ hanno un unico massimo, allora esiste un equilibrio di Nash? (sempre sotto hp di $f,g : [0,1]\rightarrow RR$ continue)
Stavo appunto per postare questo ragionamento, ubermensch
Siano $f(x,y)$ e $g(x,y)$ funzioni continue $[0,1]x[0,1]\to RR$. Supponiamo che per ogni $a\in [0,1]$, le funzioni $f(x,a)$ e $g(a,y)$ abbiano un solo massimo in $[0,1]$. Allora esiste un equilibrio di Nash.
Consideriamo le funzioni $X,Y:[0,1]\to [0,1]$ cosi' definite:
$X(a)$ e' tale che $f(X(a),a)$ e' il punto di massimo della funzione $f(x,a)$ e analogamente $Y(a)$ e' tale che $g(a,Y(a))$ e' il punto di massimo della funzione $g(a,y)$
Ora essendo $X,Y$ continue, la funzione $X\circ Y: [0,1]\to [0,1]$ e' continua. Per il teorema di punto fisso di Brouwer, esiste un $bar x\in [0,1]$ tale che $X\circ Y(bar x)=bar x$.
Ma allora la coppia $(bar x, Y(bar x))$ e' un equilibrio di Nash per costruzione.
Come corollario abbiamo che per trovare il controesempio bisogna scartare tutte le funzioni crescenti.
Siano $f(x,y)$ e $g(x,y)$ funzioni continue $[0,1]x[0,1]\to RR$. Supponiamo che per ogni $a\in [0,1]$, le funzioni $f(x,a)$ e $g(a,y)$ abbiano un solo massimo in $[0,1]$. Allora esiste un equilibrio di Nash.
Consideriamo le funzioni $X,Y:[0,1]\to [0,1]$ cosi' definite:
$X(a)$ e' tale che $f(X(a),a)$ e' il punto di massimo della funzione $f(x,a)$ e analogamente $Y(a)$ e' tale che $g(a,Y(a))$ e' il punto di massimo della funzione $g(a,y)$
Ora essendo $X,Y$ continue, la funzione $X\circ Y: [0,1]\to [0,1]$ e' continua. Per il teorema di punto fisso di Brouwer, esiste un $bar x\in [0,1]$ tale che $X\circ Y(bar x)=bar x$.
Ma allora la coppia $(bar x, Y(bar x))$ e' un equilibrio di Nash per costruzione.
Come corollario abbiamo che per trovare il controesempio bisogna scartare tutte le funzioni crescenti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo