PaperlayerView exact revision on arXiv

Source-linked AI summary

Weighted Fair Division of Indivisible Mixed Manna

Nicholas Teh

arXiv:2609.01580v1cs.GT

TL;DR

The paper asks whether weighted fair allocations exist for indivisible mixed manna and what welfare and WMMS guarantees accompany them. It proves polynomial-time WEF1 existence generally, establishes unbounded utilitarian loss, and identifies a structured valuation class with polynomial-time exact WMMS allocations and additive guarantees from WEF1.

  • Problem

    Weighted mixed manna lacked a complete WEF1 existence result, while exact WMMS results did not cover mixed manna.

  • Method

    The paper develops polynomial-time allocation procedures and exact WMMS formulas for agents whose nonzero item values have equal magnitude.

  • Results

    WEF1 always exists generally but has unbounded utilitarian price, whereas equal-magnitude mixed values admit polynomial-time, fractionally Pareto optimal WMMS allocations and best-possible additive guarantees from WEF1.

  • Takeaways & Limitations

    Maximum-entitlement agents receive exact WMMS, and under equal entitlements every WEF1 allocation is MMS-fair.

  • Takeaways & Limitations

    Allowing a second positive magnitude can eliminate exact WMMS allocations, and unrestricted entitlement ratios rule out any fixed multiplicative WMMS guarantee compatible with WEF1 for chores.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies fair division when indivisible items can be goods, chores, or subjective across agents, and when agents have unequal entitlements. It asks whether complete WEF1 allocations exist, how much welfare WEF1 can cost, and when WEF1 relates to WMMS.

  • Problem setting: Mixed manna contains indivisible items that may be desirable, neutral, or burdensome, including items with different signs for different agents.Indivisibility can prevent exact envy-freeness even in simple goods instances.
  • Problem setting: Weighted fairness accounts for positive entitlements representing differences such as rent contributions, group sizes, or prior claims.Weighted envy-freeness compares values per unit entitlement.
  • Fairness notions: WEF1 relaxes exact weighted envy-freeness by allowing one suitably valued item to be removed from the recipient’s bundle or the observer’s bundle.The relevant deletion depends on whether the item is a good or chore in the comparison.
  • Fairness notions: WMMS compares an agent’s value for labeled bundles per unit entitlement and scales the minimum by that agent’s entitlement.Unlike WEF1’s pairwise comparison, WMMS is based on an agent-defined partition.
  • Open problems: Complete WEF1 existence was open for weighted mixed manna, while exact WMMS results covered binary goods or chores but not mixed manna.For unrestricted mixed manna, no positive uniform multiplicative MMS guarantee was known even with equal entitlements.
  • Research questions: The paper asks whether complete weighted WEF1 always exists, what utilitarian welfare WEF1 sacrifices, and when exact WMMS or guarantees follow.These questions distinguish general additive valuations from an equal-magnitude valuation class.

1. A complete WEF1 allocation always exists and can be computed in polynomial

The paper proves polynomial-time existence of complete WEF1 allocations for arbitrary positive entitlements, then establishes unbounded welfare loss and exact WMMS results under equal-magnitude mixed values. It also gives an entitlement-dependent additive WMMS guarantee and identifies boundaries where stronger guarantees fail.

  • WEF1 existence: Every additive mixed-manna instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time.This resolves the existence question left open for weighted mixed manna.
  • WEF1 existence: The constructive algorithm combines acceptable items into bundles, separates common chores, and handles the remaining chores through case-specific allocation procedures.When at least n objective chores remain, it uses a reversed weighted picking sequence with an additional comparison property.
  • Welfare cost: The utilitarian price of WEF1 is infinite even for two unweighted agents with common item signs, normalized total values, and singleton values in {−2/3, −1/3, 1/3, 2/3}.For the indexed construction, the welfare ratio is (k + 4)/5 and tends to infinity.
  • Welfare cost: Fractional Pareto optimality does not prevent arbitrarily poor utilitarian welfare among WEF1 allocations.The construction has a welfare-maximizing WEF1 allocation that is fPO, while WEF1 still assigns many items to lower-valuing agents.
  • WMMS: With equal-magnitude mixed values, exact WMMS allocations exist for arbitrary positive entitlements, are computable in polynomial time, and can be chosen fPO.Normalization yields integer targets, and a bipartite flow assigns enough positively valued items to meet them.
  • WEF1–WMMS relation: Every WEF1 allocation has WMMS shortfall at most a_i(1 − w_i/w_max), a best-possible additive guarantee.Maximum-entitlement agents receive exact WMMS, equal entitlements yield MMS fairness, and bounded entitlement ratios give coefficient 1 −1/κ.
  • Limits: Exact WMMS can fail when singleton values include a second positive magnitude, and unrestricted entitlement ratios rule out any fixed multiplicative WEF1-compatible WMMS guarantee for chores.A two-agent, three-item instance with values in {−1, 1, r} lacks an exact WMMS allocation for every r > 1.

2 Model and Fairness Notions

The model consists of agents with additive valuations over indivisible mixed manna and positive entitlements, and formalizes WEF1, WMMS, utilitarian welfare, and fractional Pareto optimality. These notions capture pairwise weighted envy, partition-based guarantees, welfare, and fractional efficiency.

  • Model: An instance has agents, indivisible items, positive entitlements, and additive real-valued valuations, with entitlements normalized to sum to one.An allocation is a partition of all items among agents.
  • Model: Mixed manna allows each item to have positive, zero, or negative value for an agent.Subjective items are nonnegative for at least one agent; objective chores are negative for every agent.
  • Weighted envy-freeness: WEF compares each agent’s own value per entitlement with every other bundle’s value per entitlement.WEF1 permits the relevant one-item deletion in mixed-manna comparisons.
  • Weighted envy-freeness: The observer–recipient formulation identifies the agent evaluating the comparison and the agent whose bundle may be altered.A useful deletion must be positively valued by the observer for a recipient good or negatively valued for an observer chore.
  • Welfare and efficiency: Utilitarian welfare is the sum of agents’ values for their assigned bundles, and its WEF1 price compares unconstrained optimum with the best positive-welfare WEF1 allocation.Fractional Pareto optimality rules out fractional improvements benefiting at least one agent without harming others.
  • Weighted maximin share: WMMS is the largest entitlement-scaled minimum value an agent can secure through a partition whose bundles are labeled by agents.When entitlements are equal, WMMS reduces to ordinary MMS.

3 A Polynomial-Time WEF1 Algorithm for Mixed Manna

The paper answers the open weighted mixed-manna existence question affirmatively: every additive instance with arbitrary positive entitlements has a complete WEF1 allocation computable in polynomial time. The proof is constructive and combines item bundling with separate handling of objective chores.

  • Main theorem: Every additive mixed-manna instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time.The theorem resolves the previously open existence question.
  • Proof strategy: The constructive proof combines selected items into acceptable bundles and establishes comparisons used to allocate objective chores.The algorithm then treats cases with at least n objective chores and fewer than n objective chores separately.

3.1 Combining Items into Acceptable Bundles

The procedure bundles subjective items and objective chores into acceptable bundles, preserving nonempty acceptance sets and ensuring leftover chores cannot be combined acceptably with any bundle. It terminates because each operation strictly reduces the number of current objects.

  • Acceptable bundles are nonempty original-item bundles valued nonnegatively by at least one agent and remain indivisible until unpacking.
  • The bundling process repeatedly merges acceptable bundles valued nonnegatively by one agent or merges a chore into a bundle when their union is acceptable.
  • At termination, acceptance sets are nonempty and pairwise disjoint, and every remaining objective chore makes every acceptable bundle negative for every agent.
  • The process terminates because every operation replaces at least two current objects by one while preserving nonempty acceptance sets and subjective-item containment.

3.2 A Two-Sided Comparison for the Reversed Weighted Picking Sequence

The reversed weighted picking sequence assigns chores according to an entitlement-balanced forward schedule and then reverses the order while choosing least-cost remaining chores. Its two-sided comparison extends the usual last-pick guarantee by also omitting a recipient’s first pick under a normalized-count condition.

  • RWPS first schedules agents by minimum assigned-position count divided by entitlement, then reverses the schedule and gives each selected agent a minimum-cost remaining chore.
  • For each agent, the last-pick chore is her last actual pick, the first-pick chore is her first actual pick, and q_i counts remaining chores after deleting the last pick per entitlement.
  • The standard comparison bounds an observer’s normalized chore cost after deleting her last pick against a recipient’s bundle.
  • When q_i ≤ q_j, the same comparison remains valid after also setting aside the recipient’s first-pick chore.
  • The proof represents each forward occurrence by an interval of normalized counts and a piecewise-constant cost function.

3.3 At Least n Remaining Objective Chores

When at least n objective chores remain, RWPS gives every agent a chore and supports a stronger WEF1 comparison. Deleting each observer’s last-pick chore eliminates all weighted envy, including comparisons involving an additional recipient chore when the normalized-count condition holds.

  • When |Z| ≥ n, the first n forward positions contain every agent, so RWPS assigns each agent at least one chore.
  • The constructed allocation assigns each acceptable bundle to an agent in its acceptance set, with at most one acceptable bundle per agent.
  • Deleting the observer’s single last-pick chore eliminates all weighted envy, establishing WEF1.
  • If the observer’s normalized remaining-pick count is no larger than the recipient’s, the comparison also permits omitting the recipient’s first-pick chore.
  • Deleting the observer’s last-pick chore is valid because it is an objective chore with negative value to that observer.

3.4 Fewer than n Remaining Objective Chores

When fewer than n objective chores remain, the algorithm refines acceptable bundles, assigns chores to selected agents, and allocates remaining bundles among the others. It then unbundles the acceptable bundles while preserving WEF1.

  • The refinement yields two useful consequences: one original item can replace deleting an entire acceptable bundle, and final bundles containing remaining chores are negative for every observer.
  • The refinement terminates and ensures every nonsingleton acceptable bundle contains a suitable original subjective item for each observer, while every remaining chore is sufficiently negative.
  • The goods-side procedure assigns real items only to agents who value them nonnegatively, and WEF1 inequalities survive removal of the corresponding real item.
  • With t=|Z|<n, the algorithm assigns each objective chore to a distinct selected agent, who then takes every remaining acceptable bundle she values nonnegatively.
  • Remaining acceptable bundles are valued nonnegatively by some unselected agent and can therefore be allocated among them using the polynomial-time goods-side procedure.
  • The resulting allocation remains WEF1 after acceptable bundles are unpacked into original items.
  • For agents receiving objective chores, deleting that chore leaves nonnegative own value and nonpositive value for other bundles; agents without chores do not envy chore holders.

3.5 Complete Algorithm and Proof

Algorithm 1 produces a complete WEF1 allocation in either exhaustive case, and the construction runs in polynomial time.

  • Both branches of Algorithm 1 output a WEF1 allocation and allocate every original item.The cases |Z| ≥ n and |Z| < n are exhaustive.
  • O(m^2) operations suffice for the refinement phase.The initial bundling performs at most m merges, and the refinement rules have the stated quadratic bound.
  • The complete algorithm is computable in polynomial time using additions, comparisons, and selections.

3.6 The Utilitarian Price of WEF1 is Unbounded

The paper constructs normalized two-agent mixed-manna instances where WEF1 allocations have bounded welfare while unconstrained welfare grows with k. This makes the utilitarian price of WEF1 unbounded, even when a welfare-maximizing fair allocation is fPO.

  • Construction: With equal entitlements, WEF1 coincides with EF1, linking the construction to known EF1 price comparisons.
  • Construction: For every k ≥ 2, the construction uses two equal-entitlement agents with normalized valuations, common item signs, and singleton values in {−2/3, −1/3, 1/3, 2/3}.
  • Welfare bound: 5/3 is the maximum welfare of any WEF1 allocation in the constructed instance.The bound follows from the cases s = 0 and s = 1, whose welfare bounds are 5/3 and 2/3, respectively.
  • Pareto efficiency: The welfare-maximizing WEF1 allocation is fractionally Pareto optimal, so fPO alone does not approximate maximum utilitarian welfare.It maximizes v1(A1) + 2v2(A2) even over fractional allocations.
  • Welfare bound: WEF1 forces at least k − 1 items to be assigned to the agent who values them less when b goes to agent 2.

4 WMMS for Equal-Magnitude Mixed Values

For equal-magnitude mixed values, arbitrary-entitlement instances admit polynomial-time exact WMMS allocations that can be fractionally Pareto optimal. Every WEF1 allocation also achieves a tight additive WMMS guarantee, while relaxing equal magnitudes or entitlement restrictions can destroy exact or multiplicative guarantees.

  • 4.1 Exact WMMS: The valuation class requires each agent’s item values to be −a_i, 0, or a_i, allowing positive and negative items in the same instance.This generalizes binary goods and binary chores by permitting both signs while preserving a common nonzero magnitude per agent.
  • 4.1 Exact WMMS: Equal-magnitude mixed instances admit exact WMMS allocations for arbitrary positive entitlements, computable in polynomial time and selectable to be fractionally Pareto optimal.When all agents have the same magnitude, the allocation also maximizes ordinary utilitarian welfare.
  • 4.1 Exact WMMS: Each agent’s WMMS equals a_i w_i λ(R_i), where R_i is her total normalized value, yielding the integer target ⌈w_i λ(R_i)⌉.The formula reduces the allocation problem to meeting integer utility targets derived from normalized values and entitlements.
  • 4.1.2 A Flow Algorithm: A bipartite flow assigns positively valued items so every agent reaches the target, while zero-valued assignments preserve normalized utilities and complete the allocation.The resulting construction gives each agent normalized utility at least the target and therefore at least her WMMS.
  • 4.1.2 A Flow Algorithm: The algorithm runs in polynomial time because each distinct R_i requires O(nm) candidate evaluations followed by a polynomial-size bipartite flow.All remaining item assignments are direct.
  • 4.2 WEF1 and WMMS: Every WEF1 allocation has a tight additive WMMS guarantee: an agent’s shortfall is at most a_i(1 − w_i/w_max).The bound is attained for every agent below maximum entitlement, including instances with identical valuations over one common good and two common chores.
  • 4.2 WEF1 and WMMS: Maximum-entitlement agents receive exact WMMS, and equal entitlements make every WEF1 allocation MMS-fair.An agent below WMMS can reach it by adding one positively valued outside item or removing one negatively valued item from her bundle.

5 Conclusion

The paper establishes broad existence results for WEF1 and structured existence results for WMMS, while showing that fairness notions differ sharply in welfare and valuation requirements.

  • Conclusion: WEF1 exists completely for arbitrary additive values and positive entitlements, with a polynomial-time algorithm that jointly handles goods and chores.The proof controls interactions between acceptable bundles and objective chores rather than treating goods and chores independently.
  • Conclusion: The utilitarian price of WEF1 is unbounded even for two unweighted agents with common item signs and normalized total values.The lower bound persists when the selected WEF1 allocation is fractionally Pareto optimal.
  • Conclusion: Equal-magnitude mixed values make WMMS exactly tractable under arbitrary entitlements, with a polynomial-time flow algorithm and fractional Pareto optimality.The WMMS formula depends on each agent’s total liked items minus disliked items, while maximum-normalized-value assignments provide fPO.
  • Conclusion: Every WEF1 allocation guarantees agent i utility at least WMMS_i − a_i(1 − w_i/w_max), with equality possible.Maximum-entitlement agents receive exact WMMS, and equal entitlements yield MMS fairness.
  • Conclusion: A second positive magnitude can destroy exact WMMS existence, while unrestricted entitlement ratios rule out any fixed multiplicative WEF1-compatible WMMS guarantee.These boundaries motivate additive rather than multiplicative comparisons for mixed manna.
  • Conclusion: Open directions include finding WEF1-and-PO allocations in general mixed manna and broader valuation classes supporting exact WMMS or meaningful additive guarantees.The paper notes that equal-entitlement WEF1-and-PO existence remains open and that extensions need assumptions beyond a small number of singleton values.

A An RWPS Comparison with Several Chores Set Aside

The appendix extends RWPS comparisons to several chores set aside by relating removed picks to normalized pick counts and proving an exact count condition.

  • Several chores set aside: The generalized theorem permits acceptable bundles assigned to j to be paired with j’s first actual chores when the negativity condition and pairwise count conditions hold.Each bundle-chore pair is negative for observer i, preventing those bundles from increasing i’s value for j’s final bundle.
  • Several chores set aside: The comparison removes the last a actual picks of observer i and sets aside the first b actual picks of recipient j.Actual picks are taken in reverse schedule order, so these sets correspond respectively to earliest and latest forward occurrences.
  • Several chores set aside: Theorem A.1 gives an RWPS guarantee for every observer-recipient pair after these multiple picks are removed.Its proof shifts the cost comparison by a/w_i and integrates RWPS cost functions over the relevant normalized-count interval.
  • Several chores set aside: The sufficient count condition is exact for guarantees over every valuation when all chores have the same cost to the observer.Under constant costs, the two sides reduce to (k_i − a)/w_i and (k_j − b)/w_j, so the condition holds if and only if the corresponding inequality holds.
  • Several chores set aside: The corollary bounds how many of recipient j’s first actual picks can always be set aside after deleting observer i’s last a actual picks.The maximum integer b is determined by the load-bound condition, with b = 0 always feasible under the stated assumptions.
  • Several chores set aside: Under the theorem’s conditions, deleting x_i eliminates all weighted envy of agent i.In the algorithm’s disjoint-acceptance case, each observer values at most one bundle assigned to a recipient nonnegatively, and deleting an objective chore is permitted.
Loading 2609.01580v1…