Answer: Both the general problem and its \(K=0\) restriction are \(\mathrm{NP}\)-complete, already for \(\tau=1\) with nonnegative additive valuations and supplies \(b_j=1/2\). Both admit exact algorithms running in \(2^{O(m)}\operatorname{poly}(\tau,L)\) time.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing the minimum payments to simultaneously achieve envy-freeness and equitability is strongly NP-hard. Unless $\text{P}=\text{NP}$, there exists no deterministic polynomial-time algorithm that approximates within any given positive factor the minimum payments to simultaneosly achieve envy-freeness and equitability.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), rational per-capita supplies \(b_j\) of indivisible task categories, and valuation functions \(v_t\) over integral bundles \(B\), choose mass variables \(\lambda_{t,B}\ge 0\) and subsidies \(p_{t,B}\le 0\) satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and the task-capacity constraints, minimizing \(S=\sum_{t,B}\lambda_{t,B}(-p_{t,B})\), subject to every positive-mass state \((t,B)\) having equal utility \(v_t(B)-p_{t,B}\) and weakly preferring its own state to every assigned state; decide in particular whether \(S=0\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) task categories with binary-rational per-capita supplies \(0<b_j\leq1\). An integral bundle is a subset \(B\subseteq\{1,\ldots,m\}\), including the empty bundle; an individual receives at most one task of each category.
Each type has a superadditive valuation \(v_t\), possibly positive or negative, with \(v_t(\emptyset)=0\), represented by a Boolean circuit mapping bundle incidence vectors to binary-rational values. Let \(L\) be the total input bit length, including circuits and a binary-rational budget \(K\geq0\).
Choose real masses \(\lambda_{t,B}\geq0\) and payments \(p_{t,B}\leq0\), satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B:j\in B}\lambda_{t,B}=b_j\) for every category \(j\); all supplied tasks must be allocated.
For every two positive-mass states \((t,B)\) and \((s,C)\), require equitability \(v_t(B)-p_{t,B}=v_s(C)-p_{s,C}\) and envy-freeness \(v_t(B)-p_{t,B}\geq v_t(C)-p_{s,C}\). Comparisons are between realized states, with weak inequalities.
The total subsidy is \(S=\sum_{t,B}\lambda_{t,B}(-p_{t,B})\); payments on zero-mass states are irrelevant.
Is deciding whether a feasible outcome with \(S\leq K\) exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? What is the classification for the restriction \(K=0\)? State running times in \(m\), \(\tau\), and \(L\).
For finite societies, minimizing subsidies subject to envy-freeness and equitability is strongly \(\mathrm{NP}\)-hard; deciding whether zero subsidy suffices is already \(\mathrm{NP}\)-hard with identical valuations. [Aziz, AAAI 2021](https://cdn.aaai.org/ojs/16645/16645-13-20139-1-2-20210518.pdf)
No result settling this precise mass-based problem was located in the literature search.
Both the general decision problem and its restriction \(K=0\) are \(\mathrm{NP}\)-complete. Hardness holds already with \(\tau=1\), a nonnegative additive valuation, and \(b_j=1/2\) for every category.
Both problems admit an exact algorithm running in
\(2^{O(m)}\operatorname{poly}(\tau,L).\)
Thus they are polynomial-time solvable for fixed \(m\), but not polynomial-time solvable in general unless \(\mathrm{P}=\mathrm{NP}\).
These statements concern inputs satisfying the stipulated superadditivity promise; recognizing that promise is not part of the decision problem.
Write \(T=\{1,\ldots,\tau\}\) for the supported types and define
\(F(B)=\max_{t\in T}v_t(B).\)
Every supported type has positive mass and therefore has at least one realized state.
Lemma. An allocation of masses can be made equitable and envy-free using nonpositive payments if and only if every realized state \((s,C)\) satisfies
\(v_s(C)=F(C).\)
For such an allocation, let
\(M=\max_{\lambda_{t,B}>0}F(B),\qquad W=\sum_{t,B}\lambda_{t,B}F(B).\)
Its minimum possible subsidy is \(M-W\).
Proof. Equitability supplies a common utility \(u\in\mathbb R\), so every realized state satisfies
\(p_{s,C}=v_s(C)-u.\)
Fix a realized state \((s,C)\) and any supported type \(t\). Choose a realized state \((t,B)\). Envy-freeness gives
\(u\geq v_t(C)-p_{s,C}=v_t(C)-v_s(C)+u.\)
Consequently \(v_t(C)\leq v_s(C)\). This holds for every supported type \(t\), proving \(v_s(C)=F(C)\).
Conversely, suppose every realized state satisfies this equality. Choose any \(u\geq M\) and set
\(p_{s,C}=F(C)-u.\)
These payments are nonpositive and give common utility \(u\). For any two realized states \((t,B)\) and \((s,C)\),
\(v_t(C)-p_{s,C}=v_t(C)-F(C)+u\leq u,\)
which proves envy-freeness.
Finally, because total population mass is one,
\(S=\sum_{t,B}\lambda_{t,B}\bigl(u-F(B)\bigr)=u-W.\)
The smallest admissible common utility is \(u=M\), giving minimum subsidy \(M-W\). \(\square\)
This characterization uses all supported types, regardless of how many possible types lie outside the support. It does not require superadditivity.
Enumerate all \(2^m\) bundles and evaluate every supported type’s circuit on every bundle. This computes \(F(B)\) and all equalities \(v_t(B)=F(B)\) in \(2^m\operatorname{poly}(\tau,L)\) time.
Let
\(\mathcal A=\{F(B):B\subseteq\{1,\ldots,m\}\}.\)
There are at most \(2^m\) distinct thresholds. For each \(\alpha\in\mathcal A\), retain precisely the states
\(E_\alpha=\{(t,B):v_t(B)=F(B),\ F(B)\leq\alpha\}.\)
Over these states, solve the following rational linear program:
\(\text{maximize }\displaystyle W=\sum_{(t,B)\in E_\alpha}\lambda_{t,B}F(B),\)
subject to
\(\displaystyle\sum_{B:(t,B)\in E_\alpha}\lambda_{t,B}=\mu_t\quad\text{for every }t,\)
\(\displaystyle\sum_{(t,B)\in E_\alpha:\,j\in B}\lambda_{t,B}=b_j\quad\text{for every }j,\)
and \(\lambda_{t,B}\geq0\).
An infeasible program is discarded. Otherwise denote its optimum by \(W_\alpha\). Accept if some threshold satisfies
\(\alpha-W_\alpha\leq K.\)
Correctness. If a threshold passes, use its optimal allocation and payments \(p_{t,B}=F(B)-\alpha\). The lemma proves fairness, and its subsidy is \(\alpha-W_\alpha\leq K\).
Conversely, suppose an outcome with subsidy at most \(K\) exists. Let \(u\) be its common utility and let \(M\) be its maximum realized value. The lemma gives \(M\leq u\), and all its realized states belong to \(E_M\). Its welfare \(W\) therefore satisfies \(W_M\geq W\). Hence
\(M-W_M\leq M-W\leq u-W=S\leq K.\)
Since \(M\in\mathcal A\), the algorithm accepts.
Bit complexity. Each program has at most \(\tau2^m\) variables and \(\tau+m\) equality constraints. All coefficients are rational with bit length polynomial in \(L\): the constraint matrix has entries in \(\{0,1\}\), and each circuit output has length bounded by its encoded output size. Exact rational linear programming runs in time polynomial in its encoded input length. [Cornell lecture notes](https://people.orie.cornell.edu/shmoys/or630/notes-06/lec18.pdf)
There are at most \(2^m\) programs, yielding total time
\(2^m\operatorname{poly}(\tau2^m,m,L)=2^{O(m)}\operatorname{poly}(\tau,L).\)
The same bound applies to \(K=0\).
We next prove membership in \(\mathrm{NP}\), including polynomial bounds on witness size.
Suppose the instance is a yes-instance. By the preceding argument, some threshold \(\alpha\in\mathcal A\) satisfies \(\alpha-W_\alpha\leq K\). Fix that threshold.
The feasible set of its linear program is compact: it is closed, and every coordinate lies between zero and one because the type masses sum to one. Thus welfare attains a maximum. Among all maximizers, choose one with the fewest positive coordinates.
Let \(A\) be the equality-constraint matrix. Its column for state \((t,B)\) consists of the type indicator vector followed by the bundle incidence vector. Thus \(A\) has \(\tau+m\) rows and entries in \(\{0,1\}\).
Sparse support. The columns corresponding to positive coordinates are linearly independent. Otherwise there is a nonzero vector \(d\), supported on those coordinates, with \(Ad=0\). Summing the type rows gives \(\sum_i d_i=0\), so \(d\) has both positive and negative coordinates.
For sufficiently small \(\varepsilon>0\), both \(\lambda+\varepsilon d\) and \(\lambda-\varepsilon d\) remain feasible. Optimality forces the objective’s inner product with \(d\) to be zero; otherwise one perturbation improves welfare. Now increase the positive perturbation until a coordinate first becomes zero. This preserves feasibility and welfare while reducing support, a contradiction.
Consequently the chosen maximizer has at most \(\tau+m\) positive coordinates.
Rational encoding. Let its support size be \(k\). The independent support columns contain a nonsingular \(k\)-by-\(k\) submatrix \(H\) formed by selecting rows. The positive masses are uniquely determined by
\(H\lambda=q,\)
where \(q\) consists of selected input masses and supplies.
Let \(D\) be the product of the denominators of the input masses and supplies. Its bit length is \(O(L)\), and every coordinate of \(Dq\) is an integer between zero and \(D\). Cramer’s rule expresses each mass as a ratio whose denominator is \(D\det(H)\). Hadamard’s inequality gives
\(|\det(H)|\leq k^{k/2},\)
and bounds each corresponding integer numerator by \(Dk^{k/2}\). Thus every mass has bit length
\(O\bigl(L+k\log(k+1)\bigr).\)
The threshold \(\alpha\), being a circuit output, also has polynomial bit length.
A certificate therefore lists \(\alpha\) and at most \(\tau+m\) realized states with positive rational masses. In polynomial time, a verifier checks:
These checks imply a feasible outcome by setting \(p_{t,B}=F(B)-\alpha\). Every yes-instance has such a polynomial-size certificate, proving membership in \(\mathrm{NP}\).
We reduce from PARTITION: given positive binary integers \(a_1,\ldots,a_m\), decide whether some subset sums to half their total. This problem is \(\mathrm{NP}\)-complete. [MIT lecture notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf)
Write \(A=\sum_j a_j\). Construct the instance
\(\tau=1,\qquad \mu_1=1,\qquad b_j=1/2\text{ for every }j,\qquad K=0,\)
with valuation
\(v_1(B)=\sum_{j\in B}a_j.\)
A Boolean circuit can compute this sum using polynomially many gates. Its outputs are integers, hence binary rationals. The valuation satisfies \(v_1(\emptyset)=0\) and is additive on disjoint bundles, so it satisfies the required superadditivity promise. The entire construction has polynomial size.
If PARTITION is a yes-instance. Choose \(J\) with \(\sum_{j\in J}a_j=A/2\). Give mass \(1/2\) bundle \(J\), and mass \(1/2\) its complement, with zero payments.
Each category occurs in exactly one of the two bundles, so its allocated mass is \(1/2\). Both bundles have value \(A/2\). Thus equitability and envy-freeness hold, and subsidy is zero.
If the constructed instance is a yes-instance. Every subsidy contribution \(\lambda_{1,B}(-p_{1,B})\) is nonnegative. Since their sum is at most zero, every realized state has \(p_{1,B}=0\).
Equitability therefore forces every realized bundle to have the same value \(u\). Using the supply equalities,
\(\displaystyle u=\sum_B\lambda_{1,B}v_1(B)=\sum_{j=1}^m a_j\sum_{B:j\in B}\lambda_{1,B}=\frac A2.\)
The first equality uses \(\sum_B\lambda_{1,B}=1\) and the common realized value. At least one bundle has positive mass, so some bundle has value \(A/2\), giving a partition.
This proves the reduction in both directions. Fractional population masses cannot circumvent it: zero subsidy and equitability require every realized bundle individually to have the target value.
The restriction \(K=0\) is \(\mathrm{NP}\)-hard by the reduction and belongs to \(\mathrm{NP}\) by the certificate argument; hence it is \(\mathrm{NP}\)-complete.
The general problem includes these zero-budget instances and also belongs to \(\mathrm{NP}\), so it too is \(\mathrm{NP}\)-complete.
The exact running time for either problem is \(2^{O(m)}\operatorname{poly}(\tau,L)\). Hardness already holds for the fixed support size \(\tau=1\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly establishes that both the general decision problem and the restriction \(K=0\) are \(\mathrm{NP}\)-complete, already for \(\tau=1\), nonnegative additive valuations, and supplies \(b_j=1/2\). The exact running time \(2^{O(m)}\operatorname{poly}(\tau,L)\) is also justified.
No major or minor mathematical issues were found. The classification is explicitly made under the stipulated superadditivity promise.
The lemma is correct in both directions.
Negative valuations cause no difficulty: the task does not require common utility to be nonnegative. The maxima exist because the state space is finite and its realized support is nonempty. Zero-mass states impose no additional restrictions.
Finding: The characterization and minimum-subsidy formula are fully established.
The threshold construction correctly captures the existence question.
\(M-W_M\leq M-W\leq u-W=S\leq K\)
is valid.
The acceptance argument does not require the optimal allocation to realize a state of value exactly \(\alpha\). Using common utility \(\alpha\) is still permissible.
Every feasible program is bounded by the type-mass constraints, so its finite optimum is attained.
Finding: Both directions of algorithmic correctness are valid.
The bit-complexity argument is sound.
A Boolean circuit has explicitly encoded output wires, so its rational output length is bounded by the input representation. Evaluating all circuits on all bundles, comparing rational values, and identifying thresholds therefore take \(2^m\operatorname{poly}(\tau,L)\) time.
Each explicitly constructed program has at most \(\tau2^m\) variables and \(\tau+m\) equality constraints, with rational coefficients of polynomial bit length. The invoked polynomial-time theorem for rational linear programming applies to these explicit programs; there is no implicit separation-oracle assumption. The cited [Cornell notes](https://people.orie.cornell.edu/shmoys/or630/notes-06/lec18.pdf) identify polynomial-time linear programming with dependence on dimensions and numerical encoding length.
Multiplying the polynomial cost per program by at most \(2^m\) thresholds gives the claimed bound. The factor involving \(m\) can be absorbed into the polynomial in \(L\), since the input explicitly lists \(m\) supplies.
Finding: The bound \(2^{O(m)}\operatorname{poly}(\tau,L)\), including polynomial time for fixed \(m\), is justified.
The certificate argument correctly handles the allowance of real masses.
The certificate describes positive rational masses and valid realized states. Its stated checks enforce the allocation constraints, the valuation-maximization condition, the payment-sign condition through \(F(B)\leq\alpha\), and the budget.
A verifier need not additionally establish \(\alpha\in\mathcal A\): any rational threshold satisfying these checks yields a feasible outcome. Membership in \(\mathcal A\) is used to establish existence of a short certificate.
Finding: Membership in \(\mathrm{NP}\) is rigorously established under the input promise.
The reduction is valid and polynomial in the binary input size. Binary-integer PARTITION is the appropriate source problem; its NP-completeness is stated in the cited [MIT notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf).
The constructed valuation is nonnegative and additive on disjoint bundles, satisfying the intended superadditivity condition. Its subset sums have polynomial bit length and can be computed by a polynomial-size Boolean circuit.
The forward direction allocates complementary bundles with equal values and zero payments. Supply, equitability, and envy-freeness all hold.
For the reverse direction, every subsidy term is nonnegative. A zero total therefore forces zero payment on every positive-mass state. Equitability then forces every realized bundle to have the same value. The supply equalities correctly identify that value as \(A/2\). Since some bundle is realized, a partition exists.
Odd \(A\) introduces no loophole: integral bundle values cannot equal its nonintegral half. Fractional masses likewise cannot avoid the requirement that each realized bundle itself have value \(A/2\).
Finding: The reduction proves the stated hardness, including fixed support size \(\tau=1\). It does not establish strong NP-hardness, and the output does not claim it does.
Both requested classifications and the running-time statement follow from the written arguments. The proof uses the mass-based model directly and does not assume that finite-society hardness transfers automatically.
Required repairs: None.
⟨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.