Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

Xiaowei Wu, Quan Xue, Shengwei ZhouIJCAI 2025 · DOI

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:

  1. 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).
  2. 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.
Structured allocation of goods and chores using a double round-robin approach.

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.

Visualization of bundle utilities and the subsidies required to reach the proportionality threshold.

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

BibTeX
@inproceedings{wu2025revisiting,
  author = {Xiaowei Wu and Quan Xue and Shengwei Zhou},
  title = {{Revisiting Proportional Allocation with Subsidy: Simplification and Improvements}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/455},
}
Figure