Answer: \(\mathrm{NP}\)-hard
Theorem 2 — class: hardness
Given rational masses \(\mu_M>0\) for an identical machine type and \(\mu_j\ge0\) for job types \(J_1,\ldots,J_r\), with processing values \(p_j>0\) and the paper’s machine/job additive valuations, partition the population so every machine unit receives an integral bundle \(k\in\mathbb{Z}_{\ge0}^r\) of job units and every job unit is assigned once; output a mass distribution \(\lambda\) over bundles satisfying \(\mathbb{E}_{\lambda}[k_j]=\mu_j/\mu_M\), maximizing \(\min\{B,\operatorname*{ess\,inf}_{k\sim\lambda}\sum_jp_jk_j\}\), where \(B\) is the fixed job-side utility.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. There is one machine type \(M\) with mass \(\mu_M>0\) and \(m\ge1\) job types \(J_j\) with masses \(\mu_j>0\), so \(\tau=m+1\). Masses are absolute quantities and need not sum to one.
Processing values \(p_j>0\) are binary rationals. Set \(B=\sum_{j=1}^m\mu_jp_j\). Additive valuations are \(v_M(J_j)=p_j\), \(v_{J_j}(M)=B\), zero between job units, and \(-(B+1)\) between distinct machine units.
Admissible coalitions contain exactly one machine unit and an integral bundle \(k\in\mathbb Z_{\ge0}^m\) of job units; empty bundles are allowed, and every job unit is assigned once. Aggregate masses may split among coalitions, but the job counts within each bundle remain integral.
A feasible allocation is a probability distribution \(\lambda\) on bundles with finite first moments satisfying \(\mathbb E_\lambda[k_j]=\mu_j/\mu_M\) for every \(j\). A machine receiving \(k\) has utility \(\sum_jp_jk_j\), and each assigned job has utility \(B\).
Compute an optimal allocation, represented by finitely many bundles and binary rational probabilities, maximizing \(W(\lambda)=\min\{B,\operatorname*{ess\,inf}_{k\sim\lambda}\sum_jp_jk_j\}\).
Is computing an allocation maximizing \(W(\lambda)\) solvable in polynomial time in \(m,\tau,L\), where \(L\) is the total input bit length, or is it NP-hard?
For finite societies, computing a maximum egalitarian partition is strongly NP-hard, including the machine/job construction above ([Aziz, Brandt, and Seedig](https://www.ijcai.org/Proceedings/11/Papers/019.pdf)).
The extended treatment retains this hardness result ([extended treatment](https://pub.dss.in.tum.de/brandt-research/ashg_journal.pdf)); no result settling the exact mass-distribution problem above was identified in the search.
Computing an exact optimal allocation is \(\mathrm{NP}\)-hard, even when \(\mu_M=1\), every job-type mass is \(1/2\), and every processing value is a positive integer. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
We prove this directly for the mass-distribution model by reduction from PARTITION.
For a bundle \(k\), write its load as \(X(k)=\sum_jp_jk_j\). The prescribed first moments imply
\( \mathbb E_\lambda[X]=\sum_jp_j\frac{\mu_j}{\mu_M}=\frac{B}{\mu_M}. \)
In particular, when \(\mu_M=1\), every feasible allocation has expected load \(B\).
Suppose such an allocation satisfies \(W(\lambda)=B\). Then \(X\ge B\) almost surely. Since \(X-B\) is nonnegative and has expectation zero, it equals zero almost surely. Thus
\( W(\lambda)=B\quad\Longleftrightarrow\quad X(k)=B\text{ for every bundle }k\text{ with }\lambda(k)>0. \)
This argument applies to distributions with infinite support: the assumed finite first moments make \(X\) integrable.
PARTITION takes positive integers \(a_1,\ldots,a_n\), encoded in binary, and asks whether some subset \(S\subseteq\{1,\ldots,n\}\) satisfies
\( 2\sum_{i\in S}a_i=\sum_{i=1}^n a_i. \)
This problem is \(\mathrm{NP}\)-complete; see the [Charles University complexity exercises](https://ktiml.mff.cuni.cz/~fink/teaching/computability_2017_18/tutorial_5.pdf).
Let
\( A=\sum_{i=1}^n a_i,\qquad q=n+1,\qquad Q=2nA+1, \)
\( D=Qq^{n-1}+2A,\qquad H=nD+1,\qquad G=\sum_{i=1}^nq^{i-1}. \)
Construct one machine type of mass \(\mu_M=1\). For each index \(i\), introduce two job types \(J_{i,0}\) and \(J_{i,1}\), both of mass \(1/2\), with processing values
\( p_{i,0}=H+Qq^{i-1},\qquad p_{i,1}=H+Qq^{i-1}+2a_i. \)
These processing values are positive integers. They are distinct: values within a pair differ by \(2a_i>0\), and the increase between consecutive radix terms exceeds \(2A\), because \(Q>2A\).
There are \(m=2n\) job types and \(\tau=2n+1\) supported types. The welfare cap specified by the task is
\( B=\frac12\sum_{i=1}^n(p_{i,0}+p_{i,1})=nH+QG+A. \)
Every processing value satisfies
\( H\le p_{i,b}\le H+D. \)
Moreover,
\( 0<QG+A\le nQq^{n-1}+A\le nD<H, \)
so
\( nH<B<(n+1)H. \)
The construction has polynomial bit length. In particular, \(q^{n-1}\) requires \(O(n\log(n+1))\) bits, and each processing value requires \(O(\log A+n\log(n+1))\) bits. All quantities can therefore be computed and written in polynomial time.
We prove that an integral bundle \(k=(k_{i,b})\) has load \(B\) if and only if it chooses exactly one job from each pair and its chosen \(J_{i,1}\) indices solve PARTITION.
Let
\( N=\sum_{i=1}^n(k_{i,0}+k_{i,1}) \)
be the total number of jobs in a bundle of load \(B\).
First, \(N=n\). Since each processing value is at least \(H\),
\( NH\le B<(n+1)H, \)
which gives \(N\le n\). If \(N\le n-1\), then
\( X(k)\le(n-1)(H+D)=nH-\bigl(H-(n-1)D\bigr)<nH<B, \)
contradicting \(X(k)=B\). Therefore \(N=n\).
Second, the selected input integers have half the total weight. Put \(c_i=k_{i,0}+k_{i,1}\). Subtracting \(nH\) from the load equation gives
\( Q\sum_{i=1}^nq^{i-1}c_i+2\sum_{i=1}^na_i k_{i,1}=QG+A. \)
Because \(N=n\),
\( 0\le 2\sum_{i=1}^na_i k_{i,1}\le 2nA<Q. \)
Also \(0<A<Q\). Reducing the displayed load equation modulo \(Q\), both residual terms lie between zero and \(Q-1\); hence
\( 2\sum_{i=1}^na_i k_{i,1}=A. \)
Third, exactly one job comes from each pair. Substituting the last equality back yields
\( \sum_{i=1}^nq^{i-1}c_i=\sum_{i=1}^nq^{i-1}. \)
Each \(c_i\) satisfies \(0\le c_i\le n=q-1\). These are therefore valid base-\(q\) digits. Uniqueness of the base-\(q\) expansion gives \(c_i=1\) for every \(i\). Explicitly, reduction modulo \(q\) gives \(c_1=1\); subtracting that digit and dividing by \(q\) repeats the argument for the remaining digits.
Thus each pair contributes either \(J_{i,0}\) or \(J_{i,1}\), and
\( S=\{i:k_{i,1}=1\} \)
satisfies \(2\sum_{i\in S}a_i=A\).
Conversely, if \(S\) satisfies that equality, the bundle defined by
\( k_{i,1}=\mathbf 1_{\{i\in S\}},\qquad k_{i,0}=1-k_{i,1} \)
has load
\( X(k)=nH+QG+2\sum_{i\in S}a_i=B. \)
This proves the claimed characterization.
If PARTITION is a yes-instance, let \(k^S\) be the bundle just constructed. Its complementary bundle, defined coordinatewise by
\( \overline{k}^{\,S}_{i,b}=1-k^S_{i,b}, \)
also has load \(B\), because the complement of \(S\) also has input weight \(A/2\).
Assign probability \(1/2\) to each of these two bundles. Every job coordinate has expectation \(1/2\), precisely its required mass divided by \(\mu_M=1\). The allocation is feasible, uses rational probabilities, and attains \(W=B\). Since the objective is capped at \(B\), it is optimal.
If an allocation attains \(W=B\), Section 2 shows that every positive-probability bundle has load exactly \(B\). At least one such bundle exists because the bundle space is countable and the probabilities sum to one. Section 4 extracts a PARTITION solution from that bundle.
We have consequently proved
\( \text{PARTITION is a yes-instance}\quad\Longleftrightarrow\quad\text{some feasible allocation has }W=B. \)
The reverse implication holds even when arbitrary real probabilities and infinite support are allowed.
For these constructed instances, all bundle loads and \(B\) are integers. The set of positive-probability loads is a nonempty subset of the nonnegative integers, so it has a minimum, which equals the essential infimum. Therefore every allocation has integer welfare. In a no-instance, every allocation satisfies \(W\le B-1\).
For completeness, the requested finite rational representation does not create an existence obstruction. Here rational probabilities are understood as fractions whose numerators and denominators are encoded in binary.
Write \(x_j=\mu_j/\mu_M\). A feasible finite rational allocation always exists: independently round each \(x_j\) to its floor or ceiling with the probabilities that preserve its expectation.
Choose a positive integer \(d\) such that every \(dp_j\) is integral. Every bundle load then belongs to \(d^{-1}\mathbb Z_{\ge0}\). Because the bundle space is countable, every allocation's essential infimum is its minimum positive-probability load. Its welfare consequently belongs to the finite set
\( \{r/d:r\in\mathbb Z_{\ge0},\ r/d\le B\}\cup\{B\}. \)
The nonempty set of attainable welfare values therefore has a maximum, say \(t\), attained by some feasible distribution.
We now replace that distribution by a finite rational one without reducing its welfare. Set
\( C_j=\lceil t/p_j\rceil,\qquad f_j(k)=\min\{k_j,C_j\}. \)
Every truncated bundle \(f(k)\) still has load at least \(t\). If no coordinate changes, its load is unchanged. If coordinate \(j\) changes, that coordinate alone contributes \(p_jC_j\ge t\).
The truncated bundles belong to a finite set \(F\), and their expected vector is coordinatewise at most \(x\). Hence the following finite rational system is feasible:
\( \sum_{f\in F}\alpha_f=1,\qquad \alpha_f\ge0,\qquad \sum_{f\in F}\alpha_f f_j\le x_j\quad\text{for every }j. \)
Its feasible set is a nonempty bounded rational polytope, so it has a rational vertex: the vertex coordinates solve a full-rank system of tight rational linear equations. Choose such rational probabilities \(\alpha_f\), and let
\( \delta_j=x_j-\sum_{f\in F}\alpha_f f_j\ge0. \)
Independently construct a finitely supported integer-valued vector \(z\) with expectation \(\delta\), again by floor-or-ceiling rounding. Its probabilities are rational. Independently sample \(f\) and \(z\), and output \(f+z\). This distribution has expectation exactly \(x\), finite support, and rational probabilities. Since \(z\) is nonnegative, every output bundle retains load at least \(t\). It therefore attains the optimum.
This establishes existence, without claiming that the finite sets used in this argument can be enumerated in polynomial time.
Suppose a polynomial-time algorithm computed an optimal allocation in the requested representation. Apply it to the constructed society and compute the minimum load among its positive-probability bundles, capped at \(B\). Exact rational arithmetic performs this comparison in polynomial time in the output length.
By Section 5, the resulting welfare equals \(B\) exactly when the original PARTITION instance is a yes-instance. The algorithm would therefore solve PARTITION in polynomial time.
This proves the requested \(\mathrm{NP}\)-hardness classification. The reduction establishes ordinary \(\mathrm{NP}\)-hardness; it makes no claim of strong \(\mathrm{NP}\)-hardness.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem: computing an exact optimal allocation is \(\mathrm{NP}\)-hard. The reduction applies directly to the stated mass-distribution model. I found no major or minor mathematical issues.
The prover uses PARTITION on a nonempty list of positive integers encoded in binary, asking whether \(2\sum_{i\in S}a_i=A\). This is precisely the version identified as \(\mathrm{NP}\)-complete in the [cited complexity exercises, Problem 1](https://ktiml.mff.cuni.cz/~fink/teaching/computability_2017_18/tutorial_5.pdf).
The argument establishes ordinary \(\mathrm{NP}\)-hardness. It correctly makes no claim of strong hardness and does not transfer finite-society hardness without a separate reduction.
Linearity of expectation gives
\[
\mathbb E_\lambda[X]=\sum_jp_j\mathbb E_\lambda[k_j]=B/\mu_M.
\]
The finite first moments and finitely many positive processing values ensure that \(X\) is integrable.
Under the stated restriction \(\mu_M=1\), \(W=B\) implies \(\operatorname{ess\,inf}X\ge B\), hence \(X\ge B\) almost surely. The nonnegative integrable variable \(X-B\) has expectation zero, so it vanishes almost surely. Conversely, an allocation supported on load-\(B\) bundles has welfare \(B\).
Because the bundle space is countable, the formulation using every positive-probability bundle is equivalent to the almost-sure formulation. This step also covers infinite support.
All constructed masses satisfy the task’s positivity requirements. There are exactly \(2n\) job types and one machine type, so \(m=2n\) and \(\tau=2n+1\).
The cap calculation is correct:
\[
B=\frac12\sum_i(p_{i,0}+p_{i,1})=nH+QG+A.
\]
The stated bounds are valid. Since \(a_i\le A\),
\[
H\le p_{i,b}\le H+Qq^{n-1}+2A=H+D.
\]
Also,
\[
0<QG+A\le nQq^{n-1}+A\le nD<H,
\]
where the final inequality follows from \(H=nD+1\). Thus \(nH<B<(n+1)H\).
Distinctness is correctly justified: within each pair the difference is \(2a_i>0\), and between consecutive pairs the radix contribution increases by at least \(Q>2A\), exceeding every possible within-pair offset.
Although the numerical values grow exponentially, their binary lengths are polynomial. The stated bound \(O(\log A+n\log(n+1))\) per processing value is valid. Computing the derived valuation values \(B\) and \(-(B+1)\), if explicitly required in the input, also preserves polynomial encoding length.
Each of the three forcing steps is valid.
\[
X(k)\le(n-1)(H+D)<nH<B,
\]
because \(H-(n-1)D=D+1>0\). Hence \(N=n\).
\[
0\le2\sum_i a_i k_{i,1}\le2nA<Q,
\]
while \(0<A<Q\). Both quantities are integers in the same complete residue range modulo \(Q\). Their congruence therefore implies equality, not merely congruence:
\[
2\sum_i a_i k_{i,1}=A.
\]
Consequently \(k_{i,1}\) is either zero or one, and its selected indices solve PARTITION. The converse substitution also gives exactly load \(B\).
These arguments remain valid for \(n=1\). Odd \(A\) causes no problem: the required equality then has no integral solution, as it should.
In a yes-instance, the selected bundle and its coordinatewise complement both have load \(B\). Giving each probability \(1/2\) produces expectation \(1/2\) in every job coordinate. This exactly matches the prescribed masses with \(\mu_M=1\), and the distribution meets the required finite rational representation.
Conversely, any distribution attaining \(B\) must be supported on exact-load bundles. A probability distribution on a countable space has at least one positive-probability bundle, so the characterization in Section 4 supplies a PARTITION solution.
The integer welfare statement is also correct. Both \(B\) and every bundle load are integers. A nonempty set of positive-probability loads therefore has a minimum, which equals the essential infimum. In a no-instance, every feasible allocation consequently has \(W\le B-1\).
This additional argument is sound and addresses the requested output representation.
Floor-or-ceiling rounding of each rational \(x_j=\mu_j/\mu_M\), followed by independent sampling, gives a feasible finite distribution with rational probabilities.
Choosing a common denominator \(d\) places all loads in \(d^{-1}\mathbb Z_{\ge0}\). Every nonempty subset of this discrete nonnegative set has a minimum. After capping at \(B\), only finitely many welfare values are possible. The nonempty set of attained values therefore contains a maximum; no compactness assumption on the original distribution space is needed.
For an optimal distribution, every positive-probability bundle has load at least its welfare \(t\). The truncation preserves this property: if any coordinate is reduced, its retained contribution alone is at least \(t\). Otherwise the load is unchanged.
Taking \(F\) to be the finite image of the distribution’s support under truncation, the induced probabilities satisfy the displayed inequalities. The resulting polytope has rational coefficients, is nonempty, and is bounded by the probability simplex. Its rational-vertex argument applies with those hypotheses satisfied.
The deficits \(\delta_j\) are rational and nonnegative. Independent floor-or-ceiling rounding produces a finite nonnegative integer vector with the required expected deficit. Adding it restores every prescribed first moment while preserving the load lower bound. Rational probabilities and finite support are preserved.
The case \(t=0\) is covered: the truncation gives the zero bundle, and the deficit construction restores feasibility.
The prover correctly distinguishes existence from polynomial-time enumeration.
A polynomial-time algorithm producing the explicit requested representation necessarily produces polynomial-length output. Its welfare can be evaluated by inspecting positive-probability bundles and performing exact rational arithmetic in polynomial time.
The proved equivalence makes comparison with \(B\) decide PARTITION using one call to that algorithm. Thus the claimed hardness of exact optimization follows. No membership claim, strong-hardness claim, or approximation-hardness claim is needed.
No repair or additional clarification is required for the mathematical argument.
⟨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.