Multivariate Algorithmics for Eliminating Envy by Donating Goods

The strongest honest case is a high-multiplicity mirror of the paper’s deletion problem for a large benefits or housing system. The original household/divorce story need not scale, but the mathematical problem does: imagine a large employer giving thousands of employees standardized bundles of indivisible benefits, where benefits may be withdrawn but not reassigned.

The right type is not merely a preference vector. Let \(G\) be a finite catalogue of good types. An agent type \(t\) consists of an additive utility vector \(u_t\in\mathbb Z_{\ge 0}^{G}\) and an initial bundle \(b_t\in\mathbb Z_{\ge0}^{G}\). Thus it records everything relevant: what the agent values and which goods it initially holds. The society is a rational distribution \(\mu\) over these types, with \(\sum_t\mu_t=1\). A unit of population mass is still an agent; goods inside that agent’s bundle remain indivisible.

A donation plan is a collection of masses \(x_{t,b}\ge0\), where \(b\preceq b_t\) is an integral residual bundle and \(\sum_{b\preceq b_t}x_{t,b}=\mu_t\). Thus \(x_{t,b}\) is the fraction of type-\(t\) agents whose remaining bundle is \(b\). This is mass transfer between agent states, not fractional ownership of an individual good. Define donated mass by \(D(x)=\sum_{t,b}x_{t,b}\lVert b_t-b\rVert_1\), retained-good mass by \(K(x)=\sum_{t,b}x_{t,b}\lVert b\rVert_1\), and welfare by \(W(x)=\sum_{t,b}x_{t,b}(u_t\cdot b)\).

The continuous fairness condition is that every supported agent state is envy-free with respect to every other supported state: whenever \(x_{t,b}>0\) and \(x_{t',b'}>0\), \(u_t\cdot b\ge u_t\cdot b'\). The decision problem asks whether there is such an \(x\) satisfying a donation bound \(D(x)\le D_0\), a retained-mass floor \(K(x)\ge K_0\), and, in the welfare version, \(W(x)\ge W_0\). This is a precise population-continuous version of EF-DG: only the population is continuized, while bundles, goods, and individual utilities remain discrete.

The regime is plausible. There may be only two or a few standardized employee types, so \(\tau\) is small, while the number of employees is enormous. Each type can have many copies of the same indivisible benefit bundle. A finite instance embeds by taking \(\mu_t=n_t/n\); conversely, a large repeated society is the high-multiplicity relaxation in which the masses \(x_{t,b}\) need not be multiples of \(1/n\). Resource counts and welfare thresholds are normalized per capita, so a bound such as \(k_+=1\) becomes the corresponding retained-good mass after blowing up the original two-agent instance into many identical copies.

My lead anchor is Theorem 3.7. The paper proves here—not merely cites—that, for identical binary-encoded valuations, EF-DG\((\#)\) with \(k_+=1\) is NP-hard already for \(n=2\) agents; the same theorem also gives NP-hardness for EF-DG\((e)\) with \(\ell_+=1\) and W[1]-hardness parameterized by \(k_-\). The proof is based on Subset Sum, and the theorem is marked \(\star\), meaning that its proof is deferred to the authors’ full version rather than imported from prior work.

The continuous question I would attach to this anchor is:

\(\mathrm{Mass\text{-}EF\text{-}DG}_{\#}\). Given \(G\), a finite set of types \(T\), rational masses \(\mu_t\), integral initial bundles \(b_t\), additive utilities \(u_t\), and normalized bounds \(D_0,K_0\), does there exist a mass donation plan \(x_{t,b}\) satisfying the mass constraints, \(D(x)\le D_0\), \(K(x)\ge K_0\), and continuous EF?

This is recognisably the authors’ problem: the input contains an initial allocation, agents have additive utilities, the only intervention is deletion of goods, and the objective is to eliminate envy subject to resource-retention constraints. It has not been weakened into a different divisible-goods problem. The expected classification is probably Class B: the population limit may remove dependence on the number of named agents, but it does not remove the subset-selection problem over indivisible goods. The source of the hardness in Theorem 3.7 is already present with two agents, so it is not obviously population-multiplicity hardness that should dissolve.

That expectation needs a proof, because mass splitting could help. A cohort can divide among several residual bundles, and this convexification might defeat the particular Subset Sum gadget. The key question is whether EF forces all positive-mass residual bundles into a structure that still contains an integral subset-sum choice. If so, hardness transfers. If not, the continuous problem could become a configuration LP or a knapsack-type pricing problem. With a fixed good catalogue or bounded bundle size, I would expect tractable finite-configuration algorithms; with an unbounded catalogue, the residual-bundle space is exponential and the pricing problem may retain the paper’s combinatorics.

A useful second anchor is Theorem 4.3, also proved in this paper and marked \(\star\). It establishes that EF-DG\((\#)\) is NP-hard for \(0/1\)-valuations even when \(d=3\), \(w_a=4\), and \(w_r=3\). This is valuable because it shows that the hardness does not require large utilities, large bundles, or dense valuation data.

Its continuous counterpart would be \(\mathrm{Sparse\text{-}Mass\text{-}EF\text{-}DG}_{\#}\): the instance is the same mass model above, but every utility is \(0/1\), each agent initially holds at most three goods, each agent values at most four good types, and each good type is valued by at most three agent types. The question is whether a bounded mass of goods can be donated so that the resulting population is EF.

Here \(w_r\) must be translated to the compressed setting: with many copies of a type, a good may be valued by many individual agents, but by only a few valuation types. That is the natural high-multiplicity analogue. The scenario is a large institution with a small number of standardized sparse benefit contracts, where each benefit is relevant to only a few contract classes.

I expect this second problem also to be hard in its unrestricted type–good incidence structure, although less confidently than the lead problem. Theorem 4.3’s combinatorics lives in the incidence pattern between agents and goods, and that pattern can remain after every role is replicated into a large cohort. But continuous cohort splitting may fractionalize the covering structure, so a transfer proof is not automatic. This gives a genuine research question rather than a disguised restatement.

The scope is deliberately limited. These mirrors cover the EF-DG number variant and its sparse \(0/1\) hardness regime. They do not claim to continuize every EF1 result, every welfare-parameterized theorem, or the paper’s algorithms. The latter would require separate work on configuration representations, separation, and rounding.

The weakest point is that the paper’s most compelling hardness results are driven by the indivisible resource structure, not by the number of agents. If the real application has one-off heirlooms and only a handful of agents, there is no honest continuum. Even in the repeated-cohort setting, EF is support-sensitive and the residual-bundle configuration space can be exponential, so no immediate LP miracle follows. But that weakness does not invalidate the mirror: it identifies the precise boundary question. The paper has a credible high-multiplicity population regime, and the central computational issue is whether its discrete deletion hardness transfers, disappears through cohort mixing, or turns into a tractable configuration-optimization problem.