Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen agents have monotone nondecreasing valuations, determining whether a given instance admits an MMS allocation is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite resource set \(M\), rational type masses \(\mu_t\) summing to \(1\), and rational piecewise-linear monotone nondecreasing utility curves \(u_t(j,z)\) for each type \(t\), resource \(j\), and population load \(z\in[0,1]\), let \(\theta_t=\max_{j\in M}u_t(j,1)\). Does there exist a mass assignment \(x_{t,j}\geq 0\) with \(\sum_j x_{t,j}=\mu_t\), loads \(y_j=\sum_t x_{t,j}\), and \(x_{t,j}>0\Rightarrow u_t(j,y_j)\geq\theta_t\) for every \(t,j\)?
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; assume \(\sum_{t=1}^{\tau}\mu_t=1\).
Let \(M\) be a nonempty resource set with \(m=|M|\). For every type \(t\) and resource \(j\), the input specifies a continuous monotone nondecreasing piecewise-linear function \(u_t(j,\cdot):[0,1]\to\mathbb R\) by an explicit list of rational breakpoints and rational values, with linear interpolation. Utilities may be negative. Let \(L\) be the total binary input length.
Define \(\theta_t=\max_{j\in M}u_t(j,1)\). A feasible assignment consists of real masses \(x_{t,j}\geq0\) satisfying \(\sum_{j\in M}x_{t,j}=\mu_t\), with loads \(y_j=\sum_{t=1}^{\tau}x_{t,j}\), such that \(x_{t,j}>0\Rightarrow u_t(j,y_j)\geq\theta_t\). Types may split their mass among resources; resources have no additional capacity constraints and may be empty.
Is deciding whether a feasible assignment exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite indivisible agents with monotone nondecreasing resource utilities depending on the number of users, deciding whether every agent can attain her threshold \(\max_{j\in M}v_i(j,n)\) is NP-complete; this threshold is her maximin share.
This discrete result does not classify the mass problem specified above; no result for that exact continuous problem is verified here.
The decision problem is \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard. Hardness holds even when all masses are dyadic rationals and all utilities take values in \([0,1]\) and have at most two linear pieces.
We use the classical \(\mathrm{NP}\)-complete Exact Cover problem: given an explicitly listed family \(\mathcal S=\{S_1,\ldots,S_r\}\), with universe \(U=\bigcup_{j=1}^r S_j\), decide whether some subfamily consists of pairwise disjoint sets whose union is \(U\). This is problem 14 in [Karp’s original paper](https://studylib.net/doc/27985824/karp1972).
Discard empty sets, which cannot affect the answer. We may assume \(U\) is nonempty: empty-universe instances are always yes and can be replaced by a fixed nonempty yes-instance. Write \(n=|U|\).
Let \(D\) be the smallest power of two strictly greater than \(n\). Thus \(n<D\leq 2n\).
Create one type for every element \(e\in U\), with mass
\(\mu_e=1/D.\)
Create one additional type \(\ast\), with mass
\(\mu_\ast=1-n/D.\)
All these masses are positive dyadic rationals, and their sum is \(1\).
Create a resource \(j\) for every set \(S_j\), together with one additional resource \(d\). For each set resource, put
\(a_j=|S_j|/D.\)
Since the sets are nonempty and \(D>n\), we have \(0<a_j<1\).
For an element type \(e\in S_j\), define
\(u_e(j,y)=\min\{y/a_j,1\}.\)
Its explicit breakpoint-value list is
\((0,0),\quad(a_j,1),\quad(1,1).\)
For \(e\notin S_j\), define \(u_e(j,y)=0\). Also define \(u_e(d,y)=0\) for every element type.
For the additional type, define
\(u_\ast(d,y)=1,\qquad u_\ast(j,y)=0\quad\text{for every set resource }j.\)
Every utility is continuous, monotone nondecreasing, and piecewise linear with rational data. Because each element belongs to some set, its utility at load \(1\) is \(1\) on at least one resource. Consequently,
\(\theta_e=1\quad(e\in U),\qquad\theta_\ast=1.\)
The constructed instance has \(\tau=n+1\) types and \(m=r+1\) resources. Each utility list has at most three entries, and every rational entry has binary length \(O(\log(n+1))\). Writing all lists explicitly therefore takes polynomial time and produces polynomial total input length.
Suppose a pairwise disjoint subfamily covers \(U\). Assign each element type’s entire mass to the resource corresponding to its covering set. Assign type \(\ast\) entirely to resource \(d\).
For every selected set resource,
\(y_j=\sum_{e\in S_j}\mu_e=|S_j|/D=a_j.\)
Thus every assigned element receives utility \(1=\theta_e\). Type \(\ast\) also receives utility \(1=\theta_\ast\). All other resources are empty, so this assignment is feasible.
Now suppose a feasible assignment exists.
Because every threshold is \(1\), a utility identically equal to \(0\) prohibits positive assigned mass. Hence:
Consider any nonempty set resource \(j\). Since \(y_j>0\), at least one element type has positive mass there. Its feasibility condition requires
\(1\leq u_e(j,y_j)=\min\{y_j/a_j,1\},\)
so \(y_j\geq a_j\).
On the other hand, only members of \(S_j\) can contribute, and mass conservation gives \(x_{e,j}\leq\mu_e=1/D\). Therefore,
\(y_j=\sum_{e\in S_j}x_{e,j}\leq |S_j|/D=a_j.\)
Both inequalities force equality. Moreover, equality in this sum forces
\(x_{e,j}=1/D\quad\text{for every }e\in S_j,\)
because every summand is at most \(1/D\).
Thus every nonempty set resource consumes the entire mass of every element in its set. Two nonempty set resources cannot have overlapping sets: an overlapping element would have to assign its entire positive mass to both, contradicting mass conservation.
Finally, every element has positive mass and must assign it somewhere. It cannot use resource \(d\), so it belongs to at least one nonempty set resource. The sets corresponding to the nonempty resources therefore form an exact cover.
This proves the required equivalence and establishes \(\mathrm{NP}\)-hardness. The argument applies to fully divisible masses: the constructed utility requirements themselves force the relevant assignments to be unsplit.
We next show that allowing real assignments does not prevent polynomial-size certificates.
For every type-resource pair and every \(y\in[0,1]\), monotonicity gives
\(u_t(j,y)\leq u_t(j,1)\leq\theta_t.\)
If \(u_t(j,1)<\theta_t\), that pair can never carry positive mass.
Otherwise, \(u_t(j,1)=\theta_t\). Continuity and monotonicity imply that the set of acceptable loads is a closed interval
\(\{y\in[0,1]:u_t(j,y)\geq\theta_t\}=[a_{t,j},1].\)
Here \(a_{t,j}\) is the first listed breakpoint whose value equals \(\theta_t\). Indeed, a linear segment with both endpoint values strictly below \(\theta_t\) cannot attain \(\theta_t\), and after the first attainment monotonicity forces the utility to remain equal to \(\theta_t\).
Thus all eligible pairs and their rational thresholds \(a_{t,j}\) can be computed in polynomial time.
Fix a set \(E\) of eligible pairs. Consider the polytope \(P_E\) defined by
\(x_{t,j}\geq0,\qquad \sum_jx_{t,j}=\mu_t,\)
\(x_{t,j}=0\quad\text{when }(t,j)\notin E,\)
and
\(\sum_sx_{s,j}\geq a_{t,j}\quad\text{when }(t,j)\in E.\)
If a feasible assignment exists, taking \(E\) to be its positive support makes \(P_E\) nonempty. Conversely, every point of \(P_E\) is feasible: each positive coordinate belongs to \(E\), and its required load inequality is enforced. Coordinates in \(E\) are allowed to be zero, so no strict inequalities are needed.
Let \(N=\tau m\). Every coordinate in \(P_E\) lies between \(0\) and its type’s mass, hence between \(0\) and \(1\). Therefore a nonempty \(P_E\) is compact.
It has an extreme point: successively minimize each coordinate over the compact set of minimizers of the preceding coordinates. The resulting point is unique and extreme, since any convex decomposition would have to preserve each successive minimum.
At an extreme point, the active constraint normals span all \(N\) dimensions. Otherwise, a nonzero direction orthogonal to all active normals would permit sufficiently small perturbations in both directions while preserving every constraint, contradicting extremality. Select \(N\) independent active constraints and write them as
\(Ax=b.\)
The entries of \(A\) belong to \(\{-1,0,1\}\), and the entries of \(b\) are input masses, input breakpoints, or zero. Let \(Q\) be the product of their denominators. Its binary length is \(O(NL)\), and \(Qb\) is integral.
Cramer’s rule expresses each coordinate as a ratio of integer determinants with denominator \(Q\det A\). Hadamard’s inequality bounds \(|\det A|\) by \(N^{N/2}\); the corresponding numerator determinants have magnitude at most \(QN^{N/2}\), since \(|b_i|\leq1\). Every coordinate therefore has a rational representation of binary length
\(O(NL+N\log(N+1)).\)
Consequently, every feasible instance admits a polynomial-size rational assignment. A verifier checks nonnegativity, mass conservation, loads, and the rational load thresholds by exact arithmetic in polynomial time. The problem belongs to \(\mathrm{NP}\).
Together with the reduction, this proves \(\mathrm{NP}\)-completeness. A polynomial-time algorithm in \(m,\tau,L\) therefore exists only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the specified continuous problem correctly: it establishes \(\mathrm{NP}\)-completeness, including the stated restriction to positive dyadic masses and utilities in \([0,1]\) with at most two linear pieces. I found no major or minor mathematical issues.
The cited Exact Cover theorem matches the source problem used: an explicitly listed family of finite sets, with a disjoint subfamily required to cover their union. Exact Cover is item 14 in the cited paper’s completeness theorem. [Karp’s paper](https://studylib.net/doc/27985824/karp1972)
Removing empty sets preserves the answer. Replacing an empty-universe instance by a fixed nonempty yes-instance also preserves the answer and takes constant time. After this preprocessing, \(n\geq1\), and every universe element belongs to at least one listed set. These are precisely the hypotheses needed later.
The smallest power of two strictly greater than \(n\) satisfies \(n<D\leq2n\), including when \(n\) itself is a power of two. Consequently, every element mass \(1/D\) and the additional mass \(1-n/D\) are positive dyadic rationals. Their sum is exactly \(1\).
Thus the construction uses the required support representation, with exactly \(n+1\) positive-mass types.
Every retained set is nonempty and has size at most \(n<D\), so \(0<a_j<1\). The breakpoint list for an incident element has strictly increasing breakpoint positions and defines a continuous, monotone nondecreasing function with two linear pieces. All other utilities are constant functions and therefore satisfy the same requirements.
Every constructed utility lies in \([0,1]\). The additional resource ensures that the resource set is nonempty.
Each element belongs to some set and obtains utility \(1\) at load \(1\) on that set’s resource. No constructed utility exceeds \(1\), so its threshold is exactly \(1\). The additional type has threshold \(1\) because its utility on resource \(d\) is constantly \(1\).
The thresholds are therefore derived from the required definition; they are not independently prescribed.
There are \((n+1)(r+1)\) explicitly specified utility functions, each with a constant number of rational entries. Their entries have binary length \(O(\log(n+1))\). Both \(n\) and \(r\) are bounded by the explicitly listed source input size. Hence the output length and construction time are polynomial.
A disjoint cover assigns each element’s entire mass to exactly one covering set resource, preserving every type’s mass. A selected resource receives exactly \(|S_j|/D=a_j\), so every assigned element obtains its threshold utility. The additional type obtains its threshold on \(d\). Empty resources create no additional conditions.
This direction is correct.
Since every threshold equals \(1\), an identically zero utility cannot support a positive assignment. Therefore only members of \(S_j\) can contribute to set resource \(j\); elements cannot use \(d\); and the additional type must place all its mass on \(d\).
These conclusions follow directly from the feasibility implication.
A positive load entails at least one positive coordinate because the number of types is finite. That element’s utility condition forces \(y_j\geq a_j\).
Conversely, contributor eligibility and mass conservation give \(x_{e,j}\leq1/D\) for every member and therefore \(y_j\leq|S_j|/D=a_j\). Equality follows. Since the sum has exactly \(|S_j|\) nonnegative summands, each bounded above by \(1/D\), equality forces every summand to attain that bound.
The saturation argument is valid even though splitting is permitted.
Two nonempty set resources cannot share an element: each would require that element’s entire positive mass, contradicting its mass equation. Every element must use some set resource because its mass is positive and it cannot use \(d\). Hence the nonempty set resources correspond to pairwise disjoint sets covering the universe.
This establishes the reverse implication and proves hardness for the continuous problem itself.
Monotonicity gives \(u_t(j,y)\leq u_t(j,1)\leq\theta_t\). Thus a pair whose endpoint utility is below the threshold is unusable.
For an eligible pair, the acceptable loads form \([a_{t,j},1]\). The claimed breakpoint characterization is correct: linear interpolation between two values strictly below the threshold cannot attain it, and an eligible function cannot exceed the threshold anywhere. Its first attainment must therefore occur at a listed breakpoint.
Constant eligible functions give \(a_{t,j}=0\); attainment only at the final endpoint gives \(a_{t,j}=1\). Negative utilities do not affect this reasoning. Exact rational comparisons suffice to compute all eligibility decisions and thresholds in polynomial time.
Taking \(E\) to be the positive support of a feasible assignment makes all defining constraints of \(P_E\) hold. Conversely, any positive coordinate of a point in \(P_E\) belongs to \(E\), and its corresponding load condition is enforced.
Allowing coordinates in \(E\) to vanish causes no problem: it imposes additional load constraints but does not invalidate the converse. The argument correctly avoids strict inequalities.
Nonnegativity and the mass equations bound every coordinate between \(0\) and \(1\). The polytope is closed, so a nonempty \(P_E\) is compact.
Successive coordinate minimization produces a unique point, and the given convex-decomposition argument establishes extremality. The active-normal argument is also valid: finitely many inactive inequalities have positive slack, permitting sufficiently small perturbations in both directions if the active normals fail to span the ambient space. Equality constraints must be preserved and are included among the active constraints.
Selecting \(N\) independent active constraints produces an invertible matrix with entries in \(\{-1,0,1\}\). Its right-hand side consists only of masses, breakpoints, and zeros.
The denominator product \(Q\) has binary length \(O(NL)\). Cramer’s rule has denominator \(Q\det A\). Hadamard’s inequality applies because each ordinary column has Euclidean norm at most \(\sqrt N\), while the replaced column \(Qb\) has norm at most \(Q\sqrt N\). The stated determinant and numerator bounds follow.
Therefore each coordinate has the claimed polynomial binary length. Multiplying that bound by the \(N\) coordinates still gives a polynomial-size certificate.
Exact rational arithmetic checks nonnegativity, mass equations, loads, and the threshold condition for every positive coordinate in polynomial time. The verifier need not receive or verify extremality; extremality is used only to establish that a short witness exists.
Membership in \(\mathrm{NP}\), together with the valid reduction, establishes \(\mathrm{NP}\)-completeness. The final conditional statement about polynomial-time solvability follows.
No additional clarification or repair is required.
⟨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.