A new lower bound for multi-color discrepancy with applications to fair division

Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam

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.

Comparison of new lower bounds against previous state-of-the-art results for discrepancy and fair division metrics.

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

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 $Ω\left(\sqrt{\frac{n}{\ln{k}}}\right)$. This result improves the previously best-known lower bound of $Ω\left(\sqrt{\frac{n}{k}}\right)$ of Doerr and Srivastav [2003] and may have several applications. Here, we explore its implications on the feasibility of fair division concepts for instances with $n$ agents having valuations for a set of indivisible items. The first such concept is known as consensus $1/k$-division up to $d$ items (\cd$d$) and aims to allocate the items into $k$ bundles so that no matter which bundle each agent is assigned to, the allocation is envy-free up to $d$ items. The above lower bound implies that \cd$d$ can be infeasible for $d\in Ω\left(\sqrt{\frac{n}{\ln{k}}}\right)$. We furthermore extend our proof technique to show that there exist instances of the problem of allocating indivisible items to $k$ groups of $n$ agents in total so that envy-freeness and proportionality up to $d$ items are infeasible for $d\in Ω\left(\sqrt{\frac{n}{k\ln{k}}}\right)$ and $d\in Ω\left(\sqrt{\frac{n}{k^3\ln{k}}}\right)$, respectively. The lower bounds for fair division improve the currently best-known ones by Manurangsi and Suksompong [2022].
BibTeX
@inproceedings{caragiannis2025new,
  author = {Ioannis Caragiannis and Kasper Green Larsen and Sudarshan Shyam},
  title = {{A new lower bound for multi-color discrepancy with applications to fair division}},
  booktitle = {SAGT},
  year = {2025},
  doi = {10.1007/978-3-032-03639-1\_13},
}
Figure