Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices
2026-07-11 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explore how to fairly divide a mix of positive items (goods) and negative items (chores) among people when the items can't be split. They note that perfect fairness (envy-freeness) isn't always possible under these conditions, but adding some small amount of divisible money helps achieve it. Specifically, they prove that giving each person at most one dollar ensures a fair division, and this is the best possible limit. They also provide a method to find such a fair allocation efficiently, with the total money needed being no more than the number of people minus one.
envy-freenessindivisible itemsadditive utilitiesfair allocationgoods and choressubsidydivisible moneypolynomial timeutility boundsenvy-free allocation
Authors
Xinhang Lu, Simon Mackenzie, Mashbat Suzuki
Abstract
We study the fair allocation of $m$ indivisible items to $n$ agents with additive utilities. In our setting, each indivisible item may be a good, yielding non-negative utility to some agents, or a chore, yielding negative utility to others. Whilst envy-free allocations may not exist in the indivisible-items setting, envy-freeness can be achieved if some amount of divisible good (i.e., \emph{money}) is introduced. When each item's utility or disutility is bounded by one, we show that a subsidy of at most one dollar per agent suffices to guarantee the existence of an envy-free allocation, and that this bound is tight. Moreover, such an allocation can be computed in polynomial time. Since at least one agent need not receive any subsidy, our results imply that a total subsidy of at most $n-1$ dollars suffices to ensure envy-freeness.