2025/02/14 by Ioannis Caragiannis, Kasper Green Larsen, Caragiannis, Ioannis +3 · 1 voice · 5 citations
Physics and Astronomy · Computer Science · #Color Science and Applications #Digital Media and Visual Art
paper · pdf · doi:10.48550/arxiv.2502.10516
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 Ω(√\fracnlnk). This result improves the previously best-known lower bound of Ω(√((n)/(k))) 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∈ Ω(√\fracnlnk). 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∈ Ω(√\fracnklnk) and d∈ Ω(√\fracnk3lnk), respectively. The lower bounds for fair division improve the currently best-known ones by Manurangsi and Suksompong [2022].