arXiv preprint ·
Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
Anchored Sequential Deliberation
High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism
Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.