Cos'è un gioco, in senso tecnico

Quando più di un agente decide e gli esiti dipendono da tutte le scelte insieme, sei in un gioco. Definire questa parola con cura è la grammatica di tutto ciò che segue.

Perché questo capitolo

Quasi tutto quello che chiamiamo “intelligenza artificiale moderna” coinvolge più di un decisore. Una rete generativa antagonista contiene due reti che si combattono. Un modello allenato con apprendimento per rinforzo da feedback umano (RLHF) ha un policy player e un reward model che lo valuta. Un sistema multi-agent fatto di più LLM coordina, negozia, eventualmente compete. Anche un singolo agent che usa tool dialoga con un ambiente che reagisce. Appena ci sono due o più entità le cui scelte si influenzano, siamo in un gioco — nel senso tecnico che la teoria dei giochi ha ritagliato negli ultimi cento anni.

Questa Parte V costruisce la grammatica della decisione: prima la grammatica multi-agente (giochi, equilibri, dilemmi), poi quella di un agente solo contro un mondo stocastico (Markov decision process, Bellman, Q-learning). I capitoli successivi si appoggeranno a questi termini come a vocaboli noti. Per questo qui non parliamo di scacchi e poker per nostalgia, ma per estrarre da loro la struttura formale che serve a parlare con precisione di GAN, self-play, robustezza adversarial, RLHF, mechanism design.

Lo scopo di questo capitolo è allineare il vocabolario: cosa è un giocatore, cosa è una strategia, cosa è un payoff, cosa significa “equilibrio”, e perché queste parole — apparentemente lontane dal deep learning — sono incise nelle architetture di training che usiamo ogni giorno.

Contesto

La teoria dei giochi è una disciplina matematica giovane. Nasce in due colpi: nel 1928 con un articolo del matematico ungherese-americano John von Neumann, Zur Theorie der Gesellschaftsspiele (Sulla teoria dei giochi di società), che contiene la prima prova del teorema minimax. E nel 1944 con il trattato Theory of Games and Economic Behavior scritto da von Neumann insieme all’economista austriaco Oskar Morgenstern: ottocento pagine che pongono le basi di un programma di ricerca che, secondo gli autori, doveva rifondare l’economia sulla matematica della decisione strategica.

Il salto successivo arriva da un dottorando di Princeton, John Forbes Nash Jr., che nel 1950 pubblica una nota di pagina e mezza sui Proceedings of the National Academy of Sciences: Equilibrium points in n-person games. Generalizza il minimax di von Neumann a giochi a n giocatori non necessariamente a somma zero. Per ogni gioco finito esiste almeno un punto di equilibrio in strategie miste. Il concetto di “equilibrio di Nash” prende il suo nome da quella nota.

Negli anni successivi, Reinhard Selten introduce il subgame perfect equilibrium (1965) per raffinare il Nash in giochi sequenziali, e John Harsanyi (1967-68) estende la teoria a giochi con informazione incompleta. I tre vinceranno il premio Nobel per l’economia nel 1994, quasi cinquant’anni dopo i loro lavori fondativi.

Nel mondo dell’AI, la teoria dei giochi entra presto: il programma di scacchi di Claude Shannon (1950) si basa già implicitamente sul minimax. Negli anni Novanta, Gerald Tesauro mostra con TD-Gammon che una rete neurale allenata in self-play può raggiungere il top mondiale a backgammon — un gioco. AlphaGo (2016) e AlphaZero (2017) di DeepMind generalizzano l’idea. Nel 2014 Ian Goodfellow inventa le Generative Adversarial Networks costruendo esplicitamente il loro training come gioco minimax. Nel 2022 il team FAIR Diplomacy di Meta presenta CICERO, il primo agente di livello umano in Diplomacy, un gioco a 7 giocatori, semi-cooperativo, a informazione incompleta. Il filo conduttore è chiaro: ogni volta che si vuole far emergere comportamento strategico in un sistema artificiale, si finisce a parlare la lingua della teoria dei giochi.

flowchart LR
    GT["Teoria dei giochi<br/>giocatori, azioni, payoff, equilibrio"]
    GT --> GAN["Training GAN<br/>minimax G vs D"]
    GT --> SP["Self-play<br/>AlphaZero, TD-Gammon, OpenAI Five"]
    GT --> RLHF["RLHF / Nash Learning<br/>from preferences"]
    GT --> ADV["Robustezza adversarial<br/>saddle point min-max"]
    GT --> MD["Mechanism design<br/>Vickrey, VCG, agent platform"]

Figura 1 — concept graph: pillars (definition, equilibrium, examples) and AI bridges (GAN, self-play, RLHF, adversarial, mechanism design)

Va detto subito che la storia non è lineare. Tra il 1928 di von Neumann e il 1950 di Nash passano ventidue anni in cui la teoria fa pochi progressi: la guerra, le difficoltà di trovare un linguaggio matematico adatto, lo scetticismo degli economisti tradizionali. È il trattato di Princeton del 1944 che cambia il clima e attira matematici e economisti giovani — Kenneth Arrow, Gerard Debreu, Lloyd Shapley, Martin Shubik, lo stesso Nash. Negli anni Sessanta Selten e Harsanyi raffinano la teoria; negli anni Settanta-Ottanta Aumann formalizza common knowledge e ripetuti; negli anni Novanta nasce l’algoritmica dei giochi (Papadimitriou e altri). Negli anni 2010 il deep learning importa massicciamente il vocabolario.

Per il libro, l’attesa di vent’anni tra minimax e Nash è un promemoria utile: i risultati di esistenza arrivano molto prima dei risultati operativi. Esistenza di Nash (1950) precede di sessant’anni la PPAD-completezza (2009) che ne pone i limiti computazionali. Esistenza di equilibrio in GAN (Goodfellow 2014) precede di anni la comprensione di perché in pratica il training oscilla. Sistemi che funzionano “in equilibrio” e sistemi che convergono “all’equilibrio” sono cose diverse, e la distinzione è centrale per chi progetta agenti.

Tassonomia rapida

Prima di entrare nel formalismo conviene fissare una tassonomia minima. La useremo come bussola in tutta la Parte V.

Cooperativo vs non-cooperativo. Nei giochi cooperativi i giocatori possono stipulare accordi vincolanti e formare coalizioni; l’oggetto di studio è come dividere il valore creato (Shapley value, core, Nash bargaining). Nei giochi non-cooperativi gli accordi non sono enforceable, ogni giocatore agisce per sé; l’oggetto di studio sono gli equilibri (Nash, minimax). La maggior parte della teoria moderna parte da non-cooperativo, perché è il caso più generale e perché molti scenari “cooperativi” si possono rileggere come non-cooperativi con strutture esplicite di comunicazione e contratti.

Simultaneo vs sequenziale. Simultaneo: tutti scelgono in parallelo, senza osservare le scelte altrui. Forma normale. Esempio: morra cinese, asta a busta chiusa. Sequenziale: i giocatori si alternano, ognuno osserva (parte di) ciò che è successo prima. Forma estesa. Esempio: scacchi, contrattazione a turni.

Informazione perfetta vs imperfetta. In informazione perfetta ogni giocatore vede tutto lo storico delle azioni quando muove (scacchi, Go). In informazione imperfetta ci sono mosse nascoste o stati non osservabili (poker, battaglia navale). La forma estesa rappresenta l’imperfezione con information set: insiemi di nodi indistinguibili.

Informazione completa vs incompleta. Completa: le regole del gioco, inclusi i payoff degli altri, sono common knowledge. Incompleta: c’è incertezza sui “tipi” degli avversari (le loro valutazioni, costi, preferenze). Harsanyi (1967-68) ha mostrato come ridurre informazione incompleta a imperfetta introducendo una mossa iniziale della Natura che estrae i tipi.

Somma zero vs somma generale. In somma zero la torta è fissa: quello che vinco, lo perdi. In somma generale la torta varia con le scelte: la cooperazione può creare o distruggere valore. Il dilemma del prigioniero è a somma generale (non zero): il payoff totale è -2 a (C, C), -3 a (C, D), -4 a (D, D).

Gioco one-shot vs ripetuto. One-shot: si gioca una volta, fine. Ripetuto: si gioca molte volte, con memoria delle interazioni passate. Nei giochi ripetuti emergono fenomeni che il caso one-shot non può catturare: reputazione, punizione, cooperazione spontanea. Il “Folk Theorem” mostra che in ripetuto infinito quasi qualunque profilo individualmente razionale è sostenibile come equilibrio.

Queste dimensioni sono ortogonali: un gioco è una combinazione di scelte lungo ciascun asse. “Scacchi” = non-cooperativo, sequenziale, informazione perfetta, informazione completa, somma zero, one-shot per partita. “RLHF visto come gioco di preferenze” = non-cooperativo, simultaneo (in formulazione standard), informazione imperfetta sui tipi, somma zero su preferenze pairwise.

L’intuizione

Prima del formalismo, due angoli per arrivare a “cosa è un gioco” da direzioni diverse.

Primo angolo: decisione interdipendente

Quando decidi da solo cosa pranzare, il risultato dipende solo da te (e magari dalla pioggia). Quando giochi a scacchi, il risultato dipende da te e dall’avversario. Quando partecipi a un’asta, dipende dalla tua offerta e da quelle degli altri. Quando alleni un GAN, il successo del generatore dipende da quanto bene il discriminatore distingue.

Il salto concettuale è questo: nelle decisioni parametriche (un singolo agente contro un ambiente fisso) il problema è “scegliere il meglio dato l’ambiente”. Nelle decisioni strategiche il problema è “scegliere il meglio dato che l’altro sta scegliendo il meglio dato che io sto scegliendo il meglio dato che…”. L’interdipendenza apre un loop di ragionamento che, se non lo chiudiamo con cura, diverge. La teoria dei giochi è essenzialmente la cassetta degli attrezzi per chiudere quel loop.

Secondo angolo: la matrice come riassunto

Immagina di voler descrivere un’interazione strategica a un alieno che non sa cosa è un gioco. Cosa devi dirgli al minimo? Devi dirgli chi gioca, cosa può fare, e quale è il risultato per ciascuno per ogni combinazione di scelte. Se ci sono due giocatori e ciascuno ha un piccolo numero di opzioni, puoi metterlo tutto in una tabella: righe = scelte del primo, colonne = scelte del secondo, celle = coppia di payoff. Quella tabella è il gioco, in forma normale. Tutto il resto della teoria si costruisce ragionando su tabelle (quando è semplice) o su alberi (quando ci sono turni e informazione asimmetrica).

Questa è la potenza dell’astrazione: una negoziazione internazionale, un’asta online, un duello di pistoleri, un GAN training step, una partita di morra cinese — se hai isolato giocatori, azioni e payoff, hai un gioco. Tutto il vocabolario successivo (equilibrio, dominanza, minimax) opera su questa struttura, indipendentemente da cosa rappresenta nel mondo.

La meccanica

Costruiamo le definizioni in ordine, da quelle minimali a quelle che servono nei capitoli successivi.

Gioco in forma normale

Un gioco in forma normale (o forma strategica) è una tripla:

G = (N, (A_i){i ∈ N}, (u_i){i ∈ N})

dove

• N = {1, 2, …, n} è l’insieme dei giocatori.
• A_i è l’insieme delle azioni disponibili al giocatore i.
• u_i: A_1 × A_2 × … × A_n → ℝ è la funzione di payoff (o utilità) del giocatore i: associa a ogni profilo di azioni un numero reale che rappresenta quanto è desiderabile per i quel risultato.

Un profilo di azioni è una n-upla a = (a_1, …, a_n) con a_i ∈ A_i. Notazione tradizionale: a_{-i} è la lista delle azioni di tutti tranne i. Quindi possiamo scrivere u_i(a) come u_i(a_i, a_{-i}).

Quando n = 2 e A_1, A_2 sono finiti, il gioco si rappresenta come una matrice (o due matrici sovrapposte, una per ciascun payoff). Da qui il nome forma “matriciale”.

Strategie pure e miste

Una strategia pura è una scelta deterministica di azione: σ_i = a_i con probabilità 1.

Una strategia mista è una distribuzione di probabilità sulle strategie pure: σ_i ∈ Δ(A_i), dove Δ(A_i) è il simplesso delle distribuzioni su A_i. Se A_i = {a, b, c}, una strategia mista può essere “a con probabilità 0.5, b con 0.3, c con 0.2”.

Il payoff atteso sotto un profilo di strategie miste è la media pesata:

u_i(σ_1, …, σ_n) = Σ_a [Π_j σ_j(a_j)] u_i(a)

dove la somma è su tutti i profili di azioni pure.

Le strategie miste non sono un trucco matematico: in molti giochi sono l’unico modo di non farsi prevedere. Pensa al portiere che para un rigore: se sceglie sempre lo stesso lato, il calciatore lo sfrutta. La randomizzazione è razionale.

Forma estesa

In giochi sequenziali, la forma normale comprime troppe informazioni. Si usa la forma estesa: un albero in cui

• ogni nodo interno è uno stato di decisione, etichettato con il giocatore che muove;
• ogni arco uscente è un’azione possibile;
• ogni foglia è un esito, etichettato con il vettore dei payoff.

In presenza di informazione imperfetta, si introducono information set: insiemi di nodi che il giocatore non può distinguere quando deve muovere (perché non ha osservato la mossa precedente, per esempio).

Nota concettuale importante: ogni gioco in forma estesa ha una forma normale equivalente, ottenuta definendo “strategia” come funzione completa che a ogni information set di un giocatore associa un’azione. Il viceversa non è banale.

Equilibrio di Nash

Definizione. Un profilo di strategie σ* = (σ_1, …, σ_n) è un equilibrio di Nash se, per ogni giocatore i e per ogni strategia alternativa σ_i:

u_i(σ_i, σ{-i}) ≥ u_i(σ_i, σ*{-i})

In parole: nessun giocatore può migliorare deviando unilateralmente, dati i comportamenti degli altri. È un punto fisso della correspondenza di miglior risposta.

Teorema (Nash 1950, 1951). Ogni gioco finito (numero finito di giocatori, numero finito di azioni per giocatore) ammette almeno un equilibrio di Nash in strategie miste.

Questo è un TEOREMA di esistenza, dimostrato applicando il teorema del punto fisso di Kakutani (un risultato di analisi convessa) alla correspondenza di miglior risposta. Non è una garanzia di unicità: molti giochi hanno più equilibri.

Minimax e giochi a somma zero

Un gioco a due giocatori è a somma zero se u_1(a) + u_2(a) = 0 per ogni profilo a. Quello che vince uno, lo perde l’altro. Esempi: scacchi, Go, poker testa a testa (rispetto al guadagno attorno al tavolo), penalty shoot-out se contiamo solo il singolo tiro, GAN training (in formulazione standard).

Teorema minimax (von Neumann 1928). In un gioco finito a due giocatori a somma zero esiste un valore v del gioco tale che

max_{σ_1} min_{σ_2} u_1(σ_1, σ_2) = min_{σ_2} max_{σ_1} u_1(σ_1, σ_2) = v

Ogni coppia (σ_1, σ_2) che realizza il doppio ottimo è un equilibrio di Nash, e per giochi a somma zero a due giocatori i due concetti coincidono. Questo è il teorema che apre tutta la storia: prima di Nash, c’era già un caso fondamentale risolto.

L’intuizione: in un gioco a somma zero, il giocatore 1 può garantirsi v giocando minimax (massimizzando quanto può garantirsi al peggio); il giocatore 2 può limitare la perdita di 1 a v giocando minimax dal suo lato. I due ottimi coincidono.

Dominanza

Una strategia σ_i è strettamente dominata se esiste σ’i tale che u_i(σ’i, σ{-i}) > u_i(σ_i, σ{-i}) per ogni σ_{-i}: c’è qualcosa di sempre meglio.

Una strategia σ_i è dominante se per ogni σ’i ≠ σ_i e ogni σ{-i} vale u_i(σ_i, σ_{-i}) ≥ u_i(σ’i, σ{-i}): non c’è niente di meglio.

L’eliminazione iterata di strategie strettamente dominate (IESDS) è una procedura: rimuovi le dominate per ciascun giocatore, ripeti sul gioco ridotto. Se il processo converge a un singolo profilo, quello è l’unico equilibrio di Nash. Funziona nel dilemma del prigioniero. In generale può non terminare con un singolo profilo.

Miglior risposta

Il concetto operativo che lega tutto è quello di miglior risposta (best response). Data una scelta degli avversari σ_{-i}, la miglior risposta del giocatore i è l’insieme

BR_i(σ_{-i}) = arg max_{σ_i ∈ Δ(A_i)} u_i(σ_i, σ_{-i})

Un equilibrio di Nash è un profilo in cui ogni giocatore sta giocando una miglior risposta a tutti gli altri. Un punto fisso della correspondenza congiunta BR = (BR_1, …, BR_n).

Questa formulazione è preziosa perché trasforma il problema di trovare un equilibrio in un problema di punto fisso, e perché molti algoritmi pratici sono varianti di “iterazione di miglior risposta”: ogni giocatore aggiorna la sua strategia rispondendo al meglio alle frequenze osservate degli altri. Il fictitious play di Brown (1951), il regret matching di Hart-Mas-Colell (2000), la procedura di self-play in AlphaZero, sono tutti, a vari livelli di sofisticazione, iterazioni di miglior risposta.

In giochi a somma zero a due giocatori con strategie miste, fictitious play converge in valore atteso alla strategia minimax. In giochi più generali la convergenza non è garantita: si può oscillare attorno a equilibri o divergere.

Pseudocodice: ricerca di equilibri di Nash in 2x2

# Gioco 2x2: matrici di payoff A (per giocatore 1) e B (per giocatore 2)
# Cerchiamo equilibri puri ed eventualmente l'unico misto interno.

def equilibri_2x2(A, B):
    eq_puri = []
    for i in [0, 1]:
        for j in [0, 1]:
            # i è la riga di 1, j è la colonna di 2.
            # 1 non vuole deviare: A[i][j] >= A[1-i][j]
            # 2 non vuole deviare: B[i][j] >= B[i][1-j]
            if A[i][j] >= A[1-i][j] and B[i][j] >= B[i][1-j]:
                eq_puri.append((i, j))

    # Equilibrio misto: 1 gioca riga 0 con probabilità p, 2 gioca col 0 con prob q.
    # Indifferenza per 2: B[0][0]*p + B[1][0]*(1-p) == B[0][1]*p + B[1][1]*(1-p)
    # da cui p = (B[1][1] - B[1][0]) / (B[0][0] - B[0][1] + B[1][1] - B[1][0])
    # Indifferenza per 1: simmetrica con A.
    den_p = (B[0][0] - B[0][1]) + (B[1][1] - B[1][0])
    den_q = (A[0][0] - A[1][0]) + (A[1][1] - A[0][1])
    eq_misto = None
    if den_p != 0 and den_q != 0:
        p = (B[1][1] - B[1][0]) / den_p
        q = (A[1][1] - A[0][1]) / den_q
        if 0 < p < 1 and 0 < q < 1:
            eq_misto = (p, q)

    return eq_puri, eq_misto

Questo è un caso giocattolo: nel caso generale, calcolare un equilibrio di Nash è PPAD-completo (Daskalakis-Goldberg-Papadimitriou 2009). Lo richiamiamo nella sezione “Dove si rompe”.

Utilità nel senso di von Neumann-Morgenstern

Una nota tecnica spesso glissata: parlare di “payoff” come numero presuppone che gli esiti siano misurabili in modo coerente. Von Neumann e Morgenstern (1944, appendice tecnica) hanno mostrato che, sotto un insieme di assiomi di coerenza sulle preferenze tra lotterie (completezza, transitività, continuità, indipendenza), esiste una funzione di utilità u che rappresenta le preferenze, e u è unica a meno di trasformazioni affini positive.

Questo è importante perché spiega cosa garantiamo (e cosa no) usando payoff numerici. Garantiamo che il giocatore preferisce risultati con utilità più alta. Non garantiamo che differenze di utilità siano confrontabili tra giocatori (utility non è interpersonalmente confrontabile in vNM). Per teoria dei giochi non-cooperativa standard questo basta. Per teoria cooperativa, dove si confrontano valori tra giocatori (Shapley value), servono assunzioni aggiuntive.

Per agenti AI, questa tassonomia è importante: una funzione di reward in RL è di fatto una funzione di utilità vNM. La cross-entropy loss in supervised learning non lo è (non rappresenta preferenze su esiti, ma una distanza statistica). Quando si parla di “payoff” di un LLM si sta facendo una scelta interpretativa: di solito è una proxy reward o una preferenza pairwise indotta dal training.

Esempi

Tre esempi eterogenei, scelti per illustrare aspetti diversi.

Esempio 1 (numerico): dilemma del prigioniero per dominanza

Due complici sono interrogati separatamente. Ciascuno può cooperare con l’altro (tacere, C) o defectare (incolpare l’altro, D). Anni di prigione (numero negativo come payoff):

	C	D
C	(-1,-1)	(-3, 0)
D	( 0,-3)	(-2,-2)

Risoluzione per dominanza. Per il giocatore 1: confronto la riga C con la riga D, colonna per colonna. Se 2 gioca C, 1 ha -1 con C, 0 con D → D è meglio. Se 2 gioca D, 1 ha -3 con C, -2 con D → D è meglio. Quindi D domina strettamente C per 1. Stesso ragionamento per 2. Eliminate le dominate, resta solo (D, D) con payoff (-2, -2).

Tragedia: (C, C) sarebbe Pareto-superiore con (-1, -1). Ma è instabile, perché ogni giocatore preferisce defectare. La razionalità individuale conduce a un esito collettivamente inferiore. Questo è il template logico di tragedie dei comuni, free-riding, climate change inazione, arms race.

Esempio 2 (codice): fictitious play su matching pennies

Il gioco matching pennies non ha equilibri puri. Vediamo con un algoritmo classico, fictitious play (Brown 1951), come due giocatori che giocano la miglior risposta alla frequenza empirica delle mosse altrui convergono all’equilibrio misto 50/50.

import numpy as np

# Payoff giocatore 1 (riga). Giocatore 2 ha payoff -A.
# Righe e colonne: 0 = T (testa), 1 = C (croce).
A = np.array([[ 1, -1],
              [-1,  1]])

# Conteggi empirici delle azioni avversarie (Laplace prior 1).
count1 = np.array([1, 1])  # cosa 2 ha giocato finora
count2 = np.array([1, 1])  # cosa 1 ha giocato finora
hist1, hist2 = [], []

for t in range(20000):
    # Miglior risposta di 1 contro frequenza di 2
    freq2 = count1 / count1.sum()
    a1 = np.argmax(A @ freq2)        # massimizza payoff atteso

    # Miglior risposta di 2 contro frequenza di 1
    freq1 = count2 / count2.sum()
    a2 = np.argmin(freq1 @ A)        # minimizza payoff di 1 = massimizza il suo

    count2[a1] += 1
    count1[a2] += 1
    hist1.append(a1)
    hist2.append(a2)

print("Frequenza 1:", np.bincount(hist1) / len(hist1))
print("Frequenza 2:", np.bincount(hist2) / len(hist2))

Le frequenze empiriche convergono a (0.5, 0.5) per entrambi, riproducendo l’equilibrio misto teorico. È un esempio di come una procedura di apprendimento (best response dynamics) ricostruisce l’equilibrio senza che nessun agente “sappia” la soluzione analitica. Un nesso forte con il self-play di AlphaZero, che è anch’esso una forma sofisticata di iterazione di miglior risposta.

Esempio 3 (scenario reale): GAN come gioco minimax

Goodfellow et al. (2014) definiscono esplicitamente le Generative Adversarial Networks come gioco minimax tra due reti. Sia G(z; θ_G) una rete che prende rumore z e produce dati sintetici, e D(x; θ_D) una rete che, dato un input x, restituisce la probabilità che x venga dalla distribuzione vera.

Il valore del gioco è

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

D vuole massimizzare V (distinguere bene), G vuole minimizzarlo (ingannare D). Il problema è min_G max_D V(D, G).

Il paper dimostra che, sotto capacità infinita e ottimizzazione globale, l’equilibrio del gioco coincide con G che genera esattamente p_data e D che restituisce sempre 1/2. Questa è EQUIVALENZA, non analogia: il framework teorico è importato pari pari.

In pratica si fa SGD alternato — non si raggiunge necessariamente l’equilibrio. Si osservano oscillazioni, mode collapse, training instabile. La teoria predice esistenza di Nash; non garantisce convergenza di un algoritmo di ottimizzazione locale a esso. È una delle ragioni per cui modelli di diffusione (che evitano la struttura adversarial) hanno preso il sopravvento per la generazione di immagini.

Figura in preparazione

GAN as minimax game: G outputs samples, D scores real vs fake, V(D, G) shown as the saddle of the loss landscape

Esempio 3-bis (forma estesa): ultimatum game

Per illustrare la forma estesa, l’ultimatum game. A propone una divisione di 100 euro: (x, 100 - x) con x ∈ {1, 2, …, 99}. B osserva la proposta e accetta o rifiuta. Se accetta, payoff (x, 100 - x). Se rifiuta, payoff (0, 0).

L’albero ha 99 nodi al livello 1 (le proposte di A), e ad ogni nodo discende una scelta binaria di B (accetta / rifiuta). Backward induction: per ogni proposta x, B confronta 100 - x con 0; accetta se 100 - x > 0, cioè per ogni x ≤ 99. Sapendo questo, A propone x = 99 e B accetta. Subgame perfect equilibrium: (99, 1).

Esperimenti reali — replicati in dozzine di varianti culturali — mostrano che B rifiuta sistematicamente offerte sotto il 30% circa, e che A tipicamente offre 40-50%. La razionalità sequenziale stretta è un cattivo modello descrittivo del comportamento umano. Per agent AI il punto è doppio: i nostri agenti possono incorporare nozioni di equità o reciprocità (utile in coordinazione), oppure essere “perfettamente razionali” in senso teoria-giochistico ma rischiare di essere puniti da counterpart umani che applicano norme sociali. La definizione del payoff implicito è una scelta di design.

Esempio 4 (di confine): battle of the sexes

Aggiungiamo un quarto esempio per illustrare la molteplicità degli equilibri. Due partner devono decidere dove uscire stasera. Lui preferisce la partita, lei l’opera, ma entrambi preferiscono uscire insieme che soli.

	Opera	Partita
Opera	(2, 1)	(0, 0)
Partita	(0, 0)	(1, 2)

Equilibri puri: (Opera, Opera) e (Partita, Partita). Entrambi sono equilibri di Nash: nessuno vuole deviare unilateralmente. C’è anche un equilibrio in strategie miste: lei gioca Opera con probabilità 2/3, lui gioca Partita con probabilità 2/3 (calcolo come nello pseudocodice precedente).

Quale equilibrio prevale? La teoria classica non lo dice. Schelling propose il concetto di focal point: un equilibrio si seleziona perché è “saliente” per ragioni culturali, storiche, psicologiche, non strettamente teoria-giochistiche. Nei sistemi multi-agente AI la selezione di equilibrio resta un problema aperto: due agenti LLM che devono coordinarsi su una convenzione hanno bisogno di qualche meccanismo esterno (linguaggio condiviso, leader designato, prior comune) per non oscillare.

Applicazioni pratiche

La grammatica del gioco si ritrova, esplicita o implicita, in molti pezzi di AI moderna.

Multi-agent reinforcement learning. Quando più agenti agiscono in un ambiente condiviso, il problema non è più un MDP ma un gioco stocastico (Shapley 1953, ripreso da Littman 1994). Algoritmi come Nash Q-learning cercano equilibri ad ogni step. La cooperazione è studiata nel paradigma centralised training, decentralised execution.

Self-play e AlphaZero. Self-play in un gioco a somma zero a informazione perfetta è una forma di iterazione di miglior risposta. AlphaZero (Silver et al. 2017) gioca contro versioni di se stesso, allena la rete sui risultati, ripete. Il limite teorico è una strategia minimax. Empiricamente, in Go e scacchi, supera sensibilmente il livello umano.

flowchart LR
  A[Policy corrente] --> B[Genera partite via self-play]
  B --> C[Raccolta traiettorie ed esiti]
  C --> D[Aggiorna policy via target supervisionato / RL]
  D --> A
  D --> E[Snapshot policy come avversario]
  E --> B

Figura 5 — pipeline di training self-play come gioco asimmetrico tra una policy corrente e snapshot precedenti, con raccolta traiettorie e update via target supervisionato

RLHF e preferenze pairwise. Recentemente Munos et al. (2024) hanno riformulato l’allineamento da preferenze come Nash Learning from Human Feedback: trovare una policy il cui output è indistinguibile, in preferenza pairwise, da una policy ideale. È un gioco a somma zero su preferenze. Frame teoria-giochistico esplicito al posto del classico reward-modeling + PPO.

Adversarial robustness. Il training adversarialmente robusto (Madry et al. 2017) è formalizzato come saddle point min_θ E[max_δ L(f_θ(x + δ), y)]. Il modello vuole minimizzare la loss; l’avversario vuole massimizzarla scegliendo perturbazioni. Minimax di von Neumann al servizio della robustezza.

CICERO e Diplomacy. Il sistema Meta 2022 combina LLM per il dialogo con planning strategico in un gioco a 7 giocatori, semi-cooperativo, a informazione incompleta con negoziazioni. È il primo agente AI a giocare Diplomacy a livello umano, e il primo caso pubblico in cui un LLM viene esplicitamente integrato in un loop di teoria dei giochi.

Mechanism design per agent platform. Quando si progettano marketplace dove agenti AI fanno bid per task, il problema è scegliere meccanismi truthful (Vickrey-Clarke-Groves) per evitare manipolazioni strategiche. Questa branca, mechanism design, è teoria dei giochi al contrario: dato un esito desiderato, progetta le regole. Sarà centrale quando gli agent diventeranno consumatori di servizi computazionali a pagamento.

Auction design per ad serving e API pricing. I marketplace digitali — Google AdWords storico, real-time bidding, exchange di compute — sono progettati intorno a meccanismi d’asta basati su Vickrey o varianti (GSP, generalized second price). Quando si progetta una piattaforma di agent che fanno bid per task computazionali, il pattern si ripete: scegli il meccanismo, calcola l’equilibrio bayesiano sotto il meccanismo, ottimizza il meccanismo per l’obiettivo della piattaforma (revenue, qualità del match, equità).

Coordination games e convenzioni multi-agente. Quando più agenti devono coordinarsi su un protocollo, una convenzione di naming, un linguaggio condiviso, siamo in un coordination game. La teoria predice equilibri multipli; la pratica richiede meccanismi di selezione (focal point, leader, evolutionary dynamics). Per multi-agent system AI, scegliere come ottenere coordinazione (linguaggio fisso, emergente, indotto da training) è un problema di progetto che la teoria dei giochi inquadra ma non risolve.

Negoziazione multi-LLM. Diversi lavori del 2024-2025 esplorano LLM che negoziano tra loro su task, risorse, ruoli (ad esempio nei sistemi swarm tipo CrewAI). Modellare queste interazioni come giochi è utile per analizzare stabilità e cooperazione, anche se la razionalità degli LLM è solo approssimativa.

Dove si rompe

La teoria dei giochi è elegante. Le sue assunzioni, esaminate da vicino, sono forti. Quando si usa per progettare o analizzare sistemi AI, va maneggiata con consapevolezza.

Razionalità perfetta. I giocatori sono assunti razionali nel senso vNM (von Neumann-Morgenstern): hanno una funzione di utilità coerente sui risultati, e massimizzano l’utilità attesa. Esperimenti decennali (Kahneman-Tversky, Thaler, Gigerenzer) mostrano che gli umani non sono così. L’ultimatum game è il caso scolastico: la teoria predice (99, 1), gli esperimenti mostrano rifiuti sotto il 30%. L’agente umano è razionale-limitato, sociale, emotivo. Estendere a “agenti AI” è ancora più scivoloso: un LLM non ha una funzione di utilità esplicita.

Common knowledge. Spesso si assume che le regole, le razionalità reciproche, le credenze, siano comuni knowledge: non solo io le conosco, ma so che tu le conosci, e tu sai che io so, e così via all’infinito. Aumann (1976) ha formalizzato questo concetto. È un’idealizzazione: nei sistemi multi-agente reali, le credenze sono limitate e asimmetriche, e i meta-livelli si troncano in fretta.

Calcolare un Nash è hard. Daskalakis, Goldberg e Papadimitriou hanno mostrato nel 2009 che trovare un equilibrio di Nash è PPAD-completo, anche per giochi a due giocatori a somma generale. Significa: non esiste (sotto ipotesi standard di teoria della complessità) un algoritmo polinomiale generale. In pratica, gli agenti reali non possono garantire di operare in equilibrio. Il fatto che Nash esista (per il teorema del 1951) non significa che sia computabile in tempo ragionevole.

Equilibri multipli e selezione. Battle of the sexes ha tre equilibri. In un gioco generico ne possono esistere molti. La teoria classica non dice quale scegliere. Schelling ha proposto i focal point (soluzioni “salienti” sociologicamente). Harsanyi-Selten hanno proposto criteri di selezione. La evolutionary stability (Maynard Smith) introduce un setting evolutivo. Nessuno è pienamente soddisfacente. Per agenti AI in ambienti aperti, la selezione di equilibrio è un problema vero e non risolto.

Payoff non scalare e non osservabile. La teoria assume payoff numerici per ogni profilo. Nei sistemi reali, le utilità sono multi-obiettivo, parzialmente ordinate, soggette a incertezza, opportunisticamente revisionate. Un agent LLM che “negozia” non massimizza un numero: produce token che ottimizzano una loss che approssima preferenze umane. Modellarlo come player teoria-giochistico è utile come prima approssimazione, va etichettato come ANALOGIA.

Cooperazione vs competizione. Il framework non-cooperativo (Nash) assume che ognuno per sé. La realtà multi-agente — incluso molti scenari AI — richiede coalizioni, accordi, contratti vincolanti. La teoria cooperativa (Shapley value, Nash bargaining solution, core) offre strumenti, ma il ponte non-cooperativo / cooperativo (Nash program) è ancora aperto.

GAN training instabile. Il teorema garantisce esistenza di un equilibrio. Non garantisce che SGD locale alternato vi converga. In pratica, GAN training mostra oscillazioni, divergenze, mode collapse. È stato uno dei motori dello spostamento verso modelli di diffusione, che non hanno una struttura adversarial e sono più stabili da allenare.

LLM come “agente razionale” è ANALOGIA, non equivalenza. Quando diciamo che due LLM “negoziano” o “giocano un gioco”, stiamo facendo una metafora utile. L’LLM non massimizza esplicitamente un payoff; produce token che hanno una distribuzione condizionata indotta dal training. Possiamo modellare il sistema come gioco e ottenere previsioni utili — ma non assumere razionalità in senso stretto. È un trabocchetto frequente nei lavori che applicano teoria dei giochi a “agenti LLM”.

Razionalità di gruppo vs individuale. Il dilemma del prigioniero illustra il fenomeno classico: la razionalità individuale (defect domina) porta a un esito Pareto-inferiore rispetto alla razionalità di gruppo (cooperare paga di più collettivamente). Nei sistemi multi-agente AI il problema è simmetrico: agenti ottimizzati ciascuno per il proprio obiettivo possono produrre esiti collettivamente disastrosi (free-riding, race to the bottom, competizione su risorse condivise). Mechanism design e training congiunto (centralized training, decentralised execution) sono tentativi di chiudere il gap.

Equilibrio non implica buon comportamento. Anche quando un sistema raggiunge un equilibrio, l’equilibrio può essere socialmente cattivo (price of anarchy alto). Tragedy of the commons, collusion in oligopoli, race conditions in coordination — sono tutti equilibri stabili. Per progettisti di sistemi AI, questo è un avviso operativo: dimostrare che un sistema è in equilibrio non basta, bisogna anche valutare la qualità dell’equilibrio rispetto a un benchmark sociale o di sistema.

Informazione incompleta e bayesianità. Harsanyi ha esteso la teoria a tipi privati e equilibri bayesiani. È elegante e potente ma richiede di specificare distribuzioni a priori sui tipi avversari. Nei sistemi reali queste distribuzioni sono raramente note. Si ricorre a robustness teoria-giochistica, regret minimization, no-regret learning — strumenti diversi che cerchiamo nei capitoli sulla complessità computazionale degli equilibri.

Backward induction e paradosso della catena. In un gioco sequenziale finito a informazione perfetta, la backward induction (algoritmo che parte dalle foglie dell’albero e risale calcolando la mossa ottima ad ogni nodo) produce un subgame perfect equilibrium (Selten 1965). È elegante e potente: scacchi, in linea di principio, si risolve così. Ma esistono casi in cui produce risultati controintuitivi. Il paradosso della catena (centipede game di Rosenthal 1981): due giocatori si alternano, ad ogni turno ciascuno può prendere e fermarsi, oppure passare al successivo lasciando crescere la torta. Backward induction predice che il primo giocatore prenda subito al primo turno. Esperimenti mostrano che giocatori reali passano molte volte. Razionalità sequenziale stretta è troppo forte come modello descrittivo, e in agenti AI introduce questioni di robustezza: un agente “perfettamente razionale” può perdere contro uno meno razionale ma più cooperativo se il payoff strutturale lo premia.

Discontinuità tra teoria e algoritmi. Un punto sottile ma importante. La teoria classica dimostra esistenza di equilibri, ma i risultati di esistenza usano strumenti non costruttivi (Kakutani, Brouwer). Trovare effettivamente l’equilibrio è un problema separato, e per giochi a somma generale è PPAD-completo. Questo significa che algoritmi convergenti (fictitious play, regret matching, no-regret learning) garantiscono convergenza solo per classi specifiche di giochi (somma zero, congestion games, certi giochi potenziali). Quando si applica teoria dei giochi a un sistema AI, bisogna chiedersi: la classe di gioco in cui sono garantisce la convergenza dell’algoritmo che sto usando?

Approssimazione invece di equilibrio. Una via pragmatica per sistemi AI è abbandonare l’idea di trovare un equilibrio esatto e accontentarsi di equilibri approssimati. Un ε-equilibrio è un profilo in cui nessuno può migliorare di più di ε deviando. È molto più trattabile computazionalmente. La stragrande maggioranza dei sistemi multi-agent reali, incluso AlphaGo e i suoi derivati, raggiungono approssimazioni di Nash, non equilibri esatti. Questo è ragionevole ma va dichiarato.

Solution concepts oltre Nash. Nash è il concetto canonico, ma non l’unico. Correlated equilibrium (Aumann 1974) generalizza Nash permettendo correlazione fra le strategie tramite un segnale comune; è più facile da raggiungere computazionalmente (poly-time per giochi finiti), ed è l’oggetto naturale dei algoritmi di no-regret learning. Coarse correlated equilibrium è ancora più rilassato. Per progettisti di multi-agent system, sapere che non bisogna necessariamente puntare a Nash — e che no-regret è raggiungibile in tempo polinomiale — è un’informazione operativa importante.

Tre frame per leggere un sistema AI come gioco

Per chiudere il cerchio prima dei collegamenti, tre frame ricorrenti che ti capiterà di vedere applicati a sistemi AI nella letteratura recente.

Frame 1: Adversarial training come saddle point. Quando alleniamo un modello robusto, c’è un avversario implicito che cerca esempi che lo ingannano. Il problema è min-max sulla loss. Lo stesso schema appare in adversarial robustness, GAN, robust RL, alcune formulazioni di RLHF. Pattern: due processi accoppiati, uno minimizza, uno massimizza, gradiente alternato. Quando funziona, abbiamo trovato un punto sella; quando oscilla, ci stiamo allontanando dall’equilibrio. Il vocabolario del gioco aiuta a capire perché.

Frame 2: Self-play come iterazione di best response. Quando un agente impara giocando contro copie di se stesso (TD-Gammon, AlphaZero, OpenAI Five, AlphaStar), siamo dentro una versione raffinata di best response dynamics in un gioco a somma zero. La teoria assicura che, in giochi a somma zero a due giocatori e con esplorazione, certe procedure convergono al valore minimax. Pattern: uno spazio di policy, un meccanismo di campionamento di avversari (uniforme, prioritized, league play), una procedura di aggiornamento. Quando il gioco è non a somma zero o multi-player, le garanzie si indeboliscono.

Frame 3: Mechanism design come gioco al contrario. Il progettista sceglie le regole; gli agenti scelgono le strategie dato il regolamento; l’esito è la composizione delle scelte. Il progettista vuole che l’esito massimizzi un obiettivo (efficienza, ricavo, equità) sotto vincoli di incentive compatibility (gli agenti non hanno interesse a barare) e participation (gli agenti hanno interesse a partecipare). Pattern: scegli regole; calcola equilibrio sotto le regole; ottimizza le regole per l’obiettivo. Vickrey auction è il caso scolastico. Per agent platform AI, framework per orchestration di tool, marketplace di model routing, è il riferimento naturale.

Collegamenti

• probabilita-base: le strategie miste sono distribuzioni di probabilità sulle azioni; il payoff atteso è un valore atteso. Senza il vocabolario di probabilità, la teoria dei giochi non si scrive.
• bayes-base: nei giochi bayesiani (informazione incompleta) Harsanyi ha mostrato che il framework è essenzialmente Bayes su tipi privati. La teoria del 1967-68 si appoggia all’apparato bayesiano.
• discesa-gradiente: il training di GAN, di policy in RL multi-agente, di adversarial robustness, è SGD su problemi minimax. La discesa di gradiente alternata è lo strumento computazionale standard per cercare equilibri.
• entropia-cross-entropy: il valore atteso di un GAN ha la forma di una cross-entropy, il che permette di leggere D come classificatore binario e G come distribuzione che minimizza la divergenza dai dati.
• somma-zero-non-zero (in preparazione): approfondisce la distinzione fondamentale, dilatando il minimax e mostrando come la struttura di payoff cambi le proprietà dei giochi.
• equilibrio-nash (in preparazione): trattazione dedicata all’equilibrio di Nash, alla sua intuizione, ai limiti, agli algoritmi.
• minimax (in preparazione): minimax come algoritmo (alpha-beta) e come concetto di equilibrio.
• dilemma-prigioniero (in preparazione): cosa il dilemma insegna nei contesti ripetuti, in evolution, in alignment.
• multi-agent (in preparazione): multi-agent systems, dove il framework di teoria dei giochi viene applicato a costellazioni di agent.
• ponte-gioco-principal-agent (in preparazione): l’allineamento come problema principal-agent, con vincoli di teoria dei giochi.

Glossario operativo del capitolo

Per riferimento veloce, i termini che useremo dappertutto nella Parte V e in molti capitoli successivi.

• Giocatore (player): entità che fa scelte. Non necessariamente umana.
• Azione (action): scelta atomica disponibile a un giocatore.
• Strategia pura: scelta deterministica di azione (o piano completo in forma estesa).
• Strategia mista: distribuzione di probabilità su strategie pure.
• Profilo di strategie: tupla che assegna una strategia a ciascun giocatore.
• Payoff (utilità): valore reale assegnato dalla funzione u_i a un profilo.
• Forma normale: matrice/tensore di payoff.
• Forma estesa: albero con information set.
• Equilibrio di Nash: profilo in cui nessuno migliora deviando unilateralmente.
• Minimax: valore garantito in un gioco a somma zero a due giocatori.
• Strategia dominante / dominata: sempre meglio / sempre peggio di un’alternativa.
• Subgame perfect equilibrium: Nash che resta tale in ogni sotto-gioco.
• Best response: insieme di strategie che massimizzano u_i contro un dato σ_{-i}.
• Common knowledge: informazione che tutti sanno, sanno che tutti sanno, e così via.

Questi termini compariranno spesso nei capitoli successivi senza ulteriore introduzione.

Una nota su agenti, giochi e definizione operativa

Chiudiamo con una sintesi pratica per chi progetta sistemi AI. Quando ti capita di analizzare un sistema multi-agente, di progettare un’architettura di training, o di leggere un paper che applica teoria dei giochi al deep learning, prova a passare per questi quattro check:

1. Chi sono i giocatori? Identifica le entità che fanno scelte. Talvolta i giocatori sono espliciti (G e D in un GAN). Talvolta uno è implicito (l’avversario in adversarial training, l’ambiente stocastico in single-agent RL — che però non è un gioco in senso proprio).
2. Cosa è lo spazio delle strategie? È finito (azioni discrete) o infinito (parametri continui di una rete)? È rappresentabile? La PPAD-completezza riguarda spazi finiti; in pratica con reti neurali si lavora in spazi continui di dimensione enorme, dove la natura degli equilibri è ancora oggetto di ricerca.
3. Qual è il payoff di ciascuno? È esplicitamente definito o emerso dal training? È a somma zero, somma generale, semi-cooperativo? È osservabile o stimato (come un reward model in RLHF)?
4. Quale solution concept stiamo invocando? Nash, minimax, Stackelberg (gerarchico), correlated equilibrium, no-regret? Diversi concetti hanno diverse proprietà computazionali e diverse interpretazioni.

Questo schema è una check-list, non una formula magica. Ti aiuta a capire quando il vocabolario della teoria dei giochi sta lavorando per te (chiarisce, predice, struttura) e quando sta solo decorando (analogia non sostenuta dai dettagli). Per i capitoli successivi della Parte V sarà la lente con cui rileggeremo Nash, minimax, dilemmi, mechanism design, e il loro intreccio con bandits, MDP, e RL.

Per andare oltre

• Osborne, M. J., & Rubinstein, A. A Course in Game Theory (MIT Press, 1994). Manuale rigoroso, breve, scritto bene. Riferimento standard per la trattazione formale di forma normale, estesa, equilibri raffinati.
• Shoham, Y., & Leyton-Brown, K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (Cambridge, 2008). Punto di vista CS. Algoritmi, complessità, learning in games, mechanism design computazionale. È il testo su cui costruire intuizione AI-oriented.
• von Neumann, J., & Morgenstern, O. Theory of Games and Economic Behavior (Princeton, 1944). Il trattato fondativo. Più storico che operativo, ma vale leggerne almeno i primi capitoli per capire da dove viene il vocabolario.
• Goodfellow, I. et al. Generative Adversarial Networks (NeurIPS 2014, arXiv:1406.2661). Il paper canonico in cui un framework di teoria dei giochi viene importato esplicitamente nel deep learning.
• Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. The complexity of computing a Nash equilibrium (CACM 2009). La doccia fredda computazionale. PPAD-completezza spiegata in modo accessibile.