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

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 Omegaleft(√fracnlnkright). This result improves the previously best-known lower bound of Omegaleft(√fracnkright) 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 (cdd) 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 cdd can be infeasible for d∈ Omegaleft(√fracnlnkright). 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∈ Omegaleft(√fracnklnkright) and d∈ Omegaleft(√fracnk3lnkright), respectively. The lower bounds for fair division improve the currently best-known ones by Manurangsi and Suksompong [2022].