Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

Xiaowei Wu, Quan Xue, Shengwei Zhou

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 4082-4090. https://doi.org/10.24963/ijcai.2025/455

In this paper, we revisit the problem of fair allocation with subsidy. We first consider the allocation of m indivisible chores to n agents with additive (dis)utility functions. Under the assumption that the maximum (dis)utility of an item can be compensated by one dollar, Wu et al. (WINE 2023) showed that a total of n/4 dollars suffices to guarantee a proportional allocation by rounding fractional allocations. Their subsidy guarantee is optimal when n is even. For odd n, there is still a small gap between the upper and lower bounds for the total subsidy. In this paper, we propose a much simpler algorithm for the problem, which does not require rounding fractional allocations, and achieves an optimal subsidy guarantee for all values of n. Different from existing works, our algorithm does not require the computation and rounding of fractional allocations and admits a much simpler analysis. We further show that our algorithm and analysis framework can be extended to the mixture of (subjective) goods and chores, achieving the optimal subsidy guarantee.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Game Theory and Economic Paradigms: GTEP: Computational social choice