Papers for

policy makers in public budgeting

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Fair item sharing with money adjusts to varying values and needs

Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna

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.

Mon 14 SeptComputer Science and Game TheoryData Structures and Algorithms
The gist
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.
Open 2609.15208v1