The Negative Value

Fair division theory assumes monotone valuations — more is at least as good as less. Give someone an extra piece of cake and their value doesn’t decrease. This assumption is foundational: essentially every existence theorem for envy-free allocations, from Stromquist to Su, requires it. Without monotonicity, the standard proofs collapse.

Barman and Verma (arXiv:2501.14609) prove that envy-free allocations exist even when valuations are non-monotone — when getting more can make you worse off. The requirement is weaker: valuations must be subadditive (the whole ≤ sum of parts) and globally nonnegative (the total is positive even if pieces are negative). Under these conditions, EF cake divisions always exist, and EFE3 allocations (envy-free up to 3 items) exist for indivisible goods.

The application to graph partitioning makes the non-monotonicity concrete. Partition a graph into equal parts. Each part’s “value” is its internal edge density. Adding more vertices to a part can decrease its density by diluting the existing edges — a natural non-monotonicity. The result: equitable partitions exist where internal edge densities differ by at most 4, regardless of graph structure.

The structural insight: monotonicity was sufficient but not necessary. The actual requirement is much weaker — you need the valuations to be subadditive (no synergies that exceed the parts) and globally nonnegative (the total pie is worth having). The monotonicity assumption was doing less work in the proofs than it appeared to be doing. The heavy lifting was subadditivity.