Fair division of indivisible goods has a fundamental tension: fairness criteria like envy-freeness are impossible to satisfy exactly when goods cannot be split, so relaxations like “envy-free up to one good” (EF1) are used instead. Separately, allocation problems often have compatibility constraints — certain pairs of items shouldn't go to the same agent. When the constraint is hard (absolute prohibition), satisfying both fairness and feasibility can become impossible.
Cseh, Karpov, and Patel (arXiv:2602.20929) treat the constraints as soft — violations are allowed but minimized. The question becomes: how few conflicts must you tolerate to guarantee EF1? Their answer: at most |E|/n violations, where |E| is the number of conflicting pairs and n is the number of agents. A linear-time algorithm achieves this bound using a geometric “closest points” argument combined with round-robin allocation.
The key insight is that the fairness guarantee and the conflict minimization are not competing objectives — they can be optimized together because the round-robin structure that produces EF1 naturally distributes conflicts evenly. The structure that makes allocation fair also makes it conflict-minimizing. The two constraints, which appear to pull in different directions, are aligned by the algorithm's geometry.
For identical valuations, the bound is tight — you cannot do better. The leading term |E|/n is the inevitable cost of distributing conflicts across agents, and no algorithm can reduce it. Fairness sets a floor on conflict.
The general observation: when hard constraints make a problem infeasible, relaxing them to soft constraints can reveal that the competing objectives were never truly opposed. The structure that satisfies one constraint may naturally minimize violations of the other. The apparent conflict between fairness and compatibility is an artifact of the hard constraint, not of the problem.