TL;DR
This paper introduces a new, stronger lower bound for multi-color discrepancy in set systems, improving on previous results. This theoretical advancement has direct implications for fair division problems, showing that certain fairness criteria (like envy-freeness and proportionality) are impossible to achieve for a larger range of "unfairness tolerance" parameters ($d$) than previously known.
What Problem Does This Paper Address?
The paper tackles two interconnected problems:
- Multi-color Discrepancy: In combinatorics, this problem asks how to color elements of a set system with $k$ colors such that within each set (subset of the universe), the number of elements of each color is as balanced as possible. The "discrepancy" measures the maximum imbalance. The goal is to find the minimum possible discrepancy achievable for any set system of a given size.
- Fair Division of Indivisible Items: In this domain, we have agents with different valuations for a set of indivisible items. The challenge is to allocate these items to agents (or groups of agents) in a way that satisfies certain fairness criteria. This paper focuses on relaxations of fairness like "envy-freeness up to $d$ items" (EFd) and "proportionality up to $d$ items" (PROPd), where an agent doesn't envy another's bundle too much, or their own bundle is "good enough" even if some items are missing. A related concept is "consensus 1/k-division up to $d$ items" (CDd).
The core problem is to understand the fundamental limits of achieving these fairness properties. Specifically, for a given number of agents, items, and groups, what is the smallest amount of "unfairness tolerance" ($d$) required to guarantee that a fair allocation always exists? The paper aims to establish lower bounds on this tolerance, showing when these fairness notions are provably impossible to satisfy.
Methods
The paper's contributions stem from two main methodological threads:
- Probabilistic Method for Discrepancy: The authors introduce a new lower bound for multi-color discrepancy using a probabilistic argument. They construct a random set system and show that the probability of not finding a $k$-coloring with discrepancy at most $d$ is less than 1. This implies that there must exist at least one set system for which any $k$-coloring has a discrepancy greater than $d$. This technique is a standard tool in discrepancy theory but is applied here to derive a tighter bound.
- Reduction from Discrepancy to Fair Division: The paper leverages the connection between multi-color discrepancy and fair division concepts, particularly CDd. They show that a lower bound on multi-color discrepancy directly translates into a lower bound on the infeasibility of CDd.
- Adapted Probabilistic Construction for Fair Division: For EFd and PROPd, the authors adapt their multi-color discrepancy proof technique. Instead of constructing set systems, they construct valuation profiles for agents. They define random valuations for items and show that the probability of an allocation being envy-free/proportional up to $d$ items is strictly less than 1. This implies the existence of instances where these fairness notions are impossible for a given $d$.
Datasets
Not discussed in the paper. The paper deals with theoretical constructions of set systems and valuation profiles rather than empirical evaluation on existing datasets.
Key Insights and Ideas
- Tighter Bounds on Discrepancy: The paper establishes a new lower bound for multi-color discrepancy of $\Omega\left(\sqrt{\frac{n}{\ln k}}\right)$, which is a significant improvement over the previous $\Omega\left(\sqrt{\frac{n}{k}}\right)$. This suggests that the number of colors ($k$) plays a less dominant role in limiting discrepancy than previously thought, especially when $k$ is large.
- Fundamental Limits of Fair Division: The improved discrepancy bound directly translates into stronger lower bounds for the feasibility of fair division concepts like CDd, EFd, and PROPd. This means that for a given level of "unfairness tolerance" $d$, these fair division notions are infeasible for a wider range of problem instances than previously understood.
- Interplay Between Discrepancy and Fairness: The work highlights the deep connection between abstract combinatorial problems like discrepancy and practical problems like fair resource allocation. The techniques developed for one domain can yield powerful insights into the other.
- Probabilistic Construction as a Powerful Tool: The paper effectively uses probabilistic methods to prove the existence of "hard" instances for both discrepancy and fair division problems, demonstrating the power of this approach in theoretical computer science.
Key Results
- Multi-color Discrepancy Lower Bound: A new lower bound of $\Omega\left(\sqrt{\frac{n}{\ln k}}\right)$ for the minimum discrepancy of any $k$-coloring of a set system with $n$ subsets. This improves upon the previous $\Omega\left(\sqrt{\frac{n}{k}}\right)$.
- Consensus 1/k-Division up to $d$ items (CDd): The paper shows that CDd can be infeasible for $d \in \Omega\left(\sqrt{\frac{n}{\ln k}}\right)$.
- Envy-Freeness up to $d$ items (EFd) for Groups: For $n$ agents partitioned into $k$ groups, EFd can be infeasible for $d \in \Omega\left(\sqrt{\frac{n}{k \ln k}}\right)$.
- Proportionality up to $d$ items (PROPd) for Groups:
- For general group sizes, PROPd can be infeasible for $d \in \Omega\left(\sqrt{\frac{n}{k^3 \ln k}}\right)$.
- A separate bound for PROPd considers the minimum group size, showing infeasibility for $d \in \Omega\left(\sqrt{\frac{\min\{n_1, \dots, n_k\}}{\ln k}}\right)$.
These bounds improve upon the best-known results from Manurangsi and Suksompong (2022).
Limitations and Future Work
- Gap Between Bounds: While the paper provides improved lower bounds, there remains a gap between these lower bounds and the existing upper bounds for these problems. Closing these gaps is identified as an obvious open problem.
- Generalization of Discrepancy: The paper focuses on a specific type of multi-color discrepancy. Further exploration of other variants or related discrepancy measures could be fruitful.
- Applications Beyond Fair Division: The authors suspect that their multi-color discrepancy lower bound may have applications in areas beyond fair division, which they suggest as an interesting avenue for future research.
- Specific Parameters: The proofs rely on specific parameter choices for $m$ (number of items) and $d$ to satisfy certain inequalities. While these choices are made to achieve the desired asymptotic bounds, exploring the behavior for different parameter regimes could be interesting.
Summary updated