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:

1. proportional allocations can be computed using $O(n\log n)$ queries, and this is optimal for deterministic protocols;
2. 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)$;
3. 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: newnotioninverse (newnotioninverseabbrev) and newnotionlinear (newnotionlinearabbrev). An allocation is newnotioninverseabbrev-$k$ if the allocation is complete and, for any subset of agents $S$ of size at most $k$, every agent $i\in S$ believes the value of all pieces allocated to agents in $S$ to be at least $\frac{1}{n-|S|+1}$, making the union of all pieces allocated to agents not in $S$ at most $\frac{n-|S|}{n-|S|+1}$; for newnotionlinearabbrev-$k$ allocations, these bounds become $\frac{|S|}{n}$ and $\frac{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. newnotioninverseabbrev-$k$ and newnotionlinearabbrev-$k$ coincide with proportionality for $k=1$. For all $k\le n$, newnotioninverseabbrev-$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$, newnotionlinearabbrev-$k$ allocations are incomparable to envy-free allocations. For $k\ge \lceil n/2\rceil$, newnotionlinearabbrev-$k$ allocations are a subset of envy-free allocations (i.e., harder to find), while newnotionlinearabbrev-$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 newnotioninverseabbrev-$n$ allocations can be computed using $O(n^4)$ queries in the Robertson–Webb model. On the flip side, finding newnotioninverseabbrev-$2$ (and therefore all newnotioninverseabbrev-$k$ for $k\ge 2$) allocations requires $\Omega (n^2)$ queries, while newnotionlinearabbrev-$2$ (and therefore all newnotionlinearabbrev-$k$ for $k\ge 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, newnotionlinearabbrev-$\lceil n/2\rceil$, and a computationally "easy" notion, newnotioninverseabbrev-$n$.