Report

CUTTING A BIRTHDAY CAKE Yonatan Aumann, Bar Ilan University How should the cake be divided? “I want lots of flowers” “I love white decorations” “No writing on my piece at all!” Model The cake: 1-dimentional the interval [0,1] Valuations: Non atomic measures on [0,1] Normalized: the entire cake is worth 1 Division: Single piece to each player, or Any number of pieces How should the cake be divided? “I want lots of flowers” “I love white decorations” “No writing on my piece at all!” Fair Division Proportional: Each player gets a piece worth to her at least 1/n Envy Free: No player prefers a piece allotted to someone else Equitable: All players assign the same value to their allotted pieces Cut and Choose Alice Alice likes the candies Bob likes the base Bob Proportional Envy free Alice cuts in the middle Bob chooses Equitable Previous Work Problem first presented by H. Steinhaus (1940) Existence theorems (e.g. [DS61,Str80]) Algorithms for different variants of the problem: Finite Algorithms (e.g. [Str49,EP84]) “Moving knife” algorithms (e.g. [Str80]) Lower bounds on the number of steps required for divisions (e.g. [SW03,EP06,Pro09]) Books: [BT96,RW98,Mou04] Example Player 1 Player 2 Players 3,4 PlayerPlayer 1 Player 1 3 Player Player 2 Player 2 4 Total: 1.5 Total: 2 Fairness Maximum Utility Social Welfare Utilitarian: Sum of players’ utilities Egalitarian: Minimum of players’ utilities Fairness vs. Welfare with Y. Dombb The Price of Fairness Given an instance: PoF = utilitarian egalitarian max welfare using any division max welfare using fair division Price of envyfreeness Price of equitability Price of proportionality Example Player 1 Player 2 Players 3,4 Envy-free Total: 1.5 Utilitarian optimum Total: 2 Utilitarian Price of Envy-Freeness: 4/3 The Price of Fairness Given an instance: PoF = max welfare using any division max welfare using fair division Seek bounds on the Price of Fairness First defined in [CKKK09] for non-connected divisions Results Price of Proportionality Utilitarian Envy freeness n Equitability n O (1) O (1) 2 n Egalitarian 1 2 1 Utilitarian Price of Envy Freeness Lower Bound Player 1 Player 2 Player 3 n Player 3n n players Best possible utilitarian: Best proportional/envy-free utilitarian: n 1 n n Utilitarian Price of envy-freeness: n /2 n 1 2 Utilitarian Price of Envy Freeness Upper Bound Envy-free piece x newpiece: new piece: piece: new x 2x 3x Key observation: In order to increase a player’s utility by , her new piece must span at least (-1) cuts. Utilitarian Price of Envy Freeness Upper Bound Maximize: i ( i 1) x i Subject to: Always holds for envy-free Final utility does not exceed 1 i xi - utility i – number of cuts xi Total number of cuts n 1 xi 1 i n ( i 1) x i 1 i i { 0 ,1,..., n 1} i We bound the solution to the program by n 2 O (1) Trading Fairness for Welfare Definitions: - un-proportional: exists player that gets at most 1/n - envy: exists player that values another player’s piece as worth at least times her own piece - un-equale: exists player that values her allotted piece as worth more than times what another player values her allotted piece Trading Fairness for Welfare Optimal utilitarian may require infinite unfairness (under all three definitions of fairness) Optimal egalitarian may require n-1 envy Egalitarian fairness does conflict with proportionality or equitability Throw One’s Cake and Have It Too with O. Artzi and Y. Dombb Example Alice Bob Bob Alice • Utilitarian welfare: 1 • Utilitarian welfare: (1.5-) How much can be gained by such “dumping”? The Dumping Effect Utilitarian: dumping can increase the utilitarian welfare by (n) Egalitarian: dumping can increase the egalitarian welfare by n/3 Asymptotically tight Pareto Improvement Pareto Improvement: No player is worse-off and some are better-off Strict Pareto Improvement: All players are better-off Theorem: Dumping cannot provide strict Pareto improvement Proof: Each player that improves must get a cut. There are only n-1 cuts. Pareto Improvement Dumping can provide Pareto improvement in which: n-2 players double their utility 2 players stay the same Pareto Improvement Player 1 Player 2 Player 3 Player 4 Player 5 Player 6 Player 7 Player 8 Player 8 Player 1 Player 2 Player 3 Player 4 Player 5 Player 6 Player 7 Pareto Improvement Player 1 Player 8 Player 2 Player 1 Player 3 Player 2 • Player 8: 1/n • Players 1-7: 0.5 Player 4 Player 3 Player 5 Player 4 Player 6 Player 5 Player 7 Player 6 • Player 8: 1/n • Player 1: 0.5 • Players 2-7: 1 Player 7 Computing Socially Optimal Divisions with Y. Dombb and A. Hassidim Computing Socially Optimal Divisions Input: evaluation functions of all players Explicit Piece-wise constant Oracle Find: Socially optimal division Utilitarian Egalitarian Hardness It is NP-complete to decide if there is a division which achieves a certain welfare threshold For both welfare functions Even for piece-wise constant evaluation functions The Discrete Version Player x Player y Player z Approximations Hard to approximate the egalitarian optimum to within (2-) No FPTAS for utilitarian welfare 8+o(1) approximation algorithm for utilitarian welfare In the oracle input model Open Problems Optimizing Social Welfare Approximating egalitarian welfare Tighter bounds for approximating utilitarian welfare Optimizing welfare with strategic players Dumping Algorithmic procedures “Optimal” Pareto improvement Can dumping help in other economic settings? General Two dimensional cake Bounded number of pieces Chores Happy Birthday ! Questions?