# Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

arXiv: https://arxiv.org/abs/2506.21727 · HTML: https://mlsanity.com/paper/2506.21727/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 26 Jun 2025.

## Builds on (most cited first, 17 of 17)

- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [Democratic Fair Allocation of Indivisible Goods](https://mlsanity.com/paper/1709.02564/) (2017)
- [Fair Division with Allocator's Preference](https://mlsanity.com/paper/2310.03475/) (2023)
- [Almost Group Envy-free Allocation of Indivisible Goods and Chores](https://mlsanity.com/paper/1907.09279/) (2019)
- [Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions](https://mlsanity.com/paper/2202.08713/) (2022)
- [Fair Division of Time: Multi-layered Cake Cutting](https://mlsanity.com/paper/2004.13397/) (2020)
- [Envy-free division of multi-layered cakes](https://mlsanity.com/paper/2106.02262/) (2021)
- [Asymptotic Existence of Fair Divisions for Groups](https://mlsanity.com/paper/1706.08219/) (2017)
- [Fair Division with Market Values](https://mlsanity.com/paper/2410.23137/) (2024)
- [Approximate Maximin Shares for Groups of Agents](https://mlsanity.com/paper/1706.09869/) (2017)
- [Consensus Halving for Sets of Items](https://mlsanity.com/paper/2007.06754/) (2020)
- [Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory](https://mlsanity.com/paper/2105.01609/) (2021)
- [Fair Division with Social Impact](https://mlsanity.com/paper/2412.14818/) (2024)
- [Resource Allocation under the Latin Square Constraint](https://mlsanity.com/paper/2501.06506/) (2025)
- [A new lower bound for multi-color discrepancy with applications to fair division](https://mlsanity.com/paper/2502.10516/) (2025)
- [Tight Lower Bound for Multicolor Discrepancy](https://mlsanity.com/paper/2504.18489/) (2025)

## Built on by (most cited first, 1 of 1)

- [Exact Cut Complexity of Equal-Length Proportional Cake Cutting](https://mlsanity.com/paper/2610.19733/) (2026)

## Abstract (arXiv)

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.