Cake-cutting is a fundamental model of dividing a heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem of dividing a discrete cake fairly in which the indivisible goods are aligned on a path and agents are interested in receiving a connected subset of items. We prove that a connected division of indivisible items satisfying a discrete counterpart of envy-freeness, called envy-freeness up to one good (EF1), always exists for any number of agents n with monotone valuations. Our result settles an open question raised by Bil\`o et al. (2019), who proved that an EF1 connected division always exists for the number of agents at most 4. Moreover, the proof can be extended to show the following secretive (1) and extra (2) versions: (1) for n agents with monotone valuations, the path can be divided into n connected bundles such that an EF1 assignment of the remaining bundles can be made to the other agents for any selection made by the secretive agent; (2) for n+1 agents with monotone valuations, the path can be divided into n connected bundles such that when any extra agent leaves, an EF1 assignment of the bundles can be made to the remaining agents.
翻译:在这项研究中,我们考虑的问题是,如何公平地分割一个分离的蛋糕,使不可分割的商品在一条路径上保持一致,而且代理商希望接收一个相连的子项。我们证明,一个互不相连的不可分割的物品的关联分工,满足一个互不相连的无嫉妒的对应物,称为无嫉妒,最多一个商品(EF1),对于任何数目的代理商来说,总是存在带有单调值(EF1)的单一体值。我们的结果解决了一个由Bil ⁇ o等人(2019年)提出的未决问题。Bil ⁇ o等人(2019年)证明,一个EF1连接的分解始终存在最多代理商数目的分解点。4. 此外,证据可以扩展,以显示以下秘密(1)和额外的(2)版本:(1) 对于有单调价的代理商,路径可以分为n连接的捆包件,这样就可以将剩余的EF1分给其他代理商,由秘密代理商作任何选择;(2)对于有单调值的n+1代理商,可以将路径分为n链接的捆件,这样,当任何额外的代理商离开托件时,任何额外的代理商时,可以使用EF1。