Thinned Quantile Shares are Universally Feasible

This paper introduces the concept of $c$-thinned quantile shares to prove the unconditional universal feasibility of a specific quantile share benchmark for fair division of indivisible goods, thereby resolving the feasibility question without relying on the rainbow Erdős matching conjecture and improving the best-known conditional guarantee.

The Gist

Imagine you are hosting a dinner party and have a basket of unique, indivisible items to give to your guests: a rare spice, a vintage spoon, a fancy napkin, and so on. You want to be fair, but you can't cut these items in half. How do you ensure everyone feels they got a "good deal" without knowing exactly how much everyone else values each item?

This is the problem of fair division. For a long time, mathematicians have tried to create a "benchmark" or a "fair share" rule that guarantees everyone gets something they consider valuable.

The Old Problem: The "Perfect" Random Draw

Previously, researchers proposed a clever idea called the Quantile Share. Imagine you tell every guest: "Imagine a magic box where every single item in the basket has a 1-in-$n$ chance of landing in your box (where $n$ is the number of guests). If you look at all the possible random boxes you could get, what is the value of the box that is better than 90% of all other random boxes?"

That value is your "fair share." If you get a real bundle of items that is at least as good as that benchmark, the division is considered fair.

The Catch:
While this sounds great, the authors of this paper found a major roadblock. To prove that this "magic box" rule works for every possible situation (universally), they had to rely on a massive, unsolved math puzzle called the Rainbow Erdős Matching Conjecture. It's like saying, "This recipe works, assuming that a specific, unproven law of physics is true." Until that law is proven, we can't be 100% sure the recipe works.

Furthermore, they found that if you try to demand a "better" share (a higher percentage of the random boxes), the system breaks down completely.

The New Solution: "Thinning" the Magic Box

The authors, Vishesh Jain, Clayton Mizgerd, and Shyam Ravichandran, introduced a simple but powerful tweak. They call it "Thinning."

Instead of giving every item a 1-in-$n$ chance of landing in a guest's box, they lower the odds. Let's say they lower it to a 1-in-100 chance (or any small fraction $c$). They call this a "Thinned Random Bundle."

The Analogy of the "Thinned" Lottery:
Imagine the original magic box was a lottery where you had a decent chance of winning a prize.

• The Old Way: You demand a prize that beats 90% of the original lottery tickets. This is too hard to guarantee for everyone.
• The New Way (Thinning): You change the rules of the lottery first. You make it so that most tickets are now "empty" or "dummy" tickets. The chance of getting a real item is much lower. Then, you ask for a prize that beats 90% of these new, weaker tickets.

Because the benchmark is now "weaker" (it's easier to beat a lottery where most tickets are losers), it becomes mathematically possible to guarantee that everyone can get a real bundle that meets this new, slightly lower standard.

The Big Breakthrough

The paper proves two main things:

1. It Works Unconditionally: By "thinning" the benchmark (making the random chance of getting an item smaller), they proved that there is a specific version of this rule that always works, no matter what the items are or how much people value them. You don't need to wait for that unsolved math puzzle to be solved anymore.

   • Think of it like this: If you can't guarantee everyone gets a Ferrari, you can guarantee everyone gets a reliable bicycle. The "thinned" share is that reliable bicycle. It's a guaranteed fair deal.

2. It Fixes the Old Math Gap: They also showed that if we do assume that unsolved math puzzle is true, we can actually go back to the original, stronger lottery (no thinning) and prove that a much higher standard (1/$e$, which is about 37%) is achievable. This closes a gap that had existed for a while.

Why "Thinning" is the Secret Sauce

You might ask: "Why not just lower the value of the share directly? Like, just say 'everyone gets 50% of the original fair share'?"

The authors explain that this doesn't work for a specific type of tricky math problem (0/1 valuations). If you just lower the number, the math problem stays exactly the same hard version.

The "Thinning" trick is different. It changes the distribution of the items before you even calculate the value.

• Analogy: Imagine trying to fit a large sofa into a small room.
  • Lowering the value: You say, "Okay, we only need a small sofa." But the room is still full of obstacles.
  • Thinning: You remove half the furniture from the room first (the "dummy" items). Now, the sofa fits easily. Once the sofa is in, you put the other furniture back. The sofa is still there, but the path to getting it was cleared by the "thinning" process.

Comparison to Other Methods

The paper also compares this new "Thinned Quantile Share" to another method called Residual Maximin Share (RMMS).

• RMMS is like saying, "I will take the worst possible scenario where my neighbors take their best items, and I want to guarantee I still get something good." It's very robust but hard to calculate.
• Thinned Quantile Share is like saying, "I want a bundle that is better than what I'd get from a specific, slightly rigged lottery."
• The Result: Sometimes RMMS is better, sometimes the Thinned Quantile Share is better. But the Thinned Quantile Share has a huge advantage: it's interpretable. You can explain it to a guest easily: "You got a bundle that is better than 90% of the random bundles you would have gotten if we played this specific lottery."

Summary

The paper solves a long-standing problem in fair division by introducing a "thinning" mechanism. By slightly lowering the probability of items appearing in a random benchmark bundle, they created a fairness rule that is guaranteed to work for everyone, every time, without needing to solve any unsolved math mysteries. It's a clever way of lowering the bar just enough to ensure everyone can step over it, while still keeping the spirit of fairness alive.

Technical Summary

Technical Summary: Thinned Quantile Shares Are Universally Feasible

Problem Statement
The paper addresses the problem of fair division of indivisible goods among $n$ agents with monotone valuations. While classical fairness benchmarks like the Proportional Share (PS) and Maximin Share (MMS) are well-understood, they are not universally feasible for general monotone valuations; specifically, no constant fraction of PS or MMS guarantees a fair allocation for all monotone valuations.

Recent work by Babichenko et al. [5] introduced quantile shares as a promising alternative. A $q$-quantile share is defined based on a random benchmark bundle $X$ where each good is included independently with probability $1/n$. The share is the $q$-quantile of the value $v(X)$. While quantile shares are ordinal, self-maximizing, and interpretable, their universal feasibility was previously known only conditionally. Babichenko et al. showed that if a "rainbow" version of the Erdős Matching Conjecture (EMC) holds, the $(1/2e)$-quantile share is universally feasible. However, they also proved that for any $q > 1/e$, the $q$-quantile share is not universally feasible. This left a significant gap: whether a universally feasible quantile share exists unconditionally, and whether the conditional bound of $1/(2e)$ could be improved to the theoretical upper bound of $1/e$.

Methodology
The authors introduce a refinement of the quantile share concept called the $c$-thinned quantile share. Instead of comparing an agent's allocation to the standard random bundle (inclusion probability $1/n$), they compare it to a $c$-thinned random bundle $X(c)$, where each good is included independently with probability $c/n$ for a fixed constant $c \in (0, 1]$.

The core methodology involves:

1. Reduction to Extremal Set Theory: The authors reduce the fair division problem to a statement about cross-dependent families of sets. A collection of families $\mathcal{F}_1, \dots, \mathcal{F}_n$ is cross-dependent if one cannot select pairwise disjoint sets $F_i \in \mathcal{F}_i$.
2. Thinning as a Parameter: By introducing the thinning parameter $c$, the authors shift the regime of the underlying extremal problem. The original quantile share ($c=1$) corresponds to a "near-perfect" matching regime where the Rainbow EMC is required. The thinned version ($c < 1$) moves the problem into a regime linearly away from the near-perfect threshold.
3. Unconditional Theorems: In this new regime, existing unconditional theorems by Frankl–Kupavskii and Kupavskii on cross-dependent families apply, bypassing the need for the unproven Rainbow EMC.
4. Optimization via Local Constancy: To improve the conditional result for the unthinned case ($c=1$), the authors utilize a "local-constancy" argument. They show that by analyzing a slightly thinned benchmark (where the probability of a "bad" event is in a lower-tail regime governed by Chernoff bounds) and then transferring the result back to the unthinned case, the factor-of-two loss in the previous conditional bound can be eliminated.

Key Contributions and Results

1. Unconditional Universal Feasibility:
   The primary result (Theorem 1.5) establishes that there exists a universal constant $c > 0$ such that the $c$-thinned $e^{-c}$-quantile share is universally feasible.

   • Specifically, the authors show that for $c = 1/250$ (for all $n \ge 2$) or $c = 1/10$ (for sufficiently large $n$), the share is feasible.
   • This is the first nontrivial share known to be universally feasible for general monotone valuations without relying on the Rainbow EMC. (Note: Feige's Residual Maximin Share (RMMS) was previously known to be universally feasible, but the authors note that quantile shares offer different structural properties).

2. Optimality of the Thinned Bound:
   The paper proves (Proposition 1.8) that for any $c \in (0, 1]$, the $c$-thinned $q$-quantile share is not universally feasible if $q > e^{-c}$. This demonstrates that the authors' result is best possible within the framework of $c$-thinned shares.

3. Improved Conditional Result for Original Quantile Shares:
   Using the thinning viewpoint and a local-constancy argument, the authors improve the conditional result for the original (unthinned) quantile share.

   • Theorem 1.7: Assuming the Rainbow Erdős Matching Conjecture, the $(1/e)$-quantile share is universally feasible.
   • This closes the gap between the previous conditional bound of $1/(2e)$ and the known upper barrier of $1/e$.

4. Comparison with Existing Shares:

   • vs. RMMS: The authors show that thinned quantile shares and RMMS are incomparable. In settings with complementary goods (e.g., needing one item from set A and one from set B), RMMS can be 0 while the thinned quantile share is 1. Conversely, for additive valuations, RMMS asymptotically exceeds the thinned quantile share by a constant factor.
   • vs. Ordinary Quantile Shares: The paper demonstrates that simply scaling the value of the ordinary quantile share (e.g., $\alpha \tau_q$) does not weaken the problem for 0/1 valuations. The "thinning" must occur at the level of the distribution generating the benchmark bundle to be effective.

Significance
The paper claims significance in providing the first unconditional proof of universal feasibility for a nontrivial share in the general monotone valuation setting, resolving a major open question left by Babichenko et al. By introducing the concept of "thinning," the authors not only bypass the need for the Rainbow EMC for a specific parameter range but also refine the understanding of the original quantile share, improving its conditional feasibility bound from $1/(2e)$ to the optimal $1/e$.

The work highlights that the obstruction to universal feasibility in the original quantile share arises from the requirement that agents receive bundles of roughly equal size in the original ground set. By adding "dummy goods" and working in a padded universe where the equal-size constraint applies to the dummy coordinates, the real goods are governed by a thinned lower-tail distribution, allowing the application of known extremal set theory results.

The authors emphasize that quantile-based shares remain attractive due to their interpretability (comparing allocations to explicit random lotteries) and computability (approximable via Monte Carlo methods), contrasting with the NP-hardness of computing RMMS even for additive valuations.