Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

1. Problema e Contesto

Il paper affronta il problema della formazione di coalizioni in scenari reali dove gli agenti sono egoisti e le loro preferenze non sono note a priori. A differenza dei modelli classici di giochi hedonici che assumono:

1. Coalizioni disgiunte (ogni agente appartiene a una sola coalizione).
2. Preferenze completamente note.

Questo lavoro introduce un nuovo modello di formazione di coalizioni con sovrapposizione possibile (POCF - Possibly Overlapping Coalition Formation) in un regime di informazione parziale.

• Sovrapposizione: Gli agenti possono partecipare a più coalizioni simultaneamente (es. un consulente che lavora su progetti in diversi domini).
• Informazione Parziale: Le preferenze degli agenti sono sconosciute. Invece di interagire attivamente con l'ambiente (che potrebbe essere costoso o rischioso, come nel caso di un'azienda di consulenza), l'algoritmo deve inferire le preferenze da un dataset offline fisso contenente interazioni passate e feedback di utilità.
• Obiettivo: Utilizzare questo dataset per inferire le preferenze e costruire una struttura di coalizioni che sia Nash Stabile (NS) (o approssimativamente tale), ovvero una configurazione in cui nessun agente può migliorare la propria utilità deviando unilateralmente.

2. Metodologia

L'autore propone un framework di apprendimento offline basato su due modelli di feedback di utilità, che differiscono per granularità delle informazioni disponibili nel dataset:

A. Modelli di Feedback

1. Feedback Semi-Blind (Semi-bandit): Il dataset fornisce l'utilità a livello di agente per ogni interazione con gli altri membri delle coalizioni scelte. Si conoscono i valori $v_{i,j}^\ell$ (utilità dell'agente $i$ verso $j$ nella coalizione $\ell$).
2. Feedback Bandit: Il dataset fornisce solo l'utilità complessiva a livello di coalizione per ogni agente ($v_i(a)$), senza dettagli sulle interazioni individuali.

B. Algoritmo Proposto: Minimizzazione del Surrogato

L'approccio centrale è l'Algoritmo 1, un framework di minimizzazione del surrogato che utilizza stime di utilità con "bonus di esplorazione" (exploration bonuses) per gestire l'incertezza.

• Stima delle Preferenze: Per ogni agente, si stima l'utilità media basandosi sui dati storici.
• Bonus di Esplorazione: Vengono introdotti limiti di confidenza (Upper/Lower Confidence Bounds) per garantire che la stima sia conservativa.
• Ottimizzazione: L'algoritmo cerca una strategia congiunta $\phi$ che minimizzi il "dual gap" (duality gap) stimato, definito come la massima differenza tra l'utilità della migliore risposta e l'utilità attuale per qualsiasi agente.
  $$\text{Gap}(\phi) \approx \max_i [V_i^*(\phi_{-i}) - V_i(\phi)]$$
  Minimizzare questo gap equivale a trovare una strategia $\epsilon$-Nash stabile.

C. Assunzioni di Copertura del Dataset

Il successo dell'apprendimento dipende da quanto il dataset copre le possibili deviazioni unilaterali:

• Caso Semi-Blind: Viene introdotta l'Assunzione 1 (Coalition Size Coverage). Il dataset deve contenere esempi di coalizioni di tutte le dimensioni che potrebbero risultare da una deviazione unilaterale da una strategia Nash stabile.
• Caso Bandit: L'Assunzione 1 non è sufficiente. Viene introdotta l'Assunzione 2 (Action Coverage), che richiede che il dataset sia almeno informativo quanto un dataset generato da deviazioni unilaterali specifiche, permettendo l'uso della regressione ridge per stimare i parametri di utilità nascosti.

3. Contributi Chiave

1. Nuovo Modello: Definizione formale di giochi POCF con preferenze simmetriche e additivamente separabili in setting offline.
2. Condizioni Necessarie e Sufficienti:
   • Per il feedback semi-blind, l'Assunzione 1 è dimostrata essere necessaria e sufficiente per un apprendimento efficiente. Senza di essa, nessun algoritmo può garantire la stabilità Nash indipendentemente dalla dimensione del dataset.
   • Per il feedback bandit, viene dimostrato che l'Assunzione 1 è insufficiente e che è necessaria un'assunzione più forte (Assunzione 2) per garantire l'apprendimento.
3. Algoritmi a Complessità Campionaria Ottimale:
   • Vengono sviluppati algoritmi che raggiungono una stabilità Nash approssimata ($\epsilon$-NS) con una complessità campionaria che dipende ottimamente da $1/\epsilon$ (fino a fattori logaritmici).
   • I limiti di complessità sono indipendenti dal numero esponenziale di azioni possibili, superando le limitazioni dei metodi tradizionali di apprendimento offline in giochi multi-agente.
4. Analisi Teorica: Dimostrazione che i giochi POCF simmetrici sono giochi potenziali, garantendo l'esistenza di almeno una strategia Nash stabile pura (e mista).

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su dataset sintetici con diverse configurazioni di agenti ($n$) e coalizioni candidate ($k$).

• Feedback Semi-Blind:
  • L'algoritmo converge a un basso dual gap (alta stabilità) quando il dataset è generato da una politica di esplorazione uniforme ($\rho_{rand}$) che soddisfa l'Assunzione 1.
  • Fallisce nel raggiungere la stabilità quando il dataset è generato da una politica che viola l'Assunzione 1 (es. $\rho_{1Rand}$ che non copre tutte le dimensioni di coalizione), confermando la necessità teorica dell'assunzione.
  • La scala del gap rispetto alla dimensione del dataset ($M$) segue la previsione teorica di $O(1/\sqrt{M})$.
• Feedback Bandit:
  • Risultati simili: l'apprendimento efficace richiede politiche di esplorazione che soddisfino l'Assunzione 2. Le politiche che non coprono sufficientemente le deviazioni portano a performance scadenti.
• Robustezza: L'algoritmo funziona bene anche con diverse distribuzioni di utilità (Uniforme, Gaussiana, dipendenti dalla dimensione della coalizione).

5. Significato e Impatto

Questo lavoro è significativo per diverse ragioni:

• Realismo: Colma il divario tra la teoria dei giochi hedonici (spesso basata su preferenze note e coalizioni disgiunte) e scenari reali complessi (consulenza, gestione di team, risorse condivise) dove le preferenze sono nascoste e le sovrapposizioni sono comuni.
• Efficienza dei Dati: Dimostra che è possibile raggiungere la stabilità strategica utilizzando solo dati storici, evitando costosi esperimenti di interazione attiva.
• Teoria dell'Apprendimento: Estende i principi dell'apprendimento offline (RL offline) ai giochi cooperativi e non cooperativi, fornendo garanzie teoriche rigorose sulla copertura necessaria dei dati per l'apprendimento di equilibri di Nash.
• Applicabilità: Offre un metodo pratico per organizzazioni che devono riorganizzare team o assegnare risorse basandosi su dati storici di performance e valutazioni tra pari, senza dover testare nuove configurazioni in tempo reale.

In sintesi, il paper stabilisce le fondamenta teoriche e pratiche per l'apprendimento di strutture di coalizioni stabili in ambienti complessi e sovrapposti, utilizzando esclusivamente dati offline, identificando chiaramente i requisiti di copertura dei dati necessari per il successo dell'apprendimento.