Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy

This paper studies the problem of fair division of indivisible goods among $k$ groups of $n_1,\dots ,n_k$ agents. We look at the worst downward deviation $\mathit{\text{PROP}}(n_1,\dots ,n_k)$ of an agent in a group from its $1\mathrm{/}k$-share. We improve the bounds of (Manurangsi and Meka, 2026) and show that $\mathit{\text{PROP}}(n_1,\dots ,n_k)=\tilde{\mathrm{\Theta }}(\sqrt{n\mathrm{/}k})$, where $n=n_1+\dots +n_k$ is the total number of agents. For the proof of the upper bound, we develop novel discrepancy-type tools and, in particular, a way to efficiently work with one-sided discrepancy constraints.