Abstract
Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong introduced a generalization of classical discrepancy theory to non-additive functions, motivated by applications in fair division. As many classical techniques from discrepancy theory seem to fail in this setting, including linear algebraic methods like the Beck-Fiala Theorem, it remains widely open whether comparable non-additive bounds can be achieved.
To better understand non-additive discrepancy, we study coverage functions in a sparse setting comparable to the classical Beck-Fiala Theorem. Our setting generalizes the additive Beck-Fiala setting, rank functions of partition matroids, and edge coverage in graphs.
More precisely, assuming each of the $n$ items covers only $t$ elements across all functions, we prove a constructive discrepancy bound that is polynomial in $t$, the number of colors $k$, and $\log n$.
Blogger's Review: This paper opens up a new research direction by introducing non-additive discrepancies into classical theory, with significant application potential in fair division problems. The constructive discrepancy bound provides a theoretical foundation for further research, warranting deeper exploration.