2026/07/17 by Haris Aziz, Zixu He, Xinhang Lu +1
#cs.GT
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 (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 ≤ 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.