The paper introduces a hierarchy of strong chromatic number variants to characterize and algorithmically guarantee SD-EF1, EF1, and EF[1,1] allocations under graph conflict constraints, showing 3Δ-1 agents suffice for any graph of maximum degree Δ.
Leveraging Matchings in Constrained Fair Division with a Conflict Graph
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We study the problem of allocating indivisible goods under constraints, expressed via a conflict graph $G$. In such an instance, the $m$ items are the vertices of $G$ and connected items cannot be allocated in the same bundle. Under this model, it is already known that EF1 allocations may not exist. Our main contribution is an analysis parametrized by the maximum degree $\Delta(G)=\Delta$ on the existence and computation of complete EF1 allocations. We address this question in various cases by leveraging results from matching theory. First, we provide a tight existence result for agents with ordered valuations and for the broader class of tiered valuations. We present an algorithm that returns an EF1 allocation when then number of items does not exceed a specific bound. This bound is determined by $n$ and $\Delta$, and it is tight when $\Delta$ is greater than $2n/3$. We also construct an approximation algorithm when $m$ exceeds this bound. For general additive valuations the problem becomes more challenging. Given the current impossibility results, we focus on the case where the number of items is at most $2n$. For this case, we provide an almost complete picture for the instances that admit EF1 allocations, by combining Round Robin with matchings.
fields
cs.GT 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Fair Allocation under Conflict Constraints via Strong Colorability
The paper introduces a hierarchy of strong chromatic number variants to characterize and algorithmically guarantee SD-EF1, EF1, and EF[1,1] allocations under graph conflict constraints, showing 3Δ-1 agents suffice for any graph of maximum degree Δ.