Fair Allocation of Divisible Goods under Non-Linear Valuations

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 piecewiseconstant 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 wellknown fairness properties: the maximin share (MMS) guarantee and envy-freeness (EF). For MMS, we devise an algorithm which always produces a 1 2𝑛-1-MMS allocation for 𝑛 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/𝑛 approximation to MMS, even when agents have onebreakpoint piecewise-constant valuations. For 𝑛 ≤ 3 agents, we show the ratio 1/𝑛 is tight. For EF, we show it is NP-hard to check the existence of an EF and Pareto optimal (PO) allocation for 𝑛 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.