On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness

We consider the classic cake-cutting problem of producing fair allocations for n agents, in the Robertson-Webb query model. In this model, it is known that: (i) proportional allocations can be computed using O(n log n) queries, and this is optimal for deterministic protocols; (ii) envy-free allocations (a subset of proportional allocations) can be computed using O( n^n^n^n^nⁿ ) queries, and the best known lower bound is Ω(n²); (iii) perfect allocations (a subset of envy-free allocations) cannot be computed using a bounded (in n) number of queries. In this work, we introduce two hierarchies of new fairness notions: Complement Harmonically Bounded (CHB) and Complement Linearly Bounded (CLB). Intuitively, these notions of fairness ask that, for every agent i, the collective value that a group of agents has (from the perspective of agent i) is limited. CHB-k and CLB-k coincide with proportionality for $k=1$. For all k ≤ n, CHB-k allocations are a superset of envy-free allocations (i.e., easier to find). On the other hand, for k ∈ [2, n/2 - 1], CLB-k allocations are incomparable to envy-free allocations. For k ≥ n/2, CLB-k allocations are a subset of envy-free allocations (i.e., harder to find). We prove that CHB-n allocations can be computed using O(n⁴) queries in the Robertson-Webb model. On the flip side, finding CHB-$2$ (and therefore all CHB-k for k ≥ 2) allocations requires Ω(n²) queries, while CLB-$2$ (and therefore all CLB-k for k ≥ 2) allocations cannot be computed using a bounded (in n) number of queries.