# Fair Division via Quantile Shares

arXiv: https://arxiv.org/abs/2312.01874 · HTML: https://mlsanity.com/paper/2312.01874/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2023.

## Built on by (most cited first, 3 of 3)

- [Policy Aggregation](https://mlsanity.com/paper/2411.03651/) (2024)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Fair Allocation in Dynamic Mechanism Design](https://mlsanity.com/paper/2406.00147/) (2024)

## Abstract (arXiv)

We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with combinatorial valuations. To capture fairness, we adopt the notion of shares, where each agent is entitled to a fair share, based on some fairness criterion, and an allocation is considered fair if the value of every agent (weakly) exceeds her fair share. A share-based notion is considered universally feasible if it admits a fair allocation for every profile of monotone valuations. A major question arises: is there a non-trivial share-based notion that is universally feasible? The most well-known share-based notions, namely proportionality and maximin share, are not universally feasible, nor are any constant approximations of them. We propose a novel share notion, where an agent assesses the fairness of a bundle by comparing it to her valuation in a random allocation. In this framework, a bundle is considered q-quantile fair, for q∈[0,1], if it is at least as good as a bundle obtained in a uniformly random allocation with probability at least q. Our main question is whether there exists a constant value of q for which the q-quantile share is universally feasible. Our main result establishes a strong connection between the feasibility of quantile shares and the classical ErdHos Matching Conjecture. Specifically, we show that if a version of this conjecture is true, then the frac12e-quantile share is universally feasible. Furthermore, we provide unconditional feasibility results for additive, unit-demand and matroid-rank valuations for constant values of q. Finally, we discuss the implications of our results for other share notions.