NashOpt -- A Python Library for Computing Generalized Nash Equilibria

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je in een drukke stad bent waar honderden mensen tegelijkertijd proberen hun weg te vinden. Iedereen heeft zijn eigen bestemming (zijn eigen doel), maar ze moeten allemaal dezelfde straten gebruiken, dezelfde stoplichten gehoorzamen en zich houden aan de verkeersregels. Als iedereen alleen maar aan zichzelf denkt, kan het leiden tot enorme files of chaos.

Dit is precies wat NashOpt doet, maar dan voor computers en complexe systemen. Het is een nieuwe, gratis softwaretool (geschreven in Python) die helpt om de "perfecte balans" te vinden in situaties waar meerdere partijen met elkaar concurreren, maar wel afhankelijk zijn van elkaar.

Hier is een uitleg in gewone taal, met een paar leuke vergelijkingen:

1. Het Probleem: De "Spelers" en de "Gemeenschappelijke Regels"

In de wereld van NashOpt zijn er meerdere spelers (bijvoorbeeld bedrijven, auto's in een file, of stroomleveranciers).

Elk heeft een eigen doel: Bedrijf A wil zo veel mogelijk winst maken. Auto B wil zo snel mogelijk thuis zijn.
Ze delen beperkingen: Ze moeten allemaal binnen hetzelfde snelheidsgebied blijven, of ze delen dezelfde elektriciteitskabel.
Het dilemma: Als ik mijn snelheid verhoog, kan dat jouw reistijd beïnvloeden. Als jij je stroomverbruik verhoogt, kan dat de prijs voor mij verhogen.

De oplossing die NashOpt zoekt, heet een Generalized Nash Evenwicht. Dit is een situatie waarin niemand er baat bij heeft om zijn strategie te veranderen, zolang de anderen hun strategie niet veranderen. Het is alsof iedereen in de file heeft besloten: "Ik ga niet harder rijden, want dan krijg ik een boete en sta ik toch niet sneller."

2. Hoe werkt NashOpt? (De Twee Manieren)

De software gebruikt twee verschillende "denkmethoden" afhankelijk van hoe complex het spel is:

A. De "Gladde Berg" methode (Voor complexe, niet-lineaire spellen)

Stel je voor dat je in een donker, hobbelig landschap staat en je moet de laagste vallei vinden. Je kunt niet zien waar de bodem is, maar je kunt voelen of het terrein omhoog of omlaag gaat.

NashOpt gebruikt een slimme techniek (genaamd JAX) die als een super-snelheidssensor werkt. Hij "voelt" direct welke kant op je moet lopen om de beste oplossing te vinden, zonder dat je alles handmatig hoeft uit te rekenen.
Dit is perfect voor situaties waar de regels erg ingewikkeld en krom zijn (zoals in complexe economische modellen of AI).

B. De "Legpuzzel" methode (Voor lineaire, kwadratische spellen)

Soms zijn de regels heel strak en rechtlijnig (zoals in een legpuzzel waar elke stukje precies in een gleuf past).

Hier gebruikt NashOpt een andere aanpak: hij zet het hele probleem om in een Mixed-Integer Linear Program (MILP).
De analogie: Stel je voor dat je een enorme legpuzzel hebt met stukjes die ofwel "aan" of "uit" kunnen staan. NashOpt probeert alle mogelijke combinaties van deze stukjes te testen om te zien welke combinatie de beste oplossing geeft.
Het mooie hieraan is dat hij alle mogelijke oplossingen kan vinden. Soms is er niet één perfecte balans, maar meerdere. NashOpt kan ze allemaal op een rijtje zetten, zodat je kunt kiezen welke je wilt.

3. Wat kun je er allemaal mee doen?

De makers van NashOpt laten zien dat je deze tool kunt gebruiken voor veel verschillende dingen:

Het "Invers Spel" (De detective):
Stel je ziet een verkeerssituatie en je vraagt je af: "Welke verkeersregels moeten er zijn geweest om dit gedrag te veroorzaken?" NashOpt kan dit omgekeerd oplossen. Je geeft het gedrag, en de software berekent welke regels er moesten zijn om dat gedrag te krijgen.
De "Spelontwerper" (De architect):
Stel je bent een overheid of een manager. Je wilt dat de spelers (bijvoorbeeld bedrijven) een bepaald resultaat bereiken (bijvoorbeeld minder vervuiling). NashOpt helpt je om de regels van het spel (de parameters) zo in te stellen dat de spelers, terwijl ze alleen maar aan zichzelf denken, toch per ongeluk het gewenste resultaat bereiken. Dit heet een Stackelberg-spel.
Slimme Regelaars (LQR en MPC):
Dit wordt gebruikt voor robotica en zelfrijdende auto's. Als je een groep drones hebt die samen een formatie moeten vormen, maar elk drone wil zijn eigen batterij sparen, helpt NashOpt om te berekenen hoe ze samen moeten vliegen zonder te botsen, terwijl ze allemaal hun eigen belangen bewaken.

4. Waarom is dit belangrijk?

Vroeger was het heel moeilijk om dit soort berekeningen te maken, vooral als er veel spelers bij betrokken waren of als de regels erg complex waren.

Snelheid: NashOpt is razendsnel. Het kan in een fractie van een seconde berekenen wat een mensuren zou kosten.
Open Source: Het is gratis beschikbaar voor iedereen. Iedereen kan het gebruiken, aanpassen en verbeteren.
Toekomst: Het helpt ons om betere systemen te bouwen voor verkeer, energie, financiën en kunstmatige intelligentie, waar veel verschillende partijen samenwerken (of concurreren) in dezelfde ruimte.

Kort samengevat:
NashOpt is als een super-intelligente scheidsrechter die in een chaotisch spel van concurrentie de perfecte balans vindt. Hij zorgt ervoor dat niemand zich bedrogen voelt en dat het systeem als geheel zo goed mogelijk werkt, of je nu een verkeersplan maakt, een stroomnet beheert of een groep robots aanstuurt.

Each language version is independently generated for its own context, not a direct translation.

Titel: NashOpt: Een Python-bibliotheek voor het berekenen van Generalized Nash Equilibria (GNE)

Auteur: Alberto Bemporad (IMT School for Advanced Studies, Lucca, Italië)
Datum: 10 maart 2026

1. Probleemstelling

Het paper richt zich op Generalized Nash Equilibrium Problems (GNEPs) in niet-coöperatieve spellen. In deze scenario's nemen meerdere agenten (spelers) beslissingen door hun individuele doelfuncties te optimaliseren, onderworpen aan gemeenschappelijke beperkingen die afhangen van de beslissingen van de andere spelers.

De uitdagingen die worden aangepakt zijn:

Het vinden van evenwichten in zowel niet-lineaire spellen als lineair-kwadratische spellen.
Het omgaan met gedeelde ongelijkheids- en gelijkheidsbeperkingen.
Het oplossen van inverse spelproblemen (het vinden van spelparameters die leiden tot een gewenst evenwicht).
Het ontwerpen van spellen (Stackelberg-spellen) waarbij een centrale autoriteit parameters optimaliseert om een specifiek evenwicht te bereiken.
Het toepassen van deze concepten op game-theoretische besturing, zoals Lineaire Kwantum Regeling (LQR) en Model Predictive Control (MPC).

Er is een gebrek aan softwarepakketten die deze algemene klassen van GNEPs efficiënt kunnen oplossen, vooral voor toepassing in besturingssystemen.

2. Methodologie

De kern van de NashOpt-bibliotheek is het gezamenlijk oplossen van de Karush-Kuhn-Tucker (KKT) voorwaarden voor alle spelers. Een GNE wordt gedefinieerd als een toestand waarin de KKT-voorwaarden voor elke speler gelijktijdig gelden.

De methode onderscheidt zich op basis van het type spel:

A. Niet-lineaire Spellen (Nonlinear GNEs)

Formulering: De KKT-voorwaarden worden omgezet in een nul-vindingsprobleem ( $R(z, p) = 0$ ), waarbij $z$ de verzameling van primaire en duale variabelen (Lagrange-multiplicatoren) bevat.
Techniek: De complementariteitsvoorwaarden (complementary slackness) worden geëncodeerd met de Fischer-Burmeister-functie, een niet-lineaire functie die de voorwaarden $\alpha \ge 0, \beta \ge 0, \alpha\beta=0$ transformeert naar een gladde vergelijking.
Oplossing: Het probleem wordt opgelost als een niet-lineair kleinste-kwadratenprobleem (minimiseren van $\frac{1}{2}\|R(z, p)\|^2_2$ ) met behulp van algoritmen zoals Levenberg-Marquardt.
Implementatie: De bibliotheek maakt gebruik van JAX voor automatische differentiatie en Just-In-Time (JIT) compilatie, wat zorgt voor hoge prestaties.

B. Lineair-Kwadratische Spellen (Linear-Quadratic GNEs)

Formulering: Voor spellen met kwadratische kostenfuncties en lineaire beperkingen worden de KKT-voorwaarden exact herschreven als een Mixed-Integer Linear Program (MILP) of Mixed-Integer Quadratic Program (MIQP).
Techniek: De complementariteitsvoorwaarden worden gemodelleerd met "big-M" beperkingen en binaire variabelen.
Oplossing: Gebruikmakend van oplosprogramma's zoals HiGHS (open source) of Gurobi.
Voordelen: Deze methode garandeert globale optimaliteit en maakt het mogelijk om meerdere evenwichten te vinden voor hetzelfde spel door iteratief "no-good" beperkingen toe te voegen om reeds gevonden combinaties van actieve beperkingen uit te sluiten.

C. Spelontwerp en Inverse Problemen

Optimalisatie: Het probleem wordt geformuleerd als een wiskundig programma met evenwichtsbeperkingen (MPEC). Om de complexiteit te vermijden, worden de evenwichtsbeperkingen "gestraffeld" (penalty method) in de doelfunctie, wat leidt tot een genormaliseerd niet-lineair optimalisatieprobleem.
Sparsiteit: Er wordt een $\ell_1$ -regularisatie toegevoegd om spare (verspreide) evenwichtoplossingen te vinden, wat nuttig is voor het selecteren van actieve variabelen.

D. Variational GNEs (vGNE)

Een specifieke subklasse van GNEs waarbij alle spelers dezelfde Lagrange-multiplicatoren delen voor de gedeelde beperkingen. Dit vermindert het aantal variabelen aanzienlijk en kan worden opgelost via MILP of via een Proximal ADMM-algoritme voor lineair-kwadratische spellen.

3. Belangrijkste Bijdragen

Open-source Bibliotheek (NashOpt): Een Python-bibliotheek die zowel niet-lineaire als lineair-kwadratische GNEs kan oplossen, inclusief inverse spelproblemen en spelontwerp.
Unificatie van Methoden: Een raamwerk dat zowel niet-lineaire kleinste-kwadratenmethoden (voor generaliteit) als MILP/MIQP-methoden (voor efficiëntie en globale optimaliteit bij lineaire spellen) combineert.
Meerdere Evenwichten: De mogelijkheid om alle mogelijke GNEs voor een lineair-kwadratisch spel te enumereren door verschillende combinaties van actieve beperkingen te verkennen.
Toepassing op Besturing: Demonstratie van de methoden op Game-Theoretic LQR en Model Predictive Control (MPC), waarbij niet-coöperatieve strategieën worden vergeleken met centrale (coöperatieve) oplossingen.
Prestaties: Gebruik van moderne tools (JAX, HiGHS, Gurobi) voor snelle berekeningen, zelfs bij grote aantallen agenten.

4. Resultaten en Experimenten

De auteurs testen de bibliotheek op diverse scenario's:

Lineair-Kwadratische Spellen: Vergelijking tussen MILP (HiGHS/Gurobi), Levenberg-Marquardt (LM) en Proximal ADMM.
- Resultaat: MILP is ongeveer twee orde van grootte sneller dan LM voor het vinden van GNEs in lineair-kwadratische spellen. Gurobi presteert beter dan HiGHS. ADMM is competitief voor variational GNEs maar vereist meer iteraties.
Inverse Spelontwerp: Het succesvol vinden van parameters $p$ die leiden tot een gewenst evenwicht $x_{des}$ , met zeer kleine foutmarges ( $< 10^{-13}$ ).
Stackelberg Spel: Een voorbeeld met een leider en 8 volgers, waarbij de leider parameters optimaliseert. Het toont aan dat verschillende initialisaties leiden tot verschillende lokale minima (niet-convexiteit).
Game-Theoretic LQR & MPC:
- Vergelijking tussen niet-coöperatieve en centrale besturing toont aan dat niet-coöperatieve spellen vaak leiden tot minder stabiele systemen (hogere spectrale straal) en suboptimale prestaties.
- De CPU-tijd voor het oplossen van GNEP's in MPC is aanzienlijk hoger dan voor centrale QP-oplossingen, maar nog steeds haalbaar (milliseconden tot honderden milliseconden).
Sparsiteit: Demonstratie dat $\ell_1$ -regularisatie effectief is om de grootte van de oplossing (aantal niet-nul elementen) te verminderen, ten koste van een iets hogere kostenfunctie.

5. Significantie en Conclusie

Het paper introduceert een krachtig en veelzijdig hulpmiddel voor onderzoekers en ingenieurs op het gebied van game-theorie en game-theoretische besturing.

Praktische Toepasbaarheid: De bibliotheek maakt het mogelijk om complexe interacties in systemen zoals verkeersnetwerken, energienetwerken (prosumers) en markten te modelleren en te analyseren.
Ontwerp van Systemen: Het biedt een methode om de regels van een spel (de parameters) zo te ontwerpen dat het systeem van nature convergeren naar een gewenst sociaal of technisch optimaal evenwicht.
Technische Innovatie: Door de combinatie van automatische differentiatie (JAX) en geavanceerde mengd integer-programmering, overbrugt NashOpt de kloof tussen theoretische optimalisatie en praktische implementatie in real-time besturingssystemen.

De bibliotheek is open-source beschikbaar via GitHub en is ontworpen om schaalbaar te zijn, hoewel de complexiteit van MILP-oplossingen toeneemt met het aantal gedeelde beperkingen.