{"ID":2872115,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.09252","arxiv_id":"2509.09252","title":"Discrepancy Beyond Additive Functions with Applications to Fair Division","abstract":"We consider a setting where we have a ground set $M$ together with real-valued set functions $f_1, \\dots, f_n$, and the goal is to partition $M$ 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.","short_abstract":"We consider a setting where we have a ground set $M$ together with real-valued set functions $f_1, \\dots, f_n$, and the goal is to partition $M$ 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...","url_abs":"https://arxiv.org/abs/2509.09252","url_pdf":"https://arxiv.org/pdf/2509.09252v2","authors":"[\"Alexandros Hollender\",\"Pasin Manurangsi\",\"Raghu Meka\",\"Warut Suksompong\"]","published":"2025-09-11T08:37:01Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.GT\"]","methods":"[]","has_code":false}