# Almost Group Envy-free Allocation of Indivisible Goods and Chores

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2019.

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

- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Fair Allocation in Dynamic Mechanism Design](https://mlsanity.com/paper/2406.00147/) (2024)
- [Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions](https://mlsanity.com/paper/2506.21727/) (2025)
- [Multilevel Fair Allocation with Matroid-Rank Preferences](https://mlsanity.com/paper/2512.24105/) (2025)

## Abstract (arXiv)

We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of indivisible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We also prove that checking whether a given allocation satisfies GEF1 is coNP-complete when there are either only goods, only chores or both.