Fairer than Fair: Sharp Bounds for Connected Super-Proportional Cake Cutting

Abstract

We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize the existence of a connected super-proportional (also called strongly-proportional) allocation -- one in which every agent receives a contiguous piece worth strictly more than their proportional share. The characterization is supplemented with an algorithm that determines its existence using O(n · 2ⁿ) queries. We devise a simpler characterization for agents with strictly positive valuations and with equal entitlements, and present an algorithm to determine the existence of such an allocation using O(n²) queries. We provide matching lower bounds in the number of queries for both algorithms. When a connected super-proportional allocation exists, we show that it can also be computed using a similar number of queries. We also consider the problem of deciding the existence of a connected allocation of a cake in which each agent receives a piece worth a small fixed value more than their proportional share, and the problem of deciding the existence of a connected super-proportional allocation of a pie (a 1-dimensional circular cake).