On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences

This paper resolves a key open question from Gorantla et al. by deriving explicit upper bounds on the number of item copies required to guarantee envy-free allocations for arbitrary numbers of agent groups and item types, using a novel constructive technique that extends to both chores and continuous fair division settings.

The Gist

Imagine you are at a massive potluck dinner, but with a twist. You have 100 identical loaves of bread, 50 identical jars of honey, and 20 identical wheels of cheese. You need to distribute these items among three different families sitting at three different tables.

Here's the catch:

• Family A loves bread but hates cheese.
• Family B thinks honey is the best thing ever but finds bread boring.
• Family C is a cheese fanatic who thinks bread is just a vehicle for cheese.

The goal is Fairness. Specifically, we want an Envy-Free outcome. This means no family should look at another family's pile of food and think, "Hey, I wish I had their pile instead of mine."

The Problem: The "One-of-a-Kind" Nightmare

If you only had one loaf of bread, one jar of honey, and one wheel of cheese, fairness would be impossible. One family would get the bread, another the honey, and the third the cheese. The bread-lover would envy the honey-lover, and the cheese-lover would envy the bread-lover. It's a lose-lose.

For a long time, mathematicians wondered: How many copies of each item do we need to guarantee that a perfectly fair split is possible?

If you have 1,000 loaves of bread, 1,000 jars of honey, and 1,000 wheels of cheese, surely you can make everyone happy, right? But exactly how many is enough? Is it 10? 100? 1,000?

The Previous Discovery

A few years ago, researchers (Gorantla et al.) proved that yes, there is a magic number. If you have enough copies of every item, a perfect, envy-free split is guaranteed to exist.

However, their proof was like a magician pulling a rabbit out of a hat:

1. It was non-constructive: They proved the rabbit exists, but they didn't tell you how to find it.
2. It was vague: They only gave a specific number for simple cases (like 2 families or 2 types of food). For complex scenarios with many families and many food types, they just said, "It's a big number, but we don't know exactly how big."

The New Breakthrough: The "Dissimilarity" Key

This new paper by Gagushin, Mertzanidis, and Psomas solves that mystery. They didn't just prove the rabbit exists; they built a map to find it, and they gave us the exact number of copies needed.

Here is the core idea in simple terms:

1. The "Different Tastes" Advantage

The authors realized that fairness is actually easier when people have very different tastes.

Think of it like a puzzle. If everyone wants the exact same thing (e.g., everyone loves bread), it's hard to split the bread fairly because everyone is fighting for the same slice. But if Family A wants bread, Family B wants honey, and Family C wants cheese, the items naturally sort themselves out! The more "dissimilar" the families are, the easier it is to make everyone happy.

The authors created a mathematical "dissimilarity meter." They measure how far apart the families' preferences are (using concepts like distance on a graph).

• High Dissimilarity: Families want totally different things. You need fewer copies of items to be fair.
• Low Dissimilarity: Families want similar things. You need more copies to smooth out the competition.

2. The "Fractional Cake" Trick

To find the solution, the authors first imagine a world where you can cut items into tiny, fractional pieces (like slicing a loaf of bread into 0.001 slices).

• They invented a clever recipe (called the Relative Norm Mechanism) to slice the food fractionally so that everyone is perfectly happy with their share.
• In this "fractional world," the math works perfectly because you can give Family A 0.4 of a loaf and 0.6 of a jar.

3. The "Rounding" Problem

The real world doesn't allow fractional items. You can't give someone 0.4 of a loaf of bread; you have to give them a whole loaf or none.

• The challenge is: How do you turn that perfect fractional plan into a plan with whole items without making anyone jealous?
• The authors use a mathematical tool called the Frobenius Coin Problem (think of it as a way to make change). They show that if you have enough copies of each item (the "magic number"), you can shuffle the whole items around to match the fractional plan almost perfectly.
• Any tiny difference left over is so small that no one will notice or care. It's like if you were supposed to get 10.001 cookies and you got 10; you aren't going to be jealous of the person who got 10.002.

The Results: The Magic Number

The paper gives a formula for the "magic number" (let's call it $\mu$).

• If you have more than $\mu$ copies of every item type, you are guaranteed a fair split.
• The formula depends on:
  • $n$: The number of families.
  • $t$: The number of item types.
  • $\delta$: How different the families' tastes are (the "dissimilarity").

The Big Surprise:
In previous work, the number of copies needed grew wildly with the number of item types. If you had 100 types of food, you needed a massive amount of food to be fair.
In this new paper, if every family is a single person (not a group), the number of copies needed does not depend on the number of food types at all! Whether you have 2 types of food or 2,000, the amount of food needed to guarantee fairness is roughly the same, as long as the families have different tastes.

Beyond Food: Chores and Cake

The authors didn't stop at food. They showed this logic works for:

• Chores: Imagine dividing up a list of annoying tasks (washing dishes, taking out trash). If people hate different tasks, you need fewer copies of each task to make sure no one feels they got the "worst" deal.
• Cake Cutting: Imagine cutting a cake where people value different flavors (chocolate vs. vanilla) differently. If the preferences are distinct enough, you can cut the cake fairly with very few cuts.

Why This Matters

This paper is like finding a universal key for fairness.

1. It's Constructive: It doesn't just say "it's possible"; it gives a method to actually build the fair split.
2. It's General: It works for any number of people and any number of items.
3. It's Insightful: It teaches us that diversity is a strength. When people have different preferences, it's actually easier to be fair to everyone. We don't need infinite resources to be fair; we just need enough resources to accommodate the differences.

In short: If you have a big enough pile of identical items, and your friends have different tastes, you can always find a way to share that pile so that no one is jealous. And now, we know exactly how big that pile needs to be.

Technical Summary

Here is a detailed technical summary of the paper "On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences" by Gagushin, Mertzanidis, and Psomas.

1. Problem Statement

The paper addresses the fundamental problem of fair division of indivisible items (goods or chores) among agents with dissimilar preferences.

• Setting: There are $n$ agents divided into $d$ groups. Agents within the same group have identical additive valuations. There are $t$ types of items, with $k_j$ copies of item type $j$.
• Goal: To determine conditions under which an envy-free (EF) allocation exists. An allocation is envy-free if no agent (or group) prefers another agent's bundle to their own.
• Context: Previous work by Gorantla et al. [GMV23] proved that if the number of copies of each item type ($\mu$) is sufficiently large, an EF allocation exists. However, their proof was non-constructive and only provided explicit bounds for the special cases where $d=2$ (two groups) or $t=2$ (two item types).
• Open Question: What are the explicit upper bounds on $\mu$ for arbitrary numbers of groups ($d$) and item types ($t$)?

2. Methodology

The authors introduce a novel, constructive technique that bridges fair division with information theory and linear programming. The core methodology consists of three main steps:

A. The "Dissimilarity" Condition

The central insight is that fairness becomes easier to guarantee when agents' preferences are sufficiently dissimilar. The authors quantify this dissimilarity using statistical distance measures between normalized valuation vectors:

• Euclidean Distance ($\ell_2$): Used for goods.
• KL-Divergence and $\chi^2$-Divergence: Used for chores and proportional allocations.
• Intuition: If agents value items very differently, it is easier to assign items to those who value them most without creating envy.

B. Fractional Mechanisms and Gap Analysis

The authors design specific fractional allocation mechanisms to establish a lower bound on the "envy gap" (the advantage an agent has over another).

• For Goods (Relative Norm Mechanism): They define a mechanism $x^{RN}$ where the fraction of an item allocated to an agent is proportional to their $\ell_2$-normalized valuation. They prove that the envy gap between groups is lower-bounded by a function of the Euclidean distance between their valuation vectors.
• For Chores (Log-Relative Norm Mechanism): They adapt the approach for costs using logarithms and $\ell_1$-normalization, linking the gap to the KL-divergence.

C. Rounding via the Frobenius Coin Problem

The main technical challenge is converting the optimal fractional allocation into an integral one while maintaining envy-freeness and ensuring agents in the same group receive identical bundles.

• The Constraint: Agents in the same group must receive the exact same number of items. This makes simple rounding difficult if the number of items to redistribute isn't a multiple of the group sizes.
• The Solution: The authors utilize Brauer's Theorem (a result on the Frobenius coin problem). They show that if the total number of item copies $k_z$ is large enough (specifically $k_z \ge \theta$, where $\theta$ depends on group sizes and their GCD), any sufficiently large integer can be expressed as a non-negative linear combination of group sizes.
• Rounding Procedure:
  1. Solve a Linear Program (LP) to find a fractional allocation maximizing the minimum envy gap.
  2. Round the fractional solution to an integral one. This involves transferring a small number of items between groups.
  3. Key Guarantee: If the number of copies $\mu$ is large enough, the value of the "transferred" fractional items is small enough that it does not exceed the initial envy gap established by the fractional mechanism. Thus, the final integral allocation remains envy-free.

3. Key Contributions and Results

A. Explicit Upper Bounds for Envy-Free Allocations

The paper provides the first explicit upper bounds on $\mu$ (copies per item type) for arbitrary $d$ and $t$.

• Main Result (Goods): An envy-free allocation exists if:
  $$\mu \in O\left( \frac{t n^3}{g \delta^2} \right)$$
  Where:
  • $n$ is the total number of agents.
  • $t$ is the number of item types.
  • $g = \gcd(n_1, \dots, n_d)$ is the greatest common divisor of group sizes.
  • $\delta$ quantifies the dissimilarity between groups (specifically, the minimum squared $\ell_2$ distance between normalized valuation vectors).
• Special Case ($d=n$): If every agent is in their own group, the bound simplifies to $\mu \in O(n^3/\delta^2)$, notably independent of the number of item types $t$.
• Comparison: This improves upon [GMV23], which only had bounds for $d=2$ or $t=2$.

B. Extension to Chores

The framework is extended to chores (indivisible tasks with costs).

• Using the Log-Relative Norm mechanism and KL-divergence, they derive similar bounds.
• Result: An envy-free allocation for chores exists if the number of copies is sufficiently large relative to the KL-divergence between agents' cost vectors.

C. Application to Cake Cutting

The authors apply their dissimilarity condition to the continuous cake-cutting problem (Robertson-Webb query model).

• Assumptions: Valuation functions are $k$-Lipschitz continuous, and the $\ell_2$ distance between any pair of agents' density functions is at least $\sqrt{\delta}$.
• Result: They prove that a strongly envy-free allocation can be found using $O(n\sqrt{n})$ queries (specifically Eval queries), improving upon previous bounds for general valuations.

D. Proportional Allocations in Stochastic Settings

The technique is applied to proportionality (a weaker fairness notion) in stochastic settings where valuations are drawn i.i.d. from $U[0,1]$.

• Goods: Using the Trading Post Mechanism and $\chi^2$-divergence, they show that if $m \in \Omega(n)$, a proportional allocation exists with high probability.
• Chores: Using the Inverse Trading Post Mechanism, they similarly show that for $m \in \Omega(n)$, a proportional allocation of chores exists with high probability.
• Significance: This recovers state-of-the-art existence guarantees for stochastic fair division using a unified, modular framework based on f-divergences.

4. Significance and Impact

1. Resolution of Open Problems: The paper resolves the main open question from [GMV23] by providing explicit, general bounds for the existence of envy-free allocations in the "many copies" regime.
2. Constructive Framework: Unlike the non-constructive proofs of prior work, this approach relies on linear programming and rounding, offering a clearer path toward algorithmic implementation.
3. Unified Perspective: The authors demonstrate that dissimilarity is a structural feature that guarantees fairness. This shifts the focus from "identical agents" (where fairness is hard) to "dissimilar agents" (where fairness is easier), providing a new lens for analyzing tractability in fair division.
4. Broad Applicability: The technique is not limited to goods; it naturally extends to chores, continuous cake cutting, and stochastic settings, unifying results across different fair division domains.
5. Information-Theoretic Connection: The use of f-divergences (KL, $\chi^2$) to quantify fairness gaps establishes a novel and powerful link between fair division and information theory.

In summary, this work establishes that sufficient multiplicity of items combined with sufficient preference dissimilarity is a robust condition for the existence of envy-free and proportional allocations, providing explicit bounds and a versatile analytical toolkit for future research in fair division.