Abstract
This paper presents a simplified and optimal algorithm for achieving proportional fair division of indivisible items—including goods, chores, and mixtures—using monetary subsidies. By moving away from complex fractional rounding and utilizing a two-stage process involving Double Round-Robin partitioning followed by greedy assignment, the authors establish a universal subsidy bound of $n/4$ for even $n$ and $(n^2 - 1)/(4n)$ for odd $n$. This work closes the theoretical gap for odd numbers of agents and demonstrates that subjective valuations can be reduced to objective instances without increasing the required subsidy.
Introduction
The "fair division" problem involves partitioning a set of $m$ items among $n$ agents such that each agent perceives their share as fair. The gold standard for fairness is proportionality: every agent should receive a bundle worth at least $1/n$ of the total utility. However, when items are indivisible (e.g., a single car or a specific household task), perfect proportionality is often mathematically impossible. To resolve this, researchers introduce subsidies—small monetary compensations to bridge the gap for agents receiving less-than-proportional bundles.
The Challenge of Indivisibility
Previous research established that a total subsidy of $n/4$ was sufficient for chores when $n$ is even, but the methodology relied on complex fractional rounding and left a gap for odd $n$. This paper seeks a simpler, more universal algorithm that works for goods, chores, and "subjective" mixtures where agents may disagree on whether an item is a good or a chore.
Methods: A Two-Stage Framework
The authors propose a framework that avoids the complexity of fractional allocations, focusing instead on a two-stage discrete approach:
- Partitioning via Double Round-Robin: For mixtures of goods and chores, the algorithm uses a Double Round-Robin approach. Goods are allocated in one order, and chores are allocated in the reverse order. This ensures the resulting bundles are "Envy-Free up to one item" (EF1).
- Subsidy-Efficient Assignment: Once bundles are created, they are greedily assigned to agents. The algorithm picks the agent who requires the minimum subsidy to reach their proportional share for a given bundle.
Crucially, the paper introduces a reduction technique for subjective instances. If agents disagree on an item's type, the authors show how to transform the instance into an "objective" one (where everyone agrees) without increasing the total subsidy required.
Key Results and Insights
The most significant finding is that complex rounding is unnecessary; simple round-robin partitioning followed by greedy assignment reaches the theoretical lower bound for subsidies. By ensuring the initial partition is EF1, the authors guarantee that the utility gap for any agent is never larger than the utility of a single item.
The paper proves a total subsidy of $\alpha(n)$ is sufficient for any instance, where:
- $\alpha(n) = n/4$ when $n$ is even.
- $\alpha(n) = (n^2 - 1)/(4n)$ when $n$ is odd.
These results match known lower bounds, meaning no algorithm can guarantee a smaller total subsidy for these classes of problems. Furthermore, the proposed algorithms run in polynomial time, making them computationally practical for large-scale applications.
Conclusion
This work perfects the subsidy requirements for proportionality in indivisible item allocation. While it provides an optimal bound for symmetric agents, future research may extend these findings to weighted agents with different rights or explore strategyproof mechanisms to prevent agents from misrepresenting their utilities to gain larger subsidies.
Summary updated