Fair item sharing with money adjusts to varying values and needs
Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna
Computer Science and Game TheoryData Structures and Algorithms
Summary
When dividing things that people want or dislike in different ways, it’s hard to be fair to everyone. The paper looks at how to share items fairly even if people value them differently, by giving extra money called subsidies to balance things out. The authors found the best possible limit on how much money is needed to keep fairness in these tricky cases. They use advanced math to prove their results and also created a quick method to find such fair divisions when the number of people is small. This work answers questions from earlier research about sharing items that can be good or bad to different people.
What this means in practice
- •For resource allocation teams: Design allocation methods that guarantee fairness with minimum financial adjustments even when items have mixed positive and negative values to different users.
- •For policy makers in public budgeting: Plan subsidy schemes to fairly distribute resources or tasks with unequal entitlements while minimizing total costs for public programs.
A theory result. No direct application yet.
Authors
Jugal Garg, Eklavya Sharma, Xiaowei Wu
Abstract
We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a good or a chore by different agents. We focus on the fundamental fairness notion of proportionality. Since proportional allocations need not exist in this setting, we allow monetary subsidies to restore proportionality while minimizing the total subsidy. When each item's (dis)utility is bounded by 1, a total subsidy of at least τ(n) \approx n/4 may be necessary. For goods-only or chores-only instances, the best previously known upper bound was n/3-1/6 due to Wu and Zhou~(2024). We close this gap by proving that a total subsidy of at most τ(n) always suffices, thereby establishing the tight subsidy bound. Our results hold even in the more general setting of weighted mixed manna, resolving an open question posed by~Wu et al. (2023) and Garg et al. (2026). The allocation also satisfies weighted proportionality up to one item (WPROP1). Our proof develops a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) fixed-point theorem, extending the KKM framework to share-based fairness notions. Finally, we design a polynomial-time algorithm to compute such allocations for any fixed number of agents.