Discrepancy Beyond Additive Functions with Applications to Fair Division

Abstract

We consider a setting where we have a ground set $ℳ$ together with real-valued set functions $f_1,\mathrm{\dots },f_n$, and the goal is to partition $ℳ$ into two sets $S_1,S_2$ such that $|f_i(S_1)-f_i(S_2)|$ is small for every $i$. Many results in discrepancy theory can be stated in this form with the functions $f_i$ being additive. In this work, we initiate the study of the unstructured case where $f_i$ is not assumed to be additive. We show that even without the additivity assumption, the upper bound remains at most $O(\sqrt{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(\sqrt{n\log n})$ goods always exists for $n$ agents with monotone utilities. Previously, only an $O(n)$ bound was known for this setting.