A mio avviso non è così intuitivo che se $(bar x,bar y)$ è un equilibrio di Nash per un gioco finito, allora esso è anche equilibrio per l'estensione mista. Tuttavia la dimostrazione di questa proposizione non è particolarmente difficile. Per prima cosa ricordiamo la definizione di equilibrio di Nash (cito testualmente le parole del libro):
Sia dato un gioco $G=(X,Y,f,g)$. Diremo che $(bar x,bary) in XxxY$ è un equilibrio di Nash per $G$ se: $f(bar x,bar y) \ge f(x,bar y)$ per ogni $x in X$ $g(bar x,bar y) \ge g(bar x,y)$ per ogni $y in Y$

Consideriamo ora un gioco $(X,Y,f,g)$, con $X={x_1,...,x_m}$ e $Y={y_1,...,y_n}$; consideriamo inoltre gli insiemi $Delta(X)={p in RR^m : sum_(i=1)^m p_i = 1, p_i >= 0 AA i}$ e $Delta(Y)={q in RR^n : sum_(j=1)^n p_j = 1, p_j >= 0 AA j}$, che rappresentano tutte le possibili distribuzioni di probabilità su $X$ e $Y$. Possiamo a questo punto, date $p in Delta(X)$ e $q in Delta(Y)$, calcolare il payoff atteso $hat f$$(p,q)$ e $hat g$$(p,q)$ per ciascun giocatore nel modo seguente:
$hat f$$(p,q) = sum_(i=1)^m sum_(j=1)^n p_i q_j f(x_i,y_j)$
$hat g$$(p,q) = sum_(i=1)^m sum_(j=1)^n p_i q_j g(x_i,y_j)$.
Concentriamo la nostra attenzione sull'esito $(x_k,y_h)$ con $1 \le k \le m$ e $1 \le h \le n$ e ipotizziamo che esso sia un equilibrio di Nash per il gioco in strategie pure; a tal proposito ricordiamo che una strategia pura può essere vista come un caso particolare dell'estensione mista, in cui ciascun giocatore opta per una determinata strategia con probabilità $1$.
Ipotizziamo allora che l'equilibrio $(x_k,y_h)$ si ottenga assegnando ($p_i$ nel seguito indicherà la probabilità con cui il giocatore I opta per la strategia $x_i$):
$bar p:p_k=1, p_i=0 AA i != k$
$bar q:q_h=1, q_j=0 AA j != h$
quindi l'esito $(bar p, bar q)$ in strategie miste equivale all'esito $(x_k,y_h)$ in strategie pure. Ovviamente risulta $hat f$$(bar p,bar q) = sum_(i=1)^m sum_(j=1)^n p_i q_j f(x_i,y_j) = f(x_k,y_h)$. Essendo $(x_k,y_h)$ equilibrio di Nash, sappiamo che $f(x_k,y_h) \ge f(x_i,y_h) AA i$. Se fissiamo soltanto $bar q:q_h=1, q_j=0 AA j != h$ avremo che per ogni $p$ risulta:
$hat f$$(p,bar q) = sum_(i=1)^m sum_(j=1)^n p_i q_j f(x_i,y_j) = $
$ = p_1 f(x_1,y_h) + p_2 f(x_2,y_h) + ... + p_m f(x_m,y_h) \le $
$ \le p_1 f(x_k,y_h) + p_2 f(x_k,y_h) + ... + p_m f(x_k,y_h) = $
$ = (p_1+p_2+...+p_m) f(x_k,y_h) = f(x_k,y_h) = hat f$$(bar p,bar q)$
da cui segue che $\hat f$$(p,bar q) \le hat f$$(bar p,bar q)$ per ogni $p$, ovvero che $(bar p, bar q)=(x_k,y_h)$ è equilibrio di Nash anche per l'estensione mista del gioco. Un discorso analogo può essere fatto per la funzione $g$. QED

Mio commento:
Nulla da eccepire.
Resta la seconda parte del problema!  

Commento di Andrea Vitiello:

Per quanto riguarda la seconda parte del problema 24, direi che si deve dimostrare che in problemi di decisione individuale gli equilibri di Nash in strategie miste non si considerano. Il motivo è semplice: per problemi di decisione individuale, gli equilibri di Nash in strategie miste non migliorano in alcun modo il payoff atteso dal giocatore, quindi il payoff per ciascun equilibrio in strategie pure è pari al massimo payoff atteso in strategie miste. Consideriamo dunque un gioco in cui sia presente un solo giocatore, allora esso è del tipo $(X,f)$, con $X={x_1,...,x_m}$. Innanzitutto va osservato che in un gioco del genere tutti gli equilibri sono equivalenti, difatti presi due equilibri $x_k$ e $x_h$, allora dalla definizione di equilibrio risulta $f(x_k) \ge f(x_i)$ e $f(x_h) \ge f(x_i)$ con $1 \le i \le m$ e di conseguenza si ha $f(x_k) = f(x_h)$. Per l'estensione mista di questo gioco, detta $p$ una generica distribuzione di probabilità, si può calcolare il payoff atteso dal giocatore nel modo seguente: $hat f$$(p) = sum_(i=1)^m p_i f(x_i)$. Se ipotizziamo che il gioco abbia un unico equilibrio, per ogni distribuzione di probabilità $p$ risulta:
$hat f$$(p) = sum_(i=1)^m p_i f(x_i) \le sum_(i=1)^m p_i f(x_k) = f(x_k) sum_(i=1)^m p_i = f(x_k)$.
Come si vede il payoff atteso non può mai superare il valore di payoff corrispondente all'equilibrio in strategie pure. Il discorso non cambia in presenza di più equilibri. Si può dimostrare (qui non lo faremo) che tutti gli equilibri in strategie miste di un gioco a decisione singola sono tali da assegnare probabilità $0$ alle strategie che non siano equilibri nella forma pura. Allora ipotizziamo che nel gioco preso in considerazione si abbiano $s \le m$ equilibri in strategie pure e indichiamo con $x_(k_1),\ldots,x_(k_s)$ tali equilibri, i quali abbiamo dimostrato avere tutti valore uguale $x_k$. Indichiamo inoltre con $hat p$ una generica distribuzione di probabilità che assegna valore $0$ alla probabilità di utilizzare una strategia che non sia equilibrio di Nash. Per ogni distribuzione di probabilità $p$ risulta dunque:
$hat f$$(p) = sum_(i=1)^m p_i f(x_i) \le hat f$$(hat p) = $
$ = sum_(i=1)^s p_i f(x_(k_i)) = sum_(i=1)^s p_i f(x_k) = f(x_k) sum_(i=1)^s p_i = f(x_k)$.
Abbiamo visto come, anche in presenza di più equilibri in strategie pure, non si possa migliorare il payoff atteso rispetto al valore del payoff di un generico equilibrio di Nash. Dunque per problemi di decisione individuale l'introduzione di strategie miste non comporta alcun beneficio in termini di payoff.

Mio commento:
Condivido. Una sola osservazione: se c'è un solo giocatore, l'equilibrio di Nash si riduce a trovare un punto che massimizza la $f$.
Detto questo, rilancio!  
Come si può conciliare questo (cioè la provata inutilità delle strategie miste) con quanto avviene nel "gioco di Isbell"?
Vedasi pagg. 11-12 degli appunti sui giochi in forma estesa indicati qui.

Commento di Andrea Vitiello:

Secondo me il tranello sta nella mancanza della "memoria". Ipotizziamo un problema analogo al gioco di Isbell, con l'unica differenza che stavolta il giocatore può ricordare le mosse fatte in precedenza. Evidentemente, siccome si troverà due volte davanti a un bivio, il giocatore dovrà ciascuna delle due volte decidere se svoltare o proseguire; le possibili strategie a questo punto sono $4$:
- $(P,P)$: prosegui al primo bivio e prosegui al secondo
- $(P,S)$: prosegui al primo bivio e svolta al secondo
- $(S,S)$: svolta al primo bivio e svolta al secondo
- $(S,P)$: svolta al primo bivio e prosegui al secondo
Ci tengo a precisare che ogni indicazione riguardo a cosa fare in prossimità di ciascun incrocio è subordinato al fatto che il gioco sia ancora in corso: nel caso della strategia $(S,S)$ ad esempio il giocatore svolta al primo bivio, ma lì il gioco termina e non ci sarà un secondo bivio davanti al quale dover decidere nuovamente il da farsi. Qualcuno a questo punto potrebbe obiettare: "Perché non unire le due strategie $(S,S)$ e $(S,P)$ in una sola visto che portano allo stesso esito?" Semplicemente perché, quando si introdurranno le strategie miste, con la notazione che ho usato le cose risulteranno più semplici.
In base a quanto detto, i payoff saranno:
$f(P,P)=0$, $f(P,S)=1$, $f(S,S)=0$, $f(S,P)=0$.
Dalla teoria in altra sede trattata sappiamo che l'unico equilibrio di Nash in strategie pure di questo gioco è $(P,S)$. Sempre da risultati notevoli di teoria sappiamo che, passando all'estensione mista, avremo un unico equilibrio che corrisponde a giocare $(P,S)$ con probabilità $1$. Se consideriamo la strategia mista che prevede di attribuire probabilità $1/2$ ad ogni scelta (binaria) per ciascun bivio, essendo le scelte per ciascun bivio indipendenti, otteniamo che il payoff atteso è pari a $1/4$; notare che questo in questo caso non saremmo in presenza di un equilibrio di Nash. Ragionando così i conti tornano e, come ci aspettavamo, le strategie miste non portano alcun miglioramento!

Perché nel gioco di Isbell in forma originale sembra invece che passando in strategie miste si ottenga un miglioramento in termini di payoff atteso?
Personalmente ritengo che il "gioco" (lo si può ancora definire tale?) di Isbell sia tale per cui l'insieme delle strategie possibili vìoli una proprietà importante (che si era implicitamente assunta nella dimostrazione dell'inutilità delle strategie miste per problemi a decisione individuale): ogni strategia deve contenere l' ordine di preferenza delle mosse possibili ad ogni insieme di informazione; in parole semplici, il giocatore, non sapendo ogni volta in quale nodo dell'insieme di informazione si trovi, deve indicare quale mossa si deve tentare di effettuare per prima (qualora sia possibile, la mossa sarà effettivamente attuata) e via via l'ordine con cui provare ad effettuare le diverse mosse possibili. Non credo quindi che l'inghippo insito nel gioco di Isbell dipenda dall'utilizzo delle strategie miste, piuttosto ritengo che le caratteristiche del problema non permettano una corretta definizione delle strategie nel senso in cui le intendiamo noi. Insomma la confusione nasce dal fatto che l'insieme delle strategie per il gioco di Isbell non è lo stesso che ho considerato nella mia versione modificata del gioco e quindi il ricorso alla probabilità è a questo punto indispensabile.

Ho letto il paragone con un automa a stati finiti... Un gioco in cui il giocatore ha memoria delle mosse precedenti può essere visto come un sistema puramente dinamico deterministico a tempo discreto (ipotizziamo anche la stazionarietà per non portarci dietro la dipendenza diretta dal tempo), in cui la risposta ad ogni istante dipende dallo stato del sistema allo stesso istante... stato che a sua volta, ad ogni istante, è legato (tramite equazione alle differenze) allo stato all'istante precedente. Questo è un chiaro esempio di come il concetto di stato di un sistema sia equivalente a quello di memoria. Ovviamente se non c'è memoria (e quindi istante per istante lo stato non è univocamente determinato) le cose cambiano radicalmente...

Mio commento:
Non vorrei dare una risposta esaustiva. Mi limito ad alcuni commenti alla tua interessante replica.

• OK per l'analisi che fai del "gioco di Isbell privato dell'insieme di informazione"
• Dici: "Perché nel gioco di Isbell in forma originale sembra invece che passando in strategie miste...".
  La terminologia non è corretta (mi riferisco al termine "strategie miste").
  Osservo preliminarmente che il "gioco di Isbell" viola una delle condizioni poste da Kuhn nella definizione di gioco in forma estesa. Vedi punto 4. della definizione negli appunti sui giochi in forma estesa.
  Ciò detto, comunque, la definizione di strategia come funzione che per ogni insieme di informazione sceglie una tra le alternative disponibili in quell'insieme di informazione, ha ancora perfettamente senso nel caso del gioco di Isbell.
  Ma, allora, il giocatore ha a sua disposizione due strategie: $P,S$. E, quindi una strategia mista è $(p,1-p)$, dove $p$ è la probabilità di scegliere $P$ e $1-p$ quella di scegliere $S$. Ne segue che, con una strategia mista, non si arriva a casa (cioè, non si ottiene alcun vantaggio rispetto alle strategie "pure").
  La strategia proposta (lanciare monete ogni volta che si arriva ad un bivio) è un esempio di strategie "comportamentali" (orribile traduzione di "behavioral").
• Dici: "ritengo che il "gioco" (lo si può ancora definire tale?) di Isbell sia tale per cui l'insieme delle strategie possibili vìoli una proprietà importante"
  • Come detto sopra, viola una condizione. Quindi non è un gioco in forma estesa (secondo la definizione di Kuhn).
    Tuttavia, in una prospettiva che sia meno scolastico-libresca, può semplicemente essere che la scelta modellistica di Kuhn non sia la migliore possibile.
  • Più importante, i commenti che fai dopo mischiano in modo secondo me inopportuno la "descrizione asettica del gioco" con la "ricerca della scelta migliore da fare da parte dei giocatori". Sono arciconvinto del fatto che questa "separazione" sia molto utile. Violarla può essere fonte di malintesi ed errori. Anche se non ipostatizzo questa affermazione (non si può negare che, quanto meno, la descrizione "asettica" sia funzionale proprio alla successiva analisi strategica, mostrando che forse così completamente asettica non è).
  • Naturalmente, quando dici: "le caratteristiche del problema non permettano una corretta definizione delle strategie nel senso in cui le intendiamo noi", sono perfettamente d'accordo con te.
• I commenti su "automa a stati finiti" mi sembrano del tutto condivisibili. Non avevo mai "visto" un giocatore come "sistema dinamico deterministico, a tempo discreto". Ti ringrazio della "suggestione" implicita nel definirlo così. Aggiungo, come notazione, che le strategie miste convertono il decisore un "sistema dinamico stocastico, a tempo discreto"