Fair Allocation under Conflict Constraints
2026-05-11 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to fairly divide indivisible items among people when some items cannot go together, modeled by conflicts in a graph. They focus on fairness called EF1 (envy-freeness up to one item) and efficiency meaning no item can still be given out without causing conflicts. For two people, they prove fair and efficient divisions always exist with some assumptions and can be found efficiently in certain cases. However, without these assumptions or with more people, finding such fair divisions becomes impossible or computationally very hard. They also provide a special positive result for three or more people under specific conditions on a path graph.
envy-freeness up to one item (EF1)maximal allocationindivisible itemsconflict graphindependent setmonotone valuationadditive valuationNP-hardnessinterval graphbipartite graph
Authors
Sarfaraz Equbal, Rohit Gurjar, Ayumi Igarashi, Yatharth Kumar, Pasin Manurangsi, Swaprava Nath, Raghuvansh Saxena, Rohit Vaish, Hirotaka Yoneda
Abstract
We study the fair allocation of indivisible items subject to conflict constraints. In this framework, the items are represented as the vertices of a graph, with edges corresponding to conflicts between pairs of items. Each agent is assigned an independent set of items from the graph. Our goal is to achieve a fair and efficient allocation of these items. Fairness pertains to satisfying envy-freeness up to one item (EF1), while efficiency is defined by maximality, meaning that no unallocated item can be feasibly assigned to any agent. First, we explore the case of two agents. For monotone valuations, we show that a maximal EF1 allocation always exists on any graph. Our existence proof relies on a color-switching technique, which locally modifies a maximal allocation while preserving feasibility and restoring EF1. We further show that such allocations can be computed in pseudopolynomial time in general, and in polynomial time for additive valuations on arbitrary graphs, as well as for monotone valuations on interval and bipartite graphs. By contrast, once monotonicity is dropped, maximal EF1 allocations need not exist even for identical additive valuations, and deciding existence becomes NP-hard. Next, we consider the case with a general number of agents. Again, we arrive at a negative result: An EF1 and maximal allocation fails to exist even for three agents under identical monotone valuations, and determining the existence of such an allocation is NP-hard. On the positive side, we show that under identical non-monotone additive valuations on a path graph, an EF[1,1] and maximal allocation always exists. This result involves a novel application of the "cycle plus triangles" theorem.