Fair Allocation of Divisible Goods under Non-Linear Valuations
Computer Science and Game Theory
Summary
The authors study how to fairly divide divisible goods when people's satisfaction doesn't increase in a simple, straight line as they get more. They focus on two fairness ideas: ensuring everyone gets a decent minimum value (maximin share) and making sure no one envies another's share (envy-freeness). They create an algorithm that guarantees a fair minimum share for all agents but also show limits on how fair this can be. Additionally, they prove it's hard to check if perfectly fair and efficient divisions exist when there are multiple goods, but they find a practical solution for the case with only one good.
Authors
Haris Aziz, Zixu He, Xinhang Lu, Kaiyang Zhou
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.