We study proportional cake cutting on the interval [0,1] under an equal-length constraint requiring each of the n agents to receive a bundle of length exactly 1/n and to assign value at least 1/n to that bundle. We determine the exact worst-case cut complexity of this problem. The exact value is 2n-2 cuts for every n ≥ 1. The lower bound follows from a simple identical-valuation instance, and the main contribution is the matching upper bound, since the only all-n upper bound previously available for this problem was quadratic. Our upper-bound proof starts from the constrained necklace-splitting theorem of Jojić, Panina, and Živaljević, which gives the required partition into equal-length bundles when the number of bundles is a prime power. The main difficulty is to convert this prime-power input into an exact all-n cut bound while preserving the equal-length constraint. When r is a prime-power divisor of n and s = n/r, our transfer principle constructs r equal-length bundles, builds a balanced fractional assignment of agents to bundles, rounds it by Hall’s theorem to an assignment in which each bundle receives exactly s agents, and recurses inside the bundles without additional overhead beyond the recursive cuts. Using the same constrained necklace-splitting theorem, we also show that 2n-2 cuts suffice for equal-length envy-freeness when n is a prime power. For all n, we give an O(n^1.525) upper bound via a peeling argument based on the Stromquist-Woodall exact-share theorem. The exact all-n envy-free cut complexity remains open.

This paper explores the fair allocation of indivisible items in a multidimensional setting, motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria. Such multidimensional settings are not merely of theoretical interest but are central to many real-world applications. For example, cloud computing resources are evaluated based on multiple criteria such as CPU cores, memory, and network bandwidth. In such cases, traditional one-dimensional fairness notions fail to capture fairness across multiple attributes. To address these challenges, we study two relaxed variants of envy-freeness: weak simultaneously envy-free up to c goods (weak sEFc) and strong simultaneously envy-free up to c goods (strong sEFc), which accommodate the multidimensionality of agents’ preferences. Under the weak notion, for every pair of agents and for each dimension, any perceived envy can be eliminated by removing, if necessary, a different set of goods from the envied agent’s allocation. In contrast, the strong version requires selecting a single set of goods whose removal from the envied bundle simultaneously eliminates envy in every dimension. We provide upper and lower bounds on the relaxation parameter c that guarantee the existence of weak or strong sEFc allocations, where these bounds are independent of the total number of items. In addition, we present algorithms for checking whether a weak or strong sEFc allocation exists. Moreover, we establish NP-hardness results for checking the existence of weak sEF1 and strong sEF1 allocations.