Fair Division of Time: Multi-layered Cake Cutting
Fair Division of Time: Multi-layered Cake Cutting
复制标题
DOI：
10.24963/ijcai.2020/26
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Hadi Hosseini;Ayumi Igarashi;Andrew Searns
中科院分区：
文献类型：
--
作者：
Hadi Hosseini;Ayumi Igarashi;Andrew Searns
我们启动对多层蛋糕切割的研究，目的是在一组代理商中相当分配多个可分配的资源（蛋糕层）。关键要求是，每个代理只能在每个时间间隔中使用一个资源。几个现实生活中的应用程序对重叠的作品显示出这样的限制，例如，分配了多个设施和资源的时间间隔，或者将转移分配给医疗专业人员。我们研究了无嫉妒和比例分配的存在和计算。我们表明，当层数为两个时，可以保证有多达三种具有两种偏好类型的代理的嫉妒分配，最多可为三种具有两种偏好的代理存在。我们进一步设计了一种用于计算任何数量代理的计算比例分配的算法，当层数可分为三个和/或两个功率。
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.