AI summaryⓘ
The authors study how to fairly divide items represented as nodes in a graph among several people, where connected items can't go to the same person. They focus on fairness concepts related to envy-freeness and use a graph theory measure called the strong chromatic number to understand when fair divisions are possible. They fully describe conditions for one fairness type (SD-EF1) and provide good enough conditions for others (EF1 and EF[1,1]), showing close links between these fairness ideas and graph properties. Their work also gives ways to find these fair divisions efficiently when the number of people is large compared to the maximum node connections in the graph. This improves earlier results about coloring graphs fairly.
fair allocationconflict constraintsenvy-freenessgraph coloringstrong chromatic numberstochastic-dominance envy-freeness (SD-EF1)additive valuationsmaximum degreepolynomial-time algorithms
Abstract
In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are assigned to the same agent. We study this problem for agents with common preferences through the lens of 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 do so, we introduce a hierarchy of variants of the strong chromatic number, a graph quantity introduced independently by Alon and Fellows in the early nineties. Our results reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified route to both existential and algorithmic results. For SD-EF1, we fully characterize the number of agents needed to guarantee a fair allocation of a given graph for every common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs due to Equbal, Gurjar, Igarashi, Kumar, Manurangsi, Nath, Saxena, Vaish, and Yoneda. 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 in terms of the maximum degree. We obtain that every graph with maximum degree $Δ$ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3Δ-1$. We further provide, for any $\varepsilon>0$, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least $(3+\varepsilon)Δ$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.