A new lower bound for multi-color discrepancy with applications to fair division
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915156892581888 |
|---|---|
| author | Caragiannis, Ioannis Larsen, Kasper Green Shyam, Sudarshan |
| author_facet | Caragiannis, Ioannis Larsen, Kasper Green Shyam, Sudarshan |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10516 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A new lower bound for multi-color discrepancy with applications to fair division Caragiannis, Ioannis Larsen, Kasper Green Shyam, Sudarshan Computer Science and Game Theory 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]. |
| title | A new lower bound for multi-color discrepancy with applications to fair division |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.10516 |