L'equilibrio di Nash

Un profilo di strategie in cui nessuno ha rimorsi unilaterali: il punto fisso della razionalità reciproca, e il bersaglio implicito di ogni convergenza in self-play, GAN, multi-agent RL.

Perché questo capitolo

Quando due reti neurali si addestrano l’una contro l’altra — un generatore che falsifica e un discriminatore che smaschera — verso cosa stanno convergendo, ammesso che convergano? Quando AlphaZero gioca contro se stesso milioni di volte, qual è il punto fisso del processo? Quando due agenti LLM negoziano in un setting ripetuto, esiste una nozione di “soluzione” che non sia “uno dei due barava”?

La risposta, in tutti questi casi, ha un solo nome: equilibrio di Nash. È il concetto più importante della teoria dei giochi non cooperativa, l’oggetto matematico che chiunque costruisca sistemi multi-agente finisce per invocare, esplicitamente o implicitamente. È il bersaglio dichiarato del training GAN, il limite di self-play in zero-sum, la quantità che il counterfactual regret minimization approssima nel poker, la cornice in cui il mechanism design progetta le aste.

Eppure non è una panacea. Esistono giochi con molti equilibri, equilibri Pareto-dominati da non-equilibri, equilibri irraggiungibili in tempo polinomiale, equilibri che gli umani sistematicamente non giocano. Capire dove la nozione funziona e dove si rompe è prerequisito per usarla bene — e per leggere con occhio critico la letteratura che la invoca.

Questo capitolo definisce l’equilibrio di Nash in modo formale, ne spiega l’intuizione da almeno due angoli, mostra come si calcola in casi semplici, percorre i raffinamenti che la teoria ha aggiunto in settant’anni, e collega il tutto alle applicazioni in machine learning e nei sistemi di agenti.

Contesto

Il capitolo siede in un piccolo grafo: Cos’è un gioco in senso tecnico ha introdotto la forma normale, le strategie pure e miste, il payoff, e ha menzionato l’equilibrio di Nash come nozione di soluzione. Zero-sum, non-zero-sum ha trattato il teorema minimax di von Neumann, che è il caso particolare dell’equilibrio di Nash in giochi a somma zero a due giocatori — una storia che precede Nash di vent’anni e che lui generalizza.

I personaggi principali, in ordine di apparizione:

John Forbes Nash Jr. (matematico statunitense, 1928–2015): nella tesi di dottorato a Princeton del 1950 e nell’articolo del 1951 sugli Annals of Mathematics dimostra l’esistenza di un equilibrio in strategie miste per ogni gioco finito non cooperativo. Nobel per l’economia 1994.
Reinhard Selten (economista tedesco, 1930–2016): introduce nel 1965 il subgame perfect equilibrium e nel 1975 il trembling hand perfect equilibrium, raffinando Nash per filtrare equilibri patologici. Nobel 1994 con Nash e Harsanyi.
John Harsanyi (economista ungherese-statunitense, 1920–2000): sviluppa nel 1967 l’equilibrio bayesiano per giochi a informazione incompleta. Nobel 1994.
Robert Aumann (matematico israeliano, 1930): introduce nel 1974 il correlated equilibrium e lavora alla formalizzazione della razionalità comune. Nobel 2005.
John Maynard Smith (biologo evoluzionista britannico, 1920–2004) e George Price (1973): introducono in Nature l’evolutionary stable strategy, ponte tra teoria dei giochi e biologia evolutiva.
Constantinos Daskalakis (informatico greco-statunitense): con Goldberg e Papadimitriou nel 2006/2009 dimostra che calcolare un equilibrio di Nash è PPAD-completo, fissando un confine teorico alla scalabilità del concetto.

Sullo sfondo, due strumenti matematici che useremo come scatole nere: il teorema di punto fisso di Brouwer (Luitzen Brouwer, matematico olandese, 1881–1966; ogni mappa continua dal disco chiuso in se stesso ha un punto fisso) e la sua generalizzazione di Kakutani (Shizuo Kakutani, matematico giapponese, 1911–2004; lo stesso enunciato per correspondences a valori convessi).

Il contesto storico aiuta a capire perché Nash (1951) è stato un colpo. Prima di Nash, la teoria dei giochi era essenzialmente la teoria di von Neumann e Morgenstern, costruita attorno al teorema minimax di von Neumann del 1928 e codificata in Theory of Games and Economic Behavior del 1944. Funzionava bene per zero-sum a due giocatori (dove “soluzione” è ben definita: il valore minimax) e per giochi cooperativi (dove la soluzione è un’allocazione di payoff via “core” o stable sets). Ma per giochi non cooperativi a n giocatori non c’era una nozione generale di soluzione che funzionasse oltre casi speciali.

Nash, in una tesi di ventotto pagine consegnata a ventun anni, dà la nozione generale e prova che esiste sempre. Il prezzo da pagare è ammettere strategie miste e accontentarsi di una stabilità unilaterale invece che globale. Ma in cambio si ottiene un framework universale che oggi è ovunque — dall’economia industriale alla biologia evolutiva, dalla progettazione di aste al training di GAN.

L’intuizione, due angoli

Primo angolo: nessuno ha rimorsi unilaterali

Immagina la fine di una partita: ogni giocatore ha scelto la propria strategia, i payoff sono distribuiti. Adesso poniamo a ciascuno una domanda: guardando con il senno di poi, ma assumendo che le scelte degli altri rimangano fisse, vorresti aver giocato diversamente? Se la risposta di tutti è “no”, il profilo di strategie è un equilibrio di Nash.

L’enfasi è su “unilaterale”. Nash non chiede che il profilo sia ottimo collettivamente, né che sia Pareto-efficiente, né che nessuno preferisca un mondo in cui tutti cambiano insieme. Chiede solo che nessuno da solo trovi conveniente cambiare. È una nozione di stabilità minima, locale rispetto alle deviazioni individuali. Per questo gli equilibri possono essere brutti — il dilemma del prigioniero ha equilibrio (D, D) anche se entrambi preferirebbero (C, C) — ma sono difficili da scardinare con scelte solitarie.

Secondo angolo: il punto fisso del best response

Pensiamo al ragionamento di un giocatore razionale. Date le sue credenze sulle strategie altrui, sceglie la best response: la strategia che massimizza il proprio payoff atteso. Se modellizziamo il best response come una funzione (più precisamente una correspondence: può tornare un insieme di strategie ugualmente ottimali), abbiamo una mappa che porta profili di strategie in profili di strategie. Un equilibrio di Nash è un profilo che è best response a se stesso — un punto fisso di questa mappa.

Questo riformula la stabilità in termini operativi: se ogni giocatore reagisce ottimalmente alle aspettative sugli altri, e queste aspettative sono confermate, niente cambia. Le aspettative devono essere autoconfermanti.

ANALOGIA: Nash è il “punto fisso della razionalità reciproca”. È una metafora utile ma da non confondere con un teorema: la prova di esistenza userà davvero un teorema di punto fisso, ma il senso epistemico (“è quello che giocatori veramente razionali farebbero”) richiede ipotesi aggiuntive di common knowledge che discuteremo più avanti.

Terzo angolo (per chi pensa per dinamiche): l’attrattore del best response

Un terzo modo di vedere NE, utile per chi viene da deep learning, è come stato stazionario di una dinamica. Immagina che a ogni istante un giocatore reagisca al profilo corrente passando alla propria best response. Se la dinamica si stabilizza — niente più cambiamenti — il punto in cui si stabilizza è un NE per costruzione. Il viceversa non è vero in generale: NE è punto fisso del best response, ma non tutti i punti fissi sono attrattori della dinamica del best response (alcuni sono instabili).

Questa lente è quella più vicina al training di GAN o al self-play. Il “gradient descent simultaneo” di GAN è una versione differenziabile e sincrona del best-response dynamics; chiedersi se converga a NE significa chiedersi se NE sia un attrattore stabile di una dinamica continua. La risposta in generale è no — anche in giochi semplici come bilinear zero-sum, gradient descent simultaneo cicla intorno al NE invece di convergere (Mertikopoulos et al. 2018; Daskalakis-Ilyas-Syrgkanis-Zampetakis 2018). Servono modifiche (extra-gradient, optimistic mirror descent) per ottenere convergenza al NE.

La meccanica

Definizione formale

Sia $G = (N, (S_i)_{i in N}, (u_i)_{i in N})$ un gioco in forma normale: $N = {1, ..., n}$ giocatori, $S_i$ lo spazio delle strategie pure del giocatore i, $u_i: S_1 x ... x S_n -> R$ la sua funzione di utilità.

Un profilo $s* = (s_1*, ..., s_n*)$ è equilibrio di Nash in strategie pure se per ogni i e per ogni $s_i in S_i$ :

u_i(s_i*, s_{-i}) >= u_i(s_i, s_{-i})

dove $s_{-i}* = (s_1*, ..., s_{i-1}*, s_{i+1}*, ..., s_n*)$ è il profilo degli altri.

In strategie miste ogni $σ_i$ è una distribuzione di probabilità su $S_i$ . L’utilità è il valore atteso sotto il prodotto delle distribuzioni (assunzione di indipendenza). La definizione di NE è la stessa: nessuno migliora deviando unilateralmente a qualunque altra distribuzione, o equivalentemente a qualunque pura nel supporto.

Una caratterizzazione utile: in un NE in miste, ogni giocatore è indifferente tra tutte le pure nel proprio supporto, e queste hanno payoff atteso non inferiore a quelle fuori dal supporto. Se così non fosse, sposterebbe massa dalla peggio alla meglio.

Best response

La best response del giocatore i al profilo avversario $σ_{-i}$ è:

BR_i(σ_{-i}) = argmax_{σ_i} u_i(σ_i, σ_{-i})

È in generale un insieme. Un profilo $σ*$ è NE se e solo se $σ_i* in BR_i(σ_{-i}*)$ per ogni $i$ . Definendo la correspondence congiunta $BR(σ) = BR_1(σ_{-1}) x ... x BR_n(σ_{-n})$ , gli NE sono i punti fissi di $BR$ .

Esistenza: il teorema di Nash

TEOREMA (Nash 1951). Ogni gioco finito in forma normale ammette almeno un equilibrio di Nash in strategie miste.

L’idea della prova, senza algebra. Lo spazio delle strategie miste di $i$ è il simplesso $Δ_i$ di dimensione $|S_i| - 1$ : convesso, chiuso, limitato. Il prodotto $Δ = Δ_1 x ... x Δ_n$ è ancora convesso compatto. Nash costruisce una mappa continua $T: Δ -> Δ$ con la proprietà che i punti fissi di $T$ coincidono con gli NE. Per Brouwer, ogni mappa continua da un convesso compatto in se stesso ha un punto fisso. Quindi NE esiste.

La mappa di Nash è elegante. Sia $g_{i,k}(σ) = max(0, u_i(k, σ_{-i}) - u_i(σ))$ il guadagno (non negativo) di deviare dalla mista corrente alla pura k. Poniamo:

T(σ){i,k} = (σ{i,k} + g_{i,k}(σ)) / (1 + Σ_{k’} g_{i,k’}(σ))

Cioè: si aumenta la probabilità delle pure profittevoli e si rinormalizza. Un punto fisso richiede $g_{i,k}(σ*) = 0$ per ogni i, k: nessuna pura paga la deviazione. Questo è esattamente NE.

CLASSE DI AFFERMAZIONE: TEOREMA, prova matematica completa (rinviata a Nash 1951 per i dettagli; idea sopra).

Nota la connessione con Zero-sum, non-zero-sum: in zero-sum a due giocatori NE coincide col valore minimax di von Neumann (1928). EQUIVALENZA, dimostrabile: si verifica che le strategie maximin/minimax soddisfano la condizione di Nash, e viceversa. Nash quindi generalizza minimax a n giocatori e a giochi non-zero-sum.

Conseguenze immediate della definizione

Prima di andare al calcolo, alcune osservazioni che cadono direttamente dalla definizione e che vale la pena interiorizzare.

Equilibri in pure non sempre esistono. Matching pennies è il controesempio canonico: ogni cella ha un giocatore che vuole cambiare. Solo l’estensione alle miste salva l’esistenza universale.

NE non implica unicità. Stag hunt ne ha tre, come abbiamo visto. Battle of the sexes (coordinazione asimmetrica) ne ha tre. Giochi con simmetrie spesso hanno NE simmetrici e asimmetrici.

Strategie dominate non compaiono mai con probabilità positiva in un NE. Una strategia $s_i$ è strettamente dominata se esiste $s_i'$ tale che $u_i(s_i', s_{-i}) > u_i(s_i, s_{-i})$ per ogni $s_{-i}$ . In NE in miste, $s_i$ non può avere massa: spostarla su $s_i'$ aumenterebbe il payoff. Questo giustifica la procedura di iterated elimination of strictly dominated strategies: ridurre il gioco eliminando dominanze finché possibile, prima di calcolare NE.

La dipendenza è solo dal payoff ordinale per pure, ma non per miste. Trasformazioni affini positive di $u_i$ (positive linear) preservano NE in miste. Trasformazioni monotone non lineari preservano solo NE in pure. È il motivo per cui in molti problemi serve cardinalità del payoff, non solo ordinalità.

Calcolo

Sapere che NE esiste non basta: vogliamo trovarlo. Qui la storia si complica.

Bimatrix games (2 giocatori, payoff arbitrari): l’algoritmo classico è Lemke-Howson (Lemke e Howson 1964), un cammino combinatorio sui vertici di un politopo prodotto. Termina con un NE; nel caso peggiore richiede tempo esponenziale (Savani-von Stengel 2006).

Support enumeration: per ogni coppia di supporti possibili $(T_1, T_2)$ con $T_i ⊆ S_i$ , si cercano miste $σ_i$ con supporto $T_i$ tali che i sia indifferente tra le pure in $T_i$ e queste paghino almeno quanto le pure in $S_i \ T_i$ . Sistema lineare per ogni coppia di supporti: $2^{|S_1|} · 2^{|S_2|}$ coppie, ciascuna $O(poly)$ . Esponenziale ma efficace per giochi piccoli.

Best-response dynamics: parti da un profilo arbitrario, fai update sequenziali in cui ogni giocatore migra al best response al profilo corrente. Pseudocodice:

init s = (s_1, ..., s_n) arbitrario
ripeti:
    cambiato = False
    per ogni i:
        s_i' = argmax_{s_i in S_i} u_i(s_i, s_{-i})
        se u_i(s_i', s_{-i}) > u_i(s):
            s_i = s_i'
            cambiato = True
finché not cambiato

Termina solo se il gioco ha la finite improvement property (giochi di potenziale: Monderer-Shapley 1996). In generale può ciclare.

Fictitious play (George Brown, matematico USA, 1951): ogni giocatore tiene traccia delle frequenze empiriche delle pure giocate dagli avversari nel passato e gioca best response a quelle frequenze.

init storico vuoto
per t = 1, 2, ...:
    per ogni i: σ_{-i}_emp = frequenza empirica delle pure di -i fino a t-1
    per ogni i: a_i^t = BR_i(σ_{-i}_emp)
    aggiungi a_i^t allo storico

Robinson (1951) prova che la frequenza empirica congiunta converge a un NE in zero-sum a due giocatori. Monderer-Shapley estendono ai giochi di potenziale. Non converge in generale (Shapley 1964 ha un controesempio).

Multiplicative weights / Hedge è la versione “regret-based”: ogni giocatore mantiene pesi sulle pure, li aggiorna proporzionalmente all’esponenziale del payoff atteso, gioca proporzionalmente ai pesi. È no-regret: la differenza tra payoff cumulativo e quello della miglior pura fissa cresce sublinearmente. In zero-sum a due giocatori, le miste medie convergono a NE a tasso $O(sqrt(log K / T))$ .

init w_{i,k} = 1 per ogni i, k
per t = 1, ..., T:
    σ_i^t = w_i / Σ_k w_{i,k}     # mista corrente
    ogni i gioca σ_i^t
    osserva u_{i,k}^t = u_i(k, σ_{-i}^t) per ogni pura k
    w_{i,k} *= exp(η · u_{i,k}^t)
restituisci media temporale (1/T) Σ_t σ^t

Il tasso $O(sqrt(log K / T))$ è il classico bound del regret di Hedge (Freund-Schapire 1997, generalizzato a giochi). Per giochi di dimensione moderata è efficacissimo.

Lemma di Sion / minimax computazionale. Per zero-sum a due giocatori, calcolare NE è equivalente a risolvere un programma lineare: un giocatore minimizza il payoff massimo che l’avversario può ottenere. Questo è polinomiale (Khachiyan 1979 con ellipsoid; Karmarkar 1984 interior point; in pratica simplex). È il caso “facile”. Per non-zero-sum o più di due giocatori non si riduce a LP, e arriva PPAD.

Complessità

TEOREMA (Daskalakis-Goldberg-Papadimitriou 2009; Chen-Deng 2006 per il caso 2-giocatori). Calcolare un equilibrio di Nash è PPAD-completo, anche per giochi a 2 giocatori a payoff razionali.

PPAD (“Polynomial Parity Argument, Directed”) è una classe di complessità definita da Papadimitriou (1994) per problemi la cui esistenza è garantita da un argomento di parità su un grafo diretto. Il suo problema canonico è “End-of-the-Line”: dato un grafo diretto in cui ogni nodo ha al più un predecessore e un successore, trovare un nodo terminale diverso da una sorgente data. È la versione computazionale del lemma di Sperner, equivalente a Brouwer. Si congettura che PPAD non sia contenuto in P; quindi nessun algoritmo polinomiale generale per NE è atteso.

Conseguenze pratiche: per giochi con tante azioni o tanti giocatori, calcolare NE esattamente è fuori portata. Si usano allora approssimazioni (ε-Nash: nessuno guadagna più di ε deviando), tecniche specifiche per sottoclassi (zero-sum, potenziali, succinti), o si rinuncia a NE e si punta a correlated equilibrium (calcolabile in tempo polinomiale via programmazione lineare).

Raffinamenti

NE puro è permissivo: ammette equilibri basati su minacce non credibili. Il centipede game (Rosenthal 1981) lo mostra brutalmente. Due giocatori si alternano e a ogni turno possono “fermarsi” (e prendere un payoff) o “continuare” (lasciando decidere all’altro). Il payoff cresce con i turni ma chi si ferma per primo guadagna di più dell’avversario al turno corrente. Backward induction dice: l’ultimo giocatore si fermerà per massimizzare; quindi il penultimo si ferma; e così via. Unico NE subgame perfect: fermarsi al primo turno. NE non subgame perfect: “se mai arriviamo al turno 8 mi fermerò minacciando ritorsione” — minaccia non credibile perché contraddice la razionalità nel sottogioco.

I principali raffinamenti:

Subgame perfect equilibrium (SPE), Selten 1965. In giochi in forma estesa, il profilo deve essere NE in ogni sottogioco proprio. Si calcola con backward induction nei giochi finiti a informazione perfetta. SPE elimina le minacce non credibili.

Trembling hand perfect equilibrium, Selten 1975. Un NE è THP se è limite di NE di giochi perturbati in cui ogni pura è giocata con probabilità almeno ε > 0. Cattura robustezza a piccoli errori; filtra strategie debolmente dominate.

Bayesian Nash equilibrium, Harsanyi 1967. Per giochi a informazione incompleta, ogni giocatore ha un “tipo” privato estratto da una distribuzione comunemente nota. Una strategia mappa tipi in azioni; è BNE se ogni tipo gioca BR in valore atteso sui tipi avversari. Fondamento di teoria delle aste e mechanism design.

Evolutionary stable strategy (ESS), Maynard Smith e Price 1973. Una strategia simmetrica $σ*$ è ESS se in una popolazione che la gioca, una mutazione rara $σ'$ ha payoff strettamente inferiore. Ogni ESS è NE simmetrico, non viceversa. Spiega la stabilità di equilibri sotto dinamiche replicatori — per esempio nel gioco “hawk-dove” di Maynard Smith.

Correlated equilibrium, Aumann 1974. Si introduce un mediatore pubblico che estrae un profilo s da una distribuzione $μ$ e raccomanda privatamente a ciascun giocatore la propria componente $s_i$ . $μ$ è correlated equilibrium se obbedire al segnale è BR rispetto al condizionato sulle raccomandazioni proprie. L’insieme dei correlated equilibria contiene l’inviluppo convesso degli NE, è poliedrale, calcolabile in tempo polinomiale via LP. È la soluzione naturale verso cui converge il no-regret learning (Hart-Mas-Colell 2000).

Un esempio concreto di correlated equilibrium che non è inviluppo di NE: il “battle of the sexes” con un mediatore che lancia una moneta pubblica e raccomanda di andare entrambi all’opera o entrambi alla partita. Aspettato (2.5, 2.5) — meglio del NE misto (2/3, 2/3) con payoff atteso (2/3, 2/3). Il segnale pubblico rompe la simmetria che impediva la coordinazione.

CLASSE DI AFFERMAZIONE: i raffinamenti sopra sono FILIAZIONI documentate dei NE: ogni autore cita Nash e propone un restringimento esplicito.

Esempi

Esempio 0 (riscaldamento): stag hunt e i due NE puri

Per fissare la definizione, partiamo da un esempio piccolissimo. Due cacciatori decidono indipendentemente se cacciare un cervo (Stag, richiede cooperazione) o una lepre (Hare, riesce da soli). Payoff:

              P2: Stag      P2: Hare
P1: Stag    (4, 4)        (0, 3)
P1: Hare    (3, 0)        (3, 3)

Verifichiamo (Stag, Stag). P1 fa 4; deviando a Hare farebbe 3, quindi non devia. Per simmetria P2 idem. È NE.

Verifichiamo (Hare, Hare). P1 fa 3; deviando a Stag, dato che P2 gioca Hare, farebbe 0. Non devia. NE.

Verifichiamo (Stag, Hare). P1 fa 0; deviando a Hare farebbe 3. Devia. Non è NE.

Esiste anche un NE in miste: imponendo l’indifferenza di P1, sia q la probabilità di Stag di P2, allora 4q + 0(1-q) = 3q + 3(1-q), da cui q = 3/4. Per simmetria p = 3/4. Tre equilibri in totale, quindi: (Stag,Stag), (Hare,Hare), e ((3/4,1/4), (3/4,1/4)).

Lo stag hunt mostra subito due fatti scomodi: gli NE possono essere multipli, e la teoria di Nash da sola non dice quale scegliere. (Stag,Stag) è Pareto-dominante; (Hare,Hare) è risk-dominante (sicuro contro avversario incerto). Il NE misto è instabile sotto la maggior parte delle dinamiche di learning. Quale prevarrà nella realtà dipende da fattori extra-teoria: focal points, comunicazione precedente, convenzioni culturali.

Esempio 1: matching pennies a mano (numerico)

Due giocatori scelgono simultaneamente testa (H) o croce (T). Player 1 vince se coincidono, perde se discordano. Matrice:

              P2: H        P2: T
P1: H       (+1, -1)    (-1, +1)
P1: T       (-1, +1)    (+1, -1)

Cerchiamo NE in pure: in ogni cella un giocatore è insoddisfatto e vuole cambiare. (H,H): P2 vuole T. (H,T): P1 vuole T. (T,T): P2 vuole H. (T,H): P1 vuole H. Nessun NE in pure.

NE in miste con la caratterizzazione di indifferenza. Sia p la probabilità con cui P1 gioca H, q quella con cui P2 gioca H. Per essere indifferente, P1 deve avere lo stesso payoff atteso giocando H o T:

E[u_1 | H] = q · 1 + (1-q) · (-1) = 2q - 1 E[u_1 | T] = q · (-1) + (1-q) · 1 = 1 - 2q

Indifferenza: $2q - 1 = 1 - 2q$ , quindi $q = 1/2$ . Per simmetria (zero-sum simmetrico) $p = 1/2$ . Unico NE: $(σ_1, σ_2) = ((1/2, 1/2), (1/2, 1/2))$ . Valore atteso 0.

Esempio 2: fictitious play su rock-paper-scissors (codice)

Implementiamo fictitious play in numpy per verificare la convergenza a (1/3, 1/3, 1/3).

import numpy as np

# RPS: payoff matrix per P1; P2 ha la trasposta cambiata di segno
A = np.array([[ 0, -1,  1],
              [ 1,  0, -1],
              [-1,  1,  0]])

T = 5000
# storico delle pure giocate da ciascun giocatore
counts1 = np.zeros(3)
counts2 = np.zeros(3)

# init arbitrario
counts1[0] = 1
counts2[1] = 1

for t in range(T):
    # frequenza empirica avversaria
    f2 = counts2 / counts2.sum()
    f1 = counts1 / counts1.sum()
    # best response
    a1 = int(np.argmax(A @ f2))         # P1 max contro f2
    a2 = int(np.argmin(f1 @ A))         # P2 min contro f1 (zero-sum)
    counts1[a1] += 1
    counts2[a2] += 1

print(counts1 / counts1.sum())  # atteso: ~ [0.333, 0.333, 0.333]
print(counts2 / counts2.sum())

Eseguendolo con T = 5000 si vede la convergenza alla mista uniforme, anche se le frequenze oscillano (la dinamica non si stabilizza punto a punto, solo in media). Robinson (1951) garantisce questa convergenza per zero-sum a due giocatori; il tasso di convergenza è $O(1/sqrt(T))$ .

fictitious play on RPS: empirical frequencies of P1 over 5000 steps, three curves converging to 1/3

Esempio 3: GAN come ricerca di Nash misto (scenario reale)

In GAN (Goodfellow et al. 2014) si addestra un generatore $G_θ: Z -> X$ e un discriminatore $D_φ: X -> [0,1]$ . La loss è formulata come gioco minimax:

V(G, D) = E_{x ~ p_data}[log D(x)] + E_{z ~ p_z}[log(1 - D(G(z)))]

D massimizza $V$ , G minimizza $V$ . EQUIVALENZA argomentabile: con capacità infinite, l’unico NE di questo gioco è $p_g = p_data$ con $D(x) = 1/2$ ovunque; in quell’equilibrio G genera dalla distribuzione vera e D non distingue. Il training cerca proprio questo NE — nello spazio delle distribuzioni indotte dai parametri.

In pratica le cose si rompono in modi istruttivi:

Mode collapse: G concentra massa su poche modalità di $p_data$ ignorando il resto. Costituisce un NE locale degenere — D fa fatica a distinguere su quelle modalità — ma è lontano dal NE globale.
Oscillazioni: la dinamica simultanea del gradiente $θ ← θ - η ∇_θ V$ , $φ ← φ + η ∇_φ V$ può ciclare invece di convergere, esattamente come best-response dynamics in giochi non a potenziale.
Vanishing gradients del discriminatore: se D vince troppo bene, $log(1 - D(G(z)))$ satura e G non riceve segnale.

Wasserstein GAN (Arjovsky et al. 2017), spectral normalization, two time-scale update rule (TTUR, Heusel et al. 2017), R1 regularization (Mescheder et al. 2018) sono tutti tentativi di rendere la dinamica più stabile vicino al NE. Da una prospettiva di teoria dei giochi, sono modifiche che cambiano la struttura del gioco o la dinamica di learning per garantire convergenza.

GAN training: G loss and D loss oscillating around an unstable Nash equilibrium

Esempio 4 (bonus): il dilemma del prigioniero come benchmark di NE inefficiente

Per fissare la differenza tra NE e ottimo sociale, vale la pena percorrere a mano il dilemma del prigioniero. Due sospetti, interrogati separatamente, possono confessare (Defect, D) o tacere (Cooperate, C). Payoff (anni di galera, segno cambiato per renderli maximizzazione):

              P2: C       P2: D
P1: C       (3, 3)      (0, 5)
P1: D       (5, 0)      (1, 1)

Iterated dominance: per P1, D domina C (5 > 3 contro C, 1 > 0 contro D). Idem per P2. Quindi (D, D) è l’unico NE — anche prima di pensare a strategie miste. Eppure (C, C) Pareto-domina (D, D). Il NE è socialmente inefficiente.

Cosa cambia con ripetizione? Se il gioco si ripete un numero finito noto, backward induction collassa: nell’ultimo turno (D, D), quindi nel penultimo (D, D), e così via. Unico SPE: defect ogni turno. Se la ripetizione è infinita o il termine è stocastico, il folk theorem dice che molti payoff cooperativi sono sostenibili come NE con strategie come “tit-for-tat” (Axelrod 1984). Per LLM in setting ripetuti questa distinzione conta molto: un agente che gioca il prigioniero “una volta” deve defect; uno in interazione ripetuta indefinita può ragionevolmente cooperare.

Applicazioni pratiche

Cournot duopoly: NE in azione classica. Due imprese scelgono quantità prodotte $q_1, q_2 >= 0$ . Il prezzo di mercato è $P(q_1+q_2) = a - b(q_1+q_2)$ , costo marginale $c$ . Profitto $i$ : $π_i = (a - b(q_1+q_2) - c) q_i$ . Best response di P1: $dπ_1/dq_1 = a - b q_2 - 2 b q_1 - c = 0$ , da cui $q_1 = (a-c)/(2b) - q_2/2$ . Simmetricamente per P2. Sistema lineare: $q_1* = q_2* = (a-c)/(3b)$ . È l’NE di Cournot, esempio classico di equilibrio in giochi continui. Notare: produzione totale $2(a-c)/(3b)$ minore della produzione monopolistica $(a-c)/(2b)$ e maggiore della concorrenza perfetta $(a-c)/b$ solo nominalmente; in realtà concorrenza perfetta porta $q = (a-c)/b$ con prezzo $c$ . NE Cournot è “in mezzo”.

Self-play e AlphaZero. In zero-sum a informazione perfetta a due giocatori, il NE coincide con l’ottimo minimax. Self-play (DeepMind 2017) implementa una dinamica iterativa in cui due copie del modello giocano l’una contro l’altra, e i miglioramenti via Monte Carlo Tree Search e gradient descent sui parametri convergono — sotto ipotesi forti — verso una strategia che gioca al valore minimax. È la cornice teorica dietro AlphaGo, AlphaZero, MuZero. La convergenza rigorosa è dimostrata solo in setting tabular con rate decrescenti; in deep RL è empirica.

flowchart LR
    A[policy network theta_t] -->|partita self-play| B[traiettoria s_1, a_1, ... s_T]
    B --> C[target migliorati via MCTS]
    C --> D[update gradiente]
    D -->|theta_t+1| A
    D -.fixed point.-> E[Nash equilibrium / policy minimax-ottima]

Figura 5 — pipeline di self-play AlphaZero come ricerca di un fixed point che corrisponde al Nash del gioco simmetrico zero-sum, con MCTS che migliora i target della policy network

GAN e modelli generativi adversariali. Già discusso. Vale anche per varianti come adversarial training per robustezza (Goodfellow-Shlens-Szegedy 2015), dove il “gioco” è tra il classificatore e un attaccante che perturba l’input.

Multi-agent reinforcement learning. La cornice generale è il gioco stocastico (Shapley 1953): generalizzazione di MDP a più giocatori, dove la transizione e i reward dipendono dalle azioni congiunte. Una soluzione naturale è un NE markoviano: ogni giocatore gioca la propria policy ottimale data quella degli altri, in ogni stato. Calcolarlo è ancora più duro che NE in giochi a un singolo stage. Q-learning indipendente non converge in generale: ogni agente vede un ambiente non stazionario. Algoritmi che incorporano la struttura di gioco:

Nash-Q learning (Hu-Wellman 2003) sostituisce il max di Q-learning col valore di NE del gioco di stage; converge sotto ipotesi forti.
Counterfactual regret minimization (Zinkevich et al. 2007) applica regret matching al formato extensive con informazione imperfetta; alla base di Libratus e Pluribus, sistemi che hanno battuto top professionisti a no-limit Texas hold’em.
Policy space response oracles (PSRO, Lanctot et al. 2017) generalizza fictitious play a spazi di policy parametrizzate.

No-regret learning e correlated equilibrium. Approfondiamo perché è centrale. Il risultato di Hart-Mas-Colell (2000) è centrale: se ogni agente usa una procedura no-regret semplice (regret matching, Hedge, FTRL), le frequenze empiriche congiunte convergono all’insieme dei correlated equilibria. È il motivo per cui il regret matching è onnipresente in algorithmic game theory: è efficiente, decentralizzato, e converge a una nozione di soluzione che generalizza Nash.

Una procedura $A_i$ ha regret esterno sublineare se per ogni sequenza di payoff avversari, la differenza tra il payoff cumulativo della miglior pura fissa e il payoff effettivo cresce sublinearmente in $T$ . Hedge, regret matching, FTRL hanno questa proprietà con bound $O(sqrt(T log K))$ . Hart-Mas-Colell rafforzano a regret interno: per ogni coppia (j, k) di pure, il giocatore non rimpiange di non aver sostituito ogni occorrenza di j con k. Se ogni giocatore ha regret interno sublineare, la frequenza empirica converge ai correlated equilibria. È il risultato fondante dell’algorithmic game theory moderna.

Mechanism design. Hurwicz, Maskin, Myerson (Nobel 2007) progettano regole del gioco perché il NE risultante coincida con un obiettivo (efficienza, truthful revelation, massimizzazione delle entrate). Il revelation principle riduce ogni mechanism a uno truthful direct. Esempi: VCG (Vickrey-Clarke-Groves) auctions, Myerson optimal auction. Vedi mechanism design (in preparazione) per dettagli.

Agenti LLM in giochi. Akata et al. (2023) e altri studi recenti fanno giocare LLM in dilemma del prigioniero ripetuto, battle of the sexes, ultimatum game. ANALOGIA empirica: gli LLM si comportano “near-rationally” ma sistematicamente fuori dal NE — più cooperativi nel prigioniero, sensibili al framing, fortemente influenzati dal prompt. Sono giocatori euristici, non agenti razionali nel senso della teoria dei giochi. Questo apre domande aperte su come integrare priors di teoria dei giochi nel prompting o nel fine-tuning di agenti negoziali.

RLHF come ricerca di equilibrio. In RLHF il modello cerca una policy che massimizza la reward del reward model, vincolata a non discostarsi troppo dalla policy base via penalità KL. Si può vedere come gioco a due (modello vs reward model adversariale, Goodhart) il cui NE è un compromesso. Constitutional AI e RLAIF estendono il framework con altri “giocatori” (un costituzionalista, un critico).

Adversarial training per robustezza. Goodfellow-Shlens-Szegedy (2015) mostrano che reti neurali sono fragili a perturbazioni impercettibili. Madry et al. (2018) formulano la difesa come gioco minimax: il classificatore minimizza la loss massima su perturbazioni nell’ε-palla. NE di questo gioco sarebbe un classificatore robusto certificabile. In pratica si usano dinamiche Projected Gradient Descent — di nuovo, una ricerca approssimata di NE.

Aste e meccanismi. In un’asta sigillata al secondo prezzo (Vickrey 1961), bidare il proprio valore è strategia debolmente dominante e quindi NE. Nel primo prezzo, il NE bayesiano richiede di sotto-bidare in funzione del numero di partecipanti e della distribuzione dei valori. Algoritmi pratici di ad auctions (Google AdWords, Facebook Ads) sono progettati perché certi NE bayesiani implementino allocazioni desiderate.

Dove si rompe

Selezione tra equilibri multipli. Lo stag hunt ha tre NE: due in pure ((Stag,Stag) e (Hare,Hare)) e uno in miste. (Stag,Stag) è Pareto-dominante ma rischioso (richiede fiducia); (Hare,Hare) è safe ma inefficiente. La teoria di Nash da sola non dice quale sceglieranno i giocatori. Schelling (1960) introduce i focal points — equilibri salienti per ragioni culturali o contestuali. Harsanyi-Selten (1988) propongono una teoria della selezione assiomatica complessa, poco usata nella pratica. È un problema aperto.

PPAD-hardness. Calcolare NE è intrattabile nel caso peggiore (Daskalakis-Goldberg-Papadimitriou 2009). Per giochi con molti giocatori o molte azioni, non esistono algoritmi polinomiali generali. Si usano approssimazioni ε-NE, sottoclassi trattabili (zero-sum, potenziali, congestion), o si passa a correlated equilibrium che è LP.

Razionalità comune. NE assume non solo che ogni giocatore sia razionale, ma che lo sappia di tutti gli altri, che gli altri lo sappiano di lui, e così via — common knowledge of rationality. Aumann e Brandenburger (1995, Econometrica) hanno chiarito le condizioni epistemiche: è una richiesta forte. Setting con incertezza sulla razionalità degli altri (level-k thinking, cognitive hierarchy) producono predizioni diverse da NE.

Price of anarchy. Per quantificare quanto NE si discosta dall’ottimo sociale, Koutsoupias e Papadimitriou (1999) introducono il price of anarchy: rapporto tra costo sociale del peggior NE e costo dell’ottimo. In congestion games (Roughgarden 2005) è limitato (es. 4/3 per routing affine), il che giustifica decisioni decentralizzate. In altri giochi è illimitato. Concetto centrale per progettare sistemi distribuiti dove non si può imporre coordinazione.

NE non è Pareto efficiente. Il dilemma del prigioniero è il caso paradigmatico: l’unico NE è (D,D), Pareto-dominato da (C,C). Questo non è un bug della teoria — riflette un fatto strutturale dell’incentivo individuale — ma significa che NE non si può vendere come “soluzione socialmente desiderabile”. In pubblici beni, tragedia dei commons, free-riding sono tutte istanze.

Comportamento umano fuori da NE. Camerer (Behavioral Game Theory, 2003) raccoglie evidenza sperimentale che gli umani in laboratorio si discostano sistematicamente: cooperano nel prigioniero finito ripetuto, si fermano dopo nel centipede, rifiutano offerte iniquie nell’ultimatum (dove l’unico SPE accetta qualsiasi offerta positiva). Modelli alternativi: quantal response equilibrium (McKelvey-Palfrey 1995), level-k (Stahl-Wilson 1994; Nagel 1995), cognitive hierarchy (Camerer-Ho-Chong 2004). Per progettare agenti che interagiscono con umani, NE da solo è insufficiente.

GAN training non converge a Nash. Nonostante la formulazione minimax, la dinamica simultanea del gradiente raramente converge al NE globale. Mode collapse, oscillazioni, convergenza a NE locali degeneri sono la norma. La letteratura su “Nash equilibrium in deep learning games” (Mescheder, Mertikopoulos, Daskalakis stesso) studia condizioni sufficienti sulla geometria della loss perché la dinamica converga.

Minacce non credibili. NE puro ammette equilibri irrealistici basati su minacce che chi le pronuncia non vorrà mai eseguire. Senza raffinamenti come SPE, NE prevede equilibri che fanno ridere — il “centipede non-equilibrium” è il caso scolastico. In giochi sequenziali realistici, va sempre richiesto almeno SPE.

Agenti LLM non sono giocatori razionali. Già citato: gli LLM si comportano euristicamente, con bias che dipendono da come è formulato il prompt. Per usare la teoria dei giochi come framework per agenti LLM, occorre o (a) allineare l’agente al NE via fine-tuning specifico, o (b) accettare che il modello descrive un sistema “near-rational” e usare predizioni più lasche.

Equilibri instabili sotto perturbazione. Non tutti gli NE sono ugualmente “robusti”. Il NE in miste di stag hunt si rompe alla minima perturbazione: appena uno crede che l’altro ha probabilità un po’ diversa da 3/4 di Stag, ha incentivo a passare a una pura. NE puri come (Hare,Hare) sono invece strict: piccole perturbazioni nelle credenze non li rompono. La distinzione tra equilibri strict e non-strict è centrale in dinamiche evolutive: solo gli strict possono essere ESS.

Coordinazione su equilibri “stupidi”. In presenza di NE multipli, la storia mostra che spesso ci si coordina su equilibri non Pareto-ottimali per ragioni storiche (path dependence). La tastiera QWERTY, lo standard VHS contro Betamax, le convenzioni di guida a destra/sinistra sono casi di NE selezionati per accidenti storici, non per ottimalità. Il framework Nash da solo non li distingue.

Il problema del calcolo approssimato. Anche ε-Nash con ε polinomiale è PPAD-completo (Chen-Deng-Teng 2009). Solo per ε costante esistono algoritmi PTAS sotto certe condizioni (Lipton-Markakis-Mehta 2003: supporti piccoli). In pratica significa che molti algoritmi di “approssimazione di NE” che vediamo nei paper di MARL stanno approssimando una nozione più debole — ε-NE per ε non garantito piccolo, o NE locali, o correlated equilibrium.

Polish: tre confusioni comuni

Tre errori che si vedono spesso nella letteratura applicata e che vale la pena marcare.

Confusione 1: NE come ottimo sociale. NE è stabilità unilaterale, non efficienza collettiva. Quando si dice “il sistema converge al Nash equilibrium”, non si sta dicendo che convergerà a un buon equilibrio — solo che convergerà a uno stabile. Verifica sempre il price of anarchy o il payoff sociale dell’equilibrio.

Confusione 2: NE puro vs misto. Molti paper di MARL parlano di “Nash equilibrium” senza specificare se in pure o miste. La differenza è enorme: in pure può non esistere, in miste esiste sempre ma può richiedere randomizzazione esplicita. Per agenti deterministici, NE puro è l’unico raggiungibile direttamente.

Confusione 3: NE come predizione comportamentale. NE descrive cosa farebbero giocatori razionali con common knowledge. Non descrive necessariamente cosa farà un sistema reale, specialmente se i giocatori sono LLM, reti neurali, o umani. Usa NE come bersaglio normativo, non come modello descrittivo, a meno di evidenza empirica specifica.

Collegamenti

Cos’è un gioco in senso tecnico: definisce forma normale, strategie, payoff. Prerequisito.
Zero-sum, non-zero-sum: teorema minimax come caso particolare di NE in zero-sum 2-giocatori.
Discesa del gradiente: la dinamica che approssima NE in GAN e adversarial training; i suoi modi di fallire (oscillazioni, plateau) si traducono in fallimenti di convergenza al NE.
Bayes base: la distribuzione sui tipi avversari in BNE è una posterior bayesiana; il ragionamento epistemico in NE è bayesiano.
self-play (in preparazione): il loop AlphaZero come implementazione di una dinamica che converge a NE in zero-sum.
gan (in preparazione): training adversariale come ricerca di Nash misto e perché spesso fallisce.
multi-agent (in preparazione): MARL e algoritmi che incorporano la struttura di gioco per convergere a NE o correlated equilibrium.
meccanismi-aste (in preparazione): mechanism design come progettare la regola perché il NE coincida con l’obiettivo.
dilemma-prigioniero (in preparazione): l’esempio canonico di NE Pareto-dominato.
rlhf-ppo (in preparazione): RLHF visto come gioco modello-reward.
adversarial-examples (in preparazione): adversarial training come gioco minimax tra classificatore e attaccante.
mcts (in preparazione): Monte Carlo Tree Search come strumento per implementare ricerca di NE in giochi di larga scala (AlphaZero).
equazione-bellman (in preparazione): l’equivalente “single-agent” di NE in MDP; capire le differenze chiarisce perché MARL è dura.
counterfactual-regret (in preparazione): CFR come no-regret learning in giochi extensive con informazione imperfetta.

Una nota sulla razionalità

Vale la pena chiudere con una riflessione sul significato di NE come predizione comportamentale. La teoria classica dice: se due agenti razionali con common knowledge of rationality giocano un gioco, il risultato sarà un NE. Empiricamente, gli agenti razionali “puri” sono rari. Gli umani hanno bias, gli LLM hanno priors di training, le reti neurali in adversarial training hanno induttive biases architetturali.

Eppure NE rimane utile come bersaglio normativo: ci dice cosa giocatori che volessero essere razionali farebbero. Per progettare meccanismi (aste, market design, RLHF), partire da NE è il punto di partenza giusto, anche se poi va aggiustato. Per analizzare sistemi multi-agente, NE è il primo modello da provare. Per training adversariale, NE è ciò che cerchiamo anche quando non lo raggiungiamo.

ANALOGIA finale: NE sta alla teoria dei giochi come la massimizzazione della likelihood sta alla statistica frequentista. Non è l’unico criterio possibile, non è sempre raggiungibile in pratica, può portare a risultati controintuitivi. Ma è il punto di riferimento da cui tutto il resto si misura. Conoscerne il funzionamento e i limiti è prerequisito per ogni serio lavoro su agenti che interagiscono.

Per andare oltre

Nash, J. F. (1951). “Non-cooperative Games”. Annals of Mathematics, 54: 286–295. La fonte primaria. Quattordici pagine, leggibili.
Osborne, M. J. e Rubinstein, A. (1994). A Course in Game Theory. MIT Press. Manuale standard rigoroso, copertura completa di NE e raffinamenti.
Shoham, Y. e Leyton-Brown, K. (2008). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge UP. Disponibile gratis online; ponte tra teoria dei giochi e computer science con algoritmi NE espliciti.
Daskalakis, C., Goldberg, P. W., Papadimitriou, C. H. (2009). “The Complexity of Computing a Nash Equilibrium”. SIAM J. Comput., 39(1): 195–259. Per chi vuole capire PPAD-completezza nel dettaglio.
Hart, S. e Mas-Colell, A. (2000). “A Simple Adaptive Procedure Leading to Correlated Equilibrium”. Econometrica, 68(5): 1127–1150. Il paper che lega no-regret learning a correlated equilibrium; fondamentale per chi lavora su MARL.
Camerer, C. F. (2003). Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press. La critica empirica di NE come predizione del comportamento umano. Letture obbligatoria per chi progetta agenti che interagiscono con persone.
Roughgarden, T. (2016). Twenty Lectures on Algorithmic Game Theory. Cambridge UP. Compatta, leggibile, copre price of anarchy, mechanism design, no-regret learning con rigore ma senza pesantezza.
Mertikopoulos, P. e Sandholm, W. (2018). “Riemannian game dynamics”. Journal of Economic Theory. Per chi vuole capire convergenza al NE nelle dinamiche continue, rilevante per GAN e adversarial training.
Lanctot, M. et al. (2017). “A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning”. NeurIPS. PSRO, il framework moderno per MARL ispirato a fictitious play.
Goodfellow, I. et al. (2014). “Generative Adversarial Nets”. NIPS. Il paper fondante delle GAN, leggibile in un pomeriggio, importante per vedere come NE viene invocato in deep learning.
Aumann, R. J. (1987). “Correlated Equilibrium as an Expression of Bayesian Rationality”. Econometrica. La giustificazione epistemica di correlated equilibrium come naturale rispetto a NE quando si modella esplicitamente la conoscenza.
Daskalakis, C., Ilyas, A., Syrgkanis, V., Zampetakis, M. (2018). “Training GANs with Optimism”. ICLR. Per chi vuole capire come modificare la dinamica del gradiente in GAN per ottenere convergenza dimostrabile a NE.
Akata, E. et al. (2023). “Playing repeated games with Large Language Models”. arXiv:2305.16867. Studio empirico su come LLM giocano dilemmi classici della teoria dei giochi.

Buona lettura.