🤖 machine learning

Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

Deze paper introduceert een model voor het offline leren van Nash-stabiele coalitiestructuren met mogelijk overlappende coalities onder gedeeltelijke informatie, en biedt sample-efficiënte algoritmen die agentenvoorkeuren infereren uit een offline dataset om stabiele partities te vinden.

Oorspronkelijke auteurs: Saar Cohen

Gepubliceerd 2026-02-17

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Saar Cohen

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de manager bent van een groot consultancybureau. Je hebt een team van consultants en een reeks nieuwe projecten (finance, logistiek, marketing, etc.). Je wilt de beste teams vormen, maar hier zit een addertje onder het gras:

Mensen kunnen in meerdere teams zitten: Een consultant kan tegelijkertijd werken aan een financieel project én een logistiek project.
Je kent de voorkeuren niet: Je weet niet precies wie met wie goed samenwerkt. Soms werken twee mensen fantastisch samen in de logistiek, maar ruziën ze in de financiële afdeling.
Je kunt niet experimenteren: Je kunt niet zomaar teams willekeurig samenstellen om te kijken wat er gebeurt. Dat kost te veel tijd, geld en riskeert de relatie met de klant.

Je hebt dus alleen een oud archief (een dataset) met eerdere projectresultaten en beoordelingen. Je doel is om op basis van dit oude archief een nieuwe indeling te maken waarbij niemand het idee heeft: "Ik kan mijn werk beter doen als ik naar een ander team ga." In de vakwereld noemen we dit een Nash-stabiele coalitie.

Dit paper van Saar Cohen lost precies dit probleem op. Hier is de uitleg in simpele taal:

1. Het Probleem: Gokken met een blinddoek

Normaal gesproken zouden we zeggen: "Laten we gewoon proberen!" Maar in de echte wereld is dat te duur. We moeten leren van het verleden. Het probleem is dat we niet weten waarom een team goed of slecht presteerde. We zien alleen het eindresultaat.

De auteur onderscheidt twee manieren waarop we die oude data kunnen bekijken:

De "Semi-bandit" manier (De gedetailleerde versie): We weten precies wie met wie heeft samengewerkt en hoeveel elk individu daar van genoot. Voorbeeld: We weten dat Jan en Piet in het logistieke team een 8 kregen, maar in het financiële team een 2.
De "Bandit" manier (De vaagere versie): We weten alleen het totaalresultaat van een team. Voorbeeld: We weten dat het logistieke team een 8 kreeg, maar we weten niet of dat door Jan, Piet of allebei kwam. Dit is veel lastiger te ontcijferen.

2. De Oplossing: De "Verkenner" en de "Veiligheidsmarge"

De auteur bedacht een slim algoritme (een computerprogramma) dat dit oude archief leest en een nieuw teamplan maakt. Het werkt met twee belangrijke concepten:

Het Dekkingsprincipe (De Verkenner):
Stel je voor dat je een kaart tekent van alle mogelijke teams. Om een goed team te vinden, moet je kaart alle mogelijke routes hebben gezien.
- Als iemand in het echte leven besluit om van team te wisselen (bijvoorbeeld van 3 naar 4 personen), dan moet er in je oude archief minstens één oud project zijn dat precies die situatie (4 personen) laat zien.
- Als je archief alleen maar projecten met 2 of 5 personen bevat, maar nooit 4, dan kan het algoritme niet voorspellen wat er gebeurt als iemand overstapt. Het is alsof je probeert te leren zwemmen zonder ooit in water te zijn geweest.
- De auteur bewijst dat als je archief deze "dekking" heeft, je een goed teamplan kunt maken. Als niet, is het onmogelijk om zeker te zijn.
De Veiligheidsmarge (De Optimist en de Pessimist):
Omdat we niet alles precies weten, maakt het algoritme twee schattingen voor elke mogelijke teamindeling:
1. Een optimistische schatting: "Wat is het beste dat er kan gebeuren als ik dit team kies?"
2. Een pessimistische schatting: "Wat is het slechtste dat er kan gebeuren?"
Het algoritme kiest dan de indeling waarbij zelfs in het slechtste geval niemand er beter op wordt door te switchen. Dit zorgt voor stabiliteit, zelfs als onze data niet 100% perfect is.

3. De Resultaten: Wat levert het op?

De auteur heeft bewezen dat dit algoritme werkt, zolang je oude data maar "goed genoeg" gedekt is.

Bij de gedetailleerde data (Semi-bandit): Het algoritme is heel efficiënt. Het heeft maar een klein archief nodig om een bijna-perfect stabiel team te vinden. Het is alsof je met een paar goede foto's een heel landschap kunt reconstrueren.
Bij de vaagere data (Bandit): Dit is moeilijker. Je hebt een strengere eis aan je archief nodig (je moet veel meer variatie hebben gezien). Maar zelfs dan lukt het om een goed resultaat te vinden, zolang je maar genoeg data hebt.

4. De Praktijk: De Simulatie

De auteur heeft dit getest in een computer-simulatie.

Scenario A: Ze gebruikten een archief dat alle mogelijke teamgroottes bevatte. Resultaat: Het algoritme vond snel een perfecte indeling.
Scenario B: Ze gebruikten een archief dat alleen bepaalde teamgroottes bevatte (bijvoorbeeld alleen teams van 2 of 5, nooit 3 of 4). Resultaat: Het algoritme faalde. Het kon geen stabiele indeling vinden omdat het de "gaten" in de data niet kon opvullen.

Samenvatting in één zin

Dit paper leert computers hoe ze, zonder nieuwe experimenten te doen, op basis van oude, soms onvolledige data, de perfecte teams kunnen samenstellen waarbij niemand zin heeft om te wisselen, mits die oude data genoeg variatie bevat om elke mogelijke verandering te voorspellen.

De kernboodschap: Je kunt niet leren van het verleden als je verleden niet de toekomstige scenario's dekt. Maar als je dat wel doet, kun je met slimme wiskunde de perfecte groepen vormen zonder risico's te nemen.

1. Probleemdefinitie

Het paper adresseert het probleem van coalitieformatie in een omgeving met partiele informatie. Traditionele modellen voor coalitieformatie (zoals hedonische spellen) maken vaak twee aannames die in de praktijk niet altijd gelden:

Coalities zijn disjunct (een agent hoort bij slechts één groep).
De voorkeuren van de agenten zijn volledig bekend.

In dit paper wordt een nieuw model geïntroduceerd voor mogelijk overlappende coalities (POCF - Possibly Overlapping Coalition Formation) onder offline learning omstandigheden.

Context: Agenten kunnen deelnemen aan meerdere coalities tegelijkertijd (bijv. consultants die in verschillende domeinen werken).
Onzekerheid: De voorkeuren van de agenten zijn onbekend. Er is geen interactie met de omgeving om deze te leren (zoals in online learning), omdat dit te kostbaar of riskant kan zijn.
Data: In plaats daarvan is er een vaste, offline dataset beschikbaar met historische interacties en bijbehorende nutfeedbacks.
Doel: Het doel is om op basis van deze dataset de voorkeuren van de agenten te infereren en een verdeling (partition) te vinden die Nash-stabiel is. Een verdeling is Nash-stabiel als geen enkele agent haar nut kan verhogen door eenzijdig af te wijken (unilaterally deviating) naar een andere coalitie.

2. Methodologie

De auteurs presenteren een raamwerk voor offline learning dat werkt met twee verschillende niveaus van feedbackgranulariteit:

A. Feedback Modellen

Semi-bandit feedback: De dataset bevat agent-niveau feedback. Voor elke agent is bekend wat haar specifieke nut was bij interactie met elk ander lid van haar gekozen coalities.
Bandit feedback: De dataset bevat slechts coalitie-niveau feedback. Alleen het totale nut van een agent voor haar gekozen coalities is bekend; de individuele bijdragen van andere leden zijn niet waarneembaar.

B. Algoritmisch Raamwerk (Algorithm 1)

Het paper introduceert een algemene "Surrogate Minimization" aanpak:

Schatters: Er worden nutschatters ( $\hat{v}_i$ ) gebouwd op basis van de dataset.
Exploratiebonussen: Om onzekerheid te compenseren, worden exploratiebonussen ( $b^\delta_i$ ) toegevoegd. Dit creëert een "Upper Confidence Bound" (UCB) en "Lower Confidence Bound" (LCB) voor de geschatte nutwaarden.
Optimalisatie: Het algoritme zoekt een gezamenlijke strategie $\phi$ die de geschatte "dual gap" minimaliseert. De dual gap meet het verschil tussen het huidige nut en het beste mogelijke nut dat een agent kan bereiken door eenzijdig af te wijken. Een kleine dual gap impliceert Nash-stabiliteit.

C. Aannames over Dataset Dekking

Om te garanderen dat het leren van voorkeuren mogelijk is, worden specifieke aannames gedaan over hoe de dataset de mogelijke afwijkingen dekt:

Assumptie 1 (Coalitie Grootte Dekking - Semi-bandit): De dataset moet voldoende informatie bevatten over alle mogelijke grootte van coalities die kunnen ontstaan door eenzijdige afwijkingen van een Nash-stabiele strategie.
Assumptie 2 (Actie Dekking - Bandit): Omdat individuele nutten niet zichtbaar zijn, moet de dataset minstens even informatief zijn als een dataset die gegenereerd zou zijn door een strategie die bestaat uit een Nash-stabiele uitkomst plus een eenzijdige afwijking. Dit wordt gemodelleerd via de covariantiematrix van de dataset (ridge regression).

3. Belangrijkste Bijdragen

Nieuw Model: Een formalisatie van coalitieformatie met overlappende coalities en onbekende voorkeuren in een offline setting.
Noodzakelijke en Voldoende Voorwaarden:
- Voor semi-bandit feedback wordt bewezen dat Assumptie 1 zowel noodzakelijk als voldoende is voor efficiënt leren. Als de dataset niet alle mogelijke coalitiegroottes dekt, is het onmogelijk om een stabiele uitkomst te garanderen.
- Voor bandit feedback wordt aangetoond dat Assumptie 1 onvoldoende is. Een strengere voorwaarde (Assumptie 2) is vereist om nutten betrouwbaar te schatten via regressie.
Sample Complexity: De auteurs ontwikkelen algoritmen met lage sample complexiteit. De benodigde datasetgrootte ( $M$ $M$ ) om een $\epsilon$ $ϵ$ -benadering van Nash-stabiliteit te bereiken, hangt optimaal af van $\epsilon$ $ϵ$ (tot op logaritmische factoren).
- Voor semi-bandit: $M \propto \frac{1}{\epsilon^2}$ .
- Voor bandit: $M \propto \frac{1}{\epsilon^2}$ (met een hogere afhankelijkheid van het aantal agenten $n$ en coalities $k$ ).
Potentiaal Games: Het wordt bewezen dat symmetrische POCF-spellen potentiaal-spellen zijn, wat garandeert dat er altijd ten minste één puur Nash-stabiele strategie bestaat.

4. Resultaten

Theoretische Garanties:
- Onder semi-bandit feedback en Assumptie 1 convergeert het algoritme met hoge waarschijnlijkheid naar een $\epsilon$ -Nash-stabiele strategie.
- Onder bandit feedback en Assumptie 2 wordt een vergelijkbare convergentie bewezen, hoewel de sample complexiteit hoger is vanwege de beperktere informatie.
- Er wordt bewezen dat zonder deze dekkingaannames (Assumptie 1 of 2), geen enkel algoritme een goede benadering kan garanderen, ongeacht de datasetgrootte.
Experimentele Evaluatie:
- Uitgebreide experimenten op synthetische datasets bevestigen de theorie.
- Wanneer de dataset voldoet aan de dekkingaannames (bijv. via een uniform willekeurige verkenning), convergeert het algoritme snel naar een lage dual gap (dicht bij Nash-stabiliteit).
- Wanneer de dataset de aannames schendt (bijv. door bepaalde coalitiegroottes niet te dekken), faalt het algoritme om een stabiele uitkomst te vinden, wat de noodzaak van de aannames onderstreept.
- De schaling van de prestaties met betrekking tot het aantal agenten ( $n$ ), het aantal coalities ( $k$ ) en de datasetgrootte ( $M$ ) komt overeen met de theoretische voorspellingen ( $1/\sqrt{M}$ ).

5. Significantie

Dit paper is significant omdat het een brug slaat tussen coalitieformatie (game theory) en offline reinforcement learning.

Realisme: Het lost het probleem op van het leren van voorkeuren in realistische scenario's waar actieve experimentatie te duur of riskant is (bijv. consultancy-firmen, teamvorming in organisaties).
Overlappende Coalities: Het breidt de theorie uit van disjuncte naar overlappende coalities, wat veel algemener en realistischer is voor moderne samenwerking.
Data-efficiëntie: Het biedt theoretische garanties dat men met een relatief kleine dataset (afhankelijk van $\epsilon$ ) tot een stabiele oplossing kan komen, mits de data de juiste dekking heeft. Dit is cruciaal voor toepassingen waar data verzamelen beperkt is.
Feedback Granulariteit: Het onderscheid tussen semi-bandit en bandit feedback biedt inzicht in hoe de kwaliteit van historische data (gedetailleerd vs. samengevat) de haalbaarheid van het leren beïnvloedt.

Samenvattend biedt dit werk een robuust theoretisch en praktisch raamwerk voor het automatisch vormgeven van stabiele teams in complexe, onzekere omgevingen op basis van historische data.