The algebraic structures of social organizations: the operad of cooperative games

1. Il Problema e il Contesto

La teoria dei giochi cooperativi studia come gruppi di individui (coalizioni) interagiscono e distribuiscono i guadagni. Un problema fondamentale in questo campo è la complessità computazionale e concettuale: un gioco con $n$ giocatori è definito da una funzione di coalizione che assegna un valore a ogni sottoinsieme di giocatori ($2^n - 1$ valori). Man mano che $n$ cresce, la descrizione completa diventa intrattabile.

Storicamente, si è cercato di ridurre questa complessità trattando i giochi come composizioni di giochi più semplici (ad esempio, un sistema elettorale nazionale composto da elezioni locali). Tuttavia, le nozioni precedenti di composizione (introdotte da Shapley, Owen, von Neumann e Morgenstern) erano frammentate:

• Si applicavano a classi specifiche di giochi (es. giochi semplici, giochi normalizzati).
• Mancava un quadro algebrico unificato che trattasse la composizione come una struttura fondamentale e sistematica.
• Non era chiaro come le diverse nozioni di somma, prodotto e composizione si relazionassero tra loro.

L'obiettivo principale del paper è stabilire un quadro concettuale unificato in cui la nozione di composizione/aggregazione di giochi sia la struttura definitoria, permettendo di trattare sistematicamente qualsiasi problema di aggregazione.

2. Metodologia: Teoria degli Operadi Algebrici

Gli autori adottano la teoria degli operadi algebrici, una struttura matematica nata in topologia algebrica e utilizzata in algebra, geometria e combinatoria per codificare strutture algebriche con operazioni a più ingressi e un'uscita.

• Definizione dell'Operad dei Giochi Cooperativi ($\mathcal{G}$):
  Gli autori definiscono una struttura di operad sulla collezione di tutti i giochi cooperativi (grounded, ovvero $v(\emptyset)=0$).

  • Spazio: $\mathcal{G}(n)$ è lo spazio vettoriale dei giochi a $n$ giocatori.
  • Composizione Parziale ($\circ_i$): Data una funzione di valore $\alpha$ per un gioco $\Gamma_A$ e $\beta$ per un gioco $\Gamma_B$, la composizione parziale $\Gamma_A \circ_i \Gamma_B$ sostituisce il giocatore $i$ di $\Gamma_A$ con l'intero insieme di giocatori di $\Gamma_B$.
  • Formula Chiave: La nuova funzione di valore $\gamma$ per un insieme $S$ è data da:
    $$\gamma(S) = \beta(B)\alpha(S_A) + \partial_i\alpha(S_A)\beta(S_B)$$
    dove $S_A = S \cap A$, $S_B = S \cap B$, e $\partial_i\alpha$ è la derivata (contributo marginale) del giocatore $i$ in $\Gamma_A$.
  • Interpretazione: Il termine $\beta(B)$ scala il gioco originale, mentre il termine $\partial_i\alpha \cdot \beta(S_B)$ aggiunge il valore del sottogioco $\Gamma_B$ pesato dal contributo marginale del giocatore sostituito.

• Isomorfismo con Algebre Commutative Triassociative:
  Utilizzando la trasformata di Möbius (che mappa la funzione di coalizione nei dividendi di Harsanyi), gli autori costruiscono un isomorfismo esplicito tra l'operad dei giochi cooperativi $\mathcal{G}$ e l'operad $\text{ComTriass}$ che codifica le algebre commutative triassociative (definite da Vallette).

3. Contributi Chiave e Risultati Principali

A. Presentazione Esplicita e Generazione

Grazie all'isomorfismo con $\text{ComTriass}$, il paper fornisce una presentazione dell'operad dei giochi cooperativi in termini di generatori e relazioni:

• Generatori: Qualsiasi gioco cooperativo può essere espresso come combinazione lineare di composizioni iterate di due giochi fondamentali a 2 giocatori:
  1. Il gioco del dittatore ($d_1$ o $d_2$).
  2. Il gioco di bargaining (negoziato) a 2 giocatori ($B$).
• Risultato: Questo dimostra che la struttura di tutti i giochi cooperativi è generata da questi mattoni elementari attraverso l'operazione di composizione.

B. Sottoperadi e Stabilità

Gli autori dimostrano che molte classi importanti di giochi studiati in letteratura sono stabili sotto l'operazione di composizione parziale, formando quindi dei sottoperadi:

1. Giochi Normalizzati e Semplici Monotoni: Ripristinano la struttura operadica originale di Shapley per i giochi semplici.
2. Capacità (Misure Fuzzy): Giochi non negativi e monotoni.
3. Giochi Convessi (e k-monotoni): Giochi non negativi con funzione di valore convessa (supermodulare).
4. Funzioni di Credenza (Totally Monotone): Corrispondenti alle funzioni di credenza nella teoria di Dempster-Shafer.
5. Giochi Bilanciati: Giochi con nucleo (core) non vuoto (teorema di Bondareva-Shapley).

C. Geometria: Permutaedri Generalizzati

Un risultato geometrico significativo riguarda i giochi convessi non negativi. Esiste una corrispondenza biunivoca tra questi giochi e i permutaedri generalizzati (definiti da Postnikov).

• Poiché i giochi convessi formano un sottoperad, ne consegue che l'insieme di tutti i permutaedri generalizzati ammette una struttura di operad.
• La composizione di giochi induce una nuova operazione geometrica sui permutaedri (sebbene la descrizione puramente geometrica di questa operazione sia oggetto di lavoro futuro).

D. Aggregazione delle Soluzioni

Il paper analizza come i concetti di soluzione classici si comportano sotto composizione:

• Nucleo (Core): Viene dimostrato che il prodotto tensoriale parziale di due elementi nel nucleo dei giochi componenti appartiene al nucleo del gioco composto. Se i nuclei dei componenti sono vuoti, anche quello del composto lo è. Questo conferma che la "stabilità sociale" (esistenza di una soluzione) è una proprietà robusta rispetto al livello di dettaglio del modello.
• Valore di Shapley: Viene fornita una formula esplicita per il valore di Shapley di un gioco composto, basata sulla trasformata di Möbius.
• Indice di Banzhaf: Viene scoperto un risultato elegante: l'indice di Banzhaf di un gioco composto è il prodotto tensoriale parziale dell'indice di Banzhaf del gioco "quotiente" e del valore di Shapley del gioco "componente" (normalizzato).
  $$\psi(\Gamma_A \circ_i \Gamma_B) = \frac{1}{2^{|B|-1}} \psi(\Gamma_A) \otimes_i \phi(\Gamma_B)$$
  Questo collega due indici di potere fondamentali in modo algebrico.

4. Significato e Implicazioni

1. Unificazione Teorica: Il lavoro risolve il problema dell'aggregazione (citato da Shapley) fornendo un unico linguaggio algebrico (gli operadi) che generalizza e unifica tutte le precedenti nozioni di somma, prodotto e composizione di giochi.
2. Nuova Struttura Algebrica: Trasforma la teoria dei giochi cooperativi da una collezione di modelli ad-hoc in una struttura algebrica coerente, permettendo l'uso di potenti strumenti della teoria degli operadi (omologia, coomologia, presentazioni) per studiare i giochi.
3. Interdisciplinarità: Collega la teoria dei giochi a:
   • Teoria della Misura Non Additiva: Le capacità e le misure fuzzy.
   • Teoria dell'Evidenza (Dempster-Shafer): Le funzioni di credenza e plausibilità.
   • Geometria Combinatoria: I permutaedri generalizzati e i politopi.
   • Combinatoria: Le strutture di algebre trialgebriche.
4. Impatto Pratico: La stabilità dei sottoperadi (come i giochi convessi o bilanciati) garantisce che le proprietà desiderabili (es. esistenza di un nucleo, stabilità) siano preservate quando si modellano sistemi sociali complessi come aggregazioni di sottosistemi più semplici.

In sintesi, il paper stabilisce che la struttura fondamentale dei giochi cooperativi non è quella di uno spazio vettoriale statico, ma quella di un operad dinamico, dove la composizione è l'operazione primaria che genera tutta la complessità sociale osservabile a partire da interazioni elementari.