We consider a setting where we have a ground set ℳ together with real-valued set functions f₁, …, fₙ, and the goal is to partition ℳ into two sets S₁, S₂ such that |fᵢ (S₁) - fᵢ (S₂) | is small for every i. Many results in discrepancy theory can be stated in this form with the functions fᵢ being additive. In this work, we initiate the study of the unstructured case where fᵢ is not assumed to be additive. We show that even without the additivity assumption, the upper bound remains at most O (√n log n). Our result has implications on the fair allocation of indivisible goods. In particular, we show that a consensus halving up to O (√n log n) goods always exists for n agents with monotone utilities. Previously, only an O (n) bound was known for this setting.
Hollender et al. (Thu,) studied this question.