On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
Arnav Mehra, Alexandros Psomas
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\left( n^{n^{n^{n^{n^{n}}}}} \right)$ queries, and the best known lower bound is $\Omega(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: Complement Harmonically Bounded (CHB) and Complement Linearly Bounded (CLB). An allocation is CHB-$k$, if for any subset of agents $S$ of size at most $k$, and every agent $i \in S$, the value of $i$ for the union of all pieces allocated to agents outside of $S$ is at most $\frac{n-|S|}{n-|S|+1}$; for CLB-$k$ allocations, the upper bound becomes $\frac{n-|S|}{n}$. 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. Our hierarchies bridge the gap between proportionality, envy-freeness, and super envy-freeness.CHB-$k$ and CLB-$k$ coincide with proportionality for $k=1$. For all $k \leq n$, CHB-$k$ allocations are a superset of envy-free allocations (i.e., easier to find). On the other hand, for $k \in [2, \lceil n/2 \rceil - 1]$, CLB-$k$ allocations are incomparable to envy-free allocations. For $k \geq \lceil n/2 \rceil$, CLB-$k$ allocations are a subset of envy-free allocations (i.e., harder to find), while CLB-$n$ coincides with super envy-freeness: the value of each agent for her piece is at least $1/n$, and her value for the piece allocated to any other agent is at most $1/n$. We prove that CHB-$n$ allocations can be computed using $O(n^4)$ queries in the Robertson–Webb model. On the flip side, finding CHB-$2$ (and therefore all CHB-$k$ for $k \geq 2$) allocations requires $\Omega(n^2)$ queries, while CLB-$2$ (and therefore all CLB-$k$ for $k \geq 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, CLB-$\lceil n/2 \rceil$, and a computationally ``easy'' notion, CHB-$n$.