Giochi cooperativi e valore di Shapley

Quando i giocatori possono firmare accordi vincolanti, la domanda non è più “quale strategia gioco?” ma “come dividiamo la torta?”. E quando la torta è una predizione di un modello ML, dividerla è il problema dell’interpretabilità.

Perché questo capitolo

Quando un sistema di interpretabilità ti dice “la feature età ha contribuito +0.42 alla previsione che questo cliente farà default”, quel numero è il valore di Shapley dell’età, calcolato su un gioco cooperativo dove i giocatori sono le feature. Quando un consorzio di ospedali vuole pagare ciascun partecipante in base a quanto i suoi dati hanno migliorato un modello federato, la metrica naturale è il data Shapley. Quando un orchestratore agentico combina retrieval, reranker e LLM e deve attribuire la qualità della risposta finale ai componenti, il framework matematico più solido è il valore di Shapley sul gioco cooperativo dei tool. Tutte queste applicazioni vivono o muoiono sulla stessa teoria, formulata negli anni ‘50 a Princeton, e la maggior parte di chi la usa nel 2026 non sa di starla usando.

I quattro capitoli precedenti — giochi-definizione, somma-zero-non-zero, equilibrio-nash, minimax — hanno descritto il mondo dei giochi non-cooperativi: ogni giocatore decide indipendentemente, gli accordi non sono vincolanti, l’equilibrio è il punto in cui nessuno vuole deviare unilateralmente. La teoria dei giochi cooperativi (TGC) cambia drasticamente l’inquadratura. Si assume che i giocatori possano formare coalizioni e impegnarsi a redistribuire payoff totali in modo vincolante. Non si studia la strategia individuale; si studia il valore prodotto da gruppi e come dividerlo. È un cambio di domanda — da “cosa gioco?” a “cosa mi spetta?” — più che un cambio di formalismo.

Senza questo capitolo, frasi come “feature attribution”, “credit assignment in multi-agent RL”, “data valuation in federated learning” restano slogan. Con questo capitolo, sono tutti casi particolari di un’unica matematica con assiomi, formule e teoremi di unicità che valgono dagli anni ‘50.

Contesto

La trattazione cooperativa dei giochi a n persone nasce con John von Neumann e Oskar Morgenstern (rispettivamente matematico ungaro-americano e economista austriaco) nel libro fondante Theory of Games and Economic Behavior (Princeton University Press, 1944): un trattato di oltre 600 pagine che fonda contemporaneamente la teoria dei giochi a somma zero a due giocatori e la teoria dei giochi cooperativi a n giocatori. Storicamente, il filone cooperativo precede l’enfasi non-cooperativa che John Nash imporrà a inizio anni ‘50.

I protagonisti operativi del capitolo:

• Lloyd Shapley (matematico americano, Princeton e poi UCLA, premio Nobel per l’economia 2012), che nel 1953 introduce il valore che porta il suo nome — un’unica allocazione caratterizzata da quattro assiomi.
• Donald Gillies (matematico americano), che nella sua tesi PhD del 1953 a Princeton definisce il core: l’insieme delle allocazioni stabili contro defezioni di coalizioni.
• Olga Bondareva (matematica sovietica) e di nuovo Shapley, che indipendentemente (Bondareva nel 1963, Shapley nel 1967) dimostrano il teorema che caratterizza l’esistenza del core.
• David Schmeidler (matematico ed economista israeliano), che nel 1969 introduce il nucleolus, una soluzione puntuale alternativa allo Shapley.
• John Banzhaf (avvocato americano), che nel 1965 propone un indice di potere per giochi di voto, applicandolo al disegno di consigli di amministrazione.
• Scott Lundberg e Su-In Lee (rispettivamente PhD e professoressa all’Università di Washington), che nel 2017 con il paper A Unified Approach to Interpreting Model Predictions (NeurIPS) collegano la teoria classica all’interpretabilità ML moderna sotto il nome SHAP.
• Amirata Ghorbani e James Zou (Stanford), che nel 2019 con Data Shapley portano lo stesso framework alla valutazione dei training data.

Cross-reference verso 113-116: il gioco qui ha la stessa definizione formale di giochi-definizione, ma la rappresentazione è diversa (characteristic function invece di forma normale). Il payoff resta numerico come in somma-zero-non-zero. I concetti di equilibrio di equilibrio-nash e di minimax di minimax si concentrano sulla strategia individuale; qui si concentrano sulla coalizione.

L’intuizione

Angolo 1: la torta che cresce solo se si cuoce insieme

Tre amici stanno per cuocere una torta. Da soli, ciascuno produce una torta che vale 1 euro. In coppia, qualunque coppia, producono una torta da 3 euro (uno impasta, l’altro cuoce, divisione del lavoro). Tutti e tre insieme, producono una torta da 6 euro (uno impasta, uno cuoce, uno decora). Per ANALOGIA: il valore di una coalizione è quanto il gruppo riesce a produrre da solo, non quanto un singolo individuo aggiunge.

La domanda della TGC non è “quale coalizione si forma?” — la risposta tipica è “quella di tutti, perché v(N) >= sum delle parti se il gioco è superadditivo”. La domanda è: dato che siamo tutti dentro, come dividiamo i 6 euro? In parti uguali (2-2-2)? In proporzione a quanto producevamo da soli (1-1-1, scartando 3 euro di “premio cooperazione”)? Secondo qualche altra logica?

La TGC formula la risposta in modo assiomatico. Si parte da proprietà che vorremmo che l’allocazione avesse — efficienza, simmetria, trattamento corretto dei dummy player — e si vede quale formula le soddisfa. Lo Shapley value è la risposta unica.

Angolo 2: chi è davvero indispensabile?

Cambia esempio. Ho 1 guanto sinistro (giocatore 1), tu hai 1 guanto destro (giocatore 2), il tuo amico ha 1 guanto destro (giocatore 3). Solo le coppie sinistro-destro hanno valore: 1 euro a coppia. Da soli, nulla. La coalizione {1,2} vale 1, {1,3} vale 1, {2,3} vale 0, {1,2,3} vale ancora 1 (un solo paio possibile).

Quanto vale ogni giocatore? Intuizione “scarsità di mercato”: il giocatore 1 ha il bene raro (l’unico sinistro), dovrebbe prendere quasi tutto. Intuizione “equità del contributo medio”: pensa a ogni ordine in cui i giocatori potrebbero arrivare a formare la grand coalition. Sui 3! = 6 ordini possibili, calcola il contributo marginale di ciascuno (quanto cresce v quando lui entra), poi fai la media. Otterrai φ_1 = 2/3, φ_2 = φ_3 = 1/6. Il giocatore raro prende molto, ma non tutto.

Le due intuizioni non coincidono. La prima dice (1, 0, 0): il giocatore 1 prende tutto perché senza di lui nessun affare. La seconda dice (2/3, 1/6, 1/6): il giocatore 1 prende molto, ma anche 2 e 3 contano perché in alcuni ordini di arrivo sono loro a “completare” la coppia. Sono due criteri diversi: stabilità contro defezione (il core) e equità assiomatica (lo Shapley value). A volte coincidono, a volte no.

La meccanica

Characteristic function

Sia N = {1, 2, …, n} l’insieme dei giocatori. Una characteristic function è una funzione v: 2^N -> R con v(emptyset) = 0. Per ogni sottoinsieme S ⊆ N (chiamato coalizione), v(S) è il valore (utilità totale, denaro, profitto) che la coalizione S può garantirsi, indipendentemente da cosa fanno i giocatori fuori da S. La grand coalition è N, e v(N) è il valore totale da dividere.

Questo è un TU-game, gioco a transferable utility: si assume che il valore v(S) sia divisibile arbitrariamente tra i membri di S, come fosse denaro. L’alternativa, NTU-game, ha set di payoff vector ammissibili invece di un singolo numero, ed è più complicata. Restiamo su TU.

Proprietà ricorrenti:

• Superadditività: v(S ∪ T) >= v(S) + v(T) per S ∩ T = vuoto. Unirsi non danneggia mai.
• Convessità: v(S ∪ {i}) - v(S) cresce con S. Il contributo marginale di i è più grande quando si aggiunge a coalizioni più grandi (rendimenti crescenti di scala).

Imputazioni e core

Un’allocazione è un vettore x = (x_1, …, x_n) ∈ R^n. È efficiente se sum_i x_i = v(N), individualmente razionale se x_i >= v({i}). Un’imputazione è efficiente e individualmente razionale.

Il core (Gillies 1953, formalizzato in pubblicazione nel 1959) è:

$$Core(v) = { x : sum_i x_i = v(N), e per ogni S ⊆ N: sum_{i ∈ S} x_i >= v(S) }$$

Intuizione: nessuna coalizione S ha incentivo a defezionare, perché la somma di quanto riceve già nel core è almeno v(S), il valore che otterrebbe da sola. Stabilità coalizionale.

Tre fatti sgraditi sul core:

1. Può essere vuoto: nessuna allocazione è stabile (es. simple majority game con 3 giocatori, v(S) = 1 sse |S| >= 2).
2. Quando non vuoto, può essere grande: molte allocazioni sono stabili, nessun criterio per scegliere.
3. Non considera l’equità: una soluzione nel core può dare tutto a un giocatore.

Bondareva-Shapley

TEOREMA (Bondareva 1963, Shapley 1967). Il core di un TU-game è non vuoto se e solo se il gioco è bilanciato.

Una famiglia di coalizioni B con pesi λ_S >= 0 è bilanciata se per ogni i ∈ N, sum_{S ∋ i} λ_S = 1 (i pesi formano una “partizione frazionaria” dei giocatori). Il gioco è bilanciato se per ogni famiglia bilanciata B:

$$sum_{S ∈ B} λ_S · v(S) <= v(N)$$

Significa: nessuna combinazione frazionaria di coalizioni può superare il valore della grand coalition. La prova originale di Bondareva sfrutta la dualità lineare (il core è la regione ammissibile di un LP, non vuota sse il duale è ammissibile, che si traduce in bilanciamento). Shapley nel 1967 da una prova elementare. Corollario: i giochi convessi sono bilanciati, dunque hanno core non vuoto, e in più lo Shapley value è dentro al core (Shapley 1971).

Shapley value: la formula

Il valore di Shapley (Shapley 1953) di un giocatore i in un gioco v è:

φ_i(v) = sum_{S ⊆ N\{i}} [|S|! · (n - |S| - 1)! / n!] · [v(S ∪ {i}) - v(S)]

Forma equivalente come media su permutazioni σ dell’insieme N:

$$φ_i(v) = (1/n!) · sum_σ [v(P_i^σ ∪ {i}) - v(P_i^σ)]$$

dove P_i^σ è l’insieme dei giocatori che precedono i nell’ordine σ. Lettura riga per riga:

• Si fanno arrivare i giocatori in tutti gli n! ordini possibili.
• Per ogni ordine, il contributo marginale di i è la differenza tra il valore della coalizione “chi è già arrivato + i” e “chi è già arrivato”.
• Lo Shapley di i è la media di questi contributi marginali su tutti gli ordini.

Il termine combinatorio nella prima formula è esattamente il numero di permutazioni in cui i predecessori di i formano l’insieme S, diviso n!.

I quattro assiomi

TEOREMA (Shapley 1953). Esiste un’unica funzione φ: V -> R^n (con V lo spazio dei TU-game su N) che soddisfa i seguenti assiomi, ed è data dalla formula sopra.

1. Efficiency: sum_i φ_i(v) = v(N). Si distribuisce esattamente il valore della grand coalition.
2. Symmetry: se i e j sono intercambiabili (v(S ∪ {i}) = v(S ∪ {j}) per ogni S che non contiene né i né j), allora φ_i(v) = φ_j(v).
3. Dummy player (o null player): se v(S ∪ {i}) = v(S) per ogni S (i non aggiunge nulla a nessuna coalizione), allora φ_i(v) = 0.
4. Additivity (o linearità): per due giochi v, w sullo stesso N, φ_i(v + w) = φ_i(v) + φ_i(w).

L’additività è l’assioma matematicamente più potente e meno intuitivo. Dice che se due fonti di valore (due “giochi”) agiscono sugli stessi giocatori, l’allocazione totale è la somma delle allocazioni separate. Combinata con simmetria, dummy ed efficienza, forza il valore su una base di giochi elementari (i giochi unanimità u_T) e quindi su tutto lo spazio per linearità.

Pseudocodice Monte Carlo per Shapley

Calcolo esatto: O(2^n) sottoinsiemi. Per n = 30 già un miliardo, infattibile. Approssimazione standard via Monte Carlo su permutazioni:

input: caratteristica v, giocatore i, numero campioni T
output: stima di φ_i(v)

phi_i = 0
for t = 1, ..., T:
    σ = permutazione casuale uniforme di N
    P = insieme dei giocatori che precedono i in σ
    delta_t = v(P ∪ {i}) - v(P)
    phi_i = phi_i + delta_t
return phi_i / T

Stima non distorta. Varianza decresce come 1/T. Per ogni iterazione servono due valutazioni di v, che a sua volta può essere costoso (es. addestrare un modello in data Shapley). In pratica si usano varianti smarter: stratified sampling, control variates, antithetic variates.

flowchart LR
    A[Input x e feature i] --> B[Campiona permutazione casuale sigma]
    B --> C[Predecessori P di i in sigma]
    C --> D[Calcola v(P unione i) − v(P)]
    D --> E[Accumula contributo marginale]
    E --> F{T campioni raggiunti?}
    F -->|no| B
    F -->|sì| G[Media per ottenere phi_i]

Figura 3 — pipeline Monte Carlo per stimare il valore di Shapley di una feature: campiona permutazioni, accumula contributi marginali, media su T campioni

Nucleolus in due righe

Per ogni allocazione x e coalizione S, l’eccesso è e(S, x) = v(S) - sum_{i ∈ S} x_i. Misura “quanto S è scontenta” di x: se positivo, S potrebbe ottenere di più da sola. Il nucleolus (Schmeidler 1969) è l’allocazione che minimizza lessicograficamente il vettore degli eccessi ordinato in modo decrescente. Sempre esistente, sempre unico, sempre nel core se il core non è vuoto. Costo computazionale: una sequenza di LP con 2^n vincoli, in genere peggio di Shapley.

Indici di potere: Banzhaf e Shapley-Shubik

I giochi di voto (simple games) sono il caso v(S) ∈ {0, 1}: la coalizione “vince” o “perde”. Per misurare il potere di un singolo votante esistono due famiglie di indici, entrambi casi particolari del valore di Shapley applicato a giochi monotoni.

L’indice di Banzhaf (Banzhaf 1965) conta le coalizioni S in cui i è swing, cioè critico: v(S) = 1 ma v(S \ {i}) = 0. Normalizzato dividendo per la somma degli swing di tutti i giocatori. Non pesa per ordine di arrivo: tutte le coalizioni in cui sei critico contano uguale.

L’indice di Shapley-Shubik (Shapley-Shubik 1954) è semplicemente il valore di Shapley applicato al simple game: media sui contributi marginali in tutte le permutazioni. Pesa per ordine. Equivale a chiedere: in quanti ordini di arrivo dei votanti sei tu il pivot che fa passare la mozione?

Per il Consiglio di Sicurezza ONU (5 permanenti con veto, 10 non permanenti, soglia 9 sì + nessun veto), entrambi gli indici producono numeri vicini: circa il 98% del potere ai permanenti, il 2% ai non permanenti. La struttura formale (“ogni stato un voto”) nasconde un’asimmetria di potere di due ordini di grandezza. Banzhaf e Shapley-Shubik in generale possono divergere e la scelta è una decisione modellistica: Banzhaf privilegia la prospettiva “in quante situazioni sei critico”, Shapley-Shubik “in quante traiettorie di formazione della coalizione sei pivot”.

Perché unicità di Shapley funziona: i giochi unanimità

Il punto leva tecnico della prova di unicità è una base di giochi elementari. Per ogni T ⊆ N non vuoto, il gioco unanimità u_T è definito da:

$$u_T(S) = 1 se T ⊆ S, 0 altrimenti$$

Cioè: la coalizione vince solo se contiene tutti i membri di T. Su questi giochi gli assiomi forzano una sola allocazione: i membri di T si dividono in parti uguali (1/|T|), gli altri prendono 0 (sono dummy player). Per simmetria interna a T, dummy fuori da T, ed efficienza, questa è l’unica scelta.

Lo spazio dei giochi a n giocatori ha dimensione 2^n - 1 (il numero di coalizioni non vuote). I giochi unanimità u_T per T non vuoto sono 2^n - 1 e formano una base. Ogni gioco v si scrive in modo unico come v = sum_T α_T · u_T con coefficienti α_T (chiamati dividendi di Harsanyi, John Harsanyi, economista ungherese-americano premio Nobel 1994). L’additività e la linearità (additività più scaling) si propagano dai u_T a tutti i giochi. Quindi il valore di Shapley è completamente determinato.

Lettura operativa: lo Shapley value è “il modo unico di estendere linearmente l’allocazione equa di un gioco unanimità a tutti i giochi”. L’additività non è cosmetica, è il motore.

Esempi

Esempio 1 (numerico): glove game a tre giocatori

Setup: il giocatore 1 ha un guanto sinistro, 2 e 3 hanno un guanto destro ciascuno. Solo coppie sx-dx valgono 1 euro. Characteristic function:

$$v(emptyset) = 0 v({1}) = v({2}) = v({3}) = 0 v({1,2}) = 1 v({1,3}) = 1 v({2,3}) = 0 v({1,2,3}) = 1$$

Calcolo dello Shapley di 1 via permutazioni. Ci sono 6 permutazioni di {1,2,3}; per ognuna calcolo il contributo marginale di 1 (= v(insieme con 1) - v(insieme senza 1)):

• (1,2,3): 1 entra primo. v({1}) - v(emptyset) = 0.
• (1,3,2): identico, 0.
• (2,1,3): 1 entra dopo 2. v({1,2}) - v({2}) = 1 - 0 = 1.
• (3,1,2): v({1,3}) - v({3}) = 1.
• (2,3,1): 1 entra ultimo. v({1,2,3}) - v({2,3}) = 1 - 0 = 1.
• (3,2,1): v({1,2,3}) - v({2,3}) = 1.

Media: (0 + 0 + 1 + 1 + 1 + 1) / 6 = 4/6 = 2/3. Quindi φ_1 = 2/3. Per simmetria e per efficiency, φ_2 = φ_3 = (1 - 2/3) / 2 = 1/6.

Il core invece: l’unica imputazione che soddisfa tutti i vincoli x_1 + x_2 >= 1 e x_1 + x_3 >= 1 e x_1 + x_2 + x_3 = 1 (con x_i >= 0) è (1, 0, 0). Il giocatore 1 prende tutto.

Lezione: Shapley = 2/3 per il giocatore raro è “equo” rispetto al contributo marginale medio; il core = 1 per il giocatore raro è “stabile” rispetto a defezioni. Sono criteri diversi e in questo caso non coincidono — Shapley qui è fuori dal core.

flowchart LR
    A[Input x e feature i] --> B[Campiona permutazione casuale sigma]
    B --> C[Predecessori P di i in sigma]
    C --> D[Calcola v(P unione i) − v(P)]
    D --> E[Accumula contributo marginale]
    E --> F{T campioni raggiunti?}
    F -->|no| B
    F -->|sì| G[Media per ottenere phi_i]

Figura 3 — D simplex with core region (single point at vertex) and Shapley point inside, glove game

In termini di stabilità: se il giocatore 1 propone l’allocazione Shapley (2/3, 1/6, 1/6), il giocatore 2 (o 3) può ribattere “ti do 0.7, l’altro lo escludo, mi tengo 0.3 — coalizione {1, 2} vale 1, mi conviene”. Quindi Shapley non è stabile in questo gioco. È equo nel senso assiomatico, non nel senso di sopravvivenza alla negoziazione. La scelta tra criterio dipende dal contesto: in un cost-sharing legalmente vincolante, equità conta più di stabilità; in una contrattazione libera, vince la stabilità.

Esempio 2 (codice): Monte Carlo Shapley su mini regressione

Scenario: addestriamo una regressione lineare con 4 feature x_1, x_2, x_3, x_4 e vogliamo lo Shapley di ciascuna feature per una previsione specifica. Pseudocodice in stile Python (esecuzione concettuale):

import numpy as np
from itertools import permutations

# modello f e baseline distribution già disponibili
# input specifico x da spiegare, n=4 feature

def v(S, x, f, baseline):
    # E[f(x_S, X_~S)] dove X_~S si campiona dal baseline
    # SHAP marginal version: media empirica
    z = baseline.copy()
    for j in S:
        z[:, j] = x[j]
    return f(z).mean()

def shapley_mc(i, x, f, baseline, T=10000, n=4):
    phi = 0.0
    players = list(range(n))
    for t in range(T):
        sigma = np.random.permutation(players)
        pos = list(sigma).index(i)
        S_before = set(sigma[:pos])
        S_after = S_before | {i}
        phi += v(S_after, x, f, baseline) - v(S_before, x, f, baseline)
    return phi / T

Per regressione lineare, il calcolo si chiude analiticamente (non serve Monte Carlo): ogni feature contribuisce w_i · (x_i - mean(x_i)), che è esattamente lo Shapley value marginal. Per modelli non lineari (random forest, rete neurale), il Monte Carlo è la via standard, e per ensemble di alberi esiste TreeSHAP che chiude in polinomial time esatto. Costo della versione Monte Carlo: O(T · n) valutazioni di f.

Esempio 3 (scenario reale): SHAP su un classificatore tabulare

Una banca usa un gradient boosting (LightGBM) per stimare la probabilità di default su una pratica di credito. Per la pratica di Maria Rossi, il modello restituisce p = 0.73 (alta probabilità di default). Domanda regolatoria: perché?

Si calcola SHAP. Il baseline E[f(X)] sul training set è 0.18. La somma degli SHAP values su tutte le feature più baseline deve fare 0.73 (efficiency).

Output tipico (numeri inventati a fini didattici):

$$baseline: 0.18 + debt_to_income (0.62): +0.31 + credit_history_short: +0.18 + income_low: +0.09 + employment_stable: -0.04 + collateral: -0.03 + age (45): +0.02 prediction: 0.73$$

Letto come waterfall: il modello parte dal baseline 0.18 (probabilità media); il rapporto debito-reddito di Maria spinge in su di 0.31; storia creditizia breve di altri 0.18; reddito basso di 0.09; impiego stabile riduce di 0.04; il collaterale di 0.03; l’età di 45 anni la spinge leggermente in su di 0.02. La somma dà 0.73.

Questa è la spiegazione “additive feature attribution” che SHAP fornisce, garantita dai 4 assiomi. Per la regolatoria europea (EU AI Act per credit scoring high-risk), questo tipo di spiegazione è oggi quasi standard de facto.

Esempio 4 (cost sharing): airport game

Quattro compagnie aeree condividono un aeroporto. La pista deve essere lunga abbastanza da accogliere il velivolo più grande di ciascuna compagnia. Le lunghezze richieste e i costi (proporzionali alla lunghezza) sono:

• Compagnia A (turboelica): 1 km, 1 milione.
• Compagnia B (jet regionale): 1.5 km, 1.5 milioni.
• Compagnia C (narrow-body): 2 km, 2 milioni.
• Compagnia D (wide-body): 3 km, 3 milioni.

Il costo della coalizione S è il costo della pista più lunga richiesta in S: c({A}) = 1, c({A, B}) = 1.5, c({A, B, C, D}) = 3, ecc.

Per il cost-sharing si usa il valore di Shapley sul gioco di costo (-c(S)) o equivalentemente la formula per cost games. La regola che emerge (Littlechild-Owen 1973) è elegante: ogni “segmento” di pista è pagato in parti uguali da tutte le compagnie che lo richiedono.

• Primi 1 km (richiesto da A, B, C, D): costo 1 milione, diviso per 4 = 250.000 a testa.
• Da 1 a 1.5 km (richiesto da B, C, D): 0.5 milioni, diviso per 3 ≈ 166.667 a testa.
• Da 1.5 a 2 km (richiesto da C, D): 0.5 milioni, diviso per 2 = 250.000 a testa.
• Da 2 a 3 km (richiesto solo da D): 1 milione, tutto a D.

Shapley di A = 250.000. B = 250.000 + 166.667 ≈ 416.667. C = 250.000 + 166.667 + 250.000 ≈ 666.667. D = 250.000 + 166.667 + 250.000 + 1.000.000 ≈ 1.666.667. Somma = 3 milioni. Tutto allocato.

Questa “regola dei segmenti” è applicata nei contratti reali di cost-sharing aeroportuale ed è uno dei pochi casi in cui lo Shapley value ha forma chiusa interpretabile.

Applicazioni pratiche

SHAP per interpretability ML. Libreria shap (Python, basata su Lundberg-Lee 2017): TreeSHAP per ensemble (poly-time esatto), KernelSHAP model-agnostic, DeepSHAP per reti neurali, plot summary, dependence, force, waterfall. È diventato lo standard de facto per spiegazioni locali su classificatori tabulari. Usata in finance (credit scoring), healthcare (modelli diagnostici), HR (modelli di selezione) — ovunque la regolazione richieda accountability.

Data Shapley per dataset valuation e cleaning. Identificare training point dannosi (Shapley negativo), valutare quanto un sottoinsieme di dati vale, decidere quali dati comprare, quali outlier rimuovere. In federated learning, l’incentive design naturale: ogni partecipante riceve reward proporzionale al data Shapley dei suoi dati. Beta-Shapley (Kwon-Zou 2022) e CHG-Shapley accelerano.

Multi-agent cooperative RL credit assignment. In MARL cooperativo (QMIX, VDN), il reward globale deve essere decomposto per agente. Shapley Q-value (Wang et al. 2020) usa il valore di Shapley per attribuire credit. Costo computazionale è il limite pratico: tipicamente si usano approssimazioni o si limita a Shapley su piccole coalizioni.

Mechanism design per agent platforms. Quando un orchestratore agentico chiama tool/agent multipli a pagamento (retrieval + reranker + LLM + verificatore), come dividere il costo o reward in modo “equo”? Lo Shapley è la scelta canonica perché soddisfa efficiency (tutto distribuito) + simmetria (componenti equivalenti pagati ugualmente) + dummy (componenti che non contribuiscono pagano zero). In pratica implementato con A/B su coalizioni di tool e Monte Carlo sampling.

Cooperative AI agenda (Dafoe et al. 2020). Programma di ricerca esplicito su AI che cooperano tra loro o con umani, con TGC come pilastro matematico insieme a social choice e mechanism design. Negoziazione automatica, formazione di coalizioni in mercati di agenti, divisione di risorse condivise.

Federated learning incentives. In federated learning una banca o un ospedale partecipano a un training condiviso senza scambiare dati grezzi. La domanda economica: come ripartire i profitti del modello finale in modo che nessuno abbia incentivo a sabotare (o a non partecipare)? Data Shapley è la risposta canonica: ogni partecipante riceve compenso proporzionale al valore di Shapley dei suoi dati nel gioco “performance del modello federato”. Implementazioni recenti (FedShapley, GTG-Shapley) approssimano lo Shapley senza dover riaddestrare da zero ogni volta, riusando i gradienti già scambiati.

Ensemble e model selection. Quando si combina un ensemble di modelli (stacking, bagging, voting), lo Shapley value sui modelli misura quanto ciascuno contribuisce alla performance del meta-modello. Permette di potare l’ensemble (rimuovere modelli con Shapley basso o negativo) e di pesare i contributi in modo principled.

Coalition formation in agent platforms. In sistemi multi-agent dove gruppi di agenti collaborano per task complessi (un planner, un coder, un reviewer, un tester), il framework cooperativo permette di analizzare quali coalizioni sono stabili (nel core) e come compensare i contributi. Nel 2024-2026 alcune piattaforme di agent orchestration sperimentano pricing dinamico basato su Shapley per agenti di terze parti.

Dove si rompe

Costo computazionale. Lo Shapley esatto è O(2^n). Per n = 20 sono 10^6 sottoinsiemi, per n = 30 sono 10^9. SHAP su un modello con 1000 feature è impossibile esatto. Le approssimazioni Monte Carlo hanno varianza alta: gli intervalli di confidenza sui singoli SHAP values possono essere ampi quanto i valori stessi. TreeSHAP è poly-time ma solo per tree ensemble, non generalizza ad altri modelli.

Indipendenza delle feature. SHAP standard ammette due definizioni del valore della coalizione: marginal v(S) = E[f(x_S, X_{~S})] dove le feature mancanti sono campionate dalla loro marginale, oppure conditional v(S) = E[f(x) | X_S = x_S]. Sono diverse quando le feature sono correlate. Janzing, Minorics e Blöbaum (2020), in Feature relevance quantification in explainable AI: A causality problem (AISTATS 2020), mostrano che la conditional ha leakage (una feature non causalmente rilevante può avere SHAP non zero per via della correlazione con feature rilevanti) e che la marginal corrisponde formalmente al do-operator di Pearl. Ma marginal valuta f su input fuori distribuzione (ricombinare valori di feature non visti insieme nel training rompe il modello). Causal Shapley (Heskes et al. 2020) integra un DAG causale per superare il dilemma; richiede di conoscere la struttura causale, raramente nota.

Modello non additivo, attribuzione additiva. SHAP è additive feature attribution per costruzione: f(x) ≈ baseline + sum_i φ_i. Se f ha forti interazioni (es. AND tra due feature, prodotti, soglie multiple), gli SHAP individuali non catturano l’interazione. Gli SHAP interaction values (Lundberg-Lee 2018 estensione) cattureno interazioni a coppie ma costano O(n^2) e generalizzano male oltre.

Core vuoto. Per molti giochi cooperativi realistici (majority game, weighted voting con threshold sbilanciato), il core è vuoto: nessuna allocazione è stabile contro defezioni. ε-core e altri rilassamenti danno soluzioni “quasi stabili” ma perdono il significato originale di stabilità.

TU vs NTU. La TGC operativa è quasi tutta TU (utilità trasferibile come denaro). In molti scenari reali — preferenze ordinali, beni indivisibili, vincoli di equità individuali — serve NTU, dove la teoria è più frammentata e i risultati di unicità (à la Shapley) non si trasferiscono direttamente.

Commitment vincolante. La TGC assume che i giocatori possano impegnarsi credibilmente a restare nella coalizione e dividere come pattuito. In agenti reali (umani, LLM-based, organizzazioni), il commitment va imposto da un’infrastruttura esterna (smart contract, enforcement legale, reputazione). Senza, la stabilità coalizionale è teorica.

SHAP su LLM e token attribution. Tentativi di applicare SHAP per spiegare l’output di un LLM attribuendolo ai token di input falliscono per più ragioni: i modelli sono fortemente non additivi su token (l’attention crea dipendenze pesanti); i token sono fortemente correlati (è linguaggio naturale); il “baseline” naturale (token mascherato o sostituito) crea input fuori distribuzione che attivano comportamenti del modello non rappresentativi. Le spiegazioni SHAP a livello token su LLM tendono a essere fuorvianti, e la letteratura ha spostato l’enfasi su attribuzioni a livello di concetto (probing, sparse autoencoders) o di circuito (mechanistic interpretability).

Confondere Shapley con “vera importanza causale”. SHAP è una decomposizione coerente con assiomi di equità e linearità. Non è una misura di causalità. Una feature con SHAP alto può essere correlata con la causa vera senza esserla. Per claim causali serve causal Shapley, do-calculus, structural causal models — strumenti diversi.

Instabilità degli SHAP value tra modelli equivalenti. Due modelli con accuratezza identica ma struttura interna diversa (es. due random forest addestrati con seed diversi, o un random forest e un gradient boosting che predicono entrambi correttamente lo stesso set di esempi) possono produrre SHAP value molto diversi sulle stesse istanze. La spiegazione SHAP non è una proprietà del problema, è una proprietà del modello specifico — lezione spesso dimenticata da chi presenta SHAP come “spiegazione oggettiva”.

Data Shapley è non-stabile rispetto al training. La performance v(S) di un sottoinsieme S richiede di addestrare il modello su S. Per modelli non convessi (reti neurali, gradient boosting), il risultato dipende da inizializzazione, ordine dei batch, randomness numerica. Lo Shapley computato su questa funzione rumorosa eredita il rumore. In pratica si fanno medie su più seed, moltiplicando il costo già proibitivo.

Aggregazione di SHAP value globali. Una pratica comune è mediare gli SHAP value (in valore assoluto) tra istanze del test set per ottenere una “feature importance globale”. Questa media ha senso intuitivo ma perde la garanzia assiomatica: non c’è un “global game” di cui sia il valore di Shapley. È una statistica utile, non un teorema.

Manipolazione strategica del valore. In contesti reali con incentivi (data marketplace, federated learning con compensi monetari), un partecipante può manipolare i suoi dati per gonfiare il proprio data Shapley value: duplicazione, sintesi mirata di esempi che migliorano metriche specifiche, attacchi noti come “Shapley manipulation”. Le difese (robust Shapley, certified Shapley) sono ancora terreno di ricerca aperto e non sono robuste a tutti gli attacchi noti.

Confronto tra giochi diversi. Se ridefinisci il gioco (cambiando v), cambiano gli Shapley value. In SHAP, scegliere baseline = training set vs baseline = un riferimento canonico (es. zero) cambia tutte le attribuzioni. Non esiste una scelta “neutra” del baseline; è una decisione modellistica con implicazioni interpretative non eliminabili.

Approfondimento: la prova di unicità nei dettagli — dal gioco al valore, una derivazione passo passo

Vale la pena vedere in dettaglio perché i quattro assiomi forzano la formula. La derivazione è più semplice di quanto sembri se si parte dai giochi unanimità.

Passo 1: per il gioco unanimità u_T, gli unici giocatori non dummy sono quelli in T (chi sta fuori non cambia mai il valore della coalizione, perché non basta da solo a far diventare T ⊆ S). Per dummy player, φ_i(u_T) = 0 per i ∉ T. Per simmetria, tutti i giocatori di T ricevono uguale: φ_i(u_T) = c per i ∈ T. Per efficienza, sum_i φ_i(u_T) = u_T(N) = 1, quindi c = 1/|T|.

Conclusione: φ_i(u_T) = 1/|T| se i ∈ T, 0 altrimenti.

Passo 2: ogni gioco v si scrive in modo unico come combinazione lineare v = sum_T α_T · u_T (dimostrabile per induzione su |T|, calcolando i dividendi di Harsanyi α_T = sum_{R ⊆ T} (-1)^{|T| - |R|} v(R)).

Passo 3: per additività e linearità,

$$φ_i(v) = sum_T α_T · φ_i(u_T) = sum_{T : i ∈ T} α_T / |T|$$

Espandendo gli α_T e riorganizzando si ottiene la formula classica con i contributi marginali pesati. Il valore di Shapley è completamente determinato dai 4 assiomi: nessuna libertà rimane.

Questo è anche il motivo per cui l’additività è “non negoziabile”: rilassarla apre uno spazio enorme di possibili valori. È stata oggetto di critica filosofica (perché due fonti di valore distinte dovrebbero comporsi linearmente?), e sono stati proposti valori alternativi che la rilassano (Solidarity value di Nowak-Radzik 1994 nel risultato di ricerca sopra), tutti meno usati.

Approfondimento: SHAP come gioco specifico

Per chiudere il cerchio con la pratica ML, vediamo esplicitamente come SHAP istanzia il framework.

Giocatori: le n feature di input del modello f.

Characteristic function: dato un input specifico x = (x_1, …, x_n) da spiegare, e un baseline distribution D (tipicamente il training set), il valore della coalizione S è:

$$v(S) = E_D[f(x_S, X_{N\S})] - E_D[f(X)]$$

Cioè: la prediction attesa quando le feature in S sono fissate ai valori di x e le feature fuori da S sono campionate dalla distribuzione baseline, meno il baseline globale. Il termine ”- E_D[f(X)]” rende v(emptyset) = 0 come da convenzione.

Lo Shapley di ogni feature è il suo SHAP value. La somma su tutte le feature dà v(N) = f(x) - E_D[f(X)], che riarrangiato significa:

$$f(x) = E_D[f(X)] + sum_i SHAP_i$$

— l’identità additiva alla base dei waterfall plot. Garantita da efficiency del valore di Shapley applicato a questo gioco.

Le quattro proprietà di SHAP elencate da Lundberg-Lee 2017 (local accuracy, missingness, consistency, e implicitamente symmetry) sono esattamente i quattro assiomi di Shapley tradotti nel linguaggio ML. Local accuracy = efficiency. Missingness = dummy player (una feature mai presente non riceve attribuzione). Consistency = una variante di monotonicità che equivale, sotto le altre, a simmetria + additività.

EQUIVALENZA esplicita: SHAP = valore di Shapley sul feature game. Non è un’analogia, non è una filiazione, è la stessa matematica con notazione diversa.

Collegamenti

• giochi-definizione: qui la rappresentazione è in characteristic function invece che in forma normale o estesa. Stessa cornice formale, lente diversa.
• somma-zero-non-zero: la TGC tipicamente assume superadditività (non zero-sum), perché altrimenti cooperare non avrebbe senso.
• equilibrio-nash: Nash è equilibrio non-cooperativo, il core è equilibrio coalizionale. Linguaggi diversi per stabilità.
• minimax: minimax è il “valore” garantito a un giocatore in giochi a somma zero a 2; lo Shapley è il valore “equo” di un giocatore in giochi cooperativi a n.
• mech-interp-intro (in preparazione): SHAP come baseline per interpretabilità modello, complementare ad analisi meccanistiche su circuiti interni.
• multi-agent (in preparazione): credit assignment in MARL cooperativo, formazione di coalizioni di agenti, applicazioni dirette del valore di Shapley.
• federated learning (in preparazione): data Shapley come incentive design naturale.
• mechanism design (in preparazione): TGC come uno dei tre pilastri (insieme a social choice e auction theory).
• bayesian-networks (in preparazione): causal Shapley richiede struttura DAG causale come quella delle reti bayesiane.
• regressione-lineare (in preparazione): per modelli lineari, gli SHAP value hanno forma chiusa (w_i · (x_i - mean(x_i))).
• gradient-boosting (in preparazione): TreeSHAP è l’algoritmo poly-time esatto per ensemble di alberi.

Una osservazione finale di metodo. La teoria dei giochi cooperativi è uno dei rari esempi in cui un teorema matematico astratto degli anni ‘50 ha trovato applicazione pratica massiva sessant’anni dopo, quasi senza modifiche concettuali. Il valore di Shapley di Lloyd Shapley del 1953 è esattamente lo SHAP di Lundberg-Lee del 2017 e l’incentive scheme di un consorzio federated del 2026: cambia la cornice, restano gli assiomi.

Per andare oltre

• Shapley, L. S. (1953), A Value for n-Person Games. Princeton UP. Il paper originale, 11 pagine, ancora oggi la lettura più chiara dei 4 assiomi e della prova di unicità.
• Lundberg, S. M. & Lee, S.-I. (2017), A Unified Approach to Interpreting Model Predictions. NeurIPS. arXiv:1705.07874. Il paper che collega TGC a interpretability ML.
• Osborne, M. J. & Rubinstein, A. (1994), A Course in Game Theory. MIT Press. Capitoli 13-14 sui giochi cooperativi: trattazione rigorosa accessibile, con prove complete di Bondareva-Shapley e unicità di Shapley.
• Shoham, Y. & Leyton-Brown, K. (2008), Multiagent Systems. Cambridge UP. Capitolo 12: prospettiva multi-agent computazionale, algoritmi di approssimazione, applicazioni.
• Molnar, C. (2024), Interpretable Machine Learning, capitoli 17-18 (online, christophm.github.io/interpretable-ml-book). Pratico per il lato ML, esempi con la libreria shap.
• Ghorbani, A. & Zou, J. (2019), Data Shapley: Equitable Valuation of Data for Machine Learning. ICML. arXiv:1904.02868. Punto di riferimento per data valuation e federated learning incentive.
• Janzing, D., Minorics, L., Blöbaum, P. (2020), Feature relevance quantification in explainable AI: A causality problem. AISTATS. Lettura critica fondamentale: SHAP marginal vs conditional, e perché il punto di vista causale cambia le carte.
• Maschler, M., Solan, E., Zamir, S. (2013), Game Theory. Cambridge UP. Trattamento moderno comprensivo con prove rigorose di Bondareva-Shapley, unicità del nucleolus, kernel, bargaining set.