Optimally Interpolating between Ex-Ante Fairness and Welfare

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 randomized round-robin algorithm and sortition mechanism. We propose a general framework to systematically study the 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 welfare-maximizing mechanism and the 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 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.