Evolutionary game theory: replicator dynamics ed ESS

Cosa succede alla teoria dei giochi quando i giocatori non scelgono niente — quando le strategie sono cablate e l’unica cosa che cambia è quante copie di sé stesse riescono a produrre.

Perché questo capitolo

La teoria dei giochi che hai visto finora ha un’assunzione nascosta così profonda da passare inosservata: che i giocatori siano razionali. Un giocatore razionale conosce le regole, conosce i payoff, sa calcolare la mossa migliore, e assume che anche l’avversario faccia lo stesso. Su questa assunzione poggiano l’equilibrio di Nash, il minimax, l’analisi del dilemma del prigioniero. Funziona benissimo per un economista o un giocatore di scacchi.

Non funziona per un cervo. Due cervi maschi che si contendono un harem non calcolano un equilibrio di Nash. Nascono con una strategia comportamentale scritta nei geni — quanto spingersi, quando ritirarsi — e quella strategia o si diffonde nella popolazione delle generazioni successive o si estingue, a seconda di quanti figli il cervo riesce a lasciare. Nessuno deliberava niente. Eppure le popolazioni di animali raggiungono configurazioni stabili che assomigliano in modo sospetto agli equilibri della teoria dei giochi.

Questo capitolo racconta come la teoria dei giochi sopravvive alla rimozione della razionalità. La risposta — la evolutionary game theory — non è un addolcimento della teoria classica: è una sua riformulazione più robusta. Al posto di un agente che sceglie, c’è una popolazione di strategie che competono; al posto di “quale mossa è ottima”, la domanda diventa “quali strategie sopravvivono e si diffondono”.

Da questa riformulazione escono due strumenti. Il primo è la strategia evolutivamente stabile (ESS), una strategia che una popolazione non può essere costretta ad abbandonare da un’invasione di mutanti rari. Il secondo sono le replicator dynamics, l’equazione che descrive come le frequenze delle strategie evolvono nel tempo.

E qui c’è il colpo di scena per chi costruisce sistemi AI: quell’equazione, scoperta dai biologi negli anni ‘70, è la stessa matematica che governa il self-play di AlphaGo, il population-based training, e — in forma a tempo continuo — algoritmi di apprendimento come il multiplicative weights update. Chi capisce le replicator dynamics ha in mano una lente per leggere un’intera famiglia di metodi di machine learning.

C’è anche un guadagno concettuale che precede ogni applicazione. La teoria classica dei giochi fornisce concetti di soluzione — l’equilibrio di Nash su tutti — ma lascia aperta una domanda scomoda: dato un gioco con molti equilibri, quale di questi verrà effettivamente osservato? E come ci si arriva, se i giocatori non sono calcolatori perfetti?

La teoria evolutiva risponde sostituendo alla domanda “qual è l’equilibrio” la domanda “come si muove il sistema”. Una volta che hai un’equazione del moto, l’equilibrio non è più qualcosa da postulare: è qualcosa che emerge, o non emerge, dalla dinamica. Questo spostamento — da concetti statici a sistemi dinamici — è lo stesso che si incontra, in forme diverse, nella teoria del controllo, nella cibernetica e in ogni trattazione di sistemi che cambiano nel tempo.

Contesto

L’idea che la selezione naturale possa essere descritta come un gioco non nasce con un colpo di genio isolato. Ha un precursore preciso. Nel 1930 Ronald Aylmer Fisher (statistico e biologo britannico, 1890-1962, uno dei fondatori della genetica delle popolazioni) pubblica The Genetical Theory of Natural Selection, dove spiega un fatto che a prima vista sembra arbitrario: perché nella maggior parte delle specie il rapporto tra i sessi alla nascita è circa 1:1.

L’argomento di Fisher è già, in tutto tranne il nome, teoria dei giochi evolutiva. Se i maschi fossero rari, ogni maschio avrebbe in media più accoppiamenti, quindi i genitori che producono figli maschi lascerebbero più nipoti, quindi il sesso raro sarebbe sempre favorito — finché il vantaggio sparisce e si torna a 1:1. La “mossa migliore” (fare figli del sesso raro) dipende da cosa fa il resto della popolazione. È un equilibrio di frequenza-dipendenza. Manca solo il vocabolario.

Il vocabolario arriva nel 1973. John Maynard Smith (biologo evoluzionista britannico, 1920-2004, ingegnere aeronautico di formazione passato alla biologia dopo la guerra) e George R. Price (chimico e genetista statunitense, 1922-1975, figura tanto geniale quanto tormentata) pubblicano su Nature un articolo di poche pagine intitolato The Logic of Animal Conflict (Nature 246, 1973, pp. 15-18).

La domanda di partenza è concreta e antica: perché gli animali, nei conflitti contro membri della loro stessa specie, raramente usano le armi più letali? I cervi si spingono con i palchi invece di trafiggersi i fianchi. I serpenti a sonagli lottano corpo a corpo senza mai mordersi. La spiegazione corrente all’epoca era la selezione di gruppo: una specie i cui membri si massacrano a vicenda si estingue, quindi la natura seleziona la moderazione “per il bene della specie”.

Maynard Smith e Price demoliscono questa spiegazione mostrando che non serve. La moderazione può essere stabile a livello del singolo individuo, senza alcun bene collettivo invocato. La loro arma è un modello formale — il gioco Hawk-Dove, che vedremo tra poco — e un concetto nuovo: la strategia evolutivamente stabile. Da quel paper nasce un’intera disciplina. Maynard Smith la sistematizza nel 1982 nel libro Evolution and the Theory of Games (Cambridge University Press), il testo fondativo.

Una nota sulla collaborazione, perché la storia dietro il paper del 1973 è insolita. George Price era arrivato all’evoluzione da outsider — chimico, giornalista scientifico, senza formazione biologica — e aveva sviluppato per conto suo una formula generale che descrive come cambia una caratteristica media in una popolazione sotto selezione, oggi nota come equazione di Price.

Maynard Smith, che lavorava all’idea della stabilità delle strategie, riconobbe il valore del lavoro di Price, lo cercò, e i due unirono le due intuizioni in un solo articolo. Price stava intanto attraversando una crisi personale e religiosa profonda; morì nel 1975, due anni dopo il paper. La teoria dei giochi evolutiva nasce così dall’incontro tra un biologo di mestiere e un dilettante geniale — un dettaglio che vale la pena ricordare quando la disciplina sembra una costruzione astratta calata dall’alto.

Hawk-Dove non è l’unico gioco del paper. Maynard Smith introduce anche la war of attrition, la “guerra di logoramento”: due contendenti per una risorsa si fissano negli occhi e aspettano, e vince chi resiste più a lungo, pagando però un costo proporzionale al tempo speso. È un gioco con un continuo di strategie possibili — ogni possibile durata di attesa è una strategia — e la sua ESS non è una durata fissa ma una distribuzione di probabilità sulle durate.

Se tutti aspettassero esattamente lo stesso tempo, un mutante che aspetta un istante in più vincerebbe sempre; quindi nessuna durata pura è stabile. La war of attrition mostra che le ESS miste non sono una stranezza del caso a due strategie: emergono ogni volta che essere prevedibili è uno svantaggio.

Manca ancora un pezzo: l’equazione che descrive la dinamica, cioè come le frequenze delle strategie cambiano istante per istante. La forniscono nel 1978 Peter Taylor e Leo Jonker (matematici, in un articolo su Mathematical Biosciences) e, indipendentemente, E.C. Zeeman nel 1979.

Il nome con cui la conosciamo — replicator equation — lo coniano Peter Schuster e Karl Sigmund nel 1983, notando che la stessa equazione descrive qualunque cosa faccia copie di sé stessa: molecole autocatalitiche, geni, strategie comportamentali, idee. Il testo di riferimento moderno è Evolutionary Games and Population Dynamics di Josef Hofbauer e Karl Sigmund (Cambridge University Press, 1998).

Da lì la teoria dei giochi evolutiva esce dalla biologia e si dirama. L’economia evolutiva — il libro Evolutionary Game Theory di Jörgen Weibull (MIT Press, 1995) ne è il riferimento — la usa per modellare come le convenzioni di mercato si stabilizzano senza che nessun attore le imponga. La teoria dell’evoluzione culturale di Robert Boyd e Peter Richerson tratta le idee e le norme come repliche che si diffondono per imitazione invece che per nascita. E dagli anni 2000, il filone che interessa di più questo libro: il ponte con l’apprendimento automatico, dove la replicator equation riemerge come limite di algoritmi concreti. Ne parleremo nella sezione sulle applicazioni.

Nella mappa di questa Parte, il capitolo si colloca dopo l’equilibrio di Nash e il dilemma del prigioniero. Quei capitoli ti hanno dato la teoria dei giochi con giocatori razionali. Questo la rifà senza razionalità, e nel farlo costruisce un ponte verso le equazioni differenziali e verso il reinforcement learning multi-agente del resto della Parte.

Figura in preparazione

fig-1: timeline dal 1930 al 2020 con i nodi Fisher (rapporto dei sessi), Maynard Smith & Price 1973 (ESS), Taylor-Jonker 1978 (replicator equation), Axelrod 1984 (tornei IPD), Hofbauer-Sigmund 1998, e il ramo recente AlphaStar/NeuRD 2019-2020

L’intuizione

Per capire la teoria dei giochi evolutiva servono due cambi di prospettiva. Il primo riguarda chi gioca. Il secondo riguarda come si guarda l’evoluzione delle strategie nel tempo. Sono angoli diversi e conviene tenerli separati prima di scrivere una sola formula.

Angolo 1: nessuno sceglie, tutto viene selezionato

Nella teoria dei giochi classica il giocatore è un’entità che pondera le opzioni e ne sceglie una. Nella teoria dei giochi evolutiva questa entità sparisce. Quello che resta è una popolazione e un insieme di strategie. Ogni individuo della popolazione è una strategia: la porta scritta nel suo comportamento, cablata, non negoziabile. Un individuo non può svegliarsi e decidere di cambiare strategia. Può solo fare figli, che ereditano la sua strategia.

Il meccanismo che fa “muovere” il sistema non è la deliberazione, è la selezione. Ogni individuo interagisce con altri membri della popolazione — si contende risorse, partner, territorio — e da queste interazioni ricava un payoff. Qui il payoff non è utilità soggettiva: è fitness, il numero atteso di discendenti. Una strategia che produce più fitness lascia più copie di sé stessa nella generazione successiva. La sua frequenza nella popolazione cresce. Una strategia che produce meno fitness della media diventa via via più rara, e può estinguersi.

Il rovesciamento concettuale è questo: non è l’individuo che impara, è la popolazione che “impara”, per selezione. La popolazione si comporta come un ottimizzatore lento e cieco. Non c’è mente, non c’è intenzione, non c’è calcolo. C’è solo il fatto contabile che chi fa più figli diventa più comune. Eppure il risultato — vedremo — assomiglia a un equilibrio razionale. La razionalità “emerge” dalla selezione senza che nessuno sia razionale. È lo stesso motivo per cui un mercato può allocare risorse in modo efficiente senza che nessun singolo attore abbia una visione d’insieme.

Una strategia evolutivamente stabile, in questo angolo, è una strategia che ha vinto e resta vincente: una popolazione che la adotta non può essere scalzata. Immagina una popolazione tutta fatta della strategia $\sigma$. Compare per mutazione una manciata di individui con una strategia diversa $\mu$. Se questi mutanti rari ottengono in media meno fitness della popolazione residente, diventano sempre più rari e spariscono: $\sigma$ ha respinto l’invasione. Se questo vale per qualunque mutante possibile, allora $\sigma$ è una ESS. È una strategia blindata contro le novità.

Conviene rendere concreta la parola “selezione” con un conto piccolo. Supponi una popolazione di 1000 individui, 990 della strategia $\sigma$ e 10 della mutante $\mu$. Nelle interazioni di questa generazione un individuo $\sigma$ raccoglie in media una fitness di 2.0, un individuo $\mu$ una fitness di 1.8.

Interpreta la fitness come numero atteso di discendenti: i 990 individui $\sigma$ produrranno circa $990 \times 2.0 = 1980$ figli, i 10 individui $\mu$ circa $10 \times 1.8 = 18$. La generazione successiva ha $1998$ individui, di cui la frazione di $\mu$ è $18/1998 \approx 0.90\%$: è scesa da $10/1000 = 1.00\%$ a circa $0.90\%$.

Il mutante ha perso terreno senza che nessuno lo abbia “eliminato”: è semplicemente stato superato in fecondità. Ripeti, e la frazione di $\mu$ tende a zero. Questo è tutto ciò che “selezione” significa, e questa è la regola che la replicator equation cattura in forma continua. Nessuna mente, nessuna scelta: solo conteggio di discendenti.

Angolo 2: la popolazione è un punto che scivola su un paesaggio

Il secondo angolo è geometrico, e prepara direttamente la matematica. Considera un gioco con $n$ strategie possibili. Lo stato della popolazione in un dato istante è descritto da un vettore di frequenze $x = (x_1, x_2, \dots, x_n)$, dove $x_i$ è la frazione della popolazione che gioca la strategia $i$. Queste frequenze sono non negative e sommano a 1: lo stato vive in un oggetto geometrico chiamato simplesso — per tre strategie, è un triangolo; per due, un segmento; per quattro, un tetraedro.

La popolazione, mentre il tempo passa, non è ferma in quel triangolo. È un punto che si muove. La selezione la spinge: dove esattamente, lo dice la regola “le strategie sopra la media crescono di frequenza, quelle sotto la media calano”. In ogni punto del simplesso c’è quindi una freccia che indica dove la popolazione sta andando nell’istante successivo. L’insieme di tutte queste frecce è un campo di flusso — esattamente l’oggetto che si studia per qualunque sistema dinamico, e che il capitolo sulle equazioni differenziali introduce in generale.

Da questo angolo, le domande della teoria dei giochi diventano domande di geometria del flusso. Un equilibrio di Nash è un punto dove la freccia ha lunghezza zero: la popolazione, se ci arriva, ci resta — un punto fisso. Una ESS è qualcosa di più forte: è un punto fisso attrattivo, un punto verso cui le frecce vicine puntano, così che se la popolazione viene spostata di poco ci ritorna. La distinzione tra “punto fisso” e “punto fisso attrattivo” è la stessa che in fisica separa una biglia in equilibrio in cima a una collina (la spingi e rotola via) da una biglia in fondo a una conca (la spingi e torna giù). Questa immagine — equilibrio instabile in cima, equilibrio stabile in fondo — è la chiave per capire perché ESS è più di Nash.

Angolo 3: il test del mutante raro

C’è un terzo modo di mettere a fuoco la ESS, ed è quello operativo: il test. Per stabilire se una strategia $\sigma$ è una ESS non bisogna risolvere il sistema dinamico né disegnare il campo di flusso. Basta un esperimento mentale ripetibile.

Prendi una popolazione composta quasi interamente da $\sigma$, con una piccola frazione $\varepsilon$ di mutanti che giocano $\mu$. Calcola due payoff medi: quello che riceve un individuo $\sigma$ e quello che riceve un mutante $\mu$, entrambi in quella popolazione mista. Se l’individuo $\sigma$ guadagna di più, i mutanti perdono terreno e si estinguono. Se questo accade per ogni possibile mutante $\mu$ e per ogni $\varepsilon$ abbastanza piccolo, allora $\sigma$ ha passato il test: è una ESS.

Il payoff di un residente $\sigma$ nella popolazione mista è $(1-\varepsilon)\,\pi(\sigma\mid\sigma) + \varepsilon\,\pi(\sigma\mid\mu)$: con probabilità $1-\varepsilon$ incontra un altro residente, con probabilità $\varepsilon$ un mutante. Quello di un mutante $\mu$ è $(1-\varepsilon)\,\pi(\mu\mid\sigma) + \varepsilon\,\pi(\mu\mid\mu)$. La condizione “il residente guadagna di più” è la disuguaglianza tra queste due espressioni.

Quando $\varepsilon$ è piccolissimo domina il primo termine, e la disuguaglianza si riduce a $\pi(\sigma\mid\sigma) \ge \pi(\mu\mid\sigma)$ — la prima condizione di ESS. Quando i due primi termini pareggiano, decide il secondo, e salta fuori $\pi(\sigma\mid\mu) > \pi(\mu\mid\mu)$ — la seconda condizione.

Le due condizioni formali di Maynard Smith, che nella prossima sezione scriveremo come definizione, non sono altro che questo test scomposto nei suoi due casi. È utile vederle nascere da un esperimento concreto prima di incontrarle come assiomi.

Figura in preparazione

fig-2: il simplesso a triangolo per un gioco a 3 strategie, con il campo di flusso disegnato come frecce; tre scenari affiancati — un attrattore al centro (frecce che convergono), un repulsore (frecce che divergono), e orbite chiuse attorno al centro

La meccanica

Adesso che i due angoli sono chiari, mettiamo le formule. Servono due oggetti: la definizione formale di ESS e la replicator equation.

La definizione di ESS, riga per riga

Notazione. Scriviamo $\pi(\sigma \mid \mu)$ per indicare il payoff di un individuo che gioca la strategia $\sigma$ quando il suo avversario gioca $\mu$. Le strategie $\sigma$ e $\mu$ possono essere pure (sempre la stessa mossa) o miste (una distribuzione di probabilità sulle mosse). Maynard Smith definisce: la strategia $\sigma$ è una ESS se, per ogni strategia mutante $\mu \neq \sigma$, valgono due condizioni.

Prima condizione (condizione di equilibrio):

$\pi(\sigma \mid \sigma) \;\ge\; \pi(\mu \mid \sigma)$

In parole povere: contro una popolazione interamente fatta di $\sigma$, nessuna mutante $\mu$ ottiene un payoff più alto di quello che $\sigma$ ottiene contro sé stessa. La popolazione residente è almeno altrettanto brava quanto qualunque sfidante. Questa è esattamente la condizione di equilibrio di Nash: $\sigma$ è una migliore risposta a sé stessa.

Seconda condizione (condizione di stabilità):

$\text{se } \pi(\sigma \mid \sigma) = \pi(\mu \mid \sigma), \quad\text{allora}\quad \pi(\sigma \mid \mu) > \pi(\mu \mid \mu)$

Questa condizione si attiva solo nel caso problematico: quando la mutante $\mu$ è altrettanto brava quanto $\sigma$ contro la popolazione residente (vale l’uguaglianza nella prima condizione). In quel caso la prima condizione da sola non basta a respingere l’invasione: la mutante non perde terreno, e per pura deriva casuale potrebbe accumularsi. La seconda condizione chiude la falla. Dice: quando i mutanti diventano abbastanza numerosi da incontrarsi tra loro, deve essere la residente $\sigma$ a battere $\mu$ in quegli incontri ($\pi(\sigma \mid \mu) > \pi(\mu \mid \mu)$). Così anche la mutante “neutrale” viene comunque ricacciata indietro.

Le due condizioni insieme dicono: $\sigma$ è una ESS se respinge ogni mutante o perché la batte già quando il mutante è raro (prima condizione, disuguaglianza stretta), o — quando il mutante è altrettanto bravo da raro — perché la batte quando il mutante diventa meno raro (seconda condizione). Non c’è mutante che possa prendere piede.

La replicator equation, riga per riga

La definizione di ESS è statica: ti dice se una strategia è stabile, ma non ti dice come la popolazione ci arriva. Quella è la replicator equation.

Costruiamola pezzo per pezzo. Sia $A$ la matrice dei payoff: $A_{ij}$ è il payoff che ottiene chi gioca la strategia $i$ contro chi gioca la strategia $j$. Sia $x = (x_1, \dots, x_n)$ il vettore delle frequenze.

Primo pezzo: quanto guadagna in media un individuo che gioca la strategia $i$? Pesca avversari a caso dalla popolazione attuale. Con probabilità $x_j$ incontra un giocatore di tipo $j$, e in quell’incontro guadagna $A_{ij}$. Il payoff atteso è quindi:

$f_i = (Ax)_i = \sum_{j} A_{ij}\, x_j$

Secondo pezzo: qual è il payoff medio dell’intera popolazione? È la media dei $f_i$ pesata per quanto ogni strategia è presente:

$\bar f = x^\top A x = \sum_i x_i\, f_i$

Terzo pezzo, il cuore. La regola di selezione dice: la frequenza di una strategia cresce se quella strategia rende più della media, cala se rende meno. La velocità di crescita è proporzionale al vantaggio $f_i - \bar f$, e anche a quanto la strategia è già presente. Mettendo $\dot x_i$ per “velocità di variazione di $x_i$ nel tempo”:

$\dot x_i = x_i\,\big(f_i - \bar f\big) = x_i\,\big((Ax)_i - x^\top A x\big)$

Questa è la replicator equation. Leggiamola con calma. Il termine tra parentesi, $f_i - \bar f$, è il segno del destino della strategia $i$: positivo, la strategia si diffonde; negativo, si contrae; zero, è in equilibrio. Il fattore $x_i$ davanti fa due cose tutt’altro che innocue.

Primo: se $x_i = 0$, allora $\dot x_i = 0$. Una strategia assente resta assente per sempre. La replicator equation non innova: non può far comparire una strategia nuova, può solo ridistribuire quelle già presenti. Questo è un limite serio, su cui torneremo.

Secondo: la crescita è proporzionale alla presenza attuale. Una strategia rara ma vantaggiosa cresce all’inizio lentamente — perché $x_i$ è piccolo — poi sempre più in fretta man mano che $x_i$ aumenta. È una crescita di tipo esponenziale, modulata e frenata dal fatto che il vantaggio $f_i - \bar f$ si riduce man mano che la strategia diventa comune (perché allora $\bar f$ si avvicina a $f_i$).

Tre proprietà strutturali, utili da tenere a mente. (a) Il simplesso è invariante: se le frequenze partono valide — non negative e a somma 1 — restano valide per sempre. (b) Solo le differenze di payoff contano: aggiungere una costante a una colonna di $A$ non cambia la dinamica.

La terza proprietà merita una riga a sé. (c) Equivalenza con Lotka-Volterra: la replicator equation su $n$ strategie è matematicamente equivalente, tramite un cambio di coordinate, all’equazione di Lotka-Volterra in $n-1$ dimensioni — il classico modello preda-predatore dell’ecologia. Stessa matematica, due racconti: competizione tra strategie da un lato, competizione tra specie dall’altro. Questa equivalenza è un teorema, non un’analogia: c’è una trasformazione esplicita che porta un sistema nell’altro.

Una traiettoria, numero per numero

L’equazione vista in astratto può sembrare opaca. Vale la pena seguirne una traiettoria con numeri veri, su un gioco a due strategie — il più piccolo che mostra qualcosa di interessante. Prendiamo un gioco di coordinazione: due strategie, $A$ e $B$, e la matrice di payoff

        A    B
A       3    0
B       0    2

Due individui che giocano la stessa strategia guadagnano ($A$ contro $A$ rende 3, $B$ contro $B$ rende 2); due che giocano strategie diverse non guadagnano niente. È la struttura di una situazione in cui conviene fare quello che fanno gli altri, ma una delle due convenzioni ($A$) è migliore dell’altra.

Sia $x$ la frequenza di $A$, quindi $1-x$ la frequenza di $B$. Il payoff atteso di chi gioca $A$ è $f_A = 3x + 0(1-x) = 3x$: incontra un $A$ con probabilità $x$ e in quel caso prende 3, incontra un $B$ con probabilità $1-x$ e prende 0. Allo stesso modo $f_B = 2(1-x)$. Il payoff medio della popolazione è $\bar f = x f_A + (1-x) f_B = 3x^2 + 2(1-x)^2$. La replicator equation per $A$ diventa:

$\dot x = x\,(f_A - \bar f) = x\,\big(3x - 3x^2 - 2(1-x)^2\big)$

Partiamo da una popolazione con $x = 0.4$ — quaranta per cento di $A$, sessanta di $B$ — e facciamo qualche passo a mano, usando passi di tempo piccoli (la versione discreta $x_{\text{nuovo}} = x + \Delta t \cdot \dot x$, con $\Delta t = 0.1$).

A $x = 0.4$: $f_A = 1.2$, $f_B = 1.2$. I due payoff sono uguali. Quindi $\dot x = 0$: il punto $x = 0.4$ è un punto fisso, un equilibrio. Ma è instabile, e si vede subito spostandosi appena di lato. A $x = 0.41$: $f_A = 1.23$, $f_B = 2 \cdot 0.59 = 1.18$. Ora $A$ rende più di $B$, $\dot x > 0$, la frequenza di $A$ cresce. A $x = 0.39$: $f_A = 1.17$, $f_B = 1.22$, $\dot x < 0$, $A$ cala. Lo spartiacque a $x = 0.4$ respinge da entrambi i lati: spostati un capello verso $A$ e finisci a $x = 1$ (tutti $A$); spostati verso $B$ e finisci a $x = 0$ (tutti $B$).

Questo gioco ha quindi tre punti fissi — $x = 0$, $x = 0.4$, $x = 1$ — ma solo due sono attrattori: $x = 0$ e $x = 1$. Il punto interno $x = 0.4$ è un repulsore, l’equivalente della biglia in cima alla collina. E le due strategie pure sono entrambe ESS: una popolazione tutta-$A$ non è invadibile (un $B$ raro prende 0 contro gli $A$, mentre gli $A$ prendono 3 tra loro), e lo stesso vale per tutta-$B$. Due ESS, due bacini di attrazione, e lo stato iniziale decide in quale dei due si finisce. La traiettoria numerica rende concreto cosa significhi “la popolazione scivola sul paesaggio”: da $0.4$ il sistema non si muove, da $0.41$ rotola fino a $1$, da $0.39$ rotola fino a $0$.

Il ponte tra statica e dinamica: il folk theorem

Abbiamo due descrizioni — ESS (statica) e replicator dynamics (dinamica). Come si parlano? Il legame ha un nome consolidato in letteratura, il folk theorem della evolutionary game theory (la parola “folk” segnala che è stato dimostrato a pezzi da più autori, Taylor-Jonker, Zeeman, Hofbauer-Sigmund, e poi consolidato; non ha niente a che vedere con il folk theorem dei giochi ripetuti del dilemma del prigioniero). Tre affermazioni:

1. Ogni equilibrio di Nash del gioco è un punto fisso della replicator equation.
2. Ogni punto fisso stabile (un attrattore) della replicator equation è un equilibrio di Nash.
3. Ogni ESS è un attrattore asintoticamente stabile della replicator equation.

Attenzione al verso. La terza affermazione non si inverte: esistono attrattori della replicator dynamics che non sono ESS, soprattutto in giochi con più di due strategie. Il messaggio concettuale è netto: la stabilità dinamica è un filtro. Tra tutti gli equilibri di Nash di un gioco — che possono essere molti e non tutti sensati — la dinamica seleziona quelli robusti. La teoria classica per fare questa selezione ha dovuto introdurre a mano una serie di “raffinamenti” dell’equilibrio (perfezione, properness, e altri). La teoria evolutiva la ottiene gratis: il raffinamento è la dinamica stessa. Un Nash che la dinamica non rende stabile semplicemente non si osserva a lungo, perché la popolazione ci scivola via.

ESS è più di Nash: un Nash che non sopravvive

Vale la pena rendere concreta l’inclusione “ogni ESS è Nash, non viceversa” con un gioco minimo dove un equilibrio di Nash esiste ma non è una ESS. Considera due strategie, $A$ e $B$, con questa matrice:

        A    B
A       1    1
B       1    0

Verifichiamo prima che “tutti $A$” sia un equilibrio di Nash. In una popolazione di soli $A$, un individuo $A$ prende 1 (gioca $A$ contro $A$). Un mutante $B$ prende anch’esso 1 (gioca $B$ contro $A$). Nessuno guadagna deviando da $A$: $\pi(A\mid A) = \pi(B\mid A) = 1$. La prima condizione di ESS è soddisfatta, con uguaglianza. “Tutti $A$” è quindi un equilibrio di Nash — un Nash debole, perché la disuguaglianza non è stretta.

Ora la seconda condizione. Siamo nel caso di parità, quindi serve $\pi(A\mid B) > \pi(B\mid B)$. Ma $\pi(A\mid B) = 1$ (un $A$ contro un $B$ prende 1) e $\pi(B\mid B) = 0$ (un $B$ contro un $B$ prende 0). Quindi $\pi(A\mid B) = 1 > 0 = \pi(B\mid B)$: la seconda condizione regge, e in questo caso particolare $A$ è una ESS. Cambiamo allora una sola cella per costruire il controesempio vero. Prendi la matrice

        A    B
A       1    0
B       1    0

Qui “tutti $A$” è ancora un Nash debole: $\pi(A\mid A) = \pi(B\mid A) = 1$. Ma la seconda condizione chiede $\pi(A\mid B) > \pi(B\mid B)$, e ora $\pi(A\mid B) = 0$, $\pi(B\mid B) = 0$: si ha uguaglianza, non disuguaglianza stretta. La seconda condizione fallisce.

“Tutti $A$” è un equilibrio di Nash ma non è una ESS: una manciata di mutanti $B$ pareggia ovunque, non perde mai terreno, e per pura deriva casuale può accumularsi e portare la popolazione a uno stato misto o a “tutti $B$”. È esattamente la falla che la seconda condizione di Maynard Smith serve a chiudere — e questo gioco mostra un Nash che non la supera. La morale: “è un equilibrio di Nash” garantisce che nessuno guadagni strettamente deviando, ma non garantisce che la popolazione ci resti. ESS sì.

Esempi

Tre esempi, scelti per illuminare aspetti diversi: uno biologico e numerico, uno computazionale, uno geometrico.

Hawk-Dove: l’aggressività ha un livello di equilibrio

Questo è il gioco del paper del 1973. Due individui della stessa specie si contendono una risorsa di valore $V$ — un territorio, un partner, del cibo. Ognuno può adottare una di due strategie. La strategia Hawk (falco): escala il conflitto, combatti sul serio finché non vinci o sei ferito. La strategia Dove (colomba): minaccia, ma se l’avversario escala ritirati senza combattere. Un combattimento serio comporta un costo $C$ (ferite, energia, rischio).

I payoff, riga uguale “io”, colonna uguale “avversario”:

• Hawk contro Hawk: combattono entrambi. In media ognuno vince metà delle volte ($+V$) e metà delle volte è ferito ($-C$): il payoff atteso è $(V-C)/2$.
• Hawk contro Dove: il falco escala, la colomba si ritira. Il falco prende tutta la risorsa, $V$. La colomba prende $0$.
• Dove contro Hawk: speculare. La colomba $0$, il falco $V$.
• Dove contro Dove: nessuno dei due escala. Si dividono la risorsa o se la giocano senza costi: in media $V/2$ a testa.

Consideriamo il caso interessante, quello biologicamente realistico: $C > V$, cioè il combattimento costa più di quanto vale la risorsa. Mettiamo numeri concreti: $V = 2$, $C = 4$. La matrice diventa:

            Hawk    Dove
Hawk      (2-4)/2    2
            = -1
Dove        0        1

Esiste una strategia pura che sia una ESS? No, e si verifica subito.

Una popolazione tutta-Dove non è una ESS. In una popolazione di sole colombe ognuna prende $1$. Compare un falco raro: incontra quasi solo colombe, e contro le colombe prende $2$. Il mutante falco fa $2 > 1$: la prima condizione di ESS è violata, i falchi invadono.

Una popolazione tutti-Hawk non è una ESS. In una popolazione di soli falchi ognuno prende $-1$. Compare una colomba rara: contro i falchi prende $0$. Il mutante colomba fa $0 > -1$: i falchi vengono invasi dalle colombe.

L’unica ESS è mista. Cerchiamo la frequenza $p$ di falchi alla quale Hawk e Dove rendono esattamente lo stesso — a quel punto nessuna delle due può invadere l’altra. Il payoff atteso di un falco in una popolazione con frazione $p$ di falchi è $p \cdot (-1) + (1-p) \cdot 2$. Quello di una colomba è $p \cdot 0 + (1-p) \cdot 1$. Uguagliando:

$-p + 2(1-p) = (1-p) \;\;\Longrightarrow\;\; 2 - 3p = 1 - p \;\;\Longrightarrow\;\; p = \tfrac12$

In generale la frequenza di equilibrio dei falchi è $p^* = V/C$ (qui $2/4 = 1/2$). A quella frequenza falchi e colombe hanno lo stesso payoff: la selezione non favorisce né gli uni né le altre, e la popolazione è in equilibrio. È un equilibrio attrattivo: se per caso i falchi superano $p^*$ si feriscono troppo tra loro e calano; se scendono sotto $p^*$ trovano troppe colombe da spennare e crescono. La popolazione converge a $p^*$ e ci resta.

Verifichiamo che $p^* = 1/2$ sia davvero stabile applicando il test del mutante raro. Supponi che la popolazione sia esattamente a $p^* = 1/2$ e compaia un mutante che gioca Hawk con probabilità diversa, diciamo un falco puro ($p = 1$). A $p^* = 1/2$ falco e colomba rendono già lo stesso, $0.5$ ciascuno, quindi anche il mutante falco puro rende $0.5$: il payoff non lo distingue dalla popolazione. È il caso di parità, dove decide la seconda condizione.

E qui la popolazione mista vince: un mutante falco puro, incontrando un altro mutante falco puro, prende $-1$, mentre la strategia residente contro quel mutante prende un valore più alto. I mutanti più aggressivi si penalizzano negli incontri tra loro, e la popolazione torna a $p^*$. Lo stesso ragionamento, simmetrico, respinge un mutante troppo pacifico. La frequenza $V/C$ non è solo un punto di parità: è un attrattore.

Il risultato è quello che Maynard Smith e Price volevano: l’aggressività non degenera. C’è un livello di equilibrio, e la selezione lo trova da sola. Nessun cervo calcola $V/C$. La popolazione lo “calcola” per selezione.

C’è una sottigliezza da rendere esplicita. L’ESS mista $p^* = 1/2$ si può realizzare in due modi che il payoff non distingue. O ogni individuo gioca Hawk con probabilità $1/2$ (strategia mista individuale), o metà della popolazione è fatta di falchi puri e metà di colombe pure (polimorfismo di popolazione). I due scenari hanno la stessa matematica e lo stesso payoff medio. La distinzione conta quando si passa a popolazioni finite o strutturate, dove i due regimi smettono di essere equivalenti — ma nel modello base sono indistinguibili, e questa ambiguità è una caratteristica nota della teoria, non un difetto del modello particolare.

Il dilemma del prigioniero iterato e il torneo ecologico di Axelrod

Il secondo esempio mostra la teoria evolutiva come strumento computazionale. Il punto di partenza è il dilemma del prigioniero giocato ripetutamente — l’IPD, iterated prisoner’s dilemma: due giocatori si affrontano per molti round, ognuno sceglie a ogni round se cooperare o defezionare, e ogni giocatore ricorda cosa è successo prima.

Fissiamo i numeri di un singolo round, perché servono per leggere il torneo. Una matrice standard per il dilemma del prigioniero, con C “coopera” e D “defeziona”:

        C    D
C       3    0
D       5    1

Mutua cooperazione rende 3 a testa; mutua defezione, 1 a testa; chi defeziona contro un cooperatore prende 5, e il cooperatore sfruttato prende 0. In un singolo round defezionare domina: qualunque cosa faccia l’avversario, D rende più di C ($5 > 3$ e $1 > 0$). L’unico equilibrio di Nash del gioco one-shot è “entrambi defezionano”, payoff $1$ contro un $3$ che sarebbe stato raggiungibile cooperando. Ma ripeti il gioco per duecento round, e la storia cambia: ora la mia mossa di oggi influenza la tua di domani, e cooperare può ripagare. È in questo gioco ripetuto che Axelrod manda i suoi programmi.

Tra il 1979 e il 1980 Robert Axelrod (politologo, University of Michigan) organizza due tornei: invita ricercatori di tutto il mondo a sottomettere programmi che giocano l’IPD, e li fa affrontare tutti contro tutti. Vince entrambe le volte un programma di poche righe sottomesso da Anatol Rapoport (psicologo matematico russo-canadese): tit-for-tat. La sua regola sta in una frase: coopera al primo round, poi a ogni round successivo copia la mossa che l’avversario ha fatto al round precedente.

Fin qui è un torneo, non teoria evolutiva. Il passo che porta dentro la teoria evolutiva è l’analisi successiva di Axelrod, il torneo ecologico. Invece di far giocare tutti i programmi a parità di rappresentanza una volta sola, Axelrod fa evolvere la popolazione di programmi. Funziona così, ed è letteralmente la logica replicator in versione discreta:

popolazione = {strategia: frequenza_iniziale uguale per tutte}

ripeti per molte generazioni:
    # ogni strategia affronta la popolazione attuale
    per ogni strategia s:
        f[s] = payoff medio di s contro la popolazione,
               pesato per le frequenze attuali

    f_media = somma( freq[s] * f[s] per ogni s )

    # le strategie sopra la media crescono, sotto la media calano
    per ogni strategia s:
        freq[s] = freq[s] * f[s] / f_media

    # freq resta una distribuzione: somma 1

L’ultima riga è la replicator equation in forma discreta: la nuova frequenza è la vecchia moltiplicata per il rapporto tra il payoff della strategia e il payoff medio. Strategia sopra la media, il rapporto è maggiore di 1, la frequenza cresce.

In questo torneo ecologico tit-for-tat non si limita a vincere: la sua frazione nella popolazione cresce monotonicamente generazione dopo generazione. E le strategie sfruttatrici — quelle che defezionano per estorcere payoff agli avversari ingenui — hanno un destino istruttivo. All’inizio prosperano, perché ci sono partner ingenui da spennare. Ma proprio spennandoli li portano all’estinzione, e quando i partner ingenui finiscono le sfruttatrici si ritrovano a giocare solo contro altre sfruttatrici, dove il payoff è basso per tutte. Collassano. La teoria evolutiva trasforma l’affermazione “tit-for-tat ha totalizzato più punti” nell’affermazione più forte “tit-for-tat è una strategia che si diffonde e resiste”.

Axelrod riassume nel suo libro The Evolution of Cooperation (Basic Books, 1984) quali tratti rendono una strategia evolutivamente di successo nell’IPD, e vale la pena enumerarli perché sono sorprendentemente leggibili. Una strategia vincente tende a essere gentile (non è la prima a defezionare), reattiva (punisce la defezione invece di subirla), indulgente (torna a cooperare appena l’avversario coopera, senza covare rancore) e trasparente (il suo comportamento è semplice e prevedibile, così che l’avversario possa imparare a fidarsi). Tit-for-tat ha tutti e quattro i tratti.

Una strategia che defeziona per prima guadagna qualcosa a breve, ma in un torneo ecologico si brucia i partner e poi affonda con loro. È un risultato che ha avuto eco ben oltre la teoria dei giochi: ha dato un fondamento matematico all’idea che la cooperazione possa emergere e reggere tra agenti egoisti, senza bisogno di altruismo né di un’autorità centrale, purché le interazioni si ripetano.

Una nota di onestà tecnica, perché è un punto dove è facile fare overclaim. Tit-for-tat non è una ESS in senso stretto. È neutralmente invadibile: una popolazione di tit-for-tat può essere infiltrata senza resistenza da una strategia “sempre coopera”, perché tra cooperatori incalliti tit-for-tat e sempre-coopera si comportano in modo identico e ottengono lo stesso payoff. Ed è fragile al rumore: se un errore di esecuzione fa defezionare per sbaglio, due tit-for-tat entrano in una spirale di ritorsioni reciproche.

Tit-for-tat è collettivamente stabile e robusta in molti contesti, ma chiamarla ESS sarebbe sbagliato. La distinzione tra “vince un torneo”, “è robusta” e “è una ESS” è esattamente il tipo di precisione che la teoria evolutiva permette di fare.

Rock-paper-scissors: l’equilibrio che nessuno raggiunge

Il terzo esempio mostra il limite più importante della teoria: la dinamica non sempre converge. Il gioco è sasso-carta-forbice. Tre strategie, ognuna batte una delle altre due e perde contro la terza: sasso batte forbice, forbice batte carta, carta batte sasso. La matrice dei payoff è antisimmetrica: chi vince prende $+1$, chi perde $-1$, in caso di pareggio $0$.

          Sasso  Carta  Forbice
Sasso       0     -1      +1
Carta      +1      0      -1
Forbice    -1     +1       0

Questo gioco ha un unico equilibrio di Nash: giocare le tre mosse con probabilità $1/3$ ciascuna. In termini di popolazione, è lo stato $x = (1/3, 1/3, 1/3)$ — il centro esatto del triangolo-simplesso. In quel punto le tre strategie hanno tutte lo stesso payoff atteso, $0$, e la replicator equation dà $\dot x_i = 0$ per tutte: è un punto fisso.

Ma è un punto fisso attrattivo? No. E qui sta la sorpresa. Con questa matrice antisimmetrica le traiettorie della replicator dynamics sono orbite chiuse che girano in cerchio attorno al centro, all’infinito, senza mai avvicinarsi né allontanarsi. Segui la logica: se in un certo momento il sasso è abbondante, allora la carta — che batte il sasso — ha un payoff sopra la media e cresce. Ma quando la carta diventa abbondante, sono le forbici — che battono la carta — ad avere il vantaggio, e crescono. E quando le forbici dilagano, torna a convenire il sasso. La popolazione insegue sé stessa in un ciclo perpetuo. Non converge mai all’equilibrio di Nash, pur avendolo come punto fisso.

C’è un modo preciso di vedere perché le orbite sono chiuse e non spirali. Per questa matrice esiste una quantità conservata: la funzione $x_1 x_2 x_3$, il prodotto delle tre frequenze, resta costante lungo ogni traiettoria. La popolazione si muove ma è vincolata a stare su una di queste curve di livello, che sono anelli chiusi attorno al centro. È lo stesso tipo di struttura di un pendolo senza attrito, che oscilla per sempre perché conserva l’energia: niente attrito, niente convergenza. Aggiungere “attrito” — perturbare i payoff sulla diagonale — rompe la conservazione e il centro diventa attrattore o repulsore.

Non è una curiosità astratta. La lucertola Uta stansburiana della California ha tre morfotipi maschili — gola arancione, gola blu, gola gialla — con strategie riproduttive in ciclo roccia-carta-forbice: nelle popolazioni naturali le frequenze dei tre morfotipi oscillano in cicli pluriennali, esattamente come predice il modello (Sinervo & Lively, Nature 1996).

Variando i numeri sulla diagonale della matrice il comportamento cambia: il centro può diventare un attrattore (le orbite spiraleggiano verso il centro e convergono) o un repulsore (spiraleggiano verso il bordo). Ma il caso a payoff bilanciato — orbite chiuse, nessuna convergenza — è il promemoria che “equilibrio esiste” e “la dinamica ci arriva” sono due affermazioni diverse. È anche, come vedremo tra poco, la chiave per capire perché certi algoritmi di apprendimento, messi a giocare l’uno contro l’altro, non si fermano mai.

Figura in preparazione

fig-3: gioco Hawk-Dove a sinistra con la retta del payoff atteso di Hawk e Dove in funzione della frequenza p di falchi, che si incrociano a p* = V/C; a destra il triangolo-simplesso di rock-paper-scissors con un’orbita chiusa che gira attorno al centro

Applicazioni pratiche

La teoria dei giochi evolutiva nasce dalla biologia, ma per chi costruisce sistemi AI non è materiale d’archivio. La replicator equation ricompare, sotto altri nomi, nel cuore di metodi di machine learning moderni.

Replicator dynamics come limite continuo degli algoritmi di apprendimento

Questo è il ponte più sostanziale. Esiste una famiglia di algoritmi di apprendimento online chiamati multiplicative weights update (MWU), noti anche come algoritmo Hedge: un meta-algoritmo che compare ovunque, dal boosting alla teoria dei giochi algoritmica, e che gode di forti garanzie di regret (la differenza tra quanto hai guadagnato e quanto avresti guadagnato con la migliore azione fissa col senno di poi). MWU mantiene un peso per ogni azione e, a ogni passo, moltiplica ogni peso per un fattore esponenziale nel payoff osservato per quell’azione.

Il fatto: se prendi MWU e fai tendere a zero la dimensione del passo, ottieni esattamente la replicator equation $\dot x_i = x_i(f_i - \bar f)$. La replicator dynamics è la forma a tempo continuo di MWU. Non è un’analogia suggestiva: è un’identità matematica, ottenuta come limite. La stessa cosa vale per il regret matching (Hart & Mas-Colell, 2000), il principio alla base del counterfactual regret minimization (CFR), l’algoritmo con cui sono stati battuti i campioni umani nel poker.

Perché MWU diventa la replicator equation, in una riga di intuizione: MWU aggiorna il peso $w_i$ di un’azione moltiplicandolo per qualcosa come $e^{\eta f_i}$, dove $\eta$ è il passo di apprendimento e $f_i$ il payoff osservato. Dopo la normalizzazione, la frequenza relativa di un’azione cresce in proporzione a quanto il suo payoff supera la media — esattamente la regola “sopra la media cresce”. Fai tendere $\eta$ a zero e l’aggiornamento discreto diventa l’equazione differenziale continua. Il peso che MWU dà a un’azione e la frequenza che la replicator equation dà a una strategia sono lo stesso oggetto; il passo $\eta$ è il granello di tempo che separa la versione discreta da quella continua.

La conseguenza pratica è doppia. Da un lato i teoremi della teoria evolutiva diventano strumenti per analizzare algoritmi di apprendimento: sapere quando la replicator dynamics converge ti dice quando MWU converge. Dall’altro i limiti della teoria evolutiva diventano spiegazioni di patologie reali: il fatto che in rock-paper-scissors la dinamica cicli invece di convergere spiega perché certi algoritmi di apprendimento, messi a giocare uno contro l’altro, orbitano attorno all’equilibrio senza raggiungerlo.

Questo non è un dettaglio accademico: significa che mettere due “learner” ad apprendere l’uno contro l’altro in un gioco a somma zero può non convergere a niente, e che bisogna o mediare nel tempo le strategie o modificare l’algoritmo per spezzare il ciclo. DeepMind ha costruito un algoritmo per il reinforcement learning multi-agente, Neural Replicator Dynamics (NeuRD, presentato ad AAMAS 2020), partendo proprio da questa identità: derivare un metodo di apprendimento dalla replicator equation, ereditandone le garanzie di regret.

Self-play, leghe di agenti e population-based training

AlphaGo, AlphaZero, AlphaStar: i sistemi che hanno battuto i campioni umani a Go, scacchi e StarCraft sono stati addestrati per self-play, cioè facendo giocare l’agente contro copie di sé stesso, e usando le versioni che vincono di più come avversari per la generazione successiva. Visto attraverso la lente di questo capitolo, il self-play è una replicator dynamics implementata via deep RL: le strategie — qui, le reti neurali — che vincono diventano più rappresentate nella distribuzione di avversari, quelle che perdono spariscono.

AlphaStar (Vinyals et al., Nature 2019) rende il parallelo esplicito con la sua League: non un singolo agente che si allena contro sé stesso, ma una popolazione strutturata di agenti. Alcuni sono “main agent” in addestramento continuo; altri sono “exploiter”, il cui unico scopo è trovare e sfruttare le debolezze dei main; altri ancora sono congelati come memoria storica, per evitare che l’agente dimentichi come battere strategie vecchie. DeepMind descrive l’agente finale di AlphaStar come la Nash distribution della lega: il mix di strategie meno sfruttabile — un concetto che viene dritto dalla teoria dei giochi.

La struttura della League risolve un problema concreto che la teoria evolutiva inquadra bene. Un self-play ingenuo — l’agente si allena solo contro la sua versione più recente — può cadere in un ciclo roccia-carta-forbice: la versione 3 batte la 2, la 4 batte la 3 dimenticando come si batte la 2, la 5 ricade nella strategia della 2 e batte la 4. È il ciclo che abbiamo visto, trasposto sulle reti neurali.

Tenere in vita gli avversari congelati e gli exploiter è il modo ingegneristico di spezzare il ciclo: l’agente è costretto a restare bravo contro tutte le strategie passate, non solo contro l’ultima, e questo lo spinge verso una strategia robusta — appunto, qualcosa di vicino a una ESS.

Il population-based training (PBT) generalizza l’idea: una popolazione di agenti, o di configurazioni di iperparametri, dove i migliori sopravvivono e generano varianti. È la teoria dei giochi evolutiva trasformata in ingegneria del training, e la co-evoluzione di strategie è il problema centrale del reinforcement learning multi-agente che vedi nei giochi stocastici e in multi-agent (in preparazione).

Le GAN come gioco a due giocatori

Le generative adversarial networks (GAN) — l’architettura per generare dati realistici introdotta da Ian Goodfellow e colleghi nel 2014 — sono definite dagli autori stessi, nel paper originale, come un “two-player minimax game”. Ci sono due reti: un generatore, che produce campioni falsi e vuole ingannare l’avversario, e un discriminatore, che cerca di distinguere i campioni veri da quelli falsi. Le due reti hanno una funzione obiettivo comune: il generatore vuole minimizzarla, il discriminatore massimizzarla. L’addestramento è la ricerca di un equilibrio — un equilibrio di Nash di un gioco a somma zero.

Questo inquadramento spiega una delle frustrazioni note di chi addestra le GAN: l’instabilità. Mode collapse (il generatore produce sempre lo stesso campione), oscillazioni che non si placano, training che non converge. Vista come dinamica di gioco, è la stessa patologia di rock-paper-scissors: due ottimizzatori che si rincorrono possono ciclare attorno all’equilibrio invece di raggiungerlo.

Una sottolineatura sulla classe di affermazione: tra GAN e teoria evolutiva c’è un’analogia strutturale forte e una identità formale parziale (la GAN è un gioco a somma zero), ma non una filiazione storica — Goodfellow non ha derivato le GAN da Maynard Smith. Le due cose convergono sulla stessa matematica per strade indipendenti. L’architettura GAN è trattata nel capitolo gan (in preparazione).

La co-evoluzione come lente diagnostica

Al di là dei tre casi specifici, la teoria dei giochi evolutiva è utile come lente diagnostica quando si costruiscono sistemi con più agenti che apprendono insieme. Ogni volta che due o più componenti di un sistema AI si adattano l’una all’altra — un agente che genera attacchi e uno che li filtra, un risolutore e un verificatore, due agenti in un marketplace che aggiustano i prezzi — si ha una co-evoluzione, e le domande della teoria evolutiva diventano le domande giuste da porsi.

Il sistema sta convergendo a una configurazione stabile, o sta ciclando? La strategia su cui converge è robusta — una specie di ESS — o è solo l’ultima risposta a un avversario che cambierà di nuovo? C’è una strategia “mutante” semplice, magari banale, che inviterebbe il sistema attuale?

Questa lente cambia anche la diagnosi dei fallimenti. Un sistema multi-agente che oscilla all’infinito non è necessariamente “rotto” nel senso di un bug: può star vivendo, fedelmente, un ciclo roccia-carta-forbice, e la cura non è un patch ma un cambiamento della dinamica — mediare le strategie nel tempo, tenere in memoria gli avversari passati, perturbare i payoff. E un sistema che converge in fretta a una strategia “stabile” non è automaticamente sano: potrebbe aver trovato un equilibrio di Nash povero, l’analogo di “entrambi defezionano” nel dilemma del prigioniero, e la teoria evolutiva suggerisce dove cercare i meccanismi — ripetizione, memoria, reputazione — che spostano il sistema verso un equilibrio migliore.

Dove si rompe

La teoria dei giochi evolutiva è elegante e produttiva, ma poggia su assunzioni che è onesto mettere in chiaro. I suoi limiti contano quanto i suoi risultati.

La replicator equation non innova. È il limite strutturale più pesante. Per come è scritta — il fattore $x_i$ davanti — una strategia a frequenza zero resta a frequenza zero per sempre. La replicator dynamics può solo ridistribuire la massa tra le strategie già presenti nella popolazione di partenza; non può far comparire niente di nuovo. Ma l’evoluzione vera è fatta di novità: la mutazione introduce in continuazione strategie che prima non c’erano. Per modellarla servono estensioni — la replicator-mutator equation, o il modello delle quasispecie di Manfred Eigen — che aggiungono un termine di mutazione. Chi usa la replicator dynamics nuda sta studiando una competizione a cast fisso, e deve saperlo.

Convergenza non garantita. È facile leggere “ESS implica attrattore stabile” e concludere che la dinamica finisce sempre da qualche parte di sensato. Falso. Rock-paper-scissors lo mostra: orbite chiuse, nessuna convergenza, per sempre. E ci sono giochi in cui la replicator dynamics produce dinamiche caotiche vere e proprie. Inoltre il legame tra concetti statici e dinamici è asimmetrico: ogni ESS è un attrattore, ma non ogni attrattore è una ESS, e esistono dinamiche di apprendimento alternative sotto le quali una strategia che è ESS non è affatto stabile. La frase “EGT seleziona gli equilibri robusti” è vera con cautela: dipende da quale dinamica.

Popolazione infinita, deterministica, ben mescolata. La replicator equation assume tre cose, tutte idealizzazioni. Che la popolazione sia infinita: così le frequenze sono numeri reali continui e non ci sono fluttuazioni casuali. Che la dinamica sia deterministica: niente caso. Che la popolazione sia “ben mescolata”, cioè ogni individuo abbia la stessa probabilità di incontrare chiunque altro.

Nelle popolazioni reali nessuna delle tre regge del tutto. Le popolazioni sono finite, e in una popolazione finita una strategia svantaggiata può comunque fissarsi per pura fortuna — la deriva genetica. Per trattare questo servono modelli stocastici, come il processo di Moran, dove si calcola la probabilità che un mutante invada, non la certezza; è il terreno dei processi stocastici.

E “ben mescolata” è quasi sempre falsa: gli individui interagiscono con i vicini, su un reticolo o una rete sociale, e la struttura spaziale può cambiare radicalmente l’esito — la cooperazione, per esempio, sopravvive molto meglio su un reticolo che in una popolazione ben mescolata.

ESS può non esistere. Non tutti i giochi hanno una ESS. Rock-paper-scissors, di nuovo, è l’esempio: ha un equilibrio di Nash ma nessuna ESS. Un sistema progettato assumendo che “la dinamica converga a una ESS” può trovarsi senza nessuna ESS a cui convergere.

Payoff fisso ed esogeno. Il modello assume che la matrice dei payoff $A$ sia data e costante. Nei sistemi reali — un mercato, un ecosistema, una popolazione di agenti software — il “payoff” di una strategia dipende dall’ambiente, e l’ambiente cambia, a volte proprio in risposta alle strategie adottate. Modellare questo richiede payoff dipendenti dallo stato, che escono dal quadro della replicator equation standard.

Interazioni a coppie, non di gruppo. La replicator equation nella forma vista qui assume che il payoff di un individuo derivi da una serie di incontri a due: la matrice $A$ ha due indici, “io” e “l’avversario”. Molti fenomeni reali sono invece interazioni di gruppo — la produzione di un bene comune, la caccia collettiva, una votazione — dove il payoff dipende dalla composizione di un intero gruppo, non di una coppia. Esistono estensioni della teoria ai giochi $n$-personali, ma la versione base, quella che dà le formule più pulite e i risultati più citati, è limitata al caso a coppie. Applicarla dove le interazioni sono genuinamente collettive è un’approssimazione, e va dichiarata come tale.

Selezione pura, senza altri meccanismi evolutivi. La replicator equation isola un solo meccanismo: la selezione, cioè il fatto che chi rende di più si diffonde. Lascia fuori la mutazione (l’abbiamo già detto), ma anche la migrazione, la ricombinazione, la deriva, la struttura genetica diploide. È un modello del cuore della dinamica selettiva, deliberatamente spogliato. Per la biologia delle popolazioni vera questa è una semplificazione forte; per chi la usa come modello di apprendimento o di competizione tra strategie astratte, è invece spesso esattamente il livello di dettaglio giusto. Sapere cosa è stato tolto è il prerequisito per usarla bene.

Il salto dalla biologia all’AI va fatto con cura. Self-play, population-based training e GAN condividono la matematica della teoria evolutiva — questa è una identità formale, verificabile. Ma le idealizzazioni biologiche non si trasferiscono gratis. Una “popolazione” di reti neurali in una lega di self-play è tipicamente piccola — decine, non infinita — quindi tutti gli effetti da popolazione finita sono in gioco. E la matrice dei payoff in un torneo di agenti AI non è affatto fissa: cambia a ogni iterazione, perché gli avversari imparano. Usare la teoria evolutiva per ragionare su questi sistemi è produttivo; usarla per garantire convergenza è un overclaim.

Collegamenti

• L’equilibrio di Nash — la ESS è un raffinamento del concetto di Nash: la prima delle due condizioni di ESS è la condizione di Nash, e ogni ESS è un equilibrio di Nash. Il capitolo da leggere prima di questo.
• Il dilemma del prigioniero — il torneo ecologico di Axelrod, tit-for-tat e l’evoluzione della cooperazione sono l’esempio centrale di questo capitolo applicato all’IPD.
• Somma zero, somma generale — rock-paper-scissors è un gioco a somma zero, Hawk-Dove è a somma generale: la distinzione spiega perché il primo cicla e il secondo converge a una ESS.
• Minimax — la “Nash distribution” come strategia meno sfruttabile, usata da AlphaStar, è parente diretta del valore minimax di un gioco a somma zero.
• Giochi stocastici — la co-evoluzione di strategie e il reinforcement learning multi-agente sono la versione stocastica e sequenziale della competizione tra strategie vista qui.
• Alignment come problema principal-agent — selezione di strategie, incentivi e payoff sono lo stesso vocabolario con cui si discute l’allineamento.
• Equazioni differenziali a intuizione — la replicator equation è un’equazione differenziale, e il campo di flusso sul simplesso è un sistema dinamico nel senso preciso di quel capitolo.
• Processi stocastici — le popolazioni reali sono finite: per trattare la deriva e la probabilità di invasione servono modelli stocastici come il processo di Moran, che superano il limite “popolazione infinita” della replicator equation.

Per andare oltre

• Maynard Smith, J. & Price, G.R., The Logic of Animal Conflict, Nature 246 (1973), pp. 15-18 — il paper fondativo, breve e leggibile, dove compaiono per la prima volta ESS e il gioco Hawk-Dove.
• Maynard Smith, J., Evolution and the Theory of Games, Cambridge University Press, 1982 — il libro che sistematizza la disciplina; trattazione completa di ESS, Hawk-Dove, war of attrition.
• Hofbauer, J. & Sigmund, K., Evolutionary Games and Population Dynamics, Cambridge University Press, 1998 — il testo di riferimento moderno per la replicator equation e il legame con i sistemi dinamici.
• Evolutionary Game Theory, Stanford Encyclopedia of Philosophy (plato.stanford.edu/entries/game-evolutionary) — una trattazione concettuale accurata e gratuita, con le definizioni formali e la discussione dei limiti.
• Cressman, R. & Tao, Y., The replicator equation and other game dynamics, PNAS 111 (2014) — survey sulla replicator equation e il folk theorem della teoria evolutiva.
• Vinyals, O. et al., Grandmaster level in StarCraft II using multi-agent reinforcement learning, Nature 575 (2019) — il paper di AlphaStar, per vedere la League, il population-based training e la Nash distribution applicati a un sistema AI reale.