Weighted Fair Division of Indivisible Mixed Manna

1 Introduction

• The introduction frames indivisible mixed manna and unequal entitlements as fairness challenges, asking about WEF1 existence, its welfare cost, and exact or guaranteed WMMS.It distinguishes envy-based WEF1 from the partition-based WMMS benchmark and notes that complete WEF1 existence for weighted mixed manna was open.Source: §1 · pp. 1–2

1.1 Our Results

• Every additive mixed-manna instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time, resolving an open question [17].Source: §1.1 · pp. 2–3
• The WEF1 algorithm bundles items valued nonnegatively by at least one agent, sets aside common chores, and handles cases according to whether at least n common chores remain.It uses a reversed weighted picking sequence when at least n remain, and a refined bundling and weighted-goods procedure when fewer remain.Source: §1.1 · p. 3
• (k + 4)/5 is the welfare ratio for the constructed two-agent instances, tending to infinity although maximum welfare is (k + 4)/3 and maximum WEF1 welfare is 5/3.The instances have equal entitlements, normalized total values, common item signs, and singleton values in {−2/3, −1/3, 1/3, 2/3}.Source: §1.1 · p. 3
• A welfare-maximizing WEF1 allocation in the construction is fractionally Pareto optimal, while the two-agent chores-only EF1 price is 5/4.Allowing both common goods and common chores makes the price unbounded.Source: §1.1 · p. 3

3. WMMS for equal-magnitude mixed values.

• For equal-magnitude mixed values and arbitrary positive entitlements, an exact WMMS allocation exists, is computable in polynomial time, and can be chosen fractionally Pareto optimal.It maximizes the sum of utilities normalized by each agent’s magnitude, even over fractional allocations; when magnitudes are equal, it also maximizes ordinary utilitarian welfare.Source: §3 · p. 3
• After normalization, WMMS is determined by each agent’s total normalized value and the entitlement vector; a bipartite flow assigns items to meet positive utility targets.Remaining items can be allocated without reducing agents below their targets, assigning each item to an agent who values it most after normalization to obtain the welfare and fPO conclusions.Source: §3 · pp. 3–4
• An agent’s WEF1 shortfall below WMMS is at most her magnitude times one minus her entitlement divided by the largest entitlement, and this bound is best possible.Equality can occur for every agent below the largest entitlement, even with identical valuations over one common good and two common chores; agents at maximum entitlement receive exact WMMS, and equal entitlements imply MMS-fairness.Source: §3 · p. 4
• For every r > 1, some two-agent, three-item instance with values in {−1, 1, r} has no exact WMMS allocation, and unrestricted entitlement ratios preclude any fixed multiplicative WMMS guarantee compatible with WEF1 for chores.The additive comparison is appropriate because mixed-manna WMMS values may be positive, zero, or negative.Source: §3 · p. 4

1.2 Related Work

• Theorem 4.2 is presented as the first exact WMMS existence theorem for mixed manna with arbitrary positive entitlements and an arbitrary number of items.Theorem 4.4 gives exact WMMS to maximum-entitlement agents, exact MMS under equal entitlements, and a best-possible entitlement-dependent additive guarantee for other agents.Source: §1.2 · pp. 5–6

2 Model and Fairness Notions

• An instance has agents with positive entitlements, indivisible items, and additive valuations; an allocation partitions the items, and equal entitlements define the unweighted setting.Entitlements are normalized to sum to 1.Source: §2 · p. 6
• Mixed manna allows items to be positive, zero, or negative for an agent; an item is subjective if someone values it nonnegatively, and an objective chore if everyone values it negatively.Source: §2 · p. 6

2.1 Weighted Envy-Freeness

• WEF requires each agent’s value per unit entitlement for their own bundle to be at least that of every other bundle; WEF1 permits removing a recipient’s good or the observer’s own chore [17].Exact WEF need not exist, even with two agents and one item that both value positively.Source: §2.1 · p. 6

2.2 Weighted Maximin Share

• WMMS adapts MMS to unequal entitlements by comparing an agent’s value for a partition bundle, scaled by its label’s entitlement; an allocation is WMMS-fair when each agent reaches their share.With equal entitlements, WMMS reduces to ordinary MMS.Source: §2.2 · p. 7
• An integral allocation is fractionally Pareto optimal if no allocation allowing fractional item division weakly improves everyone’s utility and strictly improves at least one agent’s [3] [17] [25].Source: §2.2 · p. 7

3 A Polynomial-Time WEF1 Algorithm for Mixed Manna

• Garg and Sharma [17] left open whether every additive mixed-manna instance with arbitrary positive entitlements admits a complete WEF1 allocation.The result answers this question affirmatively.Source: §3 · p. 7
• Every additive mixed-manna instance with arbitrary positive entitlements has a complete WEF1 allocation computable in polynomial time.This resolves the existence question left open by Garg and Sharma [17].Source: §3 · p. 7

3.1 Combining Items into Acceptable Bundles

• An acceptable bundle is a nonempty bundle of original items valued nonnegatively by at least one agent, and remains indivisible until unpacking.Source: §3.1 · p. 7
• The process starts with subjective items as singleton bundles and objective chores in Z, then merges bundles accepted by an agent or adds a chore that keeps a bundle nonnegative for an agent.Source: §3.1 · p. 8
• The process terminates with nonempty, pairwise disjoint acceptance sets, and every remaining objective chore makes each bundle negative for every agent when added.Source: §3.1 · p. 8
• Every acceptable bundle contains at least one original subjective item.Source: §3.1 · p. 8

A Two-Sided Comparison for the Reversed Weighted Picking Sequence

• RWPS schedules each position to an agent with the fewest prior turns per unit of entitlement, then has that agent take a least-cost remaining chore in reverse order.The schedule has length |Z| and applies to objective chores with positive costs.Source: §3.2 · p. 8
• For bundles with at least one chore, qi=(ki−1)/wi measures the recipient’s chore count after deleting her last-pick chore, normalized by entitlement.Chores are indexed by their forward-schedule positions: xi is the last actual pick and yi is the first actual pick.Source: §3.2 · p. 8
• The comparison guarantees the standard chores bound after removing one chore from the observer’s bundle, and when qi≤qj it remains valid after also omitting j’s first-pick chore.The proof compares normalized-count cost functions across schedule occurrences and integrates the resulting cost comparison.Source: §3.2 · pp. 8–9
• When qi≤qj, j’s first-pick chore can be paired with an acceptable bundle assigned to j, and that pair has negative value for observer i.This uses the additional comparison that omits j’s first-pick chore from the recipient’s bundle.Source: §3.2 · p. 9

3.3 At Least n Remaining Objective Chores

• When |Z| ≥ n, RWPS puts every agent in the first n forward positions, ensuring each agent has k_i ≥ 1.Source: §3.3 · p. 9
• Each bundle B is assigned to an acceptable agent with maximum q_j in T_B, and every agent receives at most one acceptable bundle.The assigned bundle B_i, or ∅ if none is assigned, is combined with C_i to form A_i.Source: §3.3 · p. 9
• The allocation is WEF1, and deleting a single chore eliminates all weighted envy for every agent.The deleted chore is an original objective chore.Source: §3.3 · p. 10

3.4 Fewer than n Remaining Objective Chores

• Refinement terminates with every remaining objective chore more negative to each observer than their total value for all nonnegative acceptable bundles.For every nonsingleton acceptable bundle and observer, some original subjective item can be deleted so the remaining bundle is negative to that observer.Source: §3.4 · p. 11

3.4.1 A weighted goods procedure for subjective items

• The weighted goods procedure assigns each bundle to an agent who values it nonnegatively and provides a positive-item deletion when weighted envy remains; it runs in polynomial time.The procedure applies when every bundle has at least one nonnegative valuer among the agents receiving bundles.Source: §3.4.1 · pp. 11–12

3.4.2 Allocating the remaining chores and acceptable bundles

• The staged allocation of objective chores and acceptable bundles is WEF1 after acceptable bundles are unbundled.Each chore holder takes bundles she values nonnegatively; remaining bundles go to agents without chores using the weighted goods procedure.Source: §3.4.2 · p. 12
• When bundle-level WEF1 deletes an acceptable bundle, deleting one original item from it is at least as effective.For a nonsingleton bundle, refinement supplies a subjective item whose deletion leaves the rest negative to the observer; the goods procedure's deleted bundle has positive value to that observer.Source: §3.4.2 · p. 13

• Both exhaustive branches of Algorithm 1 produce a WEF1 allocation and allocate every original item.For |Z| ≥ n, Lemma 3.4 proves WEF1; for |Z| < n, Lemma 3.7 does.Source: §3.5 · p. 13
• The refinement performs O(m^2) operations, while RWPS and the direct goods implementation use polynomially many rounds.The few-chore refinement applies (R2) at most m times and (R1) at most |P| times for each fixed |Z|.Source: §3.5 · p. 13
• All operations use polynomially encoded rational quantities, so the complete algorithm runs in polynomial time.Bundle values sum at most m input values, and normalized counts use an integer at most m and one input entitlement.Source: §3.5 · p. 13

• The construction uses two equally entitled agents with v_i(M) = 1, common item signs, and singleton values in {−2/3, −1/3, 1/3, 2/3}.Source: §3.6 · p. 13
• The utilitarian price is (k+4)/5 → ∞, and a WEF1 allocation attaining welfare 5/3 is fPO, so the price remains unbounded under that requirement.Source: §3.6 · pp. 14–15
• Every WEF1 allocation has welfare at most 5/3, and assigning agent 1 all ordinary goods and all but one ordinary chore attains that bound.Source: §3.6 · p. 15
• Every WEF1 allocation attaining welfare 5/3 has s = 0 and d = 2; when b is assigned to agent 2, exactly k − 1 ordinary items go to the agent valuing them less.Source: §3.6 · p. 15

4.1 Existence and Polynomial-Time Computability

• Every equal-magnitude mixed instance admits a polynomial-time exact WMMS allocation that is fractionally Pareto optimal; when all agents’ magnitudes agree, it also maximizes utilitarian welfare.Each agent’s item values are restricted to −ai, 0, or ai, with ai > 0.Source: §4.1 · p. 16

4.1.1 A Formula for the WMMS Value

• For agent i, WMMS_i = ai wi λ(Ri), and the integer normalized-utility target is ⌈wi λ(Ri)⌉.The value λ(Ri) is computable in polynomial time by enumerating O(nm) candidates.Source: §4.1.1 · p. 17

4.1.2 A Flow Algorithm

• A polynomial-size bipartite flow matches agents to required liked items, then assigns common chores within bounds, yielding exact WMMS while preserving fractionally Pareto optimality.The algorithm runs in polynomial time; it assigns each item to an agent with maximum normalized value.Source: §4.1.2 · pp. 17, 19

4.2 WEF1 and WMMS for Equal-Magnitude Mixed Values

• For any WEF1 allocation, ui(Ai) ≥ wi λ(Ri) − 1 + wi/wmax; the bound is tight for smaller-entitlement agents, while maximum-entitlement agents receive exact WMMS.With equal entitlements, every WEF1 allocation is MMS-fair, and each agent can reach WMMS by adding a liked item or removing a disliked item when needed.Source: §4.2 · pp. 19–21
• When wmax/wmin ≤ κ, every WEF1 allocation also has a uniform additive WMMS guarantee for equal-magnitude mixed instances.The supplied passage states the bounded-ratio guarantee but does not provide its bound.Source: §4.2 · p. 21
• For entitlement ratios bounded by κ, the WEF1 additive WMMS-loss coefficient 1 −1/κ is best possible.Equality can occur even when the smaller-entitlement agent’s WMMS is positive.Source: §4.2 · pp. 21–22
• For every r > 1, some two-agent, three-item instance with values in {−1, 1, r} has no exact WMMS allocation.The example has no zero values and its failure therefore persists when a second positive magnitude is allowed.Source: §4.2 · p. 22

4.3 No Multiplicative Guarantee under Unrestricted Entitlements

• For every finite ρ ≥1, a two-agent instance with two identical unit-cost chores has no allocation that is both WEF1 and ρ-WMMS.With sufficiently unequal entitlements, WEF1 forces the chores to be split, and the smaller-entitlement agent’s cost-to-WMMS ratio grows without bound as her entitlement approaches zero; the additive comparison remains below one item’s cost.Source: §4.3 · pp. 22–23

5 Conclusion

• WEF1 allocations exist for arbitrary additive values and positive entitlements, via an algorithm that coordinates acceptable bundles with objective chores.The proof uses different allocation arguments depending on whether every agent can receive an objective chore.Source: §5 · p. 23
• The ratio of optimal welfare to best WEF1 welfare is unbounded, even for two unweighted agents with common item signs and normalized total values.The lower bound still holds when the selected WEF1 allocation is fractionally Pareto optimal, so Pareto efficiency does not imply utilitarian approximation.Source: §5 · p. 23
• Under equal-magnitude mixed values, WMMS is computable in polynomial time, and a flow algorithm meets all agents’ targets while achieving fractional Pareto optimality.After normalization, an agent’s WMMS depends on liked items minus disliked items; a ceiling formula yields the partition target, and maximum-normalized-value assignments give fPO.Source: §5 · pp. 23–24
• Every WEF1 allocation gives agent i utility at least WMMS_i − a_i(1 − w_i/w_max), a best-possible bound that is exact for maximum-entitlement agents and under equal entitlements.An agent below WMMS can reach it by adding one liked outside item or removing one disliked item from her bundle.Source: §5 · p. 24
• A second positive singleton-value magnitude can destroy exact WMMS existence, while unrestricted entitlement ratios rule out any fixed multiplicative WMMS guarantee compatible with WEF1.The paper notes that extensions to valuation classes allowing few singleton values need assumptions beyond that restriction alone.Source: §5 · p. 24
• Whether every general mixed-manna instance admits WEF1 and PO remains open even with equal entitlements [5], while WEF1 and fPO cannot always coexist [24, Theorem 4.3].The paper also calls for broader valuation classes supporting exact WMMS under arbitrary entitlements or meaningful additive guarantees from WEF1.Source: §5 · p. 24

RWPS comparison after removing several picks

• The RWPS comparison holds after removing i’s last a actual picks and setting aside j’s first b when (ki − a)/wi ≤ (kj − b)/wj; constant costs make this condition exact for every-valuation guarantees.Li(a) denotes i’s last a actual picks, while Fj(b) denotes j’s first b actual picks; actual picks run opposite the forward schedule.Source: A An RWPS Comparison with Several… · pp. 27–28

Number of chores that may be set aside

• After deleting i’s last a actual picks, the maximum number of j’s first actual picks that can always be set aside is the largest integer b with (ki − a)/wi ≤ (kj − b)/wj.This condition is exact for a statement that must hold for every valuation, as constant costs show.Source: A An RWPS Comparison with Several… · pp. 27–28

Theorem A.3

• Under the stated bundle-negativity and pairwise count conditions, allocating objective chores by RWPS yields WEF1, and deleting i’s objective chore eliminates all of i’s weighted envy.The condition pairs bundles assigned to j that i values nonnegatively with j’s first actual picks; each bundle-chore pair must be negative to i.Source: A An RWPS Comparison with Several… · pp. 28–29

Mixed manna interpretation

• Pairwise disjoint acceptance sets are a sufficient special case of the count requirement, since each observer values at most one bundle assigned to a recipient nonnegatively.For several such bundles, the comparison pairs each with one of the recipient’s first actual picks, provided the count condition holds for every ordered pair.Source: A An RWPS Comparison with Several… · pp. 27–29