Fair allocation of indivisible goods: Beyond additive valuations

We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper studies fair allocation of indivisible goods with different types of valuation functions, including submodular, fractionally subadditive, and subadditive valuations. Constant approximation guarantees are provided for agents with submodular and XOS valuations, and a logarithmic bound for agents with subadditive valuations. Close upper bounds for each class of valuation functions are also presented, along with algorithms to find such allocations for submodular and XOS settings in polynomial time.