Fair allocation breakthrough: $1 per agent guarantees envy-free distribution
Researchers prove a subsidy of just $1 per person can eliminate envy when splitting goods and chores.
In a new paper on arXiv, computer scientists Xinhang Lu, Simon Mackenzie, and Mashbat Suzuki tackle the classic fair division problem: splitting indivisible items among agents who may view some as goods (positive utility) and others as chores (negative utility). Without subsidies, envy-free allocations rarely exist. The team shows that if each item's absolute utility is bounded by 1, a subsidy of at most $1 per agent is sufficient to achieve envy-freeness, with a total subsidy cap of $n-1 dollars. This bound is proven tight — no smaller per-agent subsidy works in all cases.
Beyond the theoretical optimality, the result is computationally tractable: the envy-free allocation can be found in polynomial time. This moves the solution from a theoretical curiosity to a practical algorithm that could be applied in resource allocation settings, from dividing household chores with small cash adjustments to splitting assets in inheritance or assigning tasks in organizations. The work closes a long-standing open problem and provides a clear, implementable guideline for fair division with minimal side payments.
- Subsidy of at most $1 per agent guarantees envy-free allocation for indivisible goods and chores.
- Total subsidy capped at $n-1 dollars; bound proven tight.
- Allocation computable in polynomial time, enabling practical use.
Why It Matters
A simple, provably optimal subsidy rule makes envy-free division practical for real-world resource and task allocation.