MinCovTarget : A New Standard for Fair Allocation

The problem of the fair allocation of indivisible items is a relevant and challenging economic problem with several applications. For small dimensional frameworks, the problem can be solved exactly by full enumeration of all the possible allocations of the items. For higher dimensional scenarios, a numerical algorithm is called for. In this paper, we compare two state-of-the-art algorithms for the fair allocation of a number of indivisible goods amongst several agents: the Spliddit and MinCovTarget algorithms. In particular, we investigate MinCovTarget with respect to the possible choices of the target value and we propose based on our experiments two versions of the algorithm: MinCovTarget+ and MinCovTarget*. MinCovTarget+ uses different target values and selects, amongst all the minimal envy allocations found, the ones providing maximum social welfare. Our numerical analysis shows that, in case one aims to minimize envy, MinCovTarget+ is at least as good as Spliddit and, in larger dimensional frameworks, MinCovTarget+ provides no-envy allocations with an higher value of social welfare than Spliddit and at a fraction of the computation time. Moreover, MinCovTarget+ is able to rapidly obtain envy-free allocations also in the high dimensional scenarios for which Spliddit cannot be used. MinCovTarget* is an even faster version of the algorithm that uses a single target value set equal to the total value of goods. MinCovTarget* can handle huge dimensional scenarios (hundreds of agents and goods) within seconds, finding allocations with negligible envy that approximate maximum social welfare. Our numerical experiments have been run with a random uniform integral valuation of the goods to be allocated and with a novel design of the value matrix which takes into account dependent valuations