Fair Division with Conflicts: EF1 Allocation Guaranteed for Two Agents
New paper proves envy-free allocation for conflicting items using graph coloring techniques
A team of nine computer scientists from institutions including IIT, University of Tokyo, and Google Research have published a paper on fair allocation of indivisible items where certain items conflict (cannot be jointly assigned to the same agent). The items form a graph with edges representing conflicts; each agent must receive an independent set. The goal is to achieve fairness (EF1: envy-freeness up to one item) and efficiency (maximality: no unallocated item can be added feasibly to any agent).
For two agents with monotone valuations, they prove that a maximal EF1 allocation always exists on any graph, using a novel 'color-switching' technique that locally modifies allocations while preserving feasibility. This allocation can be computed in pseudopolynomial time generally, and polynomial time for additive valuations on arbitrary, interval, and bipartite graphs. However, if monotonicity is dropped, existence fails even for identical additive valuations, and deciding existence is NP-hard. For three or more agents, the news is mostly negative: even with identical monotone valuations, an EF1+maximal allocation may not exist, and checking existence is NP-hard. A positive result appears only for identical additive valuations on a path graph, where a slightly weaker fairness (EF[1,1]) can be achieved with maximality, using the 'cycle plus triangles' theorem.
- Two-agent EF1+maximal exists on any conflict graph under monotone valuations, computed pseudopolynomially
- Polynomial-time algorithms for additive valuations on arbitrary, interval, and bipartite graphs
- Three-agent case fails; existence is NP-hard even with identical monotone valuations, except for path graphs
Why It Matters
Practical implications for resource allocation with compatibility constraints, like staff scheduling or spectrum assignment, now have provable fairness guarantees.