Discrepancy Beyond Additive Functions with Applications to Fair Division
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915522871820288 |
|---|---|
| author | Hollender, Alexandros Manurangsi, Pasin Meka, Raghu Suksompong, Warut |
| author_facet | Hollender, Alexandros Manurangsi, Pasin Meka, Raghu Suksompong, Warut |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_09252 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Discrepancy Beyond Additive Functions with Applications to Fair Division Hollender, Alexandros Manurangsi, Pasin Meka, Raghu Suksompong, Warut Combinatorics Discrete Mathematics Computer Science and Game Theory 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. |
| title | Discrepancy Beyond Additive Functions with Applications to Fair Division |
| topic | Combinatorics Discrete Mathematics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2509.09252 |