Fair Division of Time: Multi-layered Cake Cutting

Fair Division of Time: Multi-layered Cake Cutting

Hadi Hosseini, Ayumi Igarashi, Andrew Searns

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 182-188. https://doi.org/10.24963/ijcai.2020/26

We initiate the study of multi-layered cake cutting with the goal of fairly allocating multiple divisible resources (layers of a cake) among a set of agents. The key requirement is that each agent can only utilize a single resource at each time interval. Several real-life applications exhibit such restrictions on overlapping pieces, for example, assigning time intervals over multiple facilities and resources or assigning shifts to medical professionals. We investigate the existence and computation of envy-free and proportional allocations. We show that envy-free allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two. We further devise an algorithm for computing proportional allocations for any number of agents when the number of layers is factorable to three and/or some power of two.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice