Redividing the Cake

Abstract

The paper considers fair allocation of resources that are already allocated in an unfair way. This setting requires a careful balance between the fairness considerations and the rights of the present owners. The paper presents re-division algorithms that attain various trade-off points between fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity -- the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity -- the cake is a two-dimensional rectangle or rectilinear polygon and the pieces should be rectangles; (d) convexity -- the cake is a two-dimensional convex polygon and the pieces should be convex. These re-division algorithms have implications on another problem: the price-of-fairness -- the loss of social welfare caused by fairness requirements. Each algorithm implies an upper bound on the price-of-fairness with the respective geometric constraints.

Improved algorithms attaining better constants in redivision algorithms and better price-of-fairness bounds

References in corpus (10)

• Online Fair Division: analysing a Food Bank problem
• Fairly Allocating Contiguous Blocks of Indivisible Items
• Fair and Square: Cake-Cutting in Two Dimensions
• Monotonicity and Competitive Equilibrium in Cake-cutting
• Social Integration in Two-Sided Matching Markets
• Cake-Cutting with Different Entitlements: How Many Cuts are Needed?
• Envy-Free Division of Land
• Nash Social Welfare, Matrix Permanent, and Stable Polynomials
• Redividing the Cake
• Counting Blanks in Polygonal Arrangements

Cited by in corpus (7)

• Democratic Fair Allocation of Indivisible Goods
• Monotonicity and Competitive Equilibrium in Cake-cutting
• Computing Welfare-Maximizing Fair Allocations of Indivisible Goods
• Envy-Free Division of Land
• The Constrained Round Robin Algorithm for Fair and Efficient Allocation
• Redividing the Cake
• Fair Multi-Cake Cutting