Mind the Gap: Cake Cutting With Separation
arXiv:2012.06682 · doi:10.1016/j.artint.2022.103783
Abstract
We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then provide algorithmic analysis of maximin share fairness in this setting -- for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved. We also prove that an envy-free or equitable allocation that allocates the maximum amount of resource exists under separation.
arXiv commentAppears in the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021
References in corpus (8)
- Weighted Envy-Freeness in Indivisible Item Allocation
- Almost Envy-Free Allocations with Connected Bundles
- Picking Sequences and Monotonicity in Weighted Fair Division
- Cake-Cutting with Different Entitlements: How Many Cuts are Needed?
- Fair Cake-Cutting among Families
- The Price of Connectivity in Fair Division
- Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
- Competitive Equilibrium For Almost All Incomes: Existence and Fairness