Answer: \(\mathrm{NP}\text{-hard}\); feasibility is \(\mathrm{NP}\text{-complete}\), even for \(\tau=1\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that [A2] holds. Let n = O m ln m . Then an EF allocation exists with probability 1 as m →∞. Before proving the theorem, two comments are in order.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite good categories \(G\), complete additive-valuation types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_g\), and rational values \(v_t(g)\), assign mass \(x_{t,b}\ge 0\) of each type \(t\) to integral bundles \(b\in\mathbb{N}^{G}\), using finitely many bundles. Require \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_g=q_g\), and \(v_t(b)\ge v_t(b')\) whenever \(x_{t,b}>0\) and \(x_{s,b'}>0\). Decide whether such an envy-free allocation exists and, if it does, compute one maximizing \(\sum_{t,b}x_{t,b}v_t(b)\).
Let \(G\) be a finite set of good categories, with \(m=|G|\). A society is given by its support: the list \(T\) of the \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a complete additive valuation specified by binary rationals \(v_t(g)\in[0,1]\). Supplies \(q_g\in\mathbb{Q}_{\ge0}\) are per capita, and \(L\) is the total input bit length. Inputs are arbitrary, without a random-generation promise.
Bundles are \(b\in\mathbb{Z}_{\ge0}^{G}\), including the empty bundle; multiple copies of a category are allowed. An allocation consists of nonnegative masses \(x_{t,b}\) with finitely many nonzero entries, satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\) for every category.
Envy-freeness requires \(v_t(b)\ge v_t(b')\) whenever \(x_{t,b}>0\) and \(x_{s,b'}>0\), including \(s=t\). Preferences are weak, ties are allowed, and every unit of supply must be allocated. Utilitarian welfare is \(\sum_{t,b}x_{t,b}v_t(b)\).
Is the problem of deciding feasibility and, when feasible, computing an envy-free allocation of maximum utilitarian welfare solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete agents with independent uniform \([0,1]\) item values, assigning each item to its highest valuer is polynomial-time and welfare-maximizing, and is envy-free with probability tending to \(1\) when \(M\ge Cn\ln M\) for a sufficiently large constant \(C\), where \(M\) counts individual items and \(n\) counts agents. [Discrete random-instance guarantee](https://ojs.aaai.org/index.php/AAAI/article/view/8884/8743).
For arbitrary discrete additive valuations, complete envy-free feasibility is \(\mathrm{NP}\)-complete. [Discrete complexity result](https://www.lamsade.dauphine.fr/~lang/papers/bouveret-lang08.pdf). No exact complexity classification for the stated support-encoded mass problem was located.
Feasibility is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when \(\tau=1\), the sole type has mass \(1\), every supply is \(1/2\), and every valuation is a strictly positive dyadic rational.
Consequently, deciding feasibility and then computing a welfare-maximizing envy-free allocation is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The reduction below explicitly allows repeated categories and fractional allocation masses.
For any envy-free allocation, all bundles assigned positive mass to a fixed type \(t\) have the same utility. Indeed, if \(x_{t,b}>0\) and \(x_{t,b'}>0\), the two directed envy comparisons give
\(v_t(b)\ge v_t(b')\) and \(v_t(b')\ge v_t(b)\).
Write this common utility as \(u_t\).
For one type of mass \(1\), exact supply allocation therefore gives
\(u=\sum_b x_bv(b)=\sum_g v(g)\sum_bx_bb_g=\sum_gv(g)q_g=v(q).\)
Thus every occupied bundle must individually have utility exactly \(v(q)\). Fractional mixing cannot relax this equality.
We use the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive integers \(s_1,\ldots,s_n\), encoded in binary, decide whether some subset has sum equal to half their total. See, for example, [Mertens, *Phase Transition in the Number Partitioning Problem*](https://arxiv.org/abs/cond-mat/9807077).
Let
\(S=\sum_{i=1}^n s_i,\qquad B=2nS+n+2,\qquad H=B^{n+1}.\)
These choices ensure
\(S<B,\qquad 2nS<B,\qquad n+1<B.\)
Create two categories \(g_i^0,g_i^1\) for each index \(i\), and define integer coefficients
\(a_i^0=H+B^i,\qquad a_i^1=H+B^i+2s_i.\)
Let \(D\) be the least power of two strictly greater than every coefficient \(a_i^\epsilon\). The allocation instance has one type of mass \(1\), with valuations and supplies
\(v(g_i^\epsilon)=a_i^\epsilon/D,\qquad q_{g_i^\epsilon}=1/2.\)
All valuations are strictly between \(0\) and \(1\) and are dyadic rationals.
Define
\(A=nH+\sum_{i=1}^n B^i+S.\)
The utility fixed by the supply vector is
\(v(q)=\frac{1}{2D}\sum_{i=1}^n(a_i^0+a_i^1)=A/D.\)
Hence every occupied bundle in an envy-free allocation must satisfy
\(\sum_{i=1}^n\bigl(a_i^0b_i^0+a_i^1b_i^1\bigr)=A.\) \(\qquad (1)\)
The binary length of \(B\) is \(O(\log n+\log S)\). Each coefficient, and the denominator \(D\), has binary length \(O(n\log B)\). There are \(2n\) categories.
Since the binary length of \(S\) is polynomial in the PARTITION input length, the entire construction has polynomial encoding length and can be computed in polynomial time.
We prove that every nonnegative integer bundle satisfying equation \((1)\) selects exactly one category from each pair and encodes a partition.
Let
\(r=\sum_{i=1}^n(b_i^0+b_i^1),\qquad c_i=b_i^0+b_i^1,\qquad w=2\sum_{i=1}^n s_i b_i^1.\)
Equation \((1)\) becomes
\(rH+\sum_{i=1}^n c_iB^i+w=nH+\sum_{i=1}^nB^i+S.\) \(\qquad (2)\)
First, put \(R=\sum_{i=1}^nB^i+S\). Its base-\(B\) digits are \(S\) in position zero and \(1\) in positions \(1,\ldots,n\). Since \(S<B\),
\(0\le R<B^{n+1}=H.\)
Every coefficient \(a_i^\epsilon\) is at least \(H\). Therefore equation \((1)\) implies
\(rH\le A=nH+R<(n+1)H,\)
so \(r\le n\).
Consequently,
\(0\le w\le 2nS<B\)
and
\(0\le\sum_{i=1}^n c_iB^i+w\le nB^n+w<nB^n+B\le(n+1)B^n<H.\)
Both lower-order terms in equation \((2)\) therefore lie between zero and \(H-1\). Uniqueness of quotient and remainder upon division by \(H\) gives
\(r=n,\qquad \sum_{i=1}^n c_iB^i+w=\sum_{i=1}^nB^i+S.\)
Now \(0\le c_i\le n<B\) and \(0\le w<B\), so the left-hand side is already a valid base-\(B\) expansion. Uniqueness of base-\(B\) representation yields
\(c_i=1\text{ for every }i,\qquad w=S.\)
Thus each pair contributes exactly one copy in total. In particular,
\(b_i^1\in\{0,1\},\qquad b_i^0=1-b_i^1,\qquad 2\sum_{i=1}^n s_i b_i^1=S.\)
The selected indices form an equal-sum partition. This proves the required exclusion of repeated-copy solutions.
Suppose the constructed instance has an envy-free allocation. Its masses sum to \(1\), so at least one bundle has positive mass.
By Section 1, this bundle satisfies equation \((1)\). Section 3 then extracts an equal-sum partition of the original integers.
Conversely, suppose \(I\subseteq\{1,\ldots,n\}\) satisfies
\(2\sum_{i\in I}s_i=S.\)
Define a bundle \(b\) by choosing \(g_i^1\) when \(i\in I\) and \(g_i^0\) otherwise. Define its complementary bundle \(\bar b\) by choosing the other category in every pair.
Their integer coefficient sums are
\(\sum_i(a_i^0b_i^0+a_i^1b_i^1)=nH+\sum_iB^i+2\sum_{i\in I}s_i=A\)
and
\(\sum_i(a_i^0\bar b_i^0+a_i^1\bar b_i^1)=nH+\sum_iB^i+2\sum_{i\notin I}s_i=A.\)
Assign mass \(1/2\) to each bundle.
Every category occurs in exactly one of these bundles, so its allocated supply is exactly \(1/2\). Both bundles have utility \(A/D\), so the allocation is envy-free.
We have proved the equivalence
\(\text{PARTITION instance is positive}\quad\Longleftrightarrow\quad\text{constructed allocation instance is feasible}.\)
This establishes \(\mathrm{NP}\)-hardness with \(\tau=1\).
We now address the possibility that feasible allocations initially use very large bundles or irrational masses.
Consider any envy-free allocation and its common type utilities \(u_t\). Additivity and exact supplies give
\(v_t(q)=\sum_{s,b}x_{s,b}v_t(b)\ge\sum_bx_{t,b}v_t(b)=\mu_tu_t,\)
where the inequality uses nonnegative valuations and masses. Since \(\mu_t>0\),
\(u_t\le v_t(q)/\mu_t.\)
Every occupied bundle \(b\), regardless of its recipient, also satisfies \(v_t(b)\le u_t\) by envy-freeness.
For any category \(g\) valued positively by some type, choose such a type \(t(g)\). Nonnegativity of the other valuation terms implies
\(b_gv_{t(g)}(g)\le v_{t(g)}(b)\le u_{t(g)}\le v_{t(g)}(q)/\mu_{t(g)}.\)
Thus every occupied bundle satisfies
\(b_g\le K_g:=\left\lfloor\frac{v_{t(g)}(q)}{\mu_{t(g)}v_{t(g)}(g)}\right\rfloor.\)
The integer \(K_g\) has binary length polynomial in the input length: it is obtained through sums, products, and quotients of the input rationals.
For a category valued zero by every type, its count affects neither envy nor welfare. We may replace its counts by a mixture of \(\lfloor q_g\rfloor\) and \(\lceil q_g\rceil\) with mean \(q_g\), independently across such categories and across occupied bundles. This produces a finite allocation preserving all type masses, supplies, utilities, and envy comparisons.
Hence these categories can be bounded by \(K_g=\lceil q_g\rceil\), also of polynomial binary length.
After those replacements, let \(J\) be the finite support of the allocation. Introduce one column for each occupied type-bundle pair \((t,b)\), consisting of:
The mass and supply equations form a linear system with \(d=\tau+m\) rows and nonnegative variables.
If its positive-support columns are linearly dependent, choose a nonzero dependence vector \(z\). Summing the type rows shows \(\sum_jz_j=0\), so \(z\) has both positive and negative entries. Moving the mass vector along \(z\) until one entry first becomes zero preserves the equations and nonnegativity and decreases the support.
Repeating gives a feasible solution with linearly independent columns, hence at most \(d\) occupied pairs. Deleting occupied pairs preserves envy-freeness.
Choose as many independent rows as remaining columns. The resulting square system has an invertible integer matrix and a rational right-hand side. Cramer’s rule shows that its unique masses are rational. After clearing the right-hand-side denominators, the determinant expansion bounds their numerator and denominator lengths polynomially in \(d\), the bundle encoding lengths, and the input length.
Therefore every feasible instance has a certificate with at most \(m+\tau\) occupied pairs, polynomial-length bundle coordinates, and polynomial-length rational masses. All mass equations, supply equations, and directed envy comparisons can be checked in polynomial time.
General feasibility is consequently in \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness proof.
In the one-type reduction, every complete allocation has welfare
\(\sum_bx_bv(b)=v(q)=A/D.\)
Thus every feasible envy-free allocation in the reduction is already welfare-maximizing. The feasibility requirement alone establishes hardness of the requested combined task.
For completeness, a welfare maximum does exist whenever a general instance is feasible. Section 5 gives a finite set of bounded bundles to which every allocation can be converted without changing welfare. For each subset of type-bundle pairs satisfying all directed envy comparisons, the mass and supply constraints define a closed, bounded polytope. There are finitely many such subsets, and their union contains exactly the envy-free allocations using the bounded bundles. A linear welfare function attains its maximum on this nonempty compact union.
Moreover, the support reduction in Section 5 preserves welfare: all retained bundles of a type have the same utility \(u_t\), and that type’s total mass remains \(\mu_t\). A maximum therefore admits a polynomial-size rational representation as well.
The conclusion concerns the arbitrary deterministic inputs in the question. It does not depend on the discrete random-instance guarantee.
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. The reduction establishes \(\mathrm{NP}\)-hardness under the stated allocation model, including repeated categories, fractional masses, ties, and exact supply allocation. The additional arguments establish membership of feasibility in \(\mathrm{NP}\) and attainment of maximum welfare. I found no major or minor mathematical issues requiring repair.
The two directed comparisons between any occupied bundles of the same type force equal utility. Positive type masses ensure that every type has an occupied bundle, so each \(u_t\) is defined.
For one type, finite support permits the stated interchange of sums. Exact supplies and total mass \(1\) then give \(u=v(q)\). Consequently, each occupied bundle individually has this utility. The argument correctly rules out using fractional mixing to compensate for unequal utilities.
The prover precisely states the binary-encoded positive-integer PARTITION decision problem. Its use as an \(\mathrm{NP}\)-complete source is valid; the cited paper identifies perfect-partition decision and its standard complexity classification. [Mertens, *Phase Transition in the Number Partitioning Problem*](https://arxiv.org/pdf/cond-mat/9807077)
The construction satisfies the input restrictions: one positive mass equal to \(1\), supplies equal to \(1/2\), and strictly positive dyadic valuations below \(1\). Choosing \(D\) strictly larger than every coefficient ensures the valuation bound.
The calculation
\[
v(q)=A/D
\]
is correct. Multiplication by \(D\) yields exactly equation \((1)\), with integer bundle coordinates.
The encoding argument correctly distinguishes coefficient magnitudes from their binary lengths. The powers of \(B\) and the denominator \(D\) require only polynomially many bits and can be computed in polynomial time.
All bounds in Section 3 are valid for a nonempty PARTITION instance.
The remainder \(R\) satisfies \(0\le R<H\): its proposed base-\(B\) digits are valid because \(S<B\). Since every coefficient is at least \(H\), equation \((1)\) gives \(r\le n\).
This bound justifies both \(w\le 2nS<B\) and \(c_i\le n<B\). The critical estimate
\[
\sum_i c_iB^i+w\le nB^n+w<nB^n+B\le(n+1)B^n<H
\]
is correct. In particular, \(B\le B^n\) and \(n+1<B\); these also hold when \(n=1\).
Quotient-and-remainder uniqueness therefore gives \(r=n\). The subsequent base-\(B\) comparison has no hidden carries, because every displayed digit is below \(B\). It correctly forces \(c_i=1\) and \(w=S\).
Thus equation \((1)\) really does force one category from each pair and an equal-sum partition. Neither repeated copies nor fractional masses create spurious feasible instances.
A feasible allocation has at least one occupied bundle because its masses sum to \(1\). Sections 1 and 3 apply to that bundle and extract a partition.
Conversely, a partition and its complementary selection each have coefficient sum \(A\). Assigning mass \(1/2\) to each gives every category exactly its required supply and gives all occupied bundles equal utility. This satisfies every envy comparison in the one-type instance.
Odd totals cause no exception: the required equation \(2\sum_i s_i b_i^1=S\) cannot hold when \(S\) is odd. The reduction equivalence is therefore valid without a parity promise.
The general inequality
\[
v_t(q)\ge\mu_tu_t
\]
follows from exact allocation, nonnegative valuations, and nonnegative masses. Envy-freeness also bounds every occupied bundle’s value to type \(t\) by \(u_t\), regardless of its recipient.
For a category positively valued by some type, these inequalities justify the stated bound \(K_g\). Its binary length is polynomial: the rational sums, products, and quotients involve only polynomially many input-sized operands. A numerically large bound therefore does not invalidate certificate size.
For universally unvalued categories, the proposed finite splitting preserves utilities and envy comparisons. Using the same mean \(q_g\) for each original occupied bundle preserves supply because total allocation mass is \(1\). Independence across these categories preserves each marginal supply. This establishes the claimed coordinate bounds without requiring the intermediate support to be polynomially small.
The column construction correctly encodes every type-mass and supply equation in \(\tau+m\) rows.
A nonzero column dependence has coordinate sum zero by summing the type rows, so it contains both signs. Moving along it to the first zero mass preserves nonnegativity and the equations while reducing support. The process retains only previously occupied pairs, so it preserves envy-freeness.
Once the remaining columns are independent, selecting equally many independent rows gives an invertible integer square system. The existing feasible masses solve that system, whose unique solution is rational by Cramer’s rule. Polynomial entry lengths and polynomial matrix dimension give polynomial numerator and denominator lengths.
The resulting certificate has at most \(m+\tau\) occupied pairs. Exact rational mass equations, supply equations, and all directed envy comparisons are polynomial-time checkable. This establishes feasibility in \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness claim.
In the reduction, exact supplies fix welfare at \(v(q)\), independently of allocation. Hardness of deciding feasibility consequently establishes hardness of the requested combined task.
The general attainment argument is also valid. The coordinate bounds depend only on the input, giving finitely many candidate bundles. For any set of pairs satisfying all directed envy comparisons, the feasible masses form a closed, bounded polytope. Allowing zero masses creates no problem: the actual occupied pairs are a subset and remain envy-free.
The finite union of these polytopes is compact and represents all bounded envy-free allocations. The conversion to bounded bundles preserves welfare, so maximizing over this union suffices. The linear objective attains a maximum.
Finally, support reduction preserves each type’s common utility and total mass, hence preserves welfare. The rational-certificate argument therefore also applies to a maximum.
No additional mathematical clarification is needed. The classification concerns arbitrary support-encoded inputs and does not use the random-instance guarantee.
⟨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.