Weighted Fair Division of Indivisible Mixed Manna
2026-09-01 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to fairly divide items that can be either good or bad among people with different rights or weights. They prove that it is always possible to distribute the items so that no one strongly envies another after removing one item, and this can be done efficiently. However, such fairness does not guarantee good overall satisfaction. They also explore a special case where each person's value for items comes from just three numbers, showing fair shares always exist and can be found quickly, with precise fairness depending on people's entitlements. The authors note that adding more complexity or very unequal rights can break these guarantees.
weighted fair divisionindivisible mixed mannaadditive valuationsweighted envy-freeness up to one item (WEF1)weighted maximin share (WMMS)fractional Pareto optimalityutilitarian price of fairnesspolynomial-time algorithmentitlementsenvy-freeness
Authors
Nicholas Teh
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.