Given a finite set of indivisible items M, agents N=1,…,n with positive entitlements w_i>0, and additive valuations v_i:2^M→R, does there always exist a complete allocation (A_1,…,A_n) of M such that, for every pair of agents i,j, there is an item o∈ A_i cup A_j satisfying fracv_i(A_i setminuso)w_i≥fracv_i(A_j setminuso)w_j, where removing o affects only the bundle to which it belongs? Moreover, does such a complete weighted-envy-free-up-to-one-item allocation always admit a polynomial-time construction?

Existence of weighted envy-freeness up to one item (WEF1)

Given a finite set of indivisible items $M$ , agents $N=\{1,\ldots,n\}$ with positive entitlements $w_i>0$ , and additive valuations $v_i:2^M\to\mathbb{R}$ , does there always exist a complete allocation $(A_1,\ldots,A_n)$ of $M$ such that, for every pair of agents $i,j$ , there is an item $o\in A_i\cup A_j$ satisfying $\frac{v_i(A_i\setminus\{o\})}{w_i}\geq\frac{v_i(A_j\setminus\{o\})}{w_j}$ , where removing $o$ affects only the bundle to which it belongs? Moreover, does such a complete weighted-envy-free-up-to-one-item allocation always admit a polynomial-time construction?

References

Primary source

arXiv

Additional references

Weighted Fair Division of Indivisible Mixed Manna — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new unrefereed paper claims to settle the existence and efficient construction of fair allocations for arbitrary positive entitlements when goods and chores are combined.

The problem asks whether complete weighted envy-freeness up to one item, denoted $\mathrm{WEF1}$ , always exists for mixed indivisible goods and chores with arbitrary positive entitlements.

Known results

For additive valuations with goods, arbitrary positive weights, and any number of agents, complete $\mathrm{WEF1}$ allocations exist and are computable in polynomial time (Chakraborty et al., 2019/2020).
A separate result establishes existence and polynomial-time computation for indivisible chores using a weighted picking sequence.
For arbitrary monotone valuations, $\mathrm{WEF1}$ need not exist (Chakraborty et al.).

September 2026 mixed-manna claim

A September 1, 2026 report links the preprint Weighted Fair Division of Indivisible Mixed Manna, which claims general existence and polynomial-time computability of complete $\mathrm{WEF1}$ allocations for arbitrary positive entitlements in the combined goods-and-chores setting. The claim is unverified.

Current status (as of September 2026): Separate goods and chores cases have established results, while the mixed-manna claim of general existence and polynomial-time computation is reported but remains unverified.

Sources

No solutions have been posted yet.