Stel dat twee mensen een cake moeten delen. De aloude methode om dit te doen is om de één te laten snijden en de ander een van de verkregen stukken te laten kiezen. De persoon die snijdt, kan dan maar het beste de cake precies in twee gelijke helften snijden, om te voorkomen dat de kiezer er met het grootste stuk vandoor gaat.
In de Notices of the American Mathematical Society van december 2006 presenteren drie wiskundigen, Steven Brams, Michael Jones en Christian Klamler, een betere snijmethode. De klassieke methode is uitstekend als de cake er overal hetzelfde uitziet, maar in de praktijk bevat een taart vaak allerlei lekkers, zoals een roosje van marsepein en blaadjes van chocolade. Niet iedereen vindt alles even lekker: de een verkiest het roosje terwijl de ander aast op een chocolaatje. De methode van Brams, Jones en Klamler houdt hier rekening mee. Zij bedachten een methode om met één keer snijden twee stukken te krijgen zó, dat beide personen meestal meer dan 50% krijgen van wat ze willen.
Wie dolgraag de aardbei wil, krijgt misschien wat minder taart, maar wel met dat wat hem het lekkerst lijkt.
Een waarderingssysteem
Bij de ‘jij-snijdt-ik-kies-methode’ waarbij rekening wordt gehouden met verschillende soorten lekkers, draait het om de subjectieve waarde die de twee mensen geven aan een stuk cake.
Veronderstel dat Aafke en Bart een rechthoekige cake moeten verdelen die voor vijftig procent met vanilleglazuur is overdekt (de linkerkant van de cake) en voor vijftig procent met chocoladeglazuur (de rechterkant). Aafke vindt de helft met vanille twee keer zo lekker als de helft met chocolade. Het is Bart om het even of hij cake met vanille danwel chocolade krijgt.
Een cake die voor de helft met vanilleglazuur is overdekt en voor de helft met chocoladeglazuur.
Beschouw de cake, die ergens recht doormidden moet worden gesneden, als het interval [0, 1]; het deel [0, ½] bevat vanille, het deel (½, 1] chocolade. De cake moet op een zeker punt in het interval [0, 1] worden doorgesneden. Aafke vindt het vanilledeel twee keer zo lekker; haar ‘waardefunctie’ is daarom wA(x) = 4/3 voor x in het interval [0, ½] en wA(x) = 2/3 voor x in het interval (½, 1]. De waarde van de hele cake is dan precies 1, want (4/3) x (1/2) + (2/3) x (1/2) = 1. Voor Bart geldt de volgende waardefunctie: wB(x) = 1 voor alle x.
De grafieken van de waardefuncties van Aafke (rood) en Bart (blauw).
De persoon die snijdt, doet dat precies op de mediaan, dat wil zeggen het punt m waarvoor geldt dat de waarde die hij of zij aan de cake toekent links van m precies even groot is als de waarde rechts van m.
Aafke vindt de mediaan als volgt. De waarde links van m is (4/3)m, de waarde rechts is (4/3)(1/2 – m) + (2/3)(1/2). Beide delen moeten gelijk zijn aan 1/2, waaruit volgt dat m = 3/8. Het is aan Bart om te kiezen. Hij zal natuurlijk het rechter deel nemen, want de waarde die hij daaraan toekent is 5/8 en dat is meer dan 3/8, de waarde die hij aan het linker deel toekent.
Als Bart snijdt, geldt m = 1/2. Aafke kiest vervolgens het linker deel, want dat deel heeft voor haar de waarde 2/3.
Het linker interval geeft het snijpunt aan als Aafke snijdt, het rechter indien Bart snijdt.
De nieuwe snijmethode
Het nadeel van de zojuist beschreven methode, is dat de snijder meestal in het nadeel is. De snijder krijgt altijd een stuk met een waarde van 1/2, terwijl de kiezer meestal een stuk krijgt met een voor hem of haar grotere waarde. Alleen in het geval dat de waardefuncties van beide personen gelijk zijn, hebben beiden een stuk met waarde 1/2.
Brams, Jones, en Klamler beschrijven een nieuwe methode om de cake te snijden, die zij de ‘surplus-methode’ noemen. Op die manier kan de cake zodanig worden gesneden dat de waarde van Aafkes stuk gelijk is aan de waarde van Barts stuk. Hierbij is een derde persoon nodig, die het mes hanteert.
De methode werkt als volgt. Aafke en Bart vertellen hun waardefuncties aan de persoon die de cake gaat snijden. Deze snijder bepaalt voor beide functies het punt in het interval [0, 1] dat de mediaan is. De mediaan voor Aafke is 3/8, de mediaan voor Bart is 1/2, zoals hiervoor is uitgerekend.
Aafke krijgt in elk geval het deel [0, 3/8] en Bart het deel [1/2, 1]. De cake wordt gesneden op een punt s ergens tussen 3/8 en 1/2. Brams, Jones, en Klamler geven twee methoden om dit punt s te bepalen.
De cake moet ergens tussen 3/8 en 1/2 worden doorgesneden.
De eerste methode is om s zó te bepalen dat Aafke en Bart een stuk cake krijgen met voor elk gelijke waarde. Aafke krijgt, bovenop het deel [0, 3/8], het deel [3/8, s. Bart krijgt, bovenop het deel [1/2, 1], het deel [ s, 1/2].
Het te verdelen deel bestaat geheel uit vanille. Het deel dat Aafke aan haar nog te krijgen stuk toekent, heeft dus de waarde (4/3)( s – 3/8). Het deel van Bart heeft voor hem de waarde 1/2 – s. Stellen we deze twee uitdrukkingen aan elkaar gelijk, dan vinden we s = 3/7. Dat betekent dat de cake op 3/7 wordt doorgesneden. Aafke krijgt het linker deel en Bart het rechter deel. Beiden hebben een stuk cake dat zij waarderen met 4/7.
De tweede methode houdt rekening met de waarde die beide personen toekennen aan het nog te verdelen stuk. Aafke geeft dat stuk de waarde (4/3)(1/2 – 3/8) = 1/6, Bart geeft de waarde 1/2 – 3/8 = 1/8. Om s te bepalen, wordt de vergelijking (4/3)( s – 3/8) / (1/6) = (1/2 – s) / (1/8) opgelost. Dat geeft s = 7/16.
Bij deze laatste methode krijgt Aafke in totaal een stuk cake dat zij waardeert met 7/12 en Bart een stuk met een waarde van 9/16. Dat is een verschil van 1/48 in het voordeel van Aafke. Dit voordeel voor Aafke is een gevolg van het feit dat het nog te verdelen stuk door Aafke als waardevoller wordt getaxeerd dan door Bart.
Andere waardefuncties
In het voorbeeld dat we hier hebben besproken, hebben de waardefuncties een heel eenvoudige vorm: ze zijn constant op een interval. Ook andere waardefuncties zijn mogelijk, zolang de oppervlakte onder de grafiek van de waardefunctie (en boven de x-as) maar gelijk is aan 1. In de onderstaande figuur zie je nog enkele voorbeelden van waardefuncties. Om het punt s waar de cake moet worden doorgesneden te vinden, is integraalrekening nodig.
Nog drie waardefuncties. Rood: y = 4/3 – x2. Blauw: y = 3/2 – 2x voor 0 ≤ x ≤ 1/2, en y = 2x – 1/2 voor 1/2 < x ≤ 1. Groen: y = 2 – 4x voor 0 ≤ x ≤ 1/2, en y = 4x – 2 voor 1/2 < x ≤ 1. De oppervlakte onder de grafiek en boven de x-as, tussen de grenzen 0 en 1, is steeds gelijk aan 1.
De onderzoekers wijzen op nog een voordeel van de nieuwe procedure: er is niet mee te sjoemelen. Wie niet de ware waardefunctie opgeeft aan de snijder, eindigt met minder cake dan mogelijk is. Hiervan geven de wiskundigen een streng bewijs in hun artikel.
Toepassingen
Het onderzoek van Brams, Jones, en Klamler is leuk en aardig, maar zal er in de praktijk iemand zijn die deze theorie toepast? Bij het verdelen van een cake natuurlijk niet, maar de ‘surplus-methode’ kan wel degelijk gebruikt worden in andere contexten.
De wiskundigen geven als voorbeeld het eerlijk verdelen van een stuk land. Het land dat aan water grenst zou voor Aafke waardevoller kunnen zijn, terwijl het land dat aan bos grenst juist voor Bart aantrekkelijk is. Met de ‘surplus-methode’ kan het land zó worden verdeeld dat beide partijen een stuk land krijgen waarmee ze even gelukkig zijn.