A new lower bound for multi-color discrepancy with applications to fair division
Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam · 2025
Read A new lower bound for multi-color discrepancy with applications to fair division by Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10516.txt.
Introduction
Ioannis Caragiannis, Kasper Green Larsen, and Sudarshan Shyam prove a new lower bound for multi-color discrepancy, a measure of how unbalanced a coloring must be. The classic problem asks for colorings where every set in a system holds each color about equally often. The authors build a set system where any coloring with k colors forces a discrepancy well above the best bound known since 2003.
They then turn the result toward fair division. One fairness idea asks that items be split into k bundles so that any agent, given any bundle, stays envy-free up to a few items. The new bound shows this can fail unless the allowance of items grows at a stated rate. Extensions cover dividing items among groups of agents under envy-freeness and proportionality rules. The bounds improve the best known results from 2022.
Catalog record
| CREATOR | Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10516
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
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 n subsets over a set of elements in which any k k -coloring of the elements has discrepancy at least OPEN Ω ( n ln k CLOSE ) \Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{n}{\ln{k}}}}}\right) . This result improves the previously best-known lower bound of OPEN Ω ( n k CLOSE ) \Omega\mathopen{}\mathclose{{\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 n agents having valuations for a set of indivisible items. The first such concept is known as consensus 1 / k 1/k -division up to d d items ( CD d d ) and aims to allocate the items into k k bundles so that no matter which bundle each agent is assigned to, the allocation is envy-free up to d d items. The above lower bound implies that CD d d can be infeasible for OPEN d ∈ Ω ( n ln k CLOSE ) d\in\Omega\mathopen{}\mathclose{{\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 k groups of n n agents in total so that envy-freeness and proportionality up to d d items are infeasible for OPEN d ∈ Ω ( n k ln k CLOSE ) d\in\Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{n}{k\ln{k}}}}}\right) and OPEN d ∈ Ω ( n k 3 ln k CLOSE ) d\in\Omega\mathopen{}\mathclose{{\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) . Conference: ; ; 1. Introduction Allocating indivisible items to agents with valuations for them has been a key problem in fair division . The notion of envy-freeness up to one item (EF1), introduced by Budish (2011) is a well-established fairness notion today. An allocation of items to agents is EF1 if every agent (weakly) prefers the bundle of items allocated to her to the bundle of items allocated to any other agent after removing one item from the latter. In contrast to the notion of envy-freeness, which is very demanding for indivisible items, EF1 can always be achieved in a number of different ways: via the envy-cycle elimination algorithm of Lipton et al. (2004) , the folklore round-robin algorithm, while it is compatible with Pareto-optimality ( Caragiannis et al., 2019 ) . A natural generalization of the standard fair division setting with indivisible items assumes that agents with different valuations for a set of items are partitioned into groups. In this setting, an allocation has one bundle per group, and the agent gets value for the items in the bundle allocated to her group. Unfortunately, EF1 allocations may not exist in this setting ( Kyropoulou et al., 2020 ) . Actually, even the further relaxed notion of envy-freeness up to d items (EF d ) may be infeasible even when d is a function of the number of agents and the number of groups. Manurangsi and Suksompong (2022) show that even envy-freeness up to \Omega\mathopen{}\mathclose{{\left(\sqrt{n}/{k^{2}}}}\right) items can be infeasible for instances with n agents partitioned into k groups. Non-trivial positive results are also known; EF d allocations do exist for d\in O\mathopen{}\mathclose{{\left(\sqrt{n}}}\right) in all instances with n agents. Notice that this bound does not depend on the number of groups. Other fairness properties that have been considered for groups of agents include relaxations of proportionality. An allocation of items to agents partitioned into k groups is proportional up to d items (PROP d ) if the value that each agent has for the bundle of items allocated to her group together with the d most valuable items not allocated to her group is at least 1/k times her total value for all items. The simplest version of PROP 1 was introduced by Conitzer et al. (2017) and is considered for groups of agents by Manurangsi and Suksompong (2022) , who prove similar bounds on d for the feasibility of PROP d allocations with those for EF d mentioned above. Another relevant fairness notion is known as consensus 1/k -division up to d items (CD d ). Here, a partition of the items to k bundles is CD d for a set of n agents with valuations for the items if the values an agent has for any pair of items differ by at most d . Manurangsi and Suksompong (2022) prove that CD d partitions always exist for d\in O\mathopen{}\mathclose{{\left(\sqrt{n}}}\right) and may not exist for d\in\Omega\mathopen{}\mathclose{{\left(\sqrt{n/k}}}\right) . In their proofs, Manurangsi and Suksompong (2022) exploit several problems and statements from discrepancy theory . For example, their lower bound for CD d follows after establishing a connection between k -allocations and k -colorings of set systems. Given a set system consisting of a universe of elements and a collection of n element subsets, a k -coloring of the elements has a discrepancy d if the number of elements colored with any color in each subset S is between |S|/k-d and |S|/k+d . Intuitively, we may think of the elements of a set system as the items of a corresponding fair division instance. Each set corresponds to a distinct agent with valuation 1 for each item corresponding to an element in her set and valuation 0 for any other item. A k -coloring of the elements directly defines an allocation of the items into k bundles. Now, the relation between the minimum discrepancy among all k -colorings of the set system and the minimum value of d for which a CD d allocation exists in the corresponding fair division instance should be clear. The lower bound of Manurangsi and Suksompong (2022) on CD d exploits such a relation and follows directly by a lower bound on multi-color discrepancy due to Doerr and Srivastav (2003) . Other notions, such as the weighted discrepancy of 2 -colorings, are used by Manurangsi and Suksompong (2022) to get upper and lower bounds on EF d and PROP d . 1.1. Our contribution In this paper, we improve the bounds on d for which CD d partitions and EF d and PROP d allocations may not exist. Our new bounds are \Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{n}{\ln{k}}}}}\right) , \Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{n}{k\ln{k}}}}}\right) , and \Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{n}{k^{3}\ln{k}}}}}\right) and apply even to instances with binary agent valuations. For instances with n_{h} agents in group h\in[k] , we also have another lower bound of d\in\Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{\min\{n_{1},n_{2},...,n_{k}\}}{\ln k}}}}\right) for PROP d . For CD d , we exploit the relation of CD d partitions on instances with binary valuations with k -colorings in set systems that have discrepancy d . So, our new lower bound for CD d follows directly by a new lower bound of \Omega\mathopen{}\mathclose{{\left(\sqrt{\frac{n}{\ln{k}}}}}\right) on multi-color discrepancy. This improves the twenty-year-old bound of \Omega\mathopen{}\mathclose{{\left(\sqrt{n/k}}}\right) by Doerr and