Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateApproximating \problem\ within an additive term of $3\cdot 10^{-4} \sumv{v}$ is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite item types \(G\), valuation types \(\Theta\), rational masses \(\mu\) with \(\sum_{\theta}\mu_\theta=1\), rational per-capita supplies \(\beta_g\), and additive valuations \(v_\theta\), compute nonnegative masses \(\lambda_{\theta,B}\) for integral bundles \(B\subseteq G\) satisfying \(\sum_B\lambda_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:g\in B}\lambda_{\theta,B}=\beta_g\), together with subsidies \(p_{\theta,B}\ge0\) satisfying \(v_\theta(B)+p_{\theta,B}\ge v_{\theta'}(B')+p_{\theta',B'}\) for all occupied pairs, minimizing \(\chi_\infty=\sum_{\theta,B}\lambda_{\theta,B}p_{\theta,B}\); in particular, determine whether one can distinguish \(\chi_\infty\le a\) from \(\chi_\infty\ge a+3\cdot10^{-4}V\), where \(V=\sum_\theta\mu_\theta v_\theta(G)\).
Let \(G\) contain \(m\geq1\) item types. A society is given by its support: the list \(\Theta\) of \(\tau\) valuation types with positive masses \(\mu_\theta\), each a binary rational, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has nonnegative rational additive valuations \(v_\theta\). Supplies \(\beta_g\in[0,1]\) and a threshold \(a\geq0\) are binary rationals; \(L\) is the total input bit length. Assume \(V:=\sum_\theta\mu_\theta v_\theta(G)>0\).
An individual receives an integral bundle \(B\subseteq G\), possibly empty, containing at most one item of each type. Choose real masses \(\lambda_{\theta,B}\geq0\) satisfying \(\sum_{B\subseteq G}\lambda_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:g\in B}\lambda_{\theta,B}=\beta_g\) for every \(g\in G\).
Each occupied pair \((\theta,B)\), meaning \(\lambda_{\theta,B}>0\), receives a real subsidy \(p_{\theta,B}\geq0\). Require \(v_\theta(B)+p_{\theta,B}\geq v_\theta(B')+p_{\theta',B'}\) for every ordered pair of occupied pairs, including pairs of the same valuation type; indifference is allowed.
Let \(\chi_\infty\) be the minimum of \(\sum_{\theta,B}\lambda_{\theta,B}p_{\theta,B}\) over these allocations and subsidies.
Can the promised cases \(\chi_\infty\leq a\) and \(\chi_\infty\geq a+3\cdot10^{-4}V\) be distinguished in time polynomial in \(m,\tau,L\), or is this promise problem NP-hard?
For finitely many agents receiving a partition of indivisible goods, minimizing total nonnegative subsidies is NP-hard to approximate within additive error \(3\cdot10^{-4}\sum_i v_i(G)\). [Source](https://cs.au.dk/~iannis/publ/C105-wine21.pdf)
For the different model of interim envy-free lotteries over matchings, polynomial-time algorithms attain optimal expected subsidy while allowing arbitrarily small violations of interim envy-freeness and payments depending on the agent and realized allocation. [Source](https://cs.au.dk/~iannis/publ/C103-ec21.pdf)
No result settling this exact mass formulation was located.
The promise problem is \(\mathrm{NP}\text{-hard}\). In fact, it is \(\mathrm{NP}\text{-hard}\) to distinguish \(\chi_\infty=0\) from \(\chi_\infty>V/2\), even when all masses and supplies are dyadic rationals and \(a=0\).
The proof below is a direct reduction for the stated mass formulation.
We reduce from proper graph \(4\)-colorability. This is \(\mathrm{NP}\text{-hard}\): adding a new vertex adjacent to every original vertex transforms graph \(3\)-colorability into graph \(4\)-colorability. Indeed, the new vertex’s color is unavailable to all original vertices, and any proper \(3\)-coloring extends by assigning the new vertex a fourth color. We use the classical \(\mathrm{NP}\)-completeness of graph \(3\)-colorability. [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1)
First observe that, in any feasible allocation, all occupied bundles of a given type \(\theta\) give the same utility. Applying envy-freeness in both directions between two such bundles gives equality. Denote this common utility by \(U_\theta\). Thus every occupied pair satisfies
\(p_{\theta,B}=U_\theta-v_\theta(B)\),
and every type \(\theta\) and occupied pair \((\eta,B)\) satisfy
\(U_\theta\geq v_\theta(B)+p_{\eta,B}\).
These facts hold regardless of how a type’s mass is split.
Let \(F=(X,E)\) be a simple undirected graph, with \(n=|X|\geq1\). Use four colors, indexed by \(\{1,2,3,4\}\).
Introduce the following item types:
There are \(C:=n+4|E|\) auxiliary types:
Also introduce a zero-valued type \(z\), an anchor type \(h\), and a selector type \(s\). Their valuations and masses are:
| Type | Items with positive value | Mass |
|---|---|---|
| \(z\) | None | \(\mu_z\) |
| \(h\) | \(v_h(A)=1\) | \(\varepsilon\) |
| \(s\) | \(v_s(A)=n\); \(v_s(g_{x,c})=1\) for all \(x,c\) | \(\varepsilon\) |
| \(t_x\) | Its marker and the four items \(g_{x,c}\), each valued \(1\) | \(d\) |
| \(t_{e,c}\), where \(e=\{x,y\}\) | Its marker, \(g_{x,c}\), and \(g_{y,c}\), each valued \(1\) | \(d\) |
All unlisted item values are zero, and valuations are additive.
Let \(Q\) be the smallest power of two at least \(C\), and let \(R\) be the smallest power of two at least \(n+1\). Set
\(d=\dfrac{1}{4Q},\qquad \varepsilon=\dfrac{1}{64QR},\qquad \mu_z=1-Cd-2\varepsilon.\)
Set supplies
\(\beta_{g_{x,c}}=\varepsilon/4,\qquad \beta_A=\varepsilon,\qquad \beta_{b_t}=d,\)
and set \(a=0\).
All masses are positive and sum to one. In particular,
\(\mu_z\geq \dfrac34-\dfrac1{32}=\dfrac{23}{32}.\)
All masses and supplies are dyadic rationals.
Suppose \(f:X\to\{1,2,3,4\}\) is a proper coloring.
Give type \(z\) the empty bundle, type \(h\) the bundle \(\{A\}\), and every auxiliary type its own marker. For the selector, take the four cyclic permutations of the colors of \(f\). Each permutation defines a bundle containing exactly one color item per vertex. Give each of these four bundles selector mass \(\varepsilon/4\).
Every color item appears in exactly one of the four selector bundles. Consequently, all supply and type-mass constraints hold exactly.
Set every subsidy to zero. Envy-freeness follows as follows:
Thus every ordered envy inequality holds, including comparisons within a type. Nonnegativity of subsidies now gives
\(\chi_\infty=0.\)
Consider any feasible allocation. Since type \(z\) has zero valuations, the observation in Section 1 shows that all its occupied pairs receive the same subsidy. Write this subsidy as \(c:=U_z\).
Envy-freeness from type \(z\) to every occupied pair gives
\(p_{\theta,B}\leq c.\)
We prove that \(c<1\) implies that \(F\) has a proper \(4\)-coloring.
Since \(\beta_A=\varepsilon>0\), some occupied bundle contains \(A\). Comparing type \(h\) with that pair gives \(U_h\geq1\), because its subsidy is nonnegative.
An occupied anchor bundle lacking \(A\) would have value zero and therefore require subsidy \(U_h\geq1\). This contradicts the bound \(p_{\theta,B}\leq c<1\).
Hence every anchor individual receives \(A\). Anchor mass and supply are both \(\varepsilon\), so no other type receives \(A\).
Comparing type \(s\) with an occupied anchor pair gives
\(U_s\geq n+p_{h,B}\geq n.\)
A selector bundle cannot contain \(A\), and its value is therefore its integer number of color items. For every occupied selector bundle \(B\),
\(v_s(B)=U_s-p_{s,B}\geq n-c>n-1.\)
Thus every occupied selector bundle contains at least \(n\) color items.
Fix an auxiliary type \(t\), and let \(S_t\) be its positively valued color items. For a vertex type, \(|S_t|=4\); for an edge-color type, \(|S_t|=2\).
The total population mass receiving at least one item from \(S_t\) is bounded by the sum of their supplies:
\(\displaystyle \sum_{\theta,B:\,B\cap S_t\neq\varnothing}\lambda_{\theta,B} \leq \sum_{g\in S_t}\beta_g \leq\varepsilon. \)
Since
\(\varepsilon<d=\mu_t,\)
some positive mass of type \(t\) receives bundles containing no item of \(S_t\). Choose one such occupied pair. Its bundle has value at most \(1\), since its only remaining positively valued item is its private marker. Therefore
\(U_t\leq1+c<2.\)
For any occupied pair \((\theta,B)\), envy-freeness and nonnegative subsidies give
\(v_t(B)\leq v_t(B)+p_{\theta,B}\leq U_t<2.\)
Consequently, no occupied bundle contains two items from \(S_t\).
Applying this to all auxiliary types establishes:
Every occupied selector bundle contains at least \(n\) color items by Section 4.2, and at most one per vertex. It therefore contains exactly one per vertex. The edge-color restrictions make these choices a proper \(4\)-coloring.
The selector has positive mass, so such an occupied bundle exists. This proves the implication.
If \(F\) is not \(4\)-colorable, every feasible allocation must therefore have \(c\geq1\). Its total subsidy is at least the subsidy paid to type \(z\):
\(\displaystyle \sum_{\theta,B}\lambda_{\theta,B}p_{\theta,B} \geq\mu_zc \geq\mu_z. \)
Thus
\(\chi_\infty\geq\mu_z.\)
This argument allows arbitrary real mass splitting and arbitrarily small positive occupied masses.
For every graph, a feasible allocation exists with total subsidy below \(1\).
Use the anchor, marker, and empty bundles from Section 3. Give the selector four bundles \(B_c:=\{g_{x,c}:x\in X\}\), each with mass \(\varepsilon/4\). Give subsidy \(1\) to type \(z\) and every auxiliary type, and subsidy zero to the anchor and selector.
The supplies hold exactly. The zero type’s utility is \(1\), and all subsidies are at most \(1\). The anchor’s utility is \(1\), which dominates every other bundle-payment pair under its valuation. The selector’s utility is \(n\); it values the anchor bundle at \(n\), other selector bundles at \(n\), and all remaining bundle-payment pairs at most \(1\).
Each auxiliary type’s utility is \(2\). It values a selector bundle at most \(2\), its own marker with subsidy at \(2\), and every other occupied pair at most \(1\). Hence all envy inequalities hold. Total subsidy is
\(\mu_z+Cd=1-2\varepsilon<1.\)
The minimum is also attained. For any feasible solution of cost at most \(1\), the zero-type argument bounds every occupied subsidy by
\(c\leq1/\mu_z\leq32/23<2.\)
Set unoccupied subsidies to zero. We may therefore restrict all subsidies to \([0,2]\) and all masses to \([0,1]\). In this finite-dimensional compact box, the supply constraints, cost bound, and conditional envy constraints define a closed set. For the latter assertion, if two pairs have positive mass at a limit point, both have positive mass eventually along any convergent sequence, so their envy inequality passes to the limit.
The feasible set in this box is nonempty, and the objective is continuous. It attains a minimum there. Since the exhibited allocation costs less than \(1\), this is also the unrestricted minimum.
The normalization is exactly
\(V=d(5n+12|E|)+\varepsilon(5n+1).\)
Here each vertex type has total value \(5\), each edge-color type has total value \(3\), the selector has total value \(5n\), and the anchor has total value \(1\).
Using \(C=n+4|E|\), \(C\leq Q\), and \(n+1\leq R\),
\(d(5n+12|E|)\leq5Cd\leq5/4,\)
and
\(\varepsilon(5n+1)\leq\dfrac{5R}{64QR}\leq5/64.\)
Therefore \(0<V\leq85/64\), while
\(\mu_z\geq23/32=46/64>85/128\geq V/2.\)
The reduction consequently has the following guarantees:
Finally, \(m=4n+C+1\) and \(\tau=C+3\). All valuation entries belong to \(\{0,1,n\}\). Since \(Q<2C\) and \(R<2(n+1)\), every numerical parameter has polynomial encoding length. Thus the construction is a polynomial-time reduction whose outputs always satisfy the required promise.
A polynomial-time distinguisher for the stated promise problem would decide graph \(4\)-colorability. This establishes the claimed \(\mathrm{NP}\text{-hardness}\).
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the stated promise problem. The reduction is correct for the exact mass formulation, including arbitrary real mass splitting and envy comparisons between occupied pairs of the same type. I found no major or minor mathematical issues.
The cited source supports the NP-completeness of graph \(3\)-colorability. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
The reduction to graph \(4\)-colorability is correct: a new universal vertex consumes one color, leaving at most three colors available to the original graph. Conversely, any proper \(3\)-coloring extends to a proper \(4\)-coloring by giving the new vertex the fourth color. The resulting graph is simple and nonempty, as required by the construction.
For two occupied pairs of the same valuation type, the two ordered envy inequalities imply equality of their utilities. Thus \(U_\theta\) is well-defined, and
\(p_{\theta,B}=U_\theta-v_\theta(B)\)
holds for every occupied pair.
Every type has positive mass and hence at least one occupied pair. Consequently, comparing its common utility with every occupied pair of another type is justified. The argument never imposes envy constraints on unoccupied pairs.
Since \(n\geq1\), \(C=n+4|E|\geq1\), so both powers of two \(Q\) and \(R\) are well-defined. The parameters \(d\) and \(\varepsilon\) are positive dyadic rationals.
The displayed lower bound on the zero-type mass is valid: \(Cd\leq1/4\) and \(2\varepsilon\leq1/32\), giving \(\mu_z\geq23/32>0\). All type masses therefore are positive and sum to one.
Every supply belongs to \([0,1]\). All valuations are nonnegative additive rational valuations, and \(a=0\) is allowed. The normalization \(V\) is positive because at least one vertex auxiliary type has positive mass and positive total valuation.
The four cyclic color permutations preserve properness. For each vertex, its assigned color ranges over all four colors exactly once, so every color item receives total mass \(\varepsilon/4\). The anchor and private-marker supplies also match their assigned masses exactly.
With zero subsidies, all envy comparisons hold:
Comparisons within each type also hold because its occupied bundles give equal utility. Nonnegative subsidies then establish \(\chi_\infty=0\).
Since the zero type has identically zero valuation, every occupied pair of that type receives the same subsidy \(c=U_z\). Its envy inequality toward any occupied pair gives \(p_{\theta,B}\leq c\).
This bound applies regardless of the pair’s positive mass, so the soundness argument remains valid for arbitrarily small occupied masses.
Positive supply of \(A\) guarantees an occupied bundle containing \(A\). Comparing the anchor with that pair yields \(U_h\geq1\).
Under \(c<1\), an occupied anchor bundle without \(A\) would require subsidy at least \(1\), contradicting the uniform bound. Thus the entire anchor mass \(\varepsilon\) receives \(A\). Because its supply is exactly \(\varepsilon\), no occupied pair of another type can contain \(A\).
The selector therefore values its own occupied bundles solely by their integer number of color items. Comparing with an occupied anchor pair gives \(U_s\geq n\), and hence
\(v_s(B)\geq n-c>n-1\).
Integrality correctly implies at least \(n\) color items in every occupied selector bundle.
For each auxiliary type, the mass receiving any item in \(S_t\) is at most the sum of those items’ supplies. This is a valid union bound even when one bundle contains several such items.
The bound is at most \(\varepsilon\), whereas the auxiliary type has mass \(d>\varepsilon\). Therefore some occupied pair of that type contains no item of \(S_t\). Its own valuation is at most \(1\), because only its private marker can contribute. Consequently, \(U_t\leq1+c<2\).
Envy-freeness and nonnegative subsidies then imply \(v_t(B)<2\) for every occupied bundle. Any bundle containing two items of \(S_t\) would have valuation at least \(2\), so it is forbidden.
The vertex auxiliaries enforce at most one color item per vertex. Together with the selector’s lower bound of \(n\) color items, this gives exactly one per vertex. The edge-color auxiliaries prohibit equal colors at adjacent vertices. Positive selector mass guarantees that at least one such occupied bundle exists.
Thus the written implication \(c<1\) implies proper \(4\)-colorability is established.
For a noncolorable graph, the preceding implication forces \(c\geq1\) in every feasible allocation. The zero type alone then contributes at least \(\mu_zc\geq\mu_z\) to total subsidy.
This proves the lower bound for every feasible solution, rather than merely for a selected allocation or a restricted form of mass splitting.
The graph-independent allocation in Section 5 satisfies all supplies. Its subsidy assignments also satisfy every envy inequality:
Its cost is exactly \(\mu_z+Cd=1-2\varepsilon<1\).
For any feasible solution of cost at most \(1\), \(\mu_zc\leq1\), so every occupied subsidy is bounded by \(1/\mu_z\leq32/23<2\). Unoccupied subsidies can be set to zero without affecting feasibility or cost.
The compactness argument is correct. There are finitely many type-bundle pairs for each constructed instance. The mass equalities, nonnegativity conditions, subsidy bounds, and cost bound define closed constraints. Conditional envy constraints are also closed: whenever both limiting masses are positive, both corresponding masses are eventually positive, so the inequality passes to the limit.
The bounded feasible set is nonempty, and the objective is continuous. Its minimum exists. Since an exhibited solution costs less than \(1\), solutions outside this cost restriction cannot improve that minimum. Thus the use of a minimum in the target definition is justified on the reduction’s instances.
The normalization is calculated correctly:
\(V=d(5n+12|E|)+\varepsilon(5n+1)\).
Vertex auxiliaries contribute total valuation \(5\) each, edge-color auxiliaries contribute \(3\) each, the selector contributes \(5n\), and the anchor contributes \(1\).
The bounds \(5n+12|E|\leq5C\) and \(5n+1\leq5R\) give \(V\leq85/64\). Therefore
\(\mu_z\geq46/64>85/128\geq V/2\).
Since \(V>0\), this implies the required strict separation from \(3\cdot10^{-4}V\).
The counts \(m=4n+C+1\) and \(\tau=C+3\) are correct. The powers of two have polynomial bit length, and the full valuation table has polynomially many entries, each in \(\{0,1,n\}\). The reduction is therefore polynomial in the source input size and produces valid promised instances in both cases.
No repair or additional clarification is needed. The output establishes NP-hardness, without asserting membership in NP or unconditional exclusion of a polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.