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 n queries, and the best known lower bound is Ω(n 2 ); (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: Harmonically Coalition-Resistant (HCR) and Linearly Coalition-Resistant (LCR). An allocation is HCR-k if the allocation is complete and, for any subset of agents S of size at most k, every agent i ∈ S believes the value of all pieces allocated to agents in S to be at least 1 n-|S|+1 , making the union of all pieces allocated to agents not in S at most n-|S| n-|S|+1 ; for LCR-k allocations, these bounds become |S| n and n-|S| n , respectively. Intuitively, these notions of fairness ask that, for every agent i, the collective value (from the perspective of agent i) that a group of agents receives is limited. If the group includes i, its value is lower-bounded, and if the group excludes i, it is upper-bounded, thus providing the agent some protection against the formation of coalitions. Our hierarchies bridge the gap between proportionality, envy-freeness, and super envy-freeness. HCR-k and LCR-k coincide with proportionality for k = 1. For all k ≤ n, HCR-k allocations are a superset of envy-free allocations (i.e., easier to find). On the other hand, for k ∈ [2, ⌈n/2⌉ -1], LCR-k allocations are incomparable to envy-free allocations. For k ≥ ⌈n/2⌉, LCR-k allocations are a subset of envy-free allocations (i.e., harder to find), while LCR-n coincides with super envy-freeness: the value of each agent for their piece is at least 1/n, and their value for the piece allocated to any other agent is at most 1/n. We prove that HCR-n allocations can be computed using O(n 4 ) queries in the Robertson-Webb model. On the flip side, finding HCR-2 (and therefore all HCR-k for k ≥ 2) allocations requires Ω(n 2 ) queries, while LCR-2 (and therefore all LCR-k for k ≥ 2) allocations cannot be computed using a bounded (in n) number of queries. Our results reveal that envy-free allocations occupy a curious middle ground, between a computationally impossible notion of fairness, LCR-⌈n/2⌉, and a computationally "easy" notion, HCR-n.