Fair Allocation of Divisible Goods under Non-Linear Valuations

Abstract

We study the problem of dividing homogeneous divisible goods among agents with non-linear valuations. Specifically, the value that an agent gains from a given good depends only on the amount of the good they receive, and is not necessarily linear with respect to the amount. For instance, under one-breakpoint piecewise-constant valuations, each agent specifies a threshold for each good such that this agent receives utility zero (resp., full utility of the good) when getting an amount below (resp., at least) the threshold. Given non-linear valuations that are additive across the goods, we focus on designing fair allocation algorithms and consider two well-known fairness properties: the maximin share (MMS) guarantee and envy-freeness (EF). For MMS, we devise an algorithm which always produces a $\frac{1}{2n-1}$-MMS allocation for $n$ agents with arbitrary non-decreasing valuations. It is worth noting that this algorithmic result is almost tight as we give an impossibility of guaranteeing more than $1/n$ approximation to MMS, even when agents have one-breakpoint piecewise-constant valuations. For $n \leq 3$ agents, we show the ratio $1/n$ is tight. Regarding envy-freeness, we show it is NP-hard to check the existence of an EF and Pareto optimal (PO) allocation for $n$ agents and at least three goods, even when agents have one-breakpoint piecewise-constant valuations. We complement the hardness result by considering the case with a single divisible good, and devising a polynomial-time algorithm to check whether an EF and PO allocation exists or not for agents with piecewise-linear valuations.