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

Jankó, Zsuzsanna and Joó, Attila and Segal-Halevi, Erel and Yuen, Sheung Man (2026) Fairer than Fair: Sharp Bounds for Connected Super-Proportional Cake Cutting. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 85. No.-39. ISSN 1076-9757

Preview

Text 19057c.pdf - Published Version Available under License Creative Commons Attribution. Download (751kB) | Preview

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 · 2n) 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(n2) 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).

Actions (login required)

Edit Item