CS Paper Radar

Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna

Jugal Garg, Eklavya Sharma, Xiaowei Wu

cs.GT cs.DS ·submitted 2026-09-14 08:29 UTC · v1
theory

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.

Comment
30 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Impossibility Bounds for Maximin Share Allocations

cs.GT ·2026-09-14 ·Tomer Ezra, Tamar Garbuz
benchmarkhighly cited similarity 0.73
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-Ω((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall. For chores, we construct instances in which every allocation gives some agent cost at least a $1+Ω((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. Both asymptotic constructions use $n+O(\log n)$ items. Together with concurrent existence results of Feige (2026), this determines the threshold $n+Θ(\log n)$ for guaranteed MMS existence under additive preferences, for both goods and chores. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.

0.41

Weighted Fair Division of Indivisible Mixed Manna

cs.GT ·2026-09-01 ·Nicholas Teh
highly cited similarity 0.73
Abstract

We study weighted fair division of indivisible mixed manna under additive valuations. First, we resolve the general existence open question for weighted envy-freeness up to one item (WEF1), and show that every instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time. We then show that existence does not imply any welfare guarantee, i.e., the utilitarian price of WEF1 is infinite, even for two unweighted agents with normalized valuations, common item signs, and singleton values in a fixed four-value set; a welfare-maximizing WEF1 allocation in the construction is fractionally Pareto optimal. Second, suppose each agent $i$ has a number $a_i>0$ such that their valuation for any item is $-a_i$, $0$, or $a_i$. Then, for arbitrary entitlements, a weighted maximin share (WMMS) allocation always exists, is computable in polynomial time, and can be chosen to be fractionally Pareto optimal. An exact formula for each WMMS value leads to a polynomial-time flow algorithm. In this class, every WEF1 allocation satisfies a best possible additive WMMS guarantee whose loss depends on the agent's entitlement relative to the largest entitlement. Thus maximum entitlement agents receive exact WMMS and, under equal entitlements, every WEF1 allocation is also MMS-fair. Allowing a second positive magnitude can violate exact WMMS, while unrestricted entitlement ratios rule out any fixed multiplicative WMMS guarantee compatible with WEF1 for chores.

0.44

Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees

cs.GT ·2026-09-02 ·Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
hot direction similarity 0.72
Abstract

We investigate the fair allocation of indivisible items among agents with asymmetric entitlements in mixed manna settings, where the items consist of both goods and chores. For additive valuations, we establish that weighted envy-free up to one item (WEF1) allocations always exist and can be computed in polynomial time. We also study fair and efficient allocation and show that weighted envy-freeness up to one transfer (WEF1T) is compatible with fractional Pareto optimality (fPO) for every mixed-manna instance. This relaxation from WEF1 to WEF1T is tight, as demonstrated by our impossibility result. We further show a best-of-both-worlds result via a finite lottery that guarantees weighted envy-freeness (WEF) in expectation, with every realized allocation satisfying WEF1T and achieving the tight characterization complemented by the existing impossibility result.

0.42

On the Incompatibility of Weighted PROPX and Pareto Optimality for Indivisible Chores

cs.GT ·2026-08-17 ·Haris Aziz, Bo Li
theory similarity 0.72
Abstract

Proportionality (PROP) is one of the simplest fairness criteria for allocating items among agents with additive preferences. With indivisible chores, however, PROP is not always satisfiable. We study proportionality up to any item (PROPX), which requires every agent to satisfy proportionality after any chore is removed from her bundle. Under strictly positive costs, we settle the weighted compatibility question negatively: weighted PROPX and Pareto optimality are incompatible already for two agents and four chores. Moreover, for every $n\geq3$, we give an $n$-agent, $(n+1)$-chore counterexample whose shares can be arbitrarily close to equal. These counterexamples are item-minimal: under strictly positive costs, weighted PROPX and Pareto optimality are always compatible when the number of chores is at most the number of agents, and they are compatible for two agents with at most three chores. Our impossibility result contrasts with the compatibility theorem of Mahara (2026) for weighted envy-freeness up to one item (EF1) and Pareto optimality .

0.04

Envy-Free Chore Allocation with Unit Subsidies under Negative Dichotomous Valuations

cs.GT ·2026-09-13 ·Mainak Sarkar, Soumyarup Sadhukhan
theory similarity 0.71
Abstract · Revised version: Added a unit-subsidy guarantee for objective mixed instances with signed binary marginals, along with additional results on…

We study the allocation of indivisible chores with subsidies under negative dichotomous valuations, where the marginal disutility of every chore is either zero or one. This is the chore analogue of the dichotomous goods model of Barman et al. (2022), for which a subsidy of at most one unit per agent is known to suffice for envy-freeness. Our main contribution is to show that the same optimal guarantee holds for chores under no structural assumption beyond binary marginals. For every instance with negative dichotomous valuations, there exists a complete allocation $\mathcal{A}$ and a subsidy vector $p\in\{0,1\}^n$ with $\sum_{i\in N} p_i\le n-1$ such that $(\mathcal{A},p)$ is envy-free. Moreover, $\mathcal{A}$ is EF1 even before subsidies are paid. The subsidy bound is tight, and both the allocation and the subsidies can be computed in polynomial time in the value-oracle model. Unlike in the corresponding goods setting, a natural incremental extension approach does not work for chores. Our proof instead exploits key properties of an envy-free partial allocation and its associated equality graph to complete the allocation and determine which agents require subsidies. As a further extension of the main theorem, we establish the same optimal unit-subsidy guarantee for objective mixed instances with signed binary marginals, where every item is a good for all agents or a chore for all agents; these valuations need not be additive. The key step is to prove that the goods-side extension argument of Barman et al.~\cite{BKNS22} remains valid even when the previously allocated bundles contain chores. Finally, even for negative dichotomous chore valuations, we show that the unit-subsidy guarantee cannot, in general, be maintained if Pareto optimality is also required.

0.14

Fair Share Allocations for Almost All Agents

cs.GT ·2026-09-27 ·Tomer Ezra, Tamar Garbuz
similarity 0.70
Abstract

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

0.23

Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores

cs.GT ·2026-09-09 ·Xiaohui Bei, Zehan Lin, Shengxin Liu, Rong Luan, Biaoshuai Tao
theory similarity 0.69
Abstract · 23 pages, no figure

We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existence of a PMMS allocation. Together with known nonexistence results for chores, this yields nonexistence for additive goods. In addition, we show that deciding if a given instance admits a PMMS allocation is NP-hard. We also give explicit instances whose PMMS factors are $226/227$ for goods and $1.102065$ for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a $4/3$-PMMS allocation.

0.38

On MMS allocations with few items

cs.GT ·2026-10-05 ·Uriel Feige
theory similarity 0.69
Abstract

We consider the problem of allocating $m$ indivisible items to $n$ agents. For $n \ge 2$, we define $μ(n)$ as the largest $m$ for which every allocation instance with $n$ agents and $m$ items has an allocation that gives each agent at least her maximin share (MMS). We prove that for general monotone valuations, $μ(n) = n + Θ(\log n)$. This holds both for goods and for chores. For arbitrary valuations (not monotone), we prove that $μ(n) = \log n + O(1)$.

0.37