Speltheorie

1. Wat is een spel?

In de speltheorie is een spel elke situatie met drie ingrediënten. Het woord is ruimer dan wat er in de kast ligt: ook twee buren die tegelijk een datum voor een feest prikken, spelen in deze zin een spel. Voor ons zijn het natuurlijk vooral kaart-, bord- en dobbelspellen.

• Spelers — wie neemt er beslissingen?
• Strategieën — welke keuzes heeft elke speler? Strikt genomen is een strategie een volledig plan: wat je doet in élke situatie die zich kan voordoen.
• Opbrengsten (in het Engels payoffs) — hoe waardeert elke speler elke mogelijke uitkomst? De getallen drukken een voorkeur uit: punten, een kans om te winnen of gewoon "hoe tevreden". Op deze site rekenen we steeds in punten of kansen.

Kiezen twee spelers tegelijk, dan zet je het spel overzichtelijk in een opbrengstmatrix. De rijen zijn de keuzes van speler A, de kolommen die van speler B. In elk vakje staat eerst de opbrengst van A en dan die van B. Een voorbeeld: twee spelers kiezen aan het begin van een kolonistenspel tegelijk een startgebied. Kiezen ze hetzelfde gebied, dan zitten ze elkaar in de weg.

Lees het zo: kiest A het noorden en B het zuiden, dan krijgt A 5 punten en B 4. Op dit spel komen we in paragraaf 3 terug. Twee verschillen zijn verder handig om te kennen. Bij een gelijktijdig spel weet je niet wat de ander kiest; bij een opeenvolgend spel zoals schaken zie je de vorige zet wel. En bij volledige informatie ligt alles open op tafel (schaken), terwijl je bij de meeste kaartspellen de handen van anderen niet kent.

2. Dominante strategieën

Een strategie is dominant als ze beter uitpakt dan elk alternatief, wat de tegenstander ook doet. Heb je zo'n strategie, dan hoef je niet te raden: je speelt haar gewoon. Een voorbeeld uit een eenvoudig bordspel over een veldslag. Speler A kiest tussen aanvallen en verdedigen; speler B kiest welke flank hij versterkt.

Kijk eerst naar A. Versterkt B links, dan levert aanvallen 3 op en verdedigen 1. Versterkt B rechts, dan is het 4 tegen 2. In beide gevallen is aanvallen beter: aanvallen is dominant.

B heeft geen dominante strategie: tegen een aanval is rechts beter (2 tegen 1), tegen verdediging juist links (3 tegen 0). Maar B kan redeneren: "A is verstandig, dus A valt aan." Dan blijft alleen de bovenste rij over, en daarin kiest B rechts. Deze werkwijze heet iteratieve eliminatie: je schrapt steeds strategieën die nooit de beste kunnen zijn, tot er weinig overblijft. Hier eindigt het spel op (aanvallen, rechterflank) met 4 punten voor A en 2 voor B.

Een verwant begrip is de zwak dominante strategie: nooit slechter en minstens één keer beter dan het alternatief. Ook die is een veilige keuze, al kan er dan meer dan één redelijke uitkomst zijn.

3. Het Nash-evenwicht

Lang niet elk spel heeft een dominante strategie. Daarom gebruikt de speltheorie een ruimer begrip: het Nash-evenwicht, genoemd naar de wiskundige John Nash, die in 1950 bewees dat elk eindig spel er minstens één heeft (eventueel met gemengde strategieën, zie paragraaf 4). Een Nash-evenwicht is een combinatie van keuzes waarbij geen enkele speler er beter van wordt als alleen hij van keuze verandert. Iedereen speelt dus een beste antwoord op wat de ander doet.

Een praktische controle: loop elk vakje af en vraag voor elke speler apart of overstappen loont. In het startgebiedspel uit paragraaf 1 is (Noord, Zuid) een evenwicht: A zou door over te stappen van 5 naar 1 punt zakken, en B van 4 naar 2. Om dezelfde reden is (Zuid, Noord) een evenwicht. In de vakjes (Noord, Noord) en (Zuid, Zuid) wil juist iedereen weg. Dat spel heeft dus twee evenwichten — en het spel zelf zegt niet welk van de twee het wordt.

Het gevangenendilemma

Het bekendste voorbeeld laat zien dat een evenwicht niet hetzelfde is als een goede uitkomst. Twee verdachten worden apart verhoord. Zwijgen ze allebei, dan krijgen ze elk één jaar. Bekent er één en zwijgt de ander, dan gaat de bekenner vrijuit en krijgt de zwijger drie jaar. Bekennen ze allebei, dan krijgen ze elk twee jaar. We schrijven jaren als negatieve opbrengst.

Voor A geldt: zwijgt B, dan is bekennen beter (0 tegen −1); bekent B, dan is bekennen ook beter (−2 tegen −3). Bekennen is dus dominant, en voor B precies zo. Het enige Nash-evenwicht is (bekennen, bekennen) met twee jaar elk — terwijl samen zwijgen voor allebei beter was geweest. De les: wat voor ieder afzonderlijk verstandig is, kan voor de groep slecht uitpakken.

Wordt hetzelfde spel vaak herhaald, dan verandert het beeld. Samenwerking kan dan blijven bestaan omdat verraad in een volgende ronde wordt afgestraft. In bekende computertoernooien van de politicoloog Robert Axelrod rond 1980 deed de eenvoudige strategie "begin vriendelijk en doe daarna na wat de ander de vorige keer deed" (tit for tat) het opvallend goed. Aan de speltafel herken je hetzelfde patroon: spelers die samen de koploper zouden moeten afremmen, hopen allebei dat de ánder die moeite neemt.

Een coördinatiespel: Klaverjassen of Catan?

Twee vrienden spreken een spelavond af, maar vergeten te zeggen welke doos ze meenemen. A speelt het liefst Klaverjassen, B liever Catan, maar beiden willen vooral hetzelfde spel spelen.

Er zijn twee evenwichten met zuivere strategieën: allebei Klaverjassen en allebei Catan. Niemand wil daar in zijn eentje van afwijken, want dan valt de avond in het water. Er is ook een derde, gemengd evenwicht. Stel dat A met kans p Klaverjassen meeneemt. B is pas onverschillig als beide keuzes hem evenveel opleveren: 1 · p = 2 · (1 − p), dus p = 2/3. Neemt B met kans q Klaverjassen mee, dan is A onverschillig als 2 · q = 1 · (1 − q), dus q = 1/3.

In dat gemengde evenwicht verwacht elke speler 2/3 punt — minder dan in elk van de twee zuivere evenwichten. De kans dat ze met verschillende dozen voor de deur staan is 2/3 · 2/3 + 1/3 · 1/3 = 5/9, ruim 55%. Coördinatiespellen worden daarom in de praktijk opgelost met afspraken en gewoonten: "op dinsdag kaarten we". Dat idee komt terug bij signalen in slagenspellen.

4. Gemengde strategieën

Een gemengde strategie is een keuze volgens vaste kansen, bijvoorbeeld "in 40% van de gevallen links". Dat klinkt vreemd — waarom zou je bewust het toeval laten kiezen? — maar in spellen zonder evenwicht in zuivere strategieën is het de enige manier om niet uitgebuit te worden.

Steen-papier-schaar

Winst telt als +1, verlies als −1, gelijkspel als 0. Omdat de winst van de één het verlies van de ander is, volstaat de opbrengst van de rijspeler.

Stel dat je tegenstander een lichte voorkeur heeft: 40% steen, 30% papier en 30% schaar. Dan levert elke zet van jou gemiddeld op:

steen: 0 · 0,4 − 1 · 0,3 + 1 · 0,3 = 0
papier: 1 · 0,4 + 0 · 0,3 − 1 · 0,3 = +0,1
schaar: −1 · 0,4 + 1 · 0,3 + 0 · 0,3 = −0,1

Wie altijd papier speelt, wint zo gemiddeld 0,1 punt per ronde: tien punten per honderd rondes. Elke afwijking van gelijke kansen is op deze manier uit te buiten. Alleen bij één derde voor elke zet leveren al jouw antwoorden precies 0 op, en heeft de ander niets om op in te spelen. Dat is het enige Nash-evenwicht van dit spel.

Het onverschilligheidsprincipe: de strafschop

Bij grotere spellen werkt dezelfde redenering: in een gemengd evenwicht kiest elke speler zijn kansen zo dat de tegenstander onverschillig wordt tussen zijn opties. Een mooi voorbeeld zonder misleiding of verborgen kaarten is de strafschop. De nemer kiest links of rechts (vanuit zijn gezichtspunt), de keeper duikt tegelijk links of rechts. In de matrix staat de kans dat de bal erin gaat; de keeper wil die kans juist zo klein mogelijk maken. De getallen zijn bedacht ter illustratie: rechts is de sterke kant van deze nemer.

Er is geen vakje waar beiden tevreden blijven: schiet de nemer altijd rechts, dan duikt de keeper altijd rechts, waarna links weer aantrekkelijk wordt, enzovoort. We zoeken dus een gemengd evenwicht.

De keeper duikt met kans q naar links. Dan scoort de nemer met links gemiddeld 0,60q + 0,95(1 − q) = 0,95 − 0,35q, en met rechts 0,90q + 0,70(1 − q) = 0,70 + 0,20q. De nemer is onverschillig als die twee gelijk zijn: 0,25 = 0,55q, dus q = 5/11 ≈ 45,5%.

De nemer schiet met kans p naar links. Duikt de keeper links, dan gaat de bal erin met kans 0,60p + 0,90(1 − p) = 0,90 − 0,30p; duikt hij rechts, dan met 0,95p + 0,70(1 − p) = 0,70 + 0,25p. Gelijkstellen geeft 0,20 = 0,55p, dus p = 4/11 ≈ 36,4%.

kans op een doelpunt in het evenwicht = 0,90 − 0,30 · 4/11 = 8,7/11 ≈ 79,1%

Vergelijk dat met de zuivere keuzes. Schiet de nemer altijd naar zijn sterke kant, dan duikt de keeper daar ook en scoort hij in 70% van de gevallen; altijd links levert zelfs maar 60% op. Door te mengen — ongeveer 64% rechts en 36% links — haalt de nemer 79,1%, wat de keeper ook doet. Onderzoek naar strafschoppen in het profvoetbal, onder meer door de econoom Ignacio Palacios-Huerta, liet zien dat nemers en keepers hun keuzes opvallend dicht bij zo'n evenwichtsverhouding verdelen.

In de gids Gemengde strategieën in de praktijk lees je hoe je dit toepast in spellen als Stratego en hoe je aan tafel werkelijk willekeurig kiest.

5. Nulsom of niet?

In een nulsomspel is de winst van de één precies het verlies van de ander; in elk vakje tellen de opbrengsten op tot nul (of tot een vast getal, wat strategisch op hetzelfde neerkomt). Steen-papier-schaar en de strafschop zijn nulsomspellen, en schaken ook: een partij levert samen altijd één punt op (1–0, ½–½ of 0–1). Voor zulke tweepersoonsspellen bewees John von Neumann in 1928 de minimaxstelling: er bestaat een vaste waarde die elke speler met een (eventueel gemengde) strategie kan garanderen. Overleg heeft geen zin; wat de één wint, verliest de ander.

In een niet-nulsomspel kunnen beide spelers er tegelijk op vooruit- of achteruitgaan. Het gevangenendilemma en het coördinatiespel zijn voorbeelden. Daar worden afspraken, signalen, reputatie en vertrouwen belangrijk.

Een spel met meer dan twee spelers kan als geheel nulsom zijn (één winnaar), terwijl een deel van de zetten dat niet is. Een ruil in Catan die twee spelers allebei verder helpt, gaat ten koste van de overige spelers — daarom is de vraag "met wíé ruil ik?" vaak belangrijker dan "wat ruil ik?".

6. Aan de speltafel

Signalen bij slagenspellen

Bij Klaverjassen, bridge en andere slagenspellen met vaste partners mag je niet zeggen wat je in je hand hebt. Het enige kanaal is de kaart die je speelt. Partners maken daarom afspraken, bijvoorbeeld: "speel ik in een kleur die ik toch niet kan winnen een hoge kaart bij, dan wil ik dat je die kleur later naspeelt; een lage kaart betekent het omgekeerde."

Speltheoretisch is dat een coördinatiespel, net als de spelavond van paragraaf 3. De omgekeerde afspraak ("laag betekent: naspelen") werkt precies even goed, zolang beide partners dezelfde gebruiken. Elke consequente afspraak is een evenwicht: wie er in zijn eentje van afwijkt, schaadt vooral het eigen team. Bij bridge moeten zulke afspraken bovendien voor de tegenstanders inzichtelijk zijn — en daar zit de keerzijde: een signaal informeert niet alleen je partner, maar ook de spelers die tegen je zijn. Soms is het slimmer níét te seinen, omdat de tegenstander meer aan de informatie heeft dan je partner.

Openingen bij schaken als speelgoedmodel

Schaken heeft volledige informatie en geen toeval, maar de voorbereiding vóór de partij kan een raadspel zijn. Neem een sterk vereenvoudigd model: wit kiest tussen 1.e4 en 1.d4, zwart bereidt zich vooral op één van beide voor. In de matrix staat de verwachte score van wit (1 = winst, ½ = remise, 0 = verlies). De getallen zijn verzonnen om het principe te tonen.

Wit speelt 1.e4 met kans p. Zwart is onverschillig als 0,50p + 0,62(1 − p) = 0,60p + 0,52(1 − p), dus 0,10 = 0,20p en p = 0,5. Zwart bereidt 1.e4 voor met kans q; wit is onverschillig als 0,60 − 0,10q = 0,52 + 0,10q, dus q = 0,4. De waarde van het spel is 0,56 voor wit.

Opvallend: het hoogste getal in de matrix (0,62) staat bij 1.d4, maar wie altijd 1.d4 speelt, wordt erop voorbereid en haalt 0,52. Afwisselen levert 0,56 op. Dat is in een notendop waarom sterke spelers hun openingsrepertoire variëren. Echte openingen zijn uiteraard veel rijker dan één matrix van twee bij twee.

Vooruitdenken in spellen met volledige informatie

In opeenvolgende spellen zonder toeval en zonder verborgen informatie kun je in principe terugredeneren: begin bij de eindstanden en bepaal steeds de beste zet een stap eerder. Al in 1913 liet Ernst Zermelo zien dat in een eindig spel als schaken daarom één van drie dingen vastligt: wit kan winst afdwingen, zwart kan winst afdwingen, of beide kunnen minstens remise afdwingen. Welke van de drie het voor schaken is, weet niemand — de boom van mogelijke partijen is daarvoor veel te groot. Voor kleinere spellen, zoals boter-kaas-en-eieren (altijd remise bij goed spel), is het antwoord wel bekend.