Source-linked AI summary
Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees
Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
TL;DR
The paper asks how to guarantee weighted fairness for indivisible mixed manna when agents have asymmetric entitlements, including alongside efficiency and randomization. It develops preprocessing and weighted-picking methods, proves polynomial-time WEF1 existence, establishes WEF1T with fPO, and constructs a lottery with ex-ante WEF and ex-post WEF1T. The results identify WEF1T as the tight relaxation in the studied settings, while leaving WEF1 with PO open.
Problem
The paper addresses whether weighted fair allocations exist and can be computed for mixed manna, and whether fairness can coexist with fractional Pareto optimality or randomized guarantees.
Method
The paper combines meta-good preprocessing, residual-chore handling, adapted weighted picking sequences, and finite-support lottery construction using incidence-vector compression.
Results
WEF1 allocations are computable in polynomial time, every instance admits WEF1T and fPO, and a finite lottery achieves ex-ante WEF with ex-post WEF1T.
Takeaways & Limitations
WEF1T is sufficient and best possible for combining weighted fairness with fPO or ex-ante WEF and ex-post fairness in mixed manna.
Takeaways & Limitations
Whether allocations satisfying both WEF1 and PO always exist remains open, even with equal entitlements.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies weighted fair division of additive mixed manna with indivisible goods and chores, resolving existence, computation, efficiency, and randomized-guarantee questions. It establishes WEF1 allocations, combines WEF1T with fPO, and obtains a finite lottery with ex-ante WEF and ex-post WEF1T.
- 1 Introduction: Mixed manna combines indivisible goods and chores, with agents evaluating items through additive valuations and possibly differing entitlements.
- 1.1 Our Contributions: The one-transfer relaxation is tight for the paper’s fairness-and-efficiency and lottery settings, while whether WEF1 and PO always coexist remains open.
- 1.1 Our Contributions: WEF1 allocations exist for every additive mixed-manna instance with arbitrary positive entitlements and can be computed in polynomial time.
- 1.1 Our Contributions: The algorithm preprocesses items into meta-goods and residual chores, then applies adapted weighted picking sequences to obtain WEF1.
- 1.1 Our Contributions: WEF1 and fPO are not generally compatible, but every mixed-manna instance admits an allocation satisfying both WEF1T and fPO.
- 1.1 Our Contributions: A finite lottery guarantees ex-ante WEF and ex-post WEF1T for every mixed-manna instance.
2 Preliminary
The preliminaries define weighted fairness, additive mixed-manna valuations, and Pareto-based efficiency. They distinguish WEF1 from WEF1T by whether one item is removed or transferred in resolving weighted envy.
- 2 Preliminary: Each agent has a positive entitlement w_i, normalized so that the entitlements sum to one; equal weights recover the unweighted setting.
- 2 Preliminary: Additive valuations assign bundle value by summing the values of its items, and an allocation is an ordered partition of the items into agents’ bundles.
- 2 Preliminary: An item may be a good or chore differently for different agents; objective goods and chores have the same sign for every agent.
- 2 Preliminary: WEF requires every agent’s entitlement-normalized bundle value to be at least that of every other agent.
- 2 Preliminary: WEF1 resolves weighted envy by removing one positively valued item from the envied bundle or one negatively valued item from the envying bundle.
- 2 Preliminary: WEF1T instead permits transferring one item, adding it to the envying bundle while removing it from the other bundle, or the reverse for a chore.
- 2 Preliminary: PO excludes Pareto improvements among integral allocations, whereas fPO excludes improvements by fractional allocations and is stronger.
3 The Computation of WEF1 Allocations
The algorithm first bundles positive items with absorbable chores into carefully structured meta-goods, then uses weighted picking sequences to allocate meta-goods and residual chores while preserving WEF1. It computes a WEF1 allocation for every mixed-manna instance in O(nm^2 log m) time.
- Algorithm Overview: The framework has two phases: meta-good bundling with residual chores, followed by adapted weighted picking sequences for their allocation.Meta-goods are allocated completely, while residual chores remain outside the bundles or are grouped during allocation.
- Meta-Good Construction: The strengthened meta-good construction starts with positive singletons and repeatedly absorbs strictly negative items, leaving residual chores with strong negative value.The modification addresses a counterexample in an earlier construction whose merged bundle failed the required structural condition.
- Meta-Good Construction: The construction initializes positive items as singleton meta-goods, computes compensation prefixes for chores, and merges each feasible chore with a minimizing prefix until no chore can be absorbed.The prefix length is the shortest number of nonnegative meta-goods needed to compensate for a chore’s disutility.
- Meta-Good Construction: Each resulting meta-good satisfies the required meta-good property, and every residual chore remains negative even when combined with any subset of meta-goods.These structural guarantees support lifting a meta-level fairness guarantee back to original items.
- Allocating the Reduced Instance: Forward weighted picking allocates meta-goods, while reversed weighted picking allocates grouped residual-chore objects; unbundling then yields a WEF1 allocation of original items.The forward procedure also ensures every agent receives nonnegative utility when allocating the meta-goods.
- Allocating the Reduced Instance: The algorithm computes a WEF1 allocation for any mixed-manna instance in O(nm^2 log m) time.Its joint allocation phase runs in O(nm^2), while the complete construction achieves the stated overall bound.
4 The Existence of WEF1T and fPO Allocations
The paper establishes that WEF1T and fPO are simultaneously attainable for every mixed-manna instance, while showing that weaker-than-WEF1T guarantees cannot generally coexist with fPO. The proof reduces instances, augments them with auxiliary items, and uses perturbed weighted-welfare maximization with a KKM argument.
- For x + y < 2, WEF(x, y) and fPO may be incompatible, making one-transfer relaxation necessary.
- WEF1T and fPO exist simultaneously for every mixed-manna instance.
- Reduction and augmentation: The proof first removes zero-maximum-valued items and modifies valuations so remaining items are objective goods or objective chores.
- Reduction and augmentation: The reduced instance is augmented with privately valued items and zero-valued dummies, preserving WEF1T and fPO when auxiliary items are discarded.
- Simplex selection via KKM: A small perturbation of weighted social welfare selects allocations through a KKM simplex-covering argument, with tie-breaking and limiting steps yielding WEF1T and fPO.
5 Best-of-both-worlds Guarantee for Weighted Envy-freeness
The section constructs a finite lottery that is ex-ante WEF and ex-post WEF1T for every mixed-manna instance, combining goods and residual-chore decompositions while preserving entitlement-weighted marginals.
- Motivation: The goods-only impossibility for ex-ante WEF and ex-post WEF(x, y) when x+y<2 motivates targeting ex-post WEF1T.Because goods-only instances are mixed-manna special cases, the incompatibility extends to mixed manna.
- Definitions: A finite lottery is a probability distribution over allocations, and ex-post WEF1T requires every allocation in its support to satisfy WEF1T.Ex-ante WEF concerns the lottery’s expected comparisons.
- Main guarantee: Theorem 5.2 guarantees a lottery that is ex-ante WEF and ex-post WEF1T for any mixed manna instance.The construction combines meta-good allocations with residual-chore allocations.
- Combining components: The construction preserves ex-ante WEF by maintaining entitlement-proportional marginals while ensuring every realized allocation satisfies WEF1T.The proof checks comparisons for positive, nonpositive, and residual-chore components before restoring original values.
- Residual chores: Residual chores use a DSE-based chores lottery whose fractional allocation is WEF and whose integral decompositions control which agents receive an extra chore.The decomposition supplies probability bounds and per-agent structural conditions used in the WEF1T verification.
- Finite support: Carathéodory compression reduces the lottery support to at most m(n−1)+1 allocations without changing itemwise marginals or losing WEF1T.The expected incidence vector lies in an affine space of dimension at most m(n−1).
6 Conclusion and Open Problem
The conclusion summarizes existence and compatibility results for fairness, efficiency, and lotteries, while leaving the simultaneous WEF1-and-PO question open.
- Conclusion: WEF1 allocations exist for additive mixed manna with arbitrary positive entitlements and are computable in polynomial time.The paper also establishes a finite lottery that is ex-ante WEF and ex-post WEF1T.
- Fairness and efficiency: Every mixed-manna instance admits an allocation satisfying both WEF1T and fractional Pareto optimality.This relaxes WEF1 while retaining the stronger efficiency requirement fPO.
- Open problem: The existence of allocations that are simultaneously WEF1 and PO remains open, even for equal entitlements.The fPO impossibility result does not resolve this weaker efficiency combination.
Declaration of the Use of AI Tools
The authors disclose that OpenAI’s GPT-5.6 Sol assisted with exploring and structuring proof constructions, while responsibility remains with the authors.
- Declaration: OpenAI’s GPT-5.6 Sol was used as a research assistant for exploring and structuring the proof constructions.The authors state that they remain fully responsible for the paper’s content, correctness, and integrity.
A Missing Proofs in Section 3.2
The section develops the meta-good allocation argument by comparing weighted picking sequences, unpacking meta-goods, and preserving WEF1 under original-item witnesses.
- Construction: The construction allocates positive-part values of G+ using Algorithm 2, ensuring every assigned meta-good is strictly positive to its owner.This positivity holds under both truncated and original valuations.
- Weighted comparison: The proof compares agents’ assigned meta-goods through interval representations and chronological orderings of items positive to the observer.The argument handles the cases ℓ=0, ℓ=1, and ℓ≥2 separately.
- Integral argument: Horizontal-length and height arguments establish the integral comparison used to derive the weighted fairness inequality.The finitely many interval endpoints do not affect the integrals.
- Unpacking: The meta-level comparison transfers back to original valuations because own values remain unchanged while target values can only decrease.This monotonicity is the bridge from truncated values to the original instance.
- One-item witness: A single original item g can witness WEF1 after unpacking a meta-good z1, because vi(g)>0 and the remainder has nonpositive value to i.Deleting g preserves the required comparison in the original allocation.
- Zero-valued meta-goods: Meta-goods that are nonpositive to everyone are assigned to a zero-valuer, preserving all existing comparisons.This completes the allocation of G0 after the positive meta-goods have been handled.
B Proof of Lemma 4.2
The proof constructs a three-agent mixed-manna instance and characterizes all fPO allocations, then shows each violates WEF(x, y) whenever x + y < 2.
- The construction uses three equally entitled agents, six items, and parameters x, y ∈ [0, 1] with x + y < 2 − 1/r for an integer r ≥ 2.The first three items are goods and the last three are chores.
- An allocation is fPO exactly when some positive entitlement multipliers make each item’s owner maximize λ_i v_i(e).The proof normalizes λ1 = 1, writes a = λ2/λ1 and b = λ3/λ1, and checks all 36 owner words.
- The multiplier characterization yields precisely 43 feasible owner words, grouped with an ordered agent pair for the WEF violation argument.Conversely, every listed word satisfies the score inequalities for some a, b > 0 and is fPO.
- For each listed fPO allocation, the proof defines the envy gap ∆ = T − U and certifies ∆ ≥ (2 − 1/r)hij(X).The certificate is obtained by direct addition across seven groups.
- Because any eligible good or chore transfer reduces the gap by at most (x + y)hij(X), no WEF(x, y) alternative applies when x + y < 2 − 1/r.Thus every fPO allocation fails WEF(x, y), proving the lemma.