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(nlogn) queries, and this is optimal for deterministic protocols; (ii) envy-free allocations (a subset of proportional allocations) can be computed using O(nnnnnn) queries, and the best known lower bound is Ω(n2); (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(n4) queries in the Robertson-Webb model. On the flip side, finding CHB-2 (and therefore all CHB-k for k≥2) allocations requires Ω(n2) queries, while CLB-2 (and therefore all CLB-k for k≥2) allocations cannot be computed using a bounded (in n) number of queries.