Ik was net bij een voordracht van Steven Brams. De beste man hield een voordracht over het verdelen van cake (niet taart, want dat is nog ingewikkelder). Dhr. Brams was hier voor COMSOC-2006 – een kleine conferentie aan de UvA over ‘computationele sociale keuzes’. Het gaat hier dus om het verdelen van goederen (al dan niet ‘deelbaar’ (1 euro kun je delen, 1 auto niet, in die zin van het woord)) tussen verschillende agents die ieder weer hun eigen voorkeuren hebben.
Een paar termen om het straks volgende voorbeeld duidelijk te maken:
- envy-freeness (‘vrij van jaloezie’) wil zoveel zeggen als: er is geen enkele agent die liever de set goederen van een andere agent wil hebben dan de set goederen die hij/zij/het nu heeft.
- efficiency of, moeilijker gezegd, Pareto-optimality, wil zeggen dat er geen mogelijkheid is om iemand meer te geven dan hij/zij/het nu heeft, zonder dat (sommige) anderen daarop achteruit gaan.
- equitability wil zeggen dat alle agents even gelukkig zijn met wat ze krijgen. Dit betekent niet per sé dat ze allemaal hetzelfde krijgen. Om een voorbeeld te noemen, stel ik mag land verdelen tussen mijn twee zoons (erfenis of zo), en het land grenst aan de ene kant aan een prachtig meer, en aan de andere kant aan een vuilnisbelt. Aangenomen dat de zoons inderdaad beiden het stuk land bij het meer leuker vinden dan dat naast de vuilnisbelt, zou het duidelijk niet ‘equitable’ zijn als ik mijn stuk land geometrisch middendoor deelde en de helft naast de vuilnisbelt aan mijn ene zoon geven, en de andere helft aan mijn andere – immers, hoewel ze fysiek evenveel gekregen hebben, is de één er gelukkiger mee dan de ander.
Dan ga ik nu een kleine aanslag plegen op het oer-Nederlandse “kiezen of delen”. Zoals we allemaal weten, is dit de eerlijkste manier om een cake te verdelen. Niet dus, zo zegt Brams. Stel je verdeelt een cake op die manier. De cake is voor de helft met chocola gevuld, en voor de helft met aardbeien. Stel, de ‘deler’ vindt de chocola twee keer zo lekker als de aarbeien. De ‘deler’ zal dan op zijn best de ‘helft’ van de waarde van de cake kunnen krijgen, door hem op 3/8 door te snijden. De ander mag dan kiezen tussen 3/4 van het chocolade deel, of het hele aardbeien deel en 1/4 van het chocolade deel. Hoe dan ook, de ‘deler’ zal nooit meer dan 50% van de waarde die hij aan de cake hecht krijgen, terwijl de ‘kiezer’ wellicht meer krijgt (bijvoorbeeld als die persoon aardbeien veel lekkerder vond). Met andere woorden, hier is weliswaar sprake van envy-freeness (want niemand zal het deel van de ander willen), en van efficiency, maar niet altijd van equitability. Brams voert een mogelijkheid aan om beiden te garanderen bij het verdelen van de cake.
Stel, we verdelen dezelfde cake tussen Aagje en Bert. Aagje vindt chocola twee keer zo lekker als aardbeien, en Bert maakt het allemaal niets uit, die wil gewoon zo veel mogelijk cake. Aagje en Bert vertellen dit allebei aan een onafhankelijke partij. Deze scheidsrechter kan dan onafhankelijk bepalen waar het fifty/fifty ‘punt’ op de cake ligt voor beide partijen. Voor Bert is dat dus middenop de cake, maar voor Aagje op 3/8 (3/4 van het chocolade deel). Vervolgens deelt de scheidsrechter het resterende deel op tussen beide partijen, in ons geval op 7/16 (midden tussen 3/8 en 1/2). Nu heeft Aagje dus 7/12 van de waarde die zijn aan de hele cake hechtte, en Bert heeft 9/16 gekregen. Dat is nog steeds niet helemaal eerlijk (equitable), maar wel eerlijker dan kiezen of delen (waar het verschil 6/12 tegen 10/16 was). Je kunt er ook voor kiezen om het resterende deel proportioneel te verdelen, maar dan kan het weer voordelig worden voor mensen om tegen de scheidsrechter te liegen over wat voor waarde ze aan welk deel hechten. Dit is allemaal wiskundig bewezen in het paper van Brams, maar voert wat mij betreft wat ver voor een blogpost.
Uiteraard wil ik niet suggereren dat je deze methode daadwerkelijk op verjaarspartijtjes gebruikt, echt praktisch is het daar niet. Maar het is een leuke metafoor voor serieuze dingen, zoals bijvoorbeeld vandaag aangehaald werd, het opdelen van Irak tussen Shiieten, Soennieten en Koerden, waarbij bepaalde partijen bepaalde heilige plaatsen belangrijk vinden, iedereen natuurlijk Bagdad wil hebben, etc.
Jelmer, weliswaar geen Koetjes en Kalfjes, maar toch wat AI. Om het even op mijn studie te betrekken, ik houd me dus, samen met twee medestudenten en de mede-organisator van deze conferentie, bezig met het schrijven van een computersimulator voor het verdelen van en onderhandelen over goederen (helaas geen cake) door verschillende agenten met verschillende behoeftes etc. Dit doe ik om uiteindelijk mijn BSc met ‘honours’ te behalen. Daarvoor volg ik ook wat interdisciplinaire extra vakken, etc. Het AI gedeelte is best interessant, maar moeilijk om zo een-twee-drie een blogpostje over te schrijven.