  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\in[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 Erd\H{o}s Matching Conjecture. Specifically,
we show that if a version of this conjecture is true, then the
$\frac{1}{2e}$-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.
