Comparing Direct Algorithms for Two-Player Fair Division of Indivisible Items - A Computational Study

We present an exhaustive computational study of algorithms for two-person allocation of indivisible objects. We identify eight algorithms that generate balanced allocations using only players' ordinal rankings and test them over all possible rankings of up to N = 12 items. Algorithms are evaluated according to the fairness and efficiency properties of the allocations they produce, including the ordinal properties of envy-freeness, Pareto-optimality, maximinality, and three similar properties based on Borda count. Our results indicate that, overall, the algorithms manage to identify a large majority of allocations that exhibit all three of the ordinal properties. Algorithms that combine bottom-up and top-down approaches find at least one good allocation whenever one exists, while other algorithms fail sometimes. Performance is not as good for Borda properties: In about 6.6% of the problems in which such an allocation exists, no algorithm can find it. We provide examples that illustrate how algorithms behave, and how they fail. We also discuss the overlap between allocations found by different algorithms, and find that algorithms combining both directions are able to find most of the allocations found by unidirectional algorithms, although there are many instances of allocations that can be found only by an algorithm in the latter group