Aggregative games with bilevel structures: Distributed algorithms and convergence analysis

Sintesi Tecnica: Giochi Aggregativi con Strutture Bilevel: Algoritmi Distribuiti e Analisi della Convergenza

Formulazione del Problee
Questo articolo affronta il problema della ricerca distribuita dell'equilibrio di Nash (NE) in giochi aggregativi (AG) caratterizzati da strutture bilevel. A differenza dei tradizionali AG in cui il termine di aggregazione è una somma diretta o una media delle azioni locali dei giocatori, l'aggregazione in questo framework è determinata dal minimizzatore della funzione obiettivo di un leader virtuale in un livello interno. Nello specifico, il gioco $\Gamma(V, \Omega, J)$ coinvolge $n$ giocatori in un livello esterno, ciascuno dei quali minimizza una funzione di costo $J_i(x_i, \sigma(x))$ dipendente dalla propria azione locale $x_i$ e da una variabile di aggregazione globale $\sigma(x)$. La variabile $\sigma(x)$ è definita come la soluzione di un problema di ottimizzazione di livello interno:
$$\sigma(x) = \arg \min_{y} \sum_{i=1}^n g_i(x_i, y)$$
dove $g_i$ rappresenta una funzione locale del giocatore $i$ e della variabile di aggregazione $y$. L'obiettivo globale del leader virtuale è la somma di queste funzioni locali, le quali si assume siano fortemente convesse rispetto a $y$.

Una sfida critica identificata è che i giocatori nel livello esterno possiedono solo informazioni locali: la propria funzione di costo $J_i$, una parte locale della funzione obiettivo del leader virtuale $g_i$ e il proprio insieme di azioni locali. Essi non possono accedere all'informazione completa della funzione obiettivo del livello interno o al termine di aggregazione globale direttamente. Di conseguenza, il gradiente della funzione di costo di un giocatore nel livello esterno dipende da $\nabla_{x_i}\sigma(x)$, il quale coinvolge l'inversa della somma delle matrici Hessiane delle funzioni del livello interno—un termine non direttamente accessibile ai singoli giocatori.

Metodologia
Per risolvere questo problema sotto un grafo di comunicazione connesso, gli autori propongono due algoritmi distribuiti:

1. Algoritmo Distribuito Basato su Gradiente del Secondo Ordine (SOGD):
   Questo algoritmo assume che i giocatori abbiano accesso alle informazioni del gradiente del secondo ordine (matrici Hessiane). Esso integra tre componenti:

   • Strategia Primal-Dual: Utilizzata per stimare l'aggregazione $\sigma(x)$ minimizzando cooperativamente la funzione obiettivo globale del livello interno.
   • Distributed Average Tracking: Impiegato per tracciare la media delle matrici Hessiane associate alle funzioni obiettivo del livello interno.
   • Discesa del Gradiente con Proiezione: I giocatori aggiornano le loro azioni nel livello esterno utilizzando una strategia di gradiente proiettato che coinvolge il metodo iterativo di Krasnoselskii-Mann. Questa strategia utilizza l'informazione Hessiana tracciata per calcolare i termini di gradiente necessari per le funzioni di costo del livello esterno.

2. Algoritmo Distribuito Basato su Gradiente del Primo Ordine (FOGD):
   Riconoscendo che il calcolo delle matrici Hessiane può essere costoso o impossibile in applicazioni ad alta dimensionalità (ad esempio, il meta-learning), gli autori propongono un metodo del primo ordine.

   • Strategia di Stima Distribuita: Inveve di calcolare le matrici Hessiane, questo algoritmo introduce una variabile ausiliaria e un parametro di perturbazione $\delta_i$. Esso stima il prodotto tra il gradiente dell'aggregazione e il gradiente della funzione di costo rispetto al secondo argomento.
   • Ottimizzazione Ausiliaria: I giocatori risolvono un problema di ottimizzazione ausiliario per stimare i termini di gradiente necessari, evitando l'uso diretto di informazioni del secondo ordine.

Contributi Chiave
L'articolo rivendica le seguenti novità e contributi:

• Framework Generalizzato: Il proposto framework bilevel generalizza gli esistenti AG a singolo livello e i problemi di ottimizzazione distribuita con obiettivi fortemente convessi. Si differenzia dalle precedenti formulazioni di giochi di Stackelberg in cui i giocatori hanno tipicamente accesso all'informazione completa del gradiente; qui, l'aggregazione dipende da una soluzione di livello interno che non è completamente osservabile.
• Design dell'Algoritmo SOGD: Gli autori sviluppano un nuovo algoritmo che combina metodi primal-dual, distributed average tracking e discesa del gradiente. Dimostrano che, sotto ipotesi deboli, le azioni dei giocatori convergono asintoticamente al NE con un tasso di convergenza di $O(\sqrt{\ln t}/t)$.
• Algoritmo FOGD e Analisi dell'Errore: Per i casi in cui le matrici Hessiane non sono disponibili, viene introdotto l'algoritmo FOGD. Gli autori stabiliscono una relazione lineare tra l'errore di convergenza e il parametro di stima $\delta_i$, provando che l'errore è lineare rispetto a tali parametri.

Risultati e Analisi della Convergenza

• Convergenza SOGD: Sotto le ipotesi di connettività del grafo, convessità, forte convessità delle funzioni interne e continuità Lipschitziana, l'algoritmo SOGD garantisce che le azioni dei giocatori $x_t$ e le stime dell'aggregazione $y_{i,t}$ convergano rispettivamente al NE $x^*$ e $\sigma(x^*)$. Il tasso di convergenza è mostrato essere $O(\sqrt{\ln t}/t)$, che gli autori notano essere più veloce del comune tasso $O(\ln t/\sqrt{t})$ per l'ottimizzazione distribuita con step-size decrescenti.
• Convergenza FOGD: L'algoritmo FOGD raggiunge la convergenza verso un NE approssimato. L'analisi teorica dimostra che gli errori di convergenza sono limitati da termini che coinvolgono i parametri di stima $\delta_i$. Nello specifico, il limite dell'errore include un termine proporzionale a $\sqrt{\delta_i} + \delta_i$, indicando che un $\delta_i$ più piccolo produce un'accuratezza maggiore, sebbene i vincoli pratici impediscano che $\delta_i$ sia arbitrariamente piccolo.
• Simulazione Numerica: Gli algoritmi sono stati testati su un problema distribuito di allocazione della potenza in una rete small-cell composta da 20 stazioni base. Le simulazioni hanno confermato che entrambi gli algoritmi guidano il sistema verso l'equilibrio teorico, con traiettorie delle metriche di errore che decadono nel tempo come previsto.

Significatività e Rivendicazioni
L'articolo si posiziona come il primo studio sui giochi aggregativi distribuiti con strutture bilevel in cui l'aggregazione è determinata dal problema di minimizzazione di livello interno di un leader virtuale e i giocatori mancano di informazioni complete riguardo questo livello interno. Gli autori sottolineano che il loro lavoro unifica i framework di ricerca per i tradizionali AG e l'ottimizzazione distribuita.

La significatività risiede nel fornire una base teorica e algoritmi pratici per scenari in cui il "prezzo" o l' "aggregazione" è una proprietà emergente di un processo di ottimizzazione complesso e distribuito (ad esempio, il pricing di rete nelle reti small-cell) piuttosto che una semplice somma di azioni. L'articolo riconosce con modestia che, sebbene l'algoritmo FOGD raggiunga una convergenza approssimata, ottenere una convergenza accurata utilizzando solo informazioni del primo ordine rimane un problema difficile per la ricerca futura. Si suggerisce che il lavoro futuro affronti i ritardi indotti dalla rete, la perdita di pacchetti e i vincoli di larghezza di banda della comunicazione.