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

Arnav Mehra, Alexandros Psomas · 2025

Read On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness by Arnav Mehra, Alexandros Psomas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12950.txt.

Introduction

Arnav Mehra and Alexandros Psomas build ladders of fairness for dividing a cake in a 2025 paper. Cake cutting is the mathematics of fair shares among agents who value pieces differently. Proportionality is the weakest classic demand; envy-freeness is stronger; perfection, stronger still, cannot be computed with bounded queries.

The authors define two hierarchies of intermediate notions that cap how much any group can collectively be worth to one agent. Level one of each ladder is proportionality, and higher levels climb toward envy-freeness. The query costs of each rung are mapped. Fair division gains a finer ruler for protocols that must stop somewhere practical.

Catalog record

CREATORArnav Mehra, Alexandros Psomas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-12950

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness Arnav Mehra, Alexandros Psomas Abstract We consider the classic cake-cutting problem of producing fair allocations for n 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 ) 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 ) O\left(n^{n^{n^{n^{n^{n}}}}}\right) queries, and the best known lower bound is Ω ⁡ ( n 2 ) \Omega(n^{2}) ; (iii) perfect allocations (a subset of envy-free allocations) cannot be computed using a bounded (in n 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 k , if for any subset of agents S S of size at most k k , and every agent i ∈ S i\in S , the value of i i for the union of all pieces allocated to agents outside of S S is at most n − | S | n − | S | + 1 \frac{n-|S|}{n-|S|+1} ; for CLB- k k allocations, the upper bound becomes n − | S | n \frac{n-|S|}{n} . Intuitively, these notions of fairness ask that, for every agent i i , the collective value that a group of agents has (from the perspective of agent i i ) is limited. CHB- k k and CLB- k k coincide with proportionality for k = 1 k=1 . For all k ≤ n k\leq n , CHB- k k allocations are a superset of envy-free allocations (i.e., easier to find). On the other hand, for k ∈ [ 2 , ⌈ n / 2 ⌉ − 1 ] k\in[2,\lceil n/2\rceil-1] , CLB- k k allocations are incomparable to envy-free allocations. For k ≥ ⌈ n / 2 ⌉ k\geq\lceil n/2\rceil , CLB- k k allocations are a subset of envy-free allocations (i.e., harder to find), while CLB- n n coincides with super envy-freeness: the value of each agent for her piece is at least 1 / n 1/n , and her value for the piece allocated to any other agent is at most 1 / n 1/n . We prove that CHB- n n allocations can be computed using O ⁡ ( n 4 ) O(n^{4}) queries in the Robertson–Webb model. On the flip side, finding CHB- 2 2 (and therefore all CHB- k k for k ≥ 2 k\geq 2 ) allocations requires Ω ⁡ ( n 2 ) \Omega(n^{2}) queries, while CLB- 2 2 (and therefore all CLB- k k for k ≥ 2 k\geq 2 ) allocations cannot be computed using a bounded (in n n ) number of queries. Our results show that envy-free allocations occupy a curious middle ground, between a computationally impossible notion of fairness, CLB- ⌈ n / 2 ⌉ \lceil n/2\rceil , and a computationally “easy” notion, CHB- n n . 1 Introduction We consider the classic problem of cake cutting, proposed by Hugo Steinhaus [ 28 ] , while in hiding during World War II [ 30 ] . In this problem, there is a heterogeneous resource, the “cake,” typically represented by the interval [0,1] . There is a set N of n agents with different valuations functions V_{1},\dots,V_{n} over subsets of the cake; these valuations functions are induced by probability measures over [0,1] (and hence, for example, the value of every agent for the entire cake is equal to 1 ). The goal in this problem is to allocate to each agent a piece of the cake — a finite union of disjoint intervals — in a fair manner, under various notions of fairness. This simple model has served as a cornerstone for fair division, shaping many of the field’s foundational questions. A major focus has been the complexity of computing fair allocations. The complexity of discrete cake-cutting protocols is measured by the number of queries they require in the query model suggested by Robertson and Webb [ 24 ] and later formalized (and named) by Woeginger and Sgall [ 31 ] . For example, it is well understood that proportional allocations , those where every agent i\in N values her piece at least 1/n , can be computed using O(n\log n) queries [ 14 ] ; and, this is tight: every deterministic protocol requires \Omega(n\log n) queries [ 16 ] . Another major notion of fairness is equitability , which requires that every agent has the same value for the piece allocated to them, i.e., for all agents i,j\in N , V_{i}(A_{i})=V_{j}(A_{j}) (where A_{\ell} is the piece allocated to agent \ell ). Procaccia and Wang [ 23 ] proved that equitable allocations cannot be computed in a bounded (in n ) number of queries. This result, in turn, rules out bounded protocols for another major notion of fairness, perfection : an allocation A is perfect if for all agents i,j\in N , V_{i}(A_{j})=1/n . 1 1 1 Which, perhaps surprisingly, always exist [ 20 , 2 ] ! Arguably the most important notion of fairness — the holy grail of fair division — is envy-freeness ; an allocation A is envy-free if every agent prefers her piece to the piece allocated to any other agent, i.e., for all agents i,j\in N , V_{i}(A_{i})\geq V_{i}(A_{j}) . It is easy to see that every perfect allocation is envy-free, and every envy-free and complete ( \cup_{i}A_{i}=[0,1] ) allocation is proportional. Unlike proportionality, equitability, and perfection, the complexity of computing (complete) envy-free allocations has been rather elusive. The existence of bounded protocols remained open for two decades until Aziz and Mackenzie [ 3 ] presented a protocol that requires at most O(n^{n^{n^{n^{n^{n}}}}}) queries. The best known lower bound is \Omega(n^{2}) [ 22 ] , leaving an astronomical gap in our understanding. In this paper, we zoom in on the landscape of fairness between proportionality and perfection, focusing on the query complexity of different notions in this less understood intermediate space. 1.1 Our contributions We introduce two new hierarchies of fairness: Complement Harmonically Bounded ( CHB ) and Complement Linearly Bounded ( CLB ). An allocation A satisfies \textsc{CHB}\text{-}k if, for every subset of agents S such that |S|\leq k , and for every agent i\in S , the value of i for the union of pieces allocated to agents not in S is at most \frac{n-|S|}{n-|S|+1} , i.e., \sum_{j\notin S}V_{i}(A_{j})\leq\frac{n-|S|}{n-|S|+1} . For \textsc{CLB}\text{-}k , the upper bound is \frac{n-|S|}{n} instead. The existence of \textsc{CHB}\text{-}k allocations is implied by the existence of envy-free allocations. Consider an envy-free allocation A ; we have that, for all agents i,j\in N , V_{i}(A_{j})\leq V_{i}(A_{i}) . Adding up for all j\notin S we have \sum_{j\notin S}V_{i}(A_{j})\leq(n-|S|)V_{i}(A_{i})\leq(n-|S|)(1-\sum_{j\notin S}V_{i}(A_{j})) ; re-arranging gives the desired inequality. The existence of \textsc{CLB}\text{-}k allocations is similarly implied by the existence of perfect allocations. Our new fairness notions are interesting precisely because they occupy a natural but largely unexplored middle ground between proportionality and envy-freeness. \textsc{CHB}\text{-}k allocations limit how much value groups

Read the complete text