New algorithm guarantees fair division of goods with non-linear valuations

A team led by Haris Aziz at UNSW Sydney tackles the classic problem of fairly dividing divisible goods when agents value goods non-linearly. For example, an agent might derive zero value below a certain threshold and full utility above it. The paper, published on arXiv and appearing at AAMAS 2025, introduces an algorithm that always produces an allocation achieving a 1/(2n-1)-MMS (maximin share) guarantee for n agents with arbitrary non-decreasing valuations. This result is almost tight: the authors prove that no algorithm can guarantee better than a 1/n approximation to MMS, even when valuations are simple piecewise-constant with a single breakpoint. For the special case of n ≤ 3 agents, the ratio 1/n is shown to be exactly tight.

The paper also delves into envy-freeness (EF) combined with Pareto optimality (PO). It proves that checking whether an EF and PO allocation exists is NP-hard for n agents with at least three goods, even under one-breakpoint piecewise-constant valuations. On the positive side, for the case of a single divisible good, the authors devise a polynomial-time algorithm that can determine the existence of EF+PO allocations for agents with piecewise-linear valuations. These results have direct implications for fair resource allocation in cloud computing, bandwidth distribution, and AI-powered market design, where non-linear valuations are common.