NashOpt -- A Python Library for Computing Generalized Nash Equilibria

NashOpt è una libreria Python open-source che calcola equilibri di Nash generalizzati in giochi non cooperativi con vincoli condivisi, sfruttando le condizioni KKT congiunte e strumenti come JAX e la programmazione lineare intera mista per risolvere sia giochi non lineari che lineari-quadratici, inclusi problemi di progettazione inversa e di Stackelberg.

L'essenziale

Immagina di essere in una stanza piena di persone che devono prendere decisioni insieme, ma ognuna ha i suoi obiettivi personali e ci sono delle regole che tutti devono rispettare. Ad esempio: guidare nello stesso traffico, usare la stessa banda internet, o gestire l'energia in una città.

La NashOpt è un "cervello digitale" (una libreria di software scritta in Python) che aiuta a capire come queste persone si comporteranno quando ognuno cercherà di fare il proprio interesse, rispettando le regole comuni. Il suo obiettivo è trovare il Punto di Equilibrio Generale di Nash: una situazione in cui nessuno ha motivo di cambiare la propria decisione perché, date le scelte degli altri, non può fare di meglio.

Ecco come funziona, spiegato con delle metafore semplici:

1. Il Problema: Trovare la "Tregua Perfetta"

Immagina un gioco dove ogni giocatore deve scegliere un percorso. Se tutti scelgono la strada più veloce per se stessi, si crea un ingorgo (il "paradosso del traffico"). NashOpt cerca di calcolare esattamente quale sarà la situazione finale: chi prenderà quale strada e quanto tempo impiegherà, sapendo che tutti stanno pensando allo stesso modo.

2. Due Modi per Risolvere il Gioco

Il software usa due "cervelli" diversi a seconda di quanto è complicato il gioco:

• Per i giochi semplici e lineari (Il Metodo dei "Blocchi Lego"):
  Se le regole e i costi sono dritti e semplici (come costruire con i Lego), NashOpt trasforma il problema in un puzzle matematico chiamato Programmazione Lineare Intera.

  • L'analogia: È come se avessi un set di istruzioni preciso per costruire un castello. Il computer prova tutte le combinazioni possibili di "blocchi" (scelte) per trovare quella che funziona meglio. Se ci sono più soluzioni possibili, NashOpt può elencarle tutte, come se ti dicesse: "Ecco 3 modi diversi per costruire il castello che soddisfano le regole".

• Per i giochi complessi e curvi (Il Metodo della "Bussola Digitale"):
  Se le regole sono curve, contorte o molto difficili (come guidare su una strada di montagna con curve strette), NashOpt usa un approccio diverso basato su JAX (una tecnologia molto veloce).

  • L'analogia: Immagina di essere su una montagna nebbiosa e devi trovare il punto più basso (il minimo costo). NashOpt lancia una "bussola" che calcola istantaneamente in quale direzione scendere. Fa milioni di calcoli al secondo per scivolare giù fino a trovare il punto di equilibrio, anche se il terreno è molto accidentato.

3. Le Applicazioni Magiche

NashOpt non si limita a guardare il gioco, può anche progettarlo:

• Il "Capo" che disegna le regole (Giochi di Stackelberg):
  Immagina un sindaco che vuole che il traffico scorra bene. NashOpt può dire al sindaco: "Se imposti il semaforo su questo colore e limiti la velocità a quel valore, i guidatori (che agiscono per interesse proprio) finiranno naturalmente per non creare ingorghi". È come se il software disegnasse le regole del gioco per ottenere un risultato desiderato.
• Il "Detective" (Giochi Inversi):
  Se vedi un risultato finale (es. "tutti usano la strada A"), NashOpt può lavorare al contrario e chiedersi: "Quali erano le regole o i prezzi che hanno portato le persone a scegliere proprio quella strada?". È come un detective che ricostruisce la scena del crimine partendo dal risultato.
• Il "Controllore del Traffico" (MPC e LQR):
  Viene usato per controllare robot o sistemi energetici. Immagina un gruppo di droni che devono volare insieme senza scontrarsi. NashOpt calcola come ogni drone deve muoversi per non urtare gli altri, massimizzando la propria efficienza.

4. Perché è speciale?

• È veloce: Usa la potenza dei computer moderni per fare calcoli che prima richiedevano ore in pochi millisecondi.
• È flessibile: Funziona sia per problemi semplici (come dividere una torta) che per problemi complessi (come gestire l'energia di una città intera).
• È gratuito: È un progetto "open-source", il che significa che chiunque può scaricarlo, studiarlo e usarlo per le proprie ricerche o applicazioni.

In sintesi:
NashOpt è come un simulatore di realtà per le decisioni umane. Ti permette di dire: "E se facessimo così? E se cambiassimo questa regola?" e ti risponde immediatamente mostrando come reagirebbero le persone, aiutandoti a progettare sistemi migliori, più sicuri ed efficienti, dove ognuno può perseguire il proprio obiettivo senza creare il caos.

Sommario tecnico

Titolo e Scopo

Il documento presenta NashOpt, una libreria Python open-source sviluppata da Alberto Bemporad per il calcolo e la progettazione di Equilibri di Nash Generalizzati (GNE) in giochi non cooperativi caratterizzati da vincoli condivisi e variabili decisionali a valori reali. L'obiettivo principale è fornire strumenti per analizzare il comportamento di agenti multipli che perseguono obiettivi individuali in un ambiente condiviso e per progettare tali giochi al fine di ottenere equilibri desiderati.

1. Formulazione del Problema

Il lavoro si concentra sul Generalized Nash Equilibrium Problem (GNEP), una situazione in cui $N$ agenti ottimizzano funzioni obiettivo individuali $f_i$ soggette a vincoli che dipendono dalle decisioni degli altri agenti (vincoli condivisi).
Il framework generale include anche problemi di design del gioco (o giochi inversi), formulati come problemi di ottimizzazione a due livelli (Single-Leader-Multi-Follower o Stackelberg):

• Un "leader" ottimizza un vettore di parametri $p$ per influenzare l'equilibrio.
• I "follower" giocano un GNEP parametrizzato da $p$.

L'obiettivo del leader può essere:

1. Risolvere un GNEP specifico.
2. Trovare un parametro $p$ per cui esiste un equilibrio.
3. Problema inverso: Trovare $p$ tale che l'equilibrio risultante $x^*$ sia il più vicino possibile a un equilibrio desiderato $x^{des}$.

2. Metodologia e Algoritmi

La libreria utilizza due approcci distinti a seconda della natura del gioco (non lineare o lineare-quadratico):

A. Giochi Non Lineari (GNE Non Lineari)

Per giochi con funzioni obiettivo e vincoli non lineari, il metodo si basa sulle condizioni di Karush-Kuhn-Tucker (KKT) congiunte di tutti i giocatori.

• Formulazione: Le condizioni KKT (stazionarietà, fattibilità, complementarità) sono trasformate in un problema di ricerca dello zero ($R(z, p) = 0$) utilizzando la funzione di complementarità non lineare di Fischer-Burmeister.
• Risoluzione: Il problema viene risolto come un problema di minimi quadrati non lineari ($\min \frac{1}{2}\|R(z, p)\|^2$).
• Tecnologie: Sfrutta JAX per la differenziazione automatica e la compilazione Just-In-Time (JIT) per alte prestazioni. Vengono utilizzati algoritmi come Levenberg-Marquardt (LM).
• Design del gioco: Per i problemi di design, le condizioni di equilibrio vengono rilassate e incorporate nella funzione obiettivo come termine di penalità (approccio MPEC rilassato), risolto tramite ottimizzazione non lineare vincolata (es. L-BFGS-B).
• Regolarizzazione: Supporta la ricerca di soluzioni sparse tramite termini di regolarizzazione $\ell_1$, riformulando il problema per gestire la non differenziabilità.

B. Giochi Lineari-Quadratici (LQ Games)

Per giochi con costi quadratici e vincoli lineari, le condizioni KKT sono necessarie e sufficienti.

• Riformulazione MILP/MIQP: Le condizioni di complementarità vengono codificate utilizzando vincoli "Big-M" e variabili binarie, trasformando il problema GNE in un Programma Lineare Intero Misto (MILP) o Quadratico Intero Misto (MIQP).
• Vantaggi: Questo approccio permette di trovare l'ottimo globale e di enumerare tutti gli equilibri possibili (corrispondenti a diverse combinazioni di vincoli attivi) iterando sul problema MILP con vincoli "no-good".
• Solutori: Utilizza solutori come HiGHS (open-source) o Gurobi.
• Variational GNE (vGNE): Una variante dove i moltiplicatori di Lagrange per i vincoli condivisi sono uguali per tutti i giocatori, riducendo il numero di variabili.
• Alternativa ADMM: Per i vGNE lineari-quadratici, viene proposta anche un'alternativa basata sull'algoritmo Proximal ADMM, che offre una soluzione chiusa per gli aggiornamenti iterativi.

3. Applicazioni ai Sistemi di Controllo

La libreria è applicata a problemi di controllo basati sulla teoria dei giochi:

1. Regolazione Lineare-Quadratica (LQR) Non Cooperativa: Calcolo di guadagni di retroazione di Nash per sistemi dinamici condivisi, confrontati con la soluzione LQR centralizzata (cooperativa).
2. Controllo Predittivo (MPC) Non Cooperativo: Formulazione di problemi MPC multi-agente con vincoli condivisi (es. limiti di output), risolti come GNEP. Viene mostrato come l'approccio competitivo possa portare a prestazioni diverse (spesso peggiori) rispetto alla soluzione cooperativa centralizzata.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su un Macbook Pro (chip M4 Max) e dimostrano l'efficacia della libreria:

• Efficienza Computazionale:
  • Per giochi LQ, l'approccio MILP (con HiGHS o Gurobi) è circa due ordini di grandezza più veloce dell'approccio a minimi quadrati non lineari (LM) per un numero crescente di agenti.
  • L'approccio ADMM è competitivo per i vGNE, ma l'MILP scala meglio per problemi di piccole e medie dimensioni.
  • La risoluzione di problemi GNE non lineari tramite JAX/LM è efficiente grazie alla compilazione JIT.
• Problemi Inversi e Design: La libreria riesce a recuperare con alta precisione i parametri di gioco che generano un equilibrio desiderato (errori nell'ordine di $10^{-13}$o$10^{-14}$).
• Sparsità: L'uso della regolarizzazione $\ell_1$ permette di ottenere equilibri sparsi, controllando il trade-off tra la sparsità della soluzione e il costo del gioco.
• Controllo: Negli esempi di LQR e MPC, la libreria calcola rapidamente gli equilibri di Nash, evidenziando le differenze significative tra comportamenti cooperativi e non cooperativi (es. stabilità del sistema e traiettorie di uscita).

5. Contributi Chiave e Significato

• Libreria Unificata: NashOpt è uno dei primi pacchetti open-source in Python che integra sia la risoluzione di GNE non lineari (tramite JAX) che lineari-quadratici (tramite MILP/MIQP) in un unico framework coerente.
• Capacità di Design: Offre strumenti nativi per il "game design" e i problemi inversi, permettendo di modellare come modificare le regole del gioco per raggiungere obiettivi di sistema.
• Enumerazione degli Equilibri: L'approccio MILP permette di identificare tutti gli equilibri possibili in giochi LQ, non solo uno, cosa rara nella letteratura attuale.
• Accessibilità: La disponibilità su GitHub e l'installazione via pip rendono queste tecniche avanzate accessibili a ricercatori e ingegneri.
• Impatto: La libreria è uno strumento prezioso per l'analisi di sistemi complessi in ingegneria (reti energetiche, controllo del traffico, sistemi wireless) ed economia, dove le interazioni strategiche e i vincoli condivisi sono fondamentali.

In sintesi, NashOpt rappresenta un avanzamento significativo nella computazione pratica degli equilibri di Nash generalizzati, combinando robustezza teorica (KKT, MILP) con tecnologie moderne di calcolo scientifico (JAX, solutori moderni).