[] Taartsnijden: niet alleen voor verjaarspartijtjes
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.
December 8th, 2006 at 13:53
Ja het was ook zo bruut geweest om het over ‘het delen van koetjes en kalfjes’ te hebben. Laten we het beschaafd houden en een cake gebruiken
Leuk verhaal Gijs! Heb speltheoretische perspectieven altijd interessant gevonden, helaas laat mijn wiskunde me vaak in de steek, Dit weerhoudt mij er niet van zoals gewoonlijk even kritisch naar dit verhaal te kijken.
De paragraaf na je opsomming gaat van onvolledige informatie uit, i.e. de deler weet niets over de preferenties van de kiezer. Nietwaar? Had hij dit wel dan had hij de cake op 5/8 kunnen opdelen, aangenomen dat de ander aarbei twee keer zo lekker vond. Dit zou dan ook tot hetzelfde resultaat leiden, maar nu in het voordeel van de deler en niet van de kiezer (eigenlijk is dit niet zeker want voor de kiezer is de keuze random tussen twee gelijken, dus wellicht zou de deler op 5/8 ‘min een beetje’ moeten gaan zitten). Dit leidt dus tot de simpele conclusie dat de keuze tussen ‘kiezen of delen’ afhangt van de kennis die jij hebt van de ander, en de kennis die de ander vermoedelijk heeft van jouw preferenties. Heb jij veel kennis van de ander, de ander vermoedelijk weinig van jou dan wil je zeker delen en vice versa. Het probleem ontstaat als deze kennis gelijk is: wie wordt dan de vraag gesteld om te kiezen of te delen? Het punt van ‘eerlijkheid’ ligt dan meer bij het feit wie de ander deze vraag gaat stellen. Bij gelijke preferenties (een cake met alleen chocolade willen we allebei zoveel mogelijk) maakt kiezen of delen theoretisch niet uit, in praktijk blijkt het delen van een cake in twee gelijken nog niet zo makkelijk en zou je dus altijd voor ‘kiezen’ moeten gaan
In speltheorie, zoals je waarschijnlijk beter weet dan ik, is er een spel dat heet ‘ultimatum game’. Dit zou kunnen zijn dat dezelfde cake wordt aangeboden aan Aagje en Bert. Nu moet Aagje een deel van de taart aan Bert geven (variërend van niets tot de hele taart). Op voorwaarde dat Bert dit voorstel accepteert mogen ze de taart houden. Weigert Bert dan krijgt geen van beide iets. Stel, Aagje geeft een stuk van 1/8 met aardbei af voor Bert. Bert heeft nu de keuze tussen dit stuk taart of helemaal niets. Het leuke is dat bij dergelijke ‘oneerlijke’ voorstellen, de utility-calculation niet slechts uit goederen bestaat maar ook uit het genot van straffen of een claim voor eerllijkheid. Zouden we alleen over utility praten met betrekking tot het stuk taart dan zou in dit geval het economische model niet kloppen. Hoe minder utility de taart oplevert, hoe groter de kans dat de utility door straffen zwaarder gaat wegen. Zit dit niet in het model dan accepteert Bert ieder stuk taart en dat is empirisch niet waar. Mijn alternatief zou zijn om te zeggen dat er variabelen ontbreken.
Dit spel pleit dus alleen maar voor de thesis van Brams, namelijk dat efficiency en envy-freeness alleen niet voldoende zijn. Zeker in het Irak-geval is dit nodig. Het houdt ook in dat er een onafhankelijke scheidsrechter met volledige kennis moet zijn die de verdeling maakt. Equitibility impliceert dus een onafhankelijke verdeler met volledige kennis van preferenties als ik het goed concludeer. Ik begin mij sterk te denken dat dit een impliciet politiek argument is tegen de rol van de VS in Irak. Heb je hem dat toevallig gevraagd?
December 13th, 2006 at 18:18
Hey Gijs, leuk stukje om te lezen. Doe je in je studie veel met speltheorie en sociale verdelingsvraagstukken?
Net als Jelmer dacht ik inderdaad ook dat in de paragraaf na de opsomming de aanname van onvolledige informatie ontbrak. Ik ben het weer niet met Jelmer eens dat je in de praktijk beter altijd voor kiezen kunt gaan. Het enige argument voor kiezen is dat de deler niet exact iets in tweeen weet te delen. Dat is welliswaar een terecht argument, maar je doet dan wel impliciet een paar aannames: dat het goed heterogeen is (dus niet verschillende delen heeft zoals de chocolade en arbeien cake), dat preferenties voor deze delen gelijk zijn of dat er geen informatie is over andermans voorkeuren. In de praktijk weet je vaak wel iets over je opponent of weet je opponent misschien wel iets over jou waardoor je maar beter kan delen ipv de verdeling af te wachten die je opponent maakt.
December 13th, 2006 at 22:24
Iljay….lees het hele stuk even dan zie je dat ik hetzelfde schrijf: alleen een chocolade cake en gelijke info over elkanders preferenties. Juist daarvoor schreef ik dat in veel gevallen delen beter kan zijn. Dat je het ‘weer niet met Jelmer eens bent’ klopt dus niet
December 13th, 2006 at 22:40
Ik zie nu dat Ilja en ik op een punt wel verschillen: als de ander meer kennis heeft dan jij over preferenties dan zegt Ilja dat je zelf moet delen…ik zei het tegenovergestelde (de ‘vice versa’ in mijn stuk). Op dit punt ga ik mee met Ilja en zijn we het dus helemaal eens. Afwachten wat de ander met meer kennis gaat doen lijkt me inderdaad niet beter dan zelf delen en er het best uithalen met de info die je hebt.
Gijs…het is tijd voor een nieuw vraagstuk!