Esistenza dellìequilibrio di Nash
Salve a tutti,
dal teorema di esistenza di un equilibrio di Nash so che se un gioco è finito questo ha sicuramente un NE (se non in strategie pure, sicuramente in strategie miste).
Se però il gioco non è finito, come nel caso che i giocatori abbiano a disposizione infinite strategie (penso ad esempio il caso in cui i giocatori devono puntare una certa cifra), esiste qualche teorema, magari facendo ulteriori ipotesi (tipo che l'intervallo deve essere almeno chiuso) che mi garantisce un equilibrio?
Ho provato a costruirmi degli esempi per vedere se riuscivo a risale ad un equilibrio, ma ho delle difficoltà quando provo a costruire l'estensione mista del gioco. In particolare se ho un numero finito di strategie associo una probabilità ad ognuna di queste, ma quando le strategie sono infinite? Uso una distribuzione? Anche su questo punto ho cercato di trovare una risposta ma niente...
Mi sarebbe davvero utile un chiarimento a proposito.
Grazie in anticipo!
dal teorema di esistenza di un equilibrio di Nash so che se un gioco è finito questo ha sicuramente un NE (se non in strategie pure, sicuramente in strategie miste).
Se però il gioco non è finito, come nel caso che i giocatori abbiano a disposizione infinite strategie (penso ad esempio il caso in cui i giocatori devono puntare una certa cifra), esiste qualche teorema, magari facendo ulteriori ipotesi (tipo che l'intervallo deve essere almeno chiuso) che mi garantisce un equilibrio?
Ho provato a costruirmi degli esempi per vedere se riuscivo a risale ad un equilibrio, ma ho delle difficoltà quando provo a costruire l'estensione mista del gioco. In particolare se ho un numero finito di strategie associo una probabilità ad ognuna di queste, ma quando le strategie sono infinite? Uso una distribuzione? Anche su questo punto ho cercato di trovare una risposta ma niente...
Mi sarebbe davvero utile un chiarimento a proposito.
Grazie in anticipo!
Risposte
Sì, c'è il teorema di Glicksberg, di poco successivo al teorema di Nash.
Se gli spazi di strategie sono spazi metrici compatti (ad esempio, un intervallo chiuso e limitato) e se i payoff sono funzioni continue, allora il gioco ha equilibri di Nash in strategie miste (misure di Borel).
Ne trovi una succinta descrizione sulla wiki inglese:
http://en.wikipedia.org/wiki/Continuous_game
[size=84]Occhio, come sempre, con wiki:
https://www.matematicamente.it/forum/l-e ... tml#404385[/size]
Qui trovi il risultato originale di Glicksberg:
http://www.ams.org/journals/proc/1952-0 ... 6638-5.pdf
Se gli spazi di strategie sono spazi metrici compatti (ad esempio, un intervallo chiuso e limitato) e se i payoff sono funzioni continue, allora il gioco ha equilibri di Nash in strategie miste (misure di Borel).
Ne trovi una succinta descrizione sulla wiki inglese:
http://en.wikipedia.org/wiki/Continuous_game
[size=84]Occhio, come sempre, con wiki:
https://www.matematicamente.it/forum/l-e ... tml#404385[/size]
Qui trovi il risultato originale di Glicksberg:
http://www.ams.org/journals/proc/1952-0 ... 6638-5.pdf
Innanzitutto grazie della tempestiva risposta!
Il teorema è chiaro, almeno concettualmente!
Prima di venire a conoscenza di questo teorema, stavo provando a ragionare su un esempio in particolare (magari è banale, ma io sono alle prime armi e non riesco ad andare avanti).
Il gioco è il seguente:
-Due giocatori (I e II) devono fare una certa puntata compresa tra 0 e 1 (estremi esclusi),
-Se il "piatto" è minore di uno vince il giocatore che ha ha fatto la puntata più piccola
-Se il "piatto" è maggiore di uno vince il giocatore che ha fatto la puntata più grande
-Se il "piatto" è uguale a 1 o le puntate dei giocatori sono uguali si spartisce il piatto a metà
-La vincita è rappresentata dal "piatto"
Le "best reply" dei due giocatori non si incontrano mai.
Infatti (se non ho commesso errori) le best reply sono (chiamo x la puntata di I e y la puntata di II):
[tex]\[
R_{I}(y)=\begin{cases}
x1-y, & \forall y\in(0,\frac{1}{2}]\\
x<1-y\;{\textstyle oppure}\; x>y, & \forall y\in[\frac{1}{2},1)\end{cases}\][/tex]
Essendo il gioco simmetrico la best reply è analoga a quella del giocatore I.
Gli insiemi che si formano non hanno punti in comune, quindi non esiste un NE in "strategie pure".
Il problema con questo esempio è che i payoff non sono funzioni continue... tuttavia come si può procedere per verificare se esistono NE in strategie miste?
È un problema che mi incuriosisce da qualche giorno, ma da solo non riesco a trovarne la soluzione... mi sarebbe d'aiuto se qualcuno potesse darmi qualche buon suggerimento su come procedere.
Grazie ancora!
Il teorema è chiaro, almeno concettualmente!
Prima di venire a conoscenza di questo teorema, stavo provando a ragionare su un esempio in particolare (magari è banale, ma io sono alle prime armi e non riesco ad andare avanti).
Il gioco è il seguente:
-Due giocatori (I e II) devono fare una certa puntata compresa tra 0 e 1 (estremi esclusi),
-Se il "piatto" è minore di uno vince il giocatore che ha ha fatto la puntata più piccola
-Se il "piatto" è maggiore di uno vince il giocatore che ha fatto la puntata più grande
-Se il "piatto" è uguale a 1 o le puntate dei giocatori sono uguali si spartisce il piatto a metà
-La vincita è rappresentata dal "piatto"
Le "best reply" dei due giocatori non si incontrano mai.
Infatti (se non ho commesso errori) le best reply sono (chiamo x la puntata di I e y la puntata di II):
[tex]\[
R_{I}(y)=\begin{cases}
x
x<1-y\;{\textstyle oppure}\; x>y, & \forall y\in[\frac{1}{2},1)\end{cases}\][/tex]
Essendo il gioco simmetrico la best reply è analoga a quella del giocatore I.
Gli insiemi che si formano non hanno punti in comune, quindi non esiste un NE in "strategie pure".
Il problema con questo esempio è che i payoff non sono funzioni continue... tuttavia come si può procedere per verificare se esistono NE in strategie miste?
È un problema che mi incuriosisce da qualche giorno, ma da solo non riesco a trovarne la soluzione... mi sarebbe d'aiuto se qualcuno potesse darmi qualche buon suggerimento su come procedere.
Grazie ancora!
Proseguo nella mia analisi dell'esempio di cui sopra.
Se modifico il gioco e suppongo invece che fare una qualsiasi puntata in (0,1) i giocatori abbiano entrambi a disposizione 99 monete da 1 centesimo e debbano decidere quante puntarne, con il vincolo che devono puntarne almeno una, ottengo un gioco finito e quindi è possibile dimostrare che esiste un NE. Ovviamente si potrebbe considerare il gioco con mille monete da un millesimo (vabbè, è il concetto che conta...) e così via.
Questo mi fa supporre (ma una supposizione non è sufficiente...) che anche per il gioco infinito debba esistere un NE.
Il problema con il quale mi scontro è che se per un numero n (finito) di strategie posso associare un $ p_i $ e un $ q_j $ ( $ i ,j= {1,...,n} $) ad ogni strategia rispettivamente del giocatore I e II che rappresentino la probabilità per ogni strategia di essere giocata (ovviamente $ sum p_i = sum q_i = 1 $ ). A quel punto posso calcolare il payoff atteso e trovare cosa accade all'equilibrio.
Quando invece le strategie sono nel continuo non so come procedere, e non riesco neppure a trovare materiale che mi sia d'aiuto (evidentemente sono anche imbranato a fare ricerche sul web).
Mi auguro che qualcuno possa darmi qualche buon suggerimento.
Grazie in anticipo per qualsiasi indicazione.
Se modifico il gioco e suppongo invece che fare una qualsiasi puntata in (0,1) i giocatori abbiano entrambi a disposizione 99 monete da 1 centesimo e debbano decidere quante puntarne, con il vincolo che devono puntarne almeno una, ottengo un gioco finito e quindi è possibile dimostrare che esiste un NE. Ovviamente si potrebbe considerare il gioco con mille monete da un millesimo (vabbè, è il concetto che conta...) e così via.
Questo mi fa supporre (ma una supposizione non è sufficiente...) che anche per il gioco infinito debba esistere un NE.
Il problema con il quale mi scontro è che se per un numero n (finito) di strategie posso associare un $ p_i $ e un $ q_j $ ( $ i ,j= {1,...,n} $) ad ogni strategia rispettivamente del giocatore I e II che rappresentino la probabilità per ogni strategia di essere giocata (ovviamente $ sum p_i = sum q_i = 1 $ ). A quel punto posso calcolare il payoff atteso e trovare cosa accade all'equilibrio.
Quando invece le strategie sono nel continuo non so come procedere, e non riesco neppure a trovare materiale che mi sia d'aiuto (evidentemente sono anche imbranato a fare ricerche sul web).
Mi auguro che qualcuno possa darmi qualche buon suggerimento.
Grazie in anticipo per qualsiasi indicazione.
Mi spiace che nei giorni scorsi non sono riuscito a dedicare molto tempo a questo problema, comunque nel tempo che mi avanza cerco di trovare qualche utile riferimento per risolverlo.
Sto leggendo in particolare "The Mathematics of games of strategy, Melvin Dresher" e "Game Theory, Fudenberg & Tirole" che trattano l'argomento dei "giochi continui" (è corretto in italiano?), al momento purtroppo solo sulle anteprime del web, ma in settimana vado a prenderli in biblioteca! Ovviamente qualsiasi suggerimento su questi o altri testi è apprezzato!
Inoltre ho letto che esiste un teorema anche per i giochi che hanno funzioni di payoff discontinue, ovvero il teorema di Dasgupta-Maskin (1986). Non sono però riuscito a trovare materiale che spieghi questo teorema (in particolare per quali funzioni è possibile applicarlo) e faccio ancora appello qui per qualche riferimento.
Grazie ancora
Sto leggendo in particolare "The Mathematics of games of strategy, Melvin Dresher" e "Game Theory, Fudenberg & Tirole" che trattano l'argomento dei "giochi continui" (è corretto in italiano?), al momento purtroppo solo sulle anteprime del web, ma in settimana vado a prenderli in biblioteca! Ovviamente qualsiasi suggerimento su questi o altri testi è apprezzato!
Inoltre ho letto che esiste un teorema anche per i giochi che hanno funzioni di payoff discontinue, ovvero il teorema di Dasgupta-Maskin (1986). Non sono però riuscito a trovare materiale che spieghi questo teorema (in particolare per quali funzioni è possibile applicarlo) e faccio ancora appello qui per qualche riferimento.
Grazie ancora
Partha Dasgupta & Eric Maskin, 1982. "The Existence of Equilibrium in Discontinuous Economic Games, 1: Theory (Now published in Review of Economic Studies, LIII (1986), pp.1-26.)," STICERD - Theoretical Economics Paper Series 54, Suntory and Toyota International Centres for Economics and Related Disciplines, LSE.
Partha Dasgupta & Eric Maskin, 1982. "The Existence of Equilibrium in Discontinuous Economic Games, 2: Applications (Now published in Review of Economic Studies, LIII (1986), pp.27-41.)," STICERD - Theoretical Economics Paper Series 55, Suntory and Toyota International Centres for Economics and Related Disciplines, LSE.
La Review of Economic Studies è reperibile in ogni decente biblioteca di facoltà di economia.
Ho anche scoperto che il mio amico Gilli se ne è occupato!
http://onlinelibrary.wiley.com/doi/10.1 ... 1/abstract
Sui due libri che indichi, il primo non lo conosco.
Il secondo, non lo suggerirei per trovarci su roba di matematica.
Puoi provare in biblio se trovi i libri di Ichiishi, Rosenmuller, o il libro appena pubblicato (ammesso che sia uscito) da Garcia Jurado (et al.).
Magari anche il buon vecchio Owen
Partha Dasgupta & Eric Maskin, 1982. "The Existence of Equilibrium in Discontinuous Economic Games, 2: Applications (Now published in Review of Economic Studies, LIII (1986), pp.27-41.)," STICERD - Theoretical Economics Paper Series 55, Suntory and Toyota International Centres for Economics and Related Disciplines, LSE.
La Review of Economic Studies è reperibile in ogni decente biblioteca di facoltà di economia.
Ho anche scoperto che il mio amico Gilli se ne è occupato!
http://onlinelibrary.wiley.com/doi/10.1 ... 1/abstract
Sui due libri che indichi, il primo non lo conosco.
Il secondo, non lo suggerirei per trovarci su roba di matematica.
Puoi provare in biblio se trovi i libri di Ichiishi, Rosenmuller, o il libro appena pubblicato (ammesso che sia uscito) da Garcia Jurado (et al.).
Magari anche il buon vecchio Owen
Grazie delle indicazioni!
Ho trovato tutto in biblio (almeno sul catalogo), tranne il libro di Garcia Jurado et al. (probabilmente non è ancora uscito).
Ho trovato tutto in biblio (almeno sul catalogo), tranne il libro di Garcia Jurado et al. (probabilmente non è ancora uscito).
No, esiste.
Ho verificato:
http://www.nextag.com/An-Introductory-C ... rices-html
E' uscito da poco, e quindi normale che non si trovi ancora in biblioteca.
Qui alcuni excerpt, tra cui l'indice:
http://www.eurospanbookstore.com/displa ... 821851517&
Ho verificato:
http://www.nextag.com/An-Introductory-C ... rices-html
E' uscito da poco, e quindi normale che non si trovi ancora in biblioteca.
Qui alcuni excerpt, tra cui l'indice:
http://www.eurospanbookstore.com/displa ... 821851517&
È vero, c'è anche l'anteprima su google, evidentemente ero un po' appisolato ieri sera quando cercavo.
Riguardo al problema che sto provando a risolvere ho fatto qualche (piccolo) passo avanti (spero).
Trattandosi di un gioco a somma zero, all'equilibrio il valore atteso del gioco deve essere 0. Inoltre poiché il gioco è simmetrico le strategie attuate dai giocatori saranno le stesse.
All'equilibri quindi i giocatori adottano una distribuzione uniforme su tutto l'intervallo. Con queste strategie quindi ogni giocatore ha un payoff atteso pari a 0.
Appena ho tempo (mi auguro stasera) provo a dimostrare che questo è l'equilibrio.
Ovviamente qualsiasi suggerimento è apprezzato!
Grazie ancora.
Riguardo al problema che sto provando a risolvere ho fatto qualche (piccolo) passo avanti (spero).
Trattandosi di un gioco a somma zero, all'equilibrio il valore atteso del gioco deve essere 0. Inoltre poiché il gioco è simmetrico le strategie attuate dai giocatori saranno le stesse.
All'equilibri quindi i giocatori adottano una distribuzione uniforme su tutto l'intervallo. Con queste strategie quindi ogni giocatore ha un payoff atteso pari a 0.
Appena ho tempo (mi auguro stasera) provo a dimostrare che questo è l'equilibrio.
Ovviamente qualsiasi suggerimento è apprezzato!
Grazie ancora.
"giacomo.bezzi":
Trattandosi di un gioco a somma zero, all'equilibrio il valore atteso del gioco deve essere 0.
Falso. In un gioco in cui il primo giocatore guadagna sempre 44 e il secondo perde sempre 44 qualunque strategia usino i giocatori non è vero che il valore (atteso???) del gioco sia 0.
"giacomo.bezzi":
Inoltre poiché il gioco è simmetrico le strategie attuate dai giocatori saranno le stesse.
All'equilibri quindi i giocatori adottano una distribuzione uniforme su tutto l'intervallo. Con queste strategie quindi ogni giocatore ha un payoff atteso pari a 0.
Un gioco simmetrico ha sempre un equilibrio simmetrico, ma può averne anche di non simmetrici.
Perché dovrebbero usare una distribuzione uniforme sull'intervallo? Non dico che sia falso, dico solo che questa affermazione andrebbe corroborata (magari provata...).
"Fioravante Patrone":
Falso. In un gioco in cui il primo giocatore guadagna sempre 44 e il secondo perde sempre 44 qualunque strategia usino i giocatori non è vero che il valore (atteso???) del gioco sia 0.
In effetti ho fatto confusione.
Ma se il gioco è sia simmetrico che a somma zero allora il valore del gioco è 0?
Per la soluzione del problema invece non riesco a dimostrare che dovrebbero usare una distribuzione uniforme, anzi....
Infatti se un giocatore adottasse una distribuzione uniforme, l'altro punterebbe una cifra molto piccola, che gli darebbe maggiori possibilità di vincere, e quindi deduco che giocare una distribuzione uniforme non è un equilibrio.
A questo punto sono un'altra volta da capo! Domani vado a procurarmi i libri suggeriti...
Grazie ancora
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo