Redividing the Cake

Redividing the Cake

Erel Segal-Halevi

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 498-504. https://doi.org/10.24963/ijcai.2018/69

A heterogeneous resource, such as a land-estate, is already divided among several agents in an unfair way.The challenge is to re-divide it among the agents in a way that balances fairness with ownership rights.We present re-division protocols that attain various combinations of 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 and the pieces should be rectangles; (d) convexity --- the cake is a two-dimensional convex polygon and the pieces should be convex.
Keywords:
Knowledge Representation and Reasoning: Geometric, Spatial, and Temporal Reasoning
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation