Proceedings

Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

Xiaowei Wu, Quan Xue, Shengwei Zhou

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4082-4090.

https://doi.org/10.24963/ijcai.2025/455

Keywords

  • Game Theory and Economic Paradigms: GTEP: Computational social choice
  • Game Theory and Economic Paradigms: GTEP: Fair division

Abstract

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.

Xiaowei Wu, Quan Xue, and Shengwei Zhou. 2025. Revisiting Proportional Allocation with Subsidy: Simplification and Improvements. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4082–4090. https://doi.org/10.24963/ijcai.2025/455
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards