MinCovTarget+: a fast heuristic algorithm for fair allocation

We introduce the MinCovTarget+ algorithm for the problem of fair allocation of indivisible items and we study its performance with respect to some popular fairness and efficiency criteria such as minimal envy, proportionality, maximal Nash welfare and maximal total welfare. By a detailed numerical analysis we compare our newly proposed algorithm with a standard algorithm for this kind of problem: the Spliddit algorithm. Our numerical analysis shows that MinCovTarget+ provides allocations with an excellent balance between fairness and efficiency criteria. In particular, it typically yields minimal (null) envy solutions with a very high value of Nash welfare, at a fraction of the computation time used by Spliddit. Moreover, MinCovTarget+ can be applied in higher dimensions where Spliddit cannot be readily implemented. Our paper is the first in the literature to present a numerical study of these algorithms using a random uniform valuation of the goods to be allocated, as well as a novel design of the value matrix that incorporates dependent valuations. All the numerical estimates in this paper were obtained using a Macbook Air (Apple M1, 8 GB RAM). The corresponding MATLAB code is available at: https://github.com/giovannipuccetti/MinCovTarget. A user-friendly version of the algorithm is available at https://www.fair-allocation.com.