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

De minimax-stelling
       
John von Neumann (1903-1957) wordt algemeen beschouwd als een van de grootste wiskundigen uit de moderne geschiedenis. Hij wordt beschouwd als de grondlegger van de speltheorie en publiceerde met Oskar Morgenstern het klassieke boek Theory of Games and Economic Behavior in 1944. 

 

Hij had het cruciale inzicht dat er in zero-sum spellen met gemengde strategieën toch altijd een (soort van) Nash-evenwicht te vinden is. Dat deed hij met onder andere zijn minimax-stelling.

Die zullen we in deze les bekijken.
       
Ik herhaal eerst nog even de al in een eerdere les genoemde minimax- en maximin- strategieën:

Noem x1, x2, ...xn de kansen op de strategieën 1 tm n voor S1
Noem y1, y2, ... ym de kansen op de strategieën 1 tm m voor S2
Noem u(x, y) de opbrengst voor S1 van strategie (x, y).
Dan geldt:

Strategie a is maximin-strategie voor S1 als:    miny(a, y) ³  miny(u(x, y))
Daar staat dat strategie a voor S1 de grootste winst van alle x-strategieën oplevert. Ofwel dat S1 de hoogste waarde uit de rij van de matrix kiest.
Je zou kunnen zeggen:  strategie a is  maxx(minyu(x , y))

Strategie b is minimax-strategie voor S2 als:    maxx(x, b) £  maxx(u(x, y))
Daar staat dat strategie b voor S2 het kleinste verlies van alle y-strategieën oplevert. Ofwel dat S2 de laagste waarde uit de kolom van de matrix kiest.
Je zou kunnen zeggen:  strategie b is  miny(maxxu(x , y))
       
We zagen in de vorige les al dat voor een Nash-evenwicht zal gelden:
       

u(a, b) = maxx(minyu(x, y)) = miny(maxxu(x, y))
       
Daar staat dat (a, b) een Nash-evenwicht is als  strategie a voor S1 een maximin-strategie is en tegelijkertijd voor S2 een minimax-strategie.

Zo, nou zijn we weer helemaal bijgepraat.

Over naar de minimax-stelling.
       
Minimax-stelling.

Eerst maar een voorbeeld.
Neem de volgende Spelmatrix A:

       
Stel verder dat S1 de kansvector X(0.2, 0.3, 0.5)  gebruikt en S2 de kansvector Y(0.1, 0.2, 0.7).
Dan is de verwachte winst voor speler S1 gelijk aan  X × (AY) = 1,68 (en voor S2 dus automatisch -1,68)

Speler S1 kan natuurlijk ook zó gaan redeneren:
       
-  Als speler S2 strategie y1 kiest dan is mijn winst  0,2 × 3 + 0,3 × 4 + 0,5 × 1 = 2,3
-  Als speler S2 strategie y2 kiest dan is mijn winst  0,2 × -1 + 0,3 × 0 + 0,5 × 3 = 1,3
-  Als speler S2 strategie y3 kiest dan is mijn winst  0,2 × 2 + 0,3 × 1 + 0,5 × 2 =1,7
Als S2 wat varieert dan weet ik nu wel zeker dat ik minstens 1,3 zal krijgen, want dat is als S2 100% strategie y2 speelt,  en als hij die mengt met andere strategieën wordt dat alleen maar beter voor mij.
       
Zoals je intussen weet was dit een  maximin-taktiek.
       
En omgekeerd kan speler S2 zó redeneren:
       
-  Als speler S1 strategie x1 kiest dan is mijn verlies  0,1 × 3 + 0,2 × -1 + 0,7 × 2 = 1,5
-  Als speler S1 strategie x2 kiest dan is mijn verlies  0,1 × 4 + 0,2 × 0 + 0,7 × 1 = 1,1
-  Als speler S1 strategie x3 kiest dan is mijn verlies  0,1 × 1 + 0,2 × 3 + 0,7 × 2 = 2,1
Als S1 wat varieert dan weet ik nu wel zeker dat ik hoogstens 2,1 zal verliezen, want dat is als S1 100% strategie x3 speelt,  en als hij die mengt met andere strategieën wordt dat alleen maar beter voor mij.
       
Zoals je intussen weet was dit een  minimax-taktiek

Maar als ik speler S1 was, dan zou ik wel even voor allerlei andere vectoren (x1, x2, x3) óók gaan berekenen wat de minimale winst zal zijn, niet alleen maar voor deze ene vector.

Nou, ik ben zo aardig geweest om voor S1 een Excel-bestand te maken met alle mogelijke variaties van x1, x2, en x3 met stapjes van 0,05 te bekijken.
Het resultaat daarvan staat in de figuur hieronder.
       

       
Bovenaan in het oranje staan de kansen x1
Links in het blauw staan de kansen x2
(de kans x3 is dan gelijk aan 1 - x1 - x2)
Op de kruising staat de verwachte minimale winst voor S1.

Je ziet dat de grootste gegarandeerde winst die S1 kan halen gelijk is aan  1,8.
Dat is hier zo bij de vectoren  X(0.10, 0.20, 0.70)  of  X(0.15, 0.20, 0.65)
Uiteraard zou je daartussen nog meer stapjes in de kansen kunnen nemen om dit nog verder te onderzoeken.
Dan vind je een grootste gegarandeerde winst voor S1 van 1,8333  (met x1 = x2 = 0,1667)

En je voelt het natuurlijk al wel aankomen..... ook S2 kan zo'n onderzoek verrichten om te kijken wanneer zijn maximale verlies zo klein mogelijk is.
Dat heb ik ook maar even voor hem gedaan, en dat leverde de volgende figuur:
       

       
Je ziet dat het kleinste maximale verlies dat S2 kan halen gelijk is aan  1,85.
Dat is hier zo bij de vector  Y(0.30, 0.15, 0.55)
Ook hier zouden we nog verder kunnen "inzoomen" door de kansen in kleinere stapjes te nemen.
Dan vind je een  kleinste maximaal verlies van 1,8333 (met y1 = 0,3333 en y2 = 0,1666)
       

Nou ja, Zeg!!!!
Dat is gelijk!!!!
Wat een toeval!
       
Of zou die matrix A net zo gekozen zijn dat dit zo uitkomt?
Nou ik kan je zeggen:  Dat is niet zo. Er komt ALTIJD voor beiden hetzelfde uit.
Als je het niet gelooft (dat deed ik eerst ook niet) probeer het dan maar uit met het Excel-bestand. Dat kun je hier vinden en daar kun je een willekeurige 3´3 matrix A invullen.

En dat is nou precies wat von Neumann met zijn minimax-stelling bewees:
       

In zero-sum spelen met gemengde strategieën waar spelers minimax-strategieën volgen,
is er  altijd een Nash-evenwicht.

       
Het geniale hiervan zit hem er niet zozeer in dat hij dit ontdekte.

We zagen zelf al dat dat met een beetje Excel wel te vinden is, alhoewel ik eerlijk moet zeggen dat het met meer dan 3 keuzes voor S1 of S2 wel veel werk wordt. Maar goed, een beetje computer kan dat wel.

Nee, het geniale zit hem erin dat von Neumann deze stelling bewees in het algemene geval!!!
OK; om dat bewijs te snappen hebben we denk ik een nieuwe les nodig....
       

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