Je leest:

Speltheorie onder de kerstboom

Speltheorie onder de kerstboom

Een analyse van ‘Secret Santa’

‘Secret Santa’ is een spel om de pakjes met Kerst te verdelen. Hoe moet je spelen om je winst te maximaliseren? Twee speltheoretici hebben het uitgezocht.

Speltheoretici Arpita Ghosh en Mohammad Mahdian van Yahoo Research in Santa Clara, Californië, hebben Secret Santa geanalyseerd, een spel om de pakjes met Kerst te verdelen. Bij Secret Santa koopt iedereen een cadeautje van vooraf afgesproken waarde, bijvoorbeeld tussen de 10 en 20 euro. Iedereen pakt het cadeautje in en alles gaat in een grote zak. Vervolgens komen alle deelnemers één voor één aan de beurt. Voor de eerste speler is het spel niet zo interessant. Die haalt een cadeautje uit de zak en pakt het uit. De tweede speler heeft nu een keuze. Die kan het eerste cadeautje stelen, of een nieuw cadeautje uit de zak halen en uitpakken. Als hij kiest voor de eerste optie, dan mag speler 1 weer een cadeautje uit de zak halen en uitpakken. Nu komt speler 3 aan de beurt. Hij mag of een al geopend cadeautje stelen, of een nieuw cadeautje uitpakken. Maar, eenmaal gestolen cadeautjes mogen niet nóg een keer gestolen worden.

Ghosh en Mahdian lieten hier een speltheoretische analyse op los om ieders winst te maximaliseren: hoe krijgt iedere speler het best mogelijke cadeautje te pakken. Ze begonnen hun analyse bij de laatste speler. Die heeft immers de makkelijkste keuze: of een geopend cadeautje stelen, of het laatste cadeautje in de zak openen. Aangezien de verwachte waarde van het ongeopende cadeautje 15 euro is, kan de laatste speler het beste een beschikbaar geopend cadeautje van meer dan 15 euro stelen. Als al deze cadeautjes al een keer gestolen zijn, dan opent hij het cadeautje uit de zak.

Vervolgens gebruikten Ghosh en Mahdian terugwaartse inductie. Ze gingen de spelers in omgekeerde volgorde één voor één af. Voor de voorlaatste speler zitten nog twee cadeautjes in de zak en deze moet rekening houden met het feit dat de laatste speler zijn cadeautje nog kan stelen. Hij moet zich daarom tevreden stellen met een lagere verwachte winst. Ghosh en Mahdian berekenden dat hij een cadeautje dat meer dan 13,75 euro waard is moet stelen, of anders een cadeautje uit de zak moet halen. Een dergelijke drempelwaardestrategie blijkt te werken voor alle spelers, alleen wordt de drempelwaarde steeds lager.

Bij acht spelers moet de tweede speler zich al tevreden stellen met een cadeautje dat meer dan 11,56 euro kost. Maar de eerste speler is natuurlijk de grootste pechvogel. Als hij als eerste een slecht cadeautje uitpakt, dan blijft hij daar het hele spel mee zitten. Om dit op te lossen is er een kleine variant bedacht. De eerste speler krijgt aan het einde van het spel nog de mogelijkheid om een cadeautje te stelen. Op die manier kunnen alle spelers verwachten naar huis te gaan met een cadeautje van 15 euro.

Dit artikel is een publicatie van Nieuw Archief voor Wiskunde (KWG).
© Nieuw Archief voor Wiskunde (KWG), alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 18 maart 2011

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.