Nulsomspel

Voor eindige nulsomspellen met twee spelers geven de verschillende speltheoretische oplossingsconcepten Nash-equilibrium, minimax en maximin alle dezelfde oplossing. Als de spelers een gemengde strategie mogen spelen, heeft het spel altijd een evenwicht.

VoorbeeldEdit

Een zero-somspel

Blauw Rood	A	B	C
1	-30 30	10 -10	-20 20
2	10 -10	-20 20	20 -20

De uitbetalingsmatrix van een spel is een handige voorstelling. Beschouw bijvoorbeeld het nulsomspel voor twee spelers dat rechts of hierboven is afgebeeld.

De volgorde van spelen verloopt als volgt: De eerste speler (rood) kiest in het geheim een van de twee acties 1 of 2; de tweede speler (blauw), niet op de hoogte van de keuze van de eerste speler, kiest in het geheim een van de drie acties A, B of C. Vervolgens worden de keuzes onthuld en het puntentotaal van elke speler wordt beïnvloed volgens de uitbetaling voor die keuzes.

Voorbeeld: Rood kiest actie 2 en Blauw kiest actie B. Wanneer de uitbetaling wordt toegewezen, krijgt Rood 20 punten en verliest Blauw 20 punten.

In dit voorbeeldspel kennen beide spelers de uitbetalingsmatrix en proberen ze het aantal van hun punten te maximaliseren. Rood zou als volgt kunnen redeneren: “Met actie 2 kan ik maximaal 20 punten verliezen en kan ik er maar 20 winnen, en met actie 1 kan ik er maar 10 verliezen maar kan ik er maximaal 30 winnen, dus actie 1 ziet er een stuk beter uit.” Met een soortgelijke redenering zou Blauw kiezen voor actie C. Als beide spelers deze acties uitvoeren, wint Rood 20 punten. Als Blauw anticipeert op de redenering van Rood en de keuze van actie 1, kan Blauw actie B kiezen, om zo 10 punten te winnen. Als Rood, op zijn beurt, op deze truc anticipeert en voor actie 2 kiest, wint Rood 20 punten.

Émile Borel en John von Neumann hadden het fundamentele inzicht dat waarschijnlijkheid een uitweg biedt uit dit raadsel. In plaats van te beslissen over een bepaalde te nemen actie, kennen de twee spelers waarschijnlijkheden toe aan hun respectieve acties, en gebruiken dan een willekeurig apparaat dat, volgens deze waarschijnlijkheden, een actie voor hen kiest. Elke speler berekent de waarschijnlijkheden zo dat het maximaal verwachte puntverlies, onafhankelijk van de strategie van de tegenstander, wordt geminimaliseerd. Dit leidt tot een lineair programmeringsprobleem met de optimale strategieën voor elke speler. Deze minimax methode kan waarschijnlijk optimale strategieën berekenen voor alle zero-sum games voor twee spelers.

Voor het bovenstaande voorbeeld blijkt dat Rood actie 1 moet kiezen met kans 4/7 en actie 2 met kans 3/7, en Blauw de kansen 0, 4/7, en 3/7 moet toekennen aan de drie acties A, B, en C. Rood wint dan gemiddeld 20/7 punten per spel.

OplossenEdit

Het Nash-evenwicht voor een zero-sum spel met twee spelers kan worden gevonden door een lineair programmeerprobleem op te lossen. Stel dat een zero-sum game een uitbetalingsmatrix M heeft waarin het element Mi,j de uitbetaling is die wordt verkregen wanneer de minimaliserende speler zuivere strategie i kiest en de maximaliserende speler zuivere strategie j kiest (d.w.z. de speler die de uitbetaling tracht te minimaliseren kiest de rij en de speler die de uitbetaling tracht te maximaliseren kiest de kolom). Veronderstel dat elk element van M positief is. Het spel zal minstens één Nash-evenwicht kennen. Het Nash-evenwicht kan worden gevonden (Raghavan 1994, p. 740) door het volgende lineaire programma op te lossen om een vector u te vinden:

Minimaliseer: ∑ i u i {\sum _{i}u_{i}} Onderworpen aan de beperkingen: u ≥ 0 M u ≥ 1.

De eerste beperking zegt dat elk element van de u-vector niet-negatief moet zijn, en de tweede beperking zegt dat elk element van de M u-vector ten minste 1 moet zijn. Voor de resulterende u-vector is het omgekeerde van de som van de elementen de waarde van het spel. Vermenigvuldiging van u met die waarde geeft een kansvector, die de kans geeft dat de maximaliserende speler elk van de mogelijke zuivere strategieën zal kiezen.

Als de spelmatrix niet alle positieve elementen heeft, voeg dan eenvoudig een constante toe aan elk element dat groot genoeg is om ze allemaal positief te maken. Dat verhoogt de waarde van het spel met die constante, en heeft geen effect op de gemengde strategieën voor het evenwicht.

De gemengde strategie voor het evenwicht van de minimaliserende speler kan worden gevonden door de duale van het gegeven lineaire programma op te lossen. Of het kan worden gevonden door met bovenstaande procedure een aangepaste uitbetalingsmatrix op te lossen die de transpositie en negatie van M is (met toevoeging van een constante zodat deze positief is), en vervolgens het resulterende spel op te lossen.

Als alle oplossingen van het lineaire programma worden gevonden, vormen zij alle Nash-evenwichten voor het spel. Omgekeerd kan elk lineair programma worden omgezet in een nul-somspel voor twee spelers door de variabelen te veranderen in de vorm van de bovenstaande vergelijkingen. Dergelijke spelen zijn dus equivalent aan lineaire programma’s, in het algemeen.

Universele oplossingEdit

Als het vermijden van een zero-sum game een actiekeuze is met enige waarschijnlijkheid voor de spelers, dan is vermijden altijd een evenwichtsstrategie voor tenminste één speler bij een zero-sum game. Voor elk nulsomspel met twee spelers waarbij een nul-nulstelling onmogelijk of niet geloofwaardig is nadat het spel is begonnen, zoals poker, is er geen andere Nash-evenwichtsstrategie dan het vermijden van het spel. Zelfs als er een geloofwaardige nul-nul gelijkspel is nadat een nulsomspel is begonnen, is dat niet beter dan de vermijdende strategie. In die zin is het interessant te vinden dat beloning-als-je-gaat in de optimale keuzeberekening voorrang heeft op alle zero-sum games van twee spelers met betrekking tot het al dan niet beginnen van het spel.

Het meest voorkomende of eenvoudige voorbeeld uit het deelgebied van de sociale psychologie is het concept van “sociale valstrikken”. In sommige gevallen kan het nastreven van individuele persoonlijke belangen het collectieve welzijn van de groep vergroten, maar in andere situaties resulteert het nastreven van persoonlijke belangen door alle partijen in wederzijds destructief gedrag.

ComplexityEdit

Het is getheoretiseerd door Robert Wright in zijn boek Nonzero: The Logic of Human Destiny, dat de samenleving in toenemende mate non-zero-sum wordt naarmate zij complexer, gespecialiseerder en onderling afhankelijker wordt.