In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, ensuring that no two adjacent vertices are assigned to the same agent. We explore this problem through three fairness criteria: Stochastic-Dominance Envy-Freeness up to one item for preference orders (SD-EF1), Envy-Freeness up to one item for monotone additive valuations (EF1), and Envy-Freeness up to one item from each side for general additive valuations (EF[1,1]). To achieve this, we introduce a hierarchy of variants of the strong chromatic number, a graph quantity that was independently introduced by Alon and Fellows in the early nineties. Our findings reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified approach to both existential and algorithmic results.
For SD-EF1, we completely characterize the number of agents needed to guarantee a fair allocation for any common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs by Equbal et al. We also show that, unlike in the SD-EF1 setting, the sufficient conditions for EF1 and EF[1,1] are not necessary in general. Our framework yields existential and algorithmic consequences regarding the maximum degree. We establish that every graph with maximum degree $\Delta$ allows for SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3\Delta-1$. Additionally, for any $\varepsilon > 0$, we provide deterministic polynomial-time algorithms that can find such allocations whenever the number of agents is at least $(3+\varepsilon)\Delta$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.
Blogger's Review: This paper delves into the application of strong chromatic numbers in fair allocation, providing practical algorithms and theoretical insights. It presents a novel approach to addressing complex resource distribution issues, particularly under conflict constraints, highlighting its significant academic value and practical implications.