Discrepancy And Fair Division For Non-Additive Valuations

Max Dupre la Tour, Kaito Fujii

We extend the notion of combinatorial discrepancy to \emph{non-additive} functions. Our main result is an upper bound of $O(\sqrt{n\log (nk)})$ on the non-additive $k$-color discre…