© h.hofstede (h.hofstede@hogeland.nl)

De Kern van een spel.
       
Door op verschillende manieren samen te werken kun je bereiken dat er meer of minder winst gemaakt wordt.
De grote vraag van deze les is:
       

Hoe moet de winst onder de deelnemers verdeeld worden?
       
Ofwel, wat wiskundiger geformuleerd:  Hoe moet  W(C) onder alle N spelers verdeeld worden?
Zo'n verdeling van de winst noemen we een verdelingsvector W(w1, w2, ..., wn) waarbij elke wi  aangeeft wat speler i van de winst krijgt. Al die wi's samen opgeteld zijn dus precies W.
 
Natuurlijk moet je eerst afspreken wat nou precies de winst is. Bij beide postzegelverkopers uit voorbeeld 1 van de vorige les is dat wel duidelijk:  Als ze samenwerken krijgen ze 475 en als ze apart hun zegels verkopen slechts 410. De coalitie geeft dus een winst van 65 euro.
De postzegelverkopers hebben dus te maken met twee getallen w1 en w2 die samen gelijk zijn aan 65.
Grafisch zou dat er zó uitzien:

       
Merk op dat ook  (-10, 75) mogelijk is. In dat geval krijgt speler 2 de hele winst plus nog 10 euro van speler 1. Dat is natuurlijk niet eerlijk, maar wel mógelijk.

Eerste logische opmerking over wat eerlijk is:
       
elke speler moet minstens evenveel krijgen als hij zou krijgen wanneer hij NIET zou samenwerken.
       
Lijkt me logisch toch?  Door samen te werken zal niemand erop achteruit willen gaan.
De verzameling van alle verdelingen waarbij dat zo is (dus waarbij niemand minder krijgt dan wanneer hij alleen werkt) heet de imputatieverzameling.
       
De imputatieverzameling van een coöperatief spel bestaat uit alle verdelingen (w1, w2, ..., wn)
die aan de volgende twee voorwaarden voldoen:
1.      w1 + w2 + ... + wn = W(C)     (alle winst wordt precies verdeeld)
2.      wi ³ W({i})  voor elke i uit C   (niemand krijgt minder dan wanneer hij alleen zou werken)
       
In ons postzegelvoorbeeld zou de imputatieverzameling dus bestaan uit het deel van de blauwe lijn hierboven waarvoor w1 ³ 0 en w2 ³ 0
Je kunt ook ervoor kiezen om de winst (waarde van de coalitie) alles wat ze in totaal binnenkrijgen te noemen (in plaats van alleen alles boven de 410 euro). Dat zou deze figuur geven:
       

       
De imputatieverzameling is het deel van de lijn waarvoor geldt dat w1 ³ 350 en tegelijkertijd  w2 ³ 60

Tijd voor een stelling.....

Meteen maar met de deur in huis vallen:
Stel dat
    C = coalitie
    I = imputatieverzameling van die coalitie,
    i = nummer van de speler
   W = waarde van een coalitie

Dan geldt de volgende stelling:
       

       
In normaal Nederlands (zucht... waarom moeten die wiskundigen alles altijd zo moeilijk maken?)
       
"De imputatieverzameling van een coalitie is niet leeg als de waarde van die coalitie minstens even groot is als de afzonderlijke waardes van alle spelers apart opgeteld".

en de stelling geldt ook andersom:

"Als de waarde van een coalitie minstens even groot is als de afzonderlijke waardes van alle spelers apart opgeteld, dan is de imputatieverzameling van die coalitie niet leeg".
       
Nog simpeler dan maar?
       
"Als de totale waarde van een samenwerkende groep groter of gelijk is dan alle afzonderlijke waarden opgeteld, dan is er een verdeling te maken waarbij niemand erop achteruit zal gaan".
       
Bewijs:
Þ Stel dat I(C) niet leeg is....
dan is er dus een verdeling (w1, w2, ...wn)  waarvoor geldt w1 + w2 + ... + wn = W(C)
en bovendien moet voor elke afzonderlijke wi gelden dat  wi  ³ W({i))

combineren we deze twee dan krijg je:
W(C) = w1 + w2 + ... + wn
³   W({1}) + W({2}) + ... + W({n})
 
  q.e.d.
       
Ü Dat is erg makkelijk;
Als het totaal groter is dan de afzonderlijke wi dan kun je iedereen gewoon minstens zijn eigen wi geven, en dan blijft er nog wat over. Dan is er dus in ieder geval een vector  W(w1, w2, ..., wn)  te vinden.
(Geef bijvoorbeeld iedereen zijn eigen wi   (dus  wi = W({i}))  en geef speler 1 wat er extra is.
q.e.d.
       
Stabiele verdeling.

We noemen een verdeling stabiel als geen enkele speler meer kan verdienen door niet samen te werken in de coalitie. Als er maar twee spelers zijn dan is een verdeling uit de imputatieverzameling altijd stabiel.
Maar bij meer spelers hoeft dat niet zo te zijn.
Neem het volgende spel met maximaal 2 spelers:
       
Coalitie geen {1} {2} {3} {12} {13} {23} {123}
Waarde 0 0 0 0 5 4 6 10
       
Als alle drie de spelers samenwerken dan is de totale winst 10
Die kan in de imputatieverzameling op allerlei manieren verdeeld zijn.
Een mogelijkheid zou zijn  {6, 2, 2} en elke speler krijgt dan in iedere geval meer dan hij alleen zou krijgen.

Maar toch zijn spelers 2 en 3 nu niet tevreden.
Zij krijgen immers elk 2, dus samen 2 + 2 = 4
Maar als ze zonder speler 1 een coalitie zouden maken (dus  {23}) dan zou hun gezamenlijke winst gelijk zijn aan 6. En die kunnen ze dan bijvoorbeeld verdelen met beiden 3, zodat ze elk meer krijgen dan bij de verdeling {6, 2, 2}

Deze verdeling is dus niet stabiel:  spelers 2 en 3 kunnen elk meer verdienen door eruit te stappen en samen te gaan werken.

om bij meer spelers stabiele verdelingen te krijgen moet je niet alleen naar de afzonderlijke spelers kijken maar ook naar alle mogelijke andere coalities. Als spelers zich kunnen afsplitsen om in een andere coalitie meer te verdienen dan zullen ze dat zeker doen.

De verzameling van alle stabiele verdelingen (dus waarbij geen enkele speler of groepjes spelers reden heeft zich af te splitsen) heet de kern van het spel.
       
De kern van een coöperatief spel is  de volgende verzameling:

Alle verdelingen (w1, w2, ..., wn) die aan de volgende twee voorwaarden voldoen:
1.
2.
       
Voorwaarde 1 zegt natuurlijk dat de totale winst onder alle deelnemers verdeeld moet worden.
Voorwaarde 2 zegt elke andere deelcoalitie (S) samen minder verdient dan de som van hun verdiensten in coalitie C.

Zo'n vector (w1, w2, ..., wn) die in de kern ligt noemen we ook wel een kern-element.
       
Voorbeeld.

Laten we deze afspraak meteen maar testen op de verdeling hierboven.
Die zag er zó uit:
       
Coalitie geen {1} {2} {3} {12} {13} {23} {123}
Waarde 0 0 0 0 5 4 6 10
       
Welke verdelingen van de winst 10  van de coalitie {123} zijn stabiel (dus zijn kern-elementen)?
Als je de winst verdeelt als  {a, b, c}  dan moet gelden:
(1)   a + b + c = 10
(2)   a + b  ³ 5
(3)   b + c  ³ 6
(4)   a + c  ³ 4

De eerste voorwaarde geeft  c = 10 - a - b
De derde geeft dan   a £ 4
De vierde geeft dan  b  £ 6
Verder moeten alle a, b en c positief zijn, want anders kunnen de spelers in hun eentje meer winst halen.
c ³ 0  geeft  a + b £ 10

Tekenen we de zes voorwaarden   (a + b  ³ 5) en   (a £ 4)  en  (b  £ 6)  en  (a ³ 0)  en  (b ³ 0)  en  (a + b £ 10)  in een assenstelsel met a en b op de assen  dan geeft dat het volgende gebied voor de kern:
       

       
Alle (a, b) punten uit het gele gebied vormen de kern van het spel (en dan is de bijbehorende c = 10 - a - b)
De hoekpunten van de kern noemen we pook wel de extreme punten.
Zo'n hoekpunt ligt altijd op minstens 2 grenslijnen en de voorwaarden die bij die grenslijnen horen noemen we de bindende voorwaarden voor het extreme punt.
Met meer dan drie spelers lukt het niet om de kern op zo'n mooie grafische manier weer te geven.
       
       
OPGAVEN
       
1. Teken de kern van de volgende spellen:
       
  a.
Coalitie geen {1} {2} {3} {12} {13} {23} {123}
Waarde 0 0 0 0 4 1 2 4
       
  b.
Coalitie geen {1} {2} {3} {12} {13} {23} {123}
Waarde 0 0 0 1 2 5 4 7
       
       

© h.hofstede (h.hofstede@hogeland.nl)