  Resource allocation problems are a fundamental domain in which to evaluate
the fairness properties of algorithms. The trade-offs between fairness and
utilization have a long history in this domain. A recent line of work has
considered fairness questions for resource allocation when the demands for the
resource are distributed across multiple groups and drawn from probability
distributions. In such cases, a natural fairness requirement is that
individuals from different groups should have (approximately) equal
probabilities of receiving the resource. A largely open question in this area
has been to bound the gap between the maximum possible utilization of the
resource and the maximum possible utilization subject to this fairness
condition.
  Here, we obtain some of the first provable upper bounds on this gap. We
obtain an upper bound for arbitrary distributions, as well as much stronger
upper bounds for specific families of distributions that are typically used to
model levels of demand. In particular, we find - somewhat surprisingly - that
there are natural families of distributions (including Exponential and Weibull)
for which the gap is non-existent: it is possible to simultaneously achieve
maximum utilization and the given notion of fairness. Finally, we show that for
power-law distributions, there is a non-trivial gap between the solutions, but
this gap can be bounded by a constant factor independent of the parameters of
the distribution.
