Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning

This paper studies fair division of divisible and indivisible items among agents whose cardinal preferences are not necessarily monotone. We establish the existence of fair divisions and develop approximation algorithms to compute them. We address two complementary valuation classes, subadditive and nonnegative, which go beyond monotone functions. Considering both the division of cake (divisible resources) and allocation of indivisible items, we obtain fairness guarantees in terms of (approximate) envy-freeness (EF) and equability (EQ).

In the context of envy-freeness, we prove that an EF division of a cake always exists under cake valuations that are subadditive and globally nonnegative (i.e., the value of the entire cake for every agent is nonnegative, but parts of the cake can be burnt). This result notably complements the nonexistence of EF allocations for burnt cakes known for more general valuations. For envy-freeness in the indivisible-items setting, we establish the existence of EFE3 allocations for subadditive and globally nonnegative valuations; again, such valuations can be non-monotone and can impart negative value to specific item subsets. In addition, we obtain universal existence of EFE3 allocations under nonnegative valuations.

We study equitability under nonnegative valuations. Here, we prove that EQE3 allocations always exist when the agents' valuations are nonnegative (and possibly non-monotone). Also, in the indivisible-items setting, we develop an approximation algorithm that, for given nonnegative valuations, finds allocations that are equitable within additive margins.

Our results have combinatorial implications. For instance, the developed results imply the following novel results: (i) The universal existence of proximately-dense subgraphs: Given any graph G = (V, E) and integer k (at most |V |), there always exists a partition V 1 , V 2 , . . . , V k of the vertex set such that the edge densities within the parts, V i , are additively within four of each other, and (ii) The universal existence of equitable graph cuts: Given any graph G = (V, E) and integer k (at most |V |), there always exists a partition V 1 , V 2 , . . . , V k ̸ = ∅ of the vertex set such that the cut function values of the parts, V i , are additively within 5∆ + 1 of each other; here, ∆ is the maximum degree of G. Further, such partitions can be computed efficiently. In addition to being interesting in and of itself, this result highlights the reach of the developed guarantees beyond fair division and even algorithmic game theory.