Abstract
A classical problem in combinatorics seeks colorings of low discrepancy. More concretely, the goal is to color the elements of a set system so that the number of appearances of any color among the elements in each set is as balanced as possible. We present a new lower bound for multi-color discrepancy, showing that there is a set system with $n$ subsets over a set of elements in which any $k$-coloring of the elements has discrepancy at least $\Omega(\sqrt{n / \ln k})$. This result improves the previously best-known lower bound of $\Omega(\sqrt{n/k})$ of Doerr and Srivastav [2003] and has significant implications for fair division. Specifically, we show that consensus $1/k$-division up to $d$ items (CD$_d$) can be infeasible for $d \in \Omega(\sqrt{n / \ln k})$. We further extend these techniques to establish tighter lower bounds for envy-freeness (EF$_d$) and proportionality (PROP$_d$) in group fair division settings, improving upon the results of Manurangsi and Suksompong [2022].
Introduction
Discrepancy theory investigates how well a discrete set can be partitioned to approximate a continuous distribution. In the context of set systems, the goal is to color elements with $k$ colors such that in every set, the distribution of colors is as uniform as possible. The "discrepancy" of a coloring is the maximum deviation from this ideal balance across all sets and colors.
This problem is not merely a combinatorial curiosity; it is deeply linked to fair division. In fair division, we aim to allocate indivisible items among agents with varying preferences. If we interpret items as elements and agents' preferences as sets, finding a low-discrepancy coloring corresponds to finding an allocation that is "fair" across different groups of agents. For over two decades, the state-of-the-art lower bound for multi-color discrepancy was $\Omega(\sqrt{n/k})$, established in 2003. However, this bound weakens significantly as the number of colors $k$ increases, leaving a gap in our understanding of the fundamental limits of fairness in large-scale systems.
Methodology
The researchers utilized the probabilistic method to establish these new bounds. By constructing a random set system (or a random valuation profile for agents), they proved that the probability of a low-discrepancy coloring existing is strictly less than one.
A key tool in this proof is the Reverse Chernoff Bound. While standard concentration inequalities like the Chernoff bound show that a random variable is likely to stay near its mean, the Reverse Chernoff bound provides a lower limit on the probability of significant deviation. By demonstrating that random valuations are likely to be sufficiently "unbalanced," the authors proved the existence of instances where no coloring can achieve the previously assumed lower discrepancy.
Furthermore, the authors did not treat discrepancy results as a "black box." Instead, they tailored their probabilistic constructions to specific fairness notions. For fair division proofs, they introduced a structure involving "group leaders" with fixed valuations and "followers" with random binary valuations. This allowed them to force specific allocation constraints and then show that random preferences would inevitably lead to unfairness for the followers.
Key Results
The primary contribution of this work is the improvement of the lower bound for multi-color discrepancy by a factor of $\sqrt{k / \ln k}$. This tighter bound directly translates to stronger impossibility results for various fair division concepts.
As shown in the table above, the new bound for multi-color discrepancy (DISC) and consensus division (CD$_d$) is $\Omega(\sqrt{n / \ln k})$. For group fair division, the bounds for envy-freeness (EF$_d$) and proportionality (PROP$_d$) were also improved to $\Omega(\sqrt{n / (k \ln k)})$ and $\Omega(\sqrt{n / (k^3 \ln k)})$, respectively. These results demonstrate that achieving fairness requires ignoring or removing a larger number of items ($d$) than previously thought. Notably, these bounds hold even for simple binary valuations, where agents only value items as 0 or 1.
Conclusion and Future Work
By breaking a long-standing stalemate in discrepancy theory, this research provides a more precise understanding of the limits of fair allocation. The introduction of the $\sqrt{\ln k}$ factor shows that discrepancy does not diminish as rapidly with an increasing number of colors as was once believed.
Despite these advances, a small gap of approximately $\Theta(\sqrt{\ln k})$ remains between the new lower bound and known upper bounds for multi-color discrepancy. Closing this gap remains an open challenge. Additionally, while the bounds for consensus division are now quite tight, there is room for further refinement of the bounds for other fair division properties like EF$_d$ and PROP$_d$. The techniques developed here may also find broader applications in other areas of computer science and mathematics where balancing discrete sets is required.
Summary updated