P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 TheGeometryofEfficientFairDivision What is the best way to divide a “cake” and allocate the pieces among some finite collectionofplayers?Inthisbook,thecakeisameasurespace,andeachplayerusesa countablyadditive,non-atomicprobabilitymeasuretoevaluatethesizeofthepiecesof cake,withdifferentplayersgenerallyusingdifferentmeasures.Theauthorinvestigates efficiencyproperties(suchasParetomaximality:isthereanotherpartitionthatwould makeeveryoneatleastashappy,andwouldmakeatleastoneplayerhappier,thanthe presentpartition?)andfairnessproperties(suchasenvy-freeness:doallplayersthinkthat theirpieceisatleastaslargeaseveryotherplayer’spiece?).Hefocusesexclusivelyon abstractexistenceresultsratherthanalgorithms,andonthegeometricobjectsthatarise naturallyinthiscontext.Byexaminingtheshapeoftheseobjectsandtherelationship between them, he demonstrates results concerning the existence of efficient and fair partitions. Thisisaworkofmathematicsthatwillbeofinteresttobothmathematiciansand economists. juliusb.barbanelisProfessorofMathematicsatUnionCollege,wherehehasalso servedasDepartmentChair.Hehaspublishednumerousarticlesintheareasofboth LogicandSetTheory,andFairDivisioninleadingmathematicaljournals. i P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 ii P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 The Geometry of Efficient Fair Division JULIUS B. BARBANEL UnionCollege Withanintroductionby ALAN D. TAYLOR UnionCollege iii cambridge university press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge cb2 2ru, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521842488 © Julius B. Barbanel 2005 This book is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2005 isbn-13 978-0-511-10985-0 eBook (NetLibrary) isbn-10 0-511-10985-7 eBook (NetLibrary) isbn-13 978-0-521-84248-8 hardback isbn-10 0-521-84248-4 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this book, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 Dedicatedto mymother,EvelynBarbanel, mywife,NancyNiefield,and my(step)children,DanielSomerfieldandBethSomerfield and Inmemoryofmyfather,JosephBarbanel,whosememorycontinuestobea sourceofinspiration. Acknowledgments Special thanks go to my Union College colleagues Alan Taylor and William Zwicker.Muchofthematerialinthisbookwasdiscussedwiththembeforeit was written. Their comments and suggestions have played an important role. I also thank Alan Taylor for introducing me to the field of fair division and for writing the introduction to this book. I thank Steven Brams of New York Universityformanystimulatingconversationsaboutfairdivisionandseveral anonymousrefereesformanyhelpfulsuggestions. v P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 vi P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 Contents IntroductionbyAlanD.Taylor page1 1. NotationandPreliminaries 7 2. GeometricObject#1a:TheIndividualPiecesSet(IPS)for TwoPlayers 16 3. WhattheIPSTellsUsAboutFairnessandEfficiencyinthe Two-PlayerContext 25 3A. Fairness 25 3B. Efficiency 31 3C. FairnessandEfficiencyTogether:Part1a 37 3D. TheSituationWithoutAbsoluteContinuity 41 4. TheIndividualPiecesSet(IPS)andtheFullIndividual PiecesSet(FIPS)fortheGeneraln-PlayerContext 56 4A. GeometricObject#1b:TheIPSfornPlayers 56 4B. WhytheIPSDoesNotSuffice 67 4C. GeometricObject#1c:TheFIPS 70 4D. ATheoremonthePossibilitiesfortheFIPS 74 5. WhattheIPSandtheFIPSTellUsAboutFairnessand EfficiencyintheGeneraln-PlayerContext 82 5A. Fairness 82 5B. Efficiency 96 5C. FairnessandEfficiencyTogether:Part1b 107 5D. TheSituationWithoutAbsoluteContinuity 111 5E. ExamplesandOpenQuestions 134 6. CharacterizingParetoOptimality:Introductionand PreliminaryIdeas 151 7. CharacterizingParetoOptimalityI:TheIPSand OptimizationofConvexCombinationsofMeasures 160 vii P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 viii Contents 7A. Introduction:TheTwo-PlayerContext 160 7B. TheCharacterization 163 7C. TheSituationWithoutAbsoluteContinuity 168 8. CharacterizingParetoOptimalityII:PartitionRatios 190 8A. Introduction:TheTwo-PlayerContext 190 8B. TheCharacterization 192 8C. TheSituationWithoutAbsoluteContinuity 208 9. GeometricObject#2:TheRadon–NikodymSet(RNS) 220 9A. TheRNS 220 9B. TheSituationWithoutAbsoluteContinuity 230 10. CharacterizingParetoOptimalityIII:TheRNS,Weller’s Construction,andw-Association 236 10A. Introduction:TheTwo-PlayerContext 236 10B. TheCharacterization 240 10C. TheSituationWithoutAbsoluteContinuity 260 11. TheShapeoftheIPS 286 11A. TheTwo-PlayerContext 286 11B. TheCaseofThreeorMorePlayers 291 12. TheRelationshipBetweentheIPSandtheRNS 298 12A. Introduction 298 12B. RelatingtheIPSandtheRNSintheTwo-PlayerContext 301 12C. RelatingtheIPSandtheRNSintheGeneraln-Player Context 308 12D. TheSituationWithoutAbsoluteContinuity 336 12E. FairnessandEfficiencyTogether:Part2 341 13. OtherIssuesInvolvingWeller’sConstruction,Partition Ratios,andParetoOptimality 352 13A. TheRelationshipbetweenPartitionRatiosand w-Association 352 13B. TradesandEfficiency 358 13C. ClassifyingtheFailureofParetoOptimality 369 13D. Convexity 374 13E. TheSituationWithoutAbsoluteContinuity 376 14. StrongParetoOptimality 385 14A. Introduction 385 14B. TheCharacterization 386 14C. ExistenceQuestionsintheTwo-PlayerContext 394 14D. ExistenceQuestionsintheGeneraln-PlayerContext 400 14E. TheSituationWithoutAbsoluteContinuity 409 14F. FairnessandEfficiencyTogether:Part3 414 P1:JZP CB769/Barbanel-FM CB769/Barbanel-fm 0521842484 March19,2005 16:55 Contents ix 15. CharacterizingParetoOptimalityUsingHyperreal Numbers 416 15A. Introduction 416 15B. ATwo-PlayerExample 419 15C. Three-PlayerExamples 424 15D. TheCharacterization 435 16. GeometricObject#1d:TheMulticakeIndividualPieces Set(MIPS)SymmetryRestored 444 16A. TheMIPSforThreePlayers 444 16B. TheMIPSfortheGeneraln-PlayerContext 447 References 451 Index 453 SymbolandAbbreviationsIndex 462