  For the fundamental problem of allocating a set of resources among
individuals with varied preferences, the quality of an allocation relates to
the degree of fairness and the collective welfare achieved. Unfortunately, in
many resource-allocation settings, it is computationally hard to maximize
welfare while achieving fairness goals.
  In this work, we consider ex-ante notions of fairness; popular examples
include the \emph{randomized round-robin algorithm} and \emph{sortition
mechanism}. We propose a general framework to systematically study the
\emph{interpolation} between fairness and welfare goals in a multi-criteria
setting. We develop two efficient algorithms ($\varepsilon-Mix$ and
$Simple-Mix$) that achieve different trade-off guarantees with respect to
fairness and welfare. $\varepsilon-Mix$ achieves an optimal multi-criteria
approximation with respect to fairness and welfare, while $Simple-Mix$ achieves
optimality up to a constant factor with zero computational overhead beyond the
underlying \emph{welfare-maximizing mechanism} and the \emph{ex-ante fair
mechanism}. Our framework makes no assumptions on either of the two underlying
mechanisms, other than that the fair mechanism produces a distribution over the
set of all allocations. Indeed, if these mechanisms are themselves
approximation algorithms, our framework will retain the approximation factor,
guaranteeing sensitivity to the quality of the underlying mechanisms, while
being \emph{oblivious} to them. We also give an extensive experimental analysis
for the aforementioned ex-ante fair mechanisms on real data sets, confirming
our theoretical analysis.
