# Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2024.

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

- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [On Approximate MMS Allocations on Restricted Graph Classes](https://mlsanity.com/paper/2508.06343/) (2025)

## Abstract (arXiv)

We study the problem of allocating indivisible resources under the connectivity constraints of a graph G. This model, initially introduced by Bouveret et al. (published in IJCAI, 2017), effectively encompasses a diverse array of scenarios characterized by spatial or temporal limitations, including the division of land plots and the allocation of time plots. In this paper, we introduce a novel fairness concept that integrates local comparisons within the social network formed by a connected allocation of the item graph. Our particular focus is to achieve pairwise-maximin fair share (PMMS) among the "neighbors" within this network. For any underlying graph structure, we show that a connected allocation that maximizes Nash welfare guarantees a (1/2)-PMMS fairness. Moreover, for two agents, we establish that a (3/4)-PMMS allocation can be efficiently computed. Additionally, we demonstrate that for three agents and the items aligned on a path, a PMMS allocation is always attainable and can be computed in polynomial time. Lastly, when agents have identical additive utilities, we present a pseudo-polynomial-time algorithm for a (3/4)-PMMS allocation, irrespective of the underlying graph G. Furthermore, we provide a polynomial-time algorithm for obtaining a PMMS allocation when G is a tree.