Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

Sintesi Tecnica: Eliminazione Sequenziale e Valore di Shapley di Unione per la Valutazione di Gruppi nei Giochi Coalizionali

Enunciato del Problema
Nella teoria dei giochi cooperativi e in campi correlati come la centralità nelle reti e la valutazione dei dati nel machine learning, una sfida fondamentale è estendere le valutazioni dei singoli giocatori ai gruppi. I metodi esistenti si basano tipicamente su due approcci diretti:

1. Somma: Aggregazione dei valori individuali (ad esempio, la somma dei valori di Shapley). Questo ignora la struttura sottostante della cooperazione e le dipendenze tra i giocatori.
2. Fusione: Trattamento del gruppo come un singolo elemento fuso e sua valutazione (ad esempio, il valore di Shapley di Fusione). Questo altera la struttura del gioco e non riesce a distinguere tra giocatori indipendenti e giocatori altamente dipendenti.

Entrambi gli approcci spesso non riescono a catturare accuratamente le dipendenze all'interno dei gruppi. Ad esempio, in un gioco in cui due coppie disgiunte di giocatori generano valore indipendentemente, sommare i valori individuali o fondere i gruppi può assegnare erroneamente un'importanza uguale a una coppia di giocatori cooperanti e a una coppia di giocatori indipendenti, non riuscendo a riflettere l'asimmetria nel loro impatto sistemico.

Metodologia
Gli autori propongono e analizzano un terzo approccio basato sull'eliminazione sequenziale. In questo quadro, gli elementi di un gruppo vengono rimossi uno alla volta e le loro valutazioni nei giochi ridotti risultanti vengono aggregate. L'ipotesi fondamentale è che questo metodo misuri naturalmente il contributo netto di un gruppo scontando gli effetti sovrapposti e focalizzandosi sul danno causato dall'assenza del gruppo.

Lo studio si fonda su un'analisi assiomatica completa dei valori di gruppo nei giochi coalizionali. La metodologia prevede:

• Definizione di Classi Assiomatiche: Gli autori introducono una classe di semivalori di gruppo (debolmente consistenti). Questi sono valori di gruppo che soddisfano Linearità, Simmetria, Debole Monotonia, Uscita del Giocatore Nullo e l'assioma del Giocatore Fittizio. Definiscono inoltre una classe corrispondente di semivalori di sinergia, che sostituiscono l'assioma del Giocatore Fittizio con l'assioma del Giocatore Fittizzante (introdotto da Grabisch e Roubens).
• Estensione Sequenziale: Il documento stabilisce che un valore di giocatore ammette un'estensione sequenziale se e solo se soddisfa la proprietà dei Contributi Bilanciati. È stato dimostrato che ogni semivalore coerente (che soddisfa l'Uscita del Giocatore Nullo) ammette un'estensione sequenziale unica.
• Funzione Potenziale: Gli autori utilizzano la funzione potenziale introdotta da Hart e Mas-Colell per caratterizzare l'estensione sequenziale del valore di Shapley.

Contributi e Risultati Chiave

1. Il Valore di Shapley di Unione:
   Gli autori introducono il Valore di Shapley di Unione come l'unica estensione sequenziale del valore di Shapley. È definito come la differenza tra il potenziale del gioco originale e il potenziale del gioco dopo la rimozione del gruppo:
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   dove $\Delta v(T)$ sono i dividendi di Harsanyi.

   • Interpretazione: Questo valore misura il "danno" inflitto al gioco quando un gruppo se ne va. Aggrega i contributi in modo che il dividendo di ogni coalizione sia contato al massimo una volta, anche se il gruppo contiene più membri di quella coalizione.
   • Assiomatizzazione: Il valore di Shapley di Unione è caratterizzato univocamente dagli assiomi di Potenziale (o Contributi Bilanciati) combinati con l'Efficienza. È anche caratterizzato univocamente tra i semivalori di gruppo dall'Uguaglianza di Gruppo (tutti i gruppi in un gioco di unanimità sono ugualmente importanti).

2. Classificazione Assiomatica dei Valori di Gruppo:
   Il documento distingue tra due varianti di valutazione del gruppo:

   • Valore Totale: Valori che valutano il valore totale di un gruppo (ad esempio, Estensione della Somma, Shapley di Fusione, Shapley di Unione). Questi sono catturati dai semivalori di gruppo.
   • Sinergia: Valori che misurano la sinergia di un gruppo (ad esempio, Indice di Interazione). Questi sono catturati dai semivalori di sinergia.
     Gli autori forniscono una corrispondenza funzionale tra queste due classi. Nello specifico, dimostrano che il Valore di Shapley di Fusione corrisponde all'Indice di Interazione (una controparte sinergica), e il Valore di Shapley di Unione corrisponde a un nuovo valore sinergico chiamato Valore di Shapley di Intersezione.

3. Il Valore di Shapley di Intersezione:
   Definito come la somma dei dividendi delle coalizioni che contengono l'intero gruppo:
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   Questo valore misura l'intersezione dei contributi. Per un gruppo di dimensione due, la somma del Valore di Shapley di Unione e del Valore di Shapley di Intersezione è uguale alla somma dei valori di Shapley individuali:
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   Questa decomposizione permette di separare il valore congiunto di un gruppo in una parte "unione" (che conta i contributi una volta sola) e una parte "intersezione" (sinergia).

4. Confronto con Lavori Esistenti:
   L'analisi chiarisce la relazione tra i valori proposti e la letteratura esistente:

   • Il Valore di Shapley di Fusione (Marichal et al.) è dimostrato essere l'unico semivalore di gruppo che soddisfa l'assioma della Coalizione Fittizia.
   • L'Indice di Interazione (Grabisch e Roubens) è identificato come un semivalore di sinergia, distinto dai semivalori di gruppo perché viola l'assioma standard del Giocatore Nullo a favore dell'assioma del Giocatore Fittizzante.
   • Il documento dimostra che l'approccio di estensione sequenziale è teoricamente robusto, in quanto si applica a tutti i semivalori coerenti e produce valori con forti proprietà assiomatiche.

Significato
Il documento afferma che l'approccio di estensione sequenziale, e in particolare il Valore di Shapley di Unione, costituisce una delle estensioni più naturali e teoricamente fondate dei valori dei giocatori ai gruppi nei giochi coalizionali. Distinguendo tra la valutazione del valore totale e la misurazione della sinergia, gli autori forniscono un quadro unificato che chiarisce le differenze tra le nozioni esistenti nella letteratura. L'introduzione dei Valori di Shapley di Unione e di Intersezione offre nuovi strumenti per analizzare le interazioni, in particolare in scenari in cui la sovrapposizione dei contributi deve essere scontata (Unione) o in cui la pura sinergia deve essere isolata (Intersezione). Il lavoro stabilisce che questi valori non sono euristiche arbitrarie, ma sono univocamente determinati da assiomi fondamentali come i Contributi Bilanciati, il Potenziale e l'Uguaglianza di Gruppo.