Answer: \(\mathsf{NP}\text{-hard}\)
Theorem 7 — class: hardness
Given a finite skill set \(S\), supported binary expertise types \(T\subseteq\{0,1\}^{S}\) with rational masses \(\mu_t>0\) summing to \(1\), and team capacity \(\kappa\), compute a rational allocation \(y_q\ge 0\) over integral team compositions \(q\in\mathbb{Z}_{\ge 0}^{T}\) with \(1\le\lVert q\rVert_1\le\kappa\), satisfying \(\sum_q q_t y_q=\mu_t\) for every type \(t\). Each team composition receives utility \(U(q)=\sum_{s\in S}\max_{t:q_t>0}t(s)\). The output must be Pareto optimal: there is no feasible allocation whose utility distribution for each type can be coupled with the output’s so that every unit of mass gets at least its previous utility and a positive mass gets strictly more.
Let \(S\) be a finite skill set, with \(m=|S|\). A society is given by its support: a nonempty list \(T\subseteq\{0,1\}^{S}\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
The capacity \(\kappa\geq1\) is an integer encoded in binary. Let \(Q=\{q\in\mathbb Z_{\geq0}^{T}:1\leq\sum_t q_t\leq\kappa\}\); compositions may contain repeated types. Define \(U(q)=\sum_{s\in S}\max_{t:q_t>0}t(s)\), received by every member of composition \(q\).
An allocation has nonnegative rational team intensities \(y_q\) satisfying \(\sum_{q\in Q}q_t y_q=\mu_t\) for every \(t\). Its output representation lists only compositions with positive intensity, together with their binary-rational intensities; \(Q\) is implicit.
For each type, define its utility mass measure \(\nu_t^y=\sum_{q\in Q}q_t y_q\delta_{U(q)}\). An allocation \(z\) Pareto dominates \(y\) if, for every \(t\), there is a coupling of \(\nu_t^y\) and \(\nu_t^z\) supported on pairs \((u,v)\) with \(v\geq u\), and these couplings assign positive total mass to \(v>u\). An allocation is Pareto optimal if no feasible rational allocation dominates it; equal utilities are ties.
Is computing a Pareto-optimal allocation polynomial-time solvable, or is it \(\mathsf{NP}\)-hard? State running times in \(m\), \(\tau\), \(\kappa\), and the total input bit length \(L\); polynomial time means polynomial in \(L\), including the binary encoding of \(\kappa\).
For finite agents with binary expertise and a coalition-size capacity, computing a Pareto-optimal partition is \(\mathsf{NP}\)-hard, and verifying one is \(\mathsf{coNP}\)-complete. [Source](https://arxiv.org/pdf/2011.01778)
No result settling this exact mass-allocation problem was located in the literature search.
Computing a Pareto-optimal allocation is \(\mathsf{NP}\)-hard, under a polynomial-time reduction making one call to a solver and working with every valid Pareto-optimal output. This holds even when the input masses are dyadic and \(\kappa\leq\tau-1\). Consequently, a polynomial-time algorithm in \(L\) would imply \(\mathsf{P}=\mathsf{NP}\).
There is an exact algorithm taking \(2^{O(\tau)}\operatorname{poly}(m,\tau,L)\) time and producing at most \(\tau\) positive compositions, with polynomial encoding length. For every fixed \(\kappa\), the problem is polynomial-time solvable.
Strict Pareto improvement is understood as positive total strict-improvement mass across the type couplings. The finite-agent comparison appears in Theorem 7 of [Hedonic Expertise Games](https://arxiv.org/pdf/2011.01778); the argument below establishes the result directly for rational mass allocations.
The NP-complete Set Cover decision problem asks whether sets \(A_1,\ldots,A_n\subseteq E\) contain a subfamily of at most \(k\) sets whose union is \(E\).
We may restrict to instances satisfying:
These restrictions preserve NP-completeness. Remove duplicate sets and decide the elementary cases involving an empty universe, a missing universe element, a universal set, \(k=1\), or \(k\geq n\). Replace any such decided instance by a fixed restricted yes-instance or no-instance. Suitable examples have \(E=\{1,2,3\}\), \(k=2\), and respectively all three two-element subsets or all three singleton subsets.
Construct a society with skill set \(S=E\). For each \(A_i\), introduce its incidence-vector type \(t_i\). Introduce one additional type \(h\) knowing every skill. Because the sets are distinct and proper, these are \(\tau=n+1\) distinct types. Set \(\kappa=k\).
We choose dyadic masses carefully. Let \(D\) be the smallest power of two strictly larger than \(kn(n-1)\), and define
\( \displaystyle \alpha=\frac{\left\lfloor D(k-1)/(kn)\right\rfloor+1}{D}, \qquad \mu_{t_i}=\alpha, \qquad \mu_h=\beta=1-n\alpha. \)
Then
\( \displaystyle \frac{k-1}{kn}<\alpha< \frac{k-1}{k(n-1)}. \)
Indeed, \(\alpha\) is strictly above the left endpoint and at most \(1/D\) above it, while
\( \displaystyle \frac{k-1}{k(n-1)}-\frac{k-1}{kn} =\frac{k-1}{kn(n-1)} >\frac1D. \)
The upper bound and \(n>k\) imply \(n\alpha<1\), so \(\beta>0\). The lower bound implies
\( \displaystyle \beta<\frac1k. \)
Thus all masses are positive dyadic rationals summing to one. Each mass has \(O(\log n)\) bits. Under bit-vector encoding, the constructed instance has \(L=O(nm+n\log n)\), where \(m=|E|\), and satisfies \(\kappa=k\leq n=\tau-1\).
Call an allocation full-utility if every positive composition has utility \(m\). Equivalently, its utility measures satisfy \(\nu_t=\mu_t\delta_m\) for every type.
Let \(y\) be any feasible allocation and write \(|q|=\sum_tq_t\). Summing the mass constraints gives
\( \displaystyle \sum_q |q|y_q=1. \)
The member mass in compositions containing \(h\) satisfies
\( \displaystyle \sum_{q:q_h>0}|q|y_q \leq k\sum_{q:q_h>0}y_q \leq k\sum_q q_hy_q =k\beta<1. \)
Consequently, some positive composition contains no \(h\). This calculation permits arbitrary repeated types and arbitrary rational intensities.
If \(y\) is full-utility, that composition covers every skill using at most \(k\) distinct candidate types. Their corresponding sets therefore form a Set Cover solution.
Conversely, suppose a cover of size at most \(k\) exists. Pad it with additional distinct indices to obtain an index set \(C\) of size exactly \(k\), still covering \(E\).
Allocate intensity \(\alpha\) to the composition containing one member of each \(t_i\) for \(i\in C\).
For each \(i\notin C\), allocate intensity \(\alpha/(k-1)\) to
\( \displaystyle q^{(i)}=(k-1)e_{t_i}+e_h. \)
Finally, allocate intensity
\( \displaystyle r=\beta-\frac{(n-k)\alpha}{k-1} =1-\frac{k(n-1)\alpha}{k-1}>0 \)
to the singleton composition \(e_h\). Here \(e_t\) denotes one member of type \(t\).
Each candidate type receives exactly its mass \(\alpha\). The universal type receives exactly
\( \displaystyle \frac{(n-k)\alpha}{k-1}+r=\beta. \)
Every composition has size at most \(k\). The composition indexed by \(C\) covers \(E\), and every other composition contains \(h\). Hence everyone receives utility \(m\). All intensities are rational.
We have proved:
A rational full-utility allocation exists if and only if the Set Cover instance is a yes-instance.
Suppose a full-utility allocation \(z\) exists. If an allocation \(y\) is not full-utility, then \(z\) Pareto dominates \(y\).
To verify this directly, for each type \(t\) use the coupling
\( \displaystyle \gamma_t=\sum_q q_ty_q\,\delta_{(U(q),m)}. \)
Its first marginal is \(\nu_t^y\), and its second marginal is \(\mu_t\delta_m=\nu_t^z\). Since \(U(q)\leq m\), every coupled member weakly improves. The total strict-improvement mass is
\( \displaystyle \sum_{q:U(q)<m}|q|y_q, \)
which is positive precisely when \(y\) is not full-utility. Therefore, whenever a cover exists, every Pareto-optimal allocation is full-utility.
Now assume a polynomial-time solver returns a Pareto-optimal allocation for the constructed society. Its explicit output contains a positive composition without \(h\), by Section 2. Choose any such composition \(q\).
Thus checking whether \(U(q)=m\) decides Set Cover. The construction and decoding are polynomial-time; a polynomial-time solver necessarily produces an output of polynomial length. This proves the claimed \(\mathsf{NP}\)-hardness.
For completeness, the implicit composition set can be reduced without enumerating integers up to \(\kappa\).
For every nonempty type subset \(A\subseteq T\) with \(d=|A|\leq\kappa\), and every \(a\in A\), define
\( \displaystyle r^{A,a}=\mathbf1_A+(\kappa-d)e_a. \)
These compositions have size exactly \(\kappa\) and support exactly \(A\). Let \(\mathcal R\) be their collection. Its size is at most
\( \displaystyle N=\sum_{d=1}^{\min(\tau,\kappa)}d\binom{\tau}{d} \leq\tau2^{\tau-1}. \)
Consider an arbitrary composition \(q\), with support \(A\), support size \(d\), and total size \(s\).
If \(\kappa=d\), then \(s=d\) and \(q=\mathbf1_A\), already in \(\mathcal R\).
Otherwise \(\kappa>d\). Define, for \(a\in A\),
\( \displaystyle \theta_a=\frac{\kappa q_a/s-1}{\kappa-d}. \)
Because \(q_a\geq1\) and \(s\leq\kappa\), each \(\theta_a\) is nonnegative. Also,
\( \displaystyle \sum_{a\in A}\theta_a =\frac{\kappa-d}{\kappa-d}=1. \)
An intensity \(y\) of composition \(q\) can be replaced by intensities \(ys\theta_a/\kappa\) of \(r^{A,a}\), because
\( \displaystyle \sum_{a\in A}\frac{ys}{\kappa}\theta_a r^{A,a} =yq. \)
All these compositions have the same support and hence the same utility. The replacement preserves each type’s member mass at that utility, so it preserves all utility measures. Rational intensities remain rational.
Applying this replacement to every positive composition proves that restricting to \(\mathcal R\) preserves every attainable utility profile.
Define total welfare by
\( \displaystyle W(y)=\sum_q |q|U(q)y_q =\sum_t\int u\,d\nu_t^y(u). \)
For any Pareto-dominating allocation \(z\), its couplings give
\( \displaystyle W(z)-W(y)=\sum_t\int(v-u)\,d\gamma_t(u,v)>0. \)
The strict inequality follows because utilities are integers, so \(v-u\geq1\) on strictly improving pairs of positive total mass.
Therefore, any welfare maximizer is Pareto optimal. By the preservation argument, it suffices to solve the explicit rational linear program
\( \displaystyle \max\left\{ \sum_{r\in\mathcal R}\kappa U(r)y_r: \sum_{r\in\mathcal R}r_ty_r=\mu_t\ \text{for every }t,\quad y_r\geq0 \right\}. \)
It is feasible: use composition \(\kappa e_t\) with intensity \(\mu_t/\kappa\) for each type. It is bounded, since summing its constraints gives \(\sum_r y_r=1/\kappa\). Hence it has a rational optimal vertex.
Such a vertex has at most \(\tau\) positive variables. Otherwise its positive columns would be linearly dependent, permitting sufficiently small perturbations in both directions while preserving feasibility, contrary to extremality.
Generating \(\mathcal R\), computing its utilities, and solving the rational linear program takes
\( \displaystyle \operatorname{poly}(N,m,\tau,L) =2^{O(\tau)}\operatorname{poly}(m,\tau,L). \)
Every composition count uses \(O(\log(\kappa+1))\) bits. Thus this algorithm’s dependence on the numerical capacity is through its binary encoding.
For fixed \(\kappa\), the bound on \(N\) gives running time
\( \displaystyle \tau^{O(\kappa)}\operatorname{poly}(m,L), \)
which is polynomial in \(L\) when \(\kappa\) is fixed.
Finally, an optimal vertex has at most \(\tau\) positive intensities. After clearing input denominators, their defining basis matrix has integer entries bounded by \(\kappa\). Cramer’s rule and the determinant bound \(r!\kappa^r\) for a basis of size \(r\leq\tau\) give an encoding length of
\( \displaystyle O\!\left(L+\tau\log(\tau\kappa+1)\right) \)
per intensity. Including the composition vectors, the complete output has
\( \displaystyle O\!\left(\tau L+\tau^2\log(\tau\kappa+1)\right) \)
bits. Hence the hardness persists despite the guaranteed existence of polynomial-length Pareto-optimal allocations.
⟨structured verdict parsed — rendered above⟩
The reduction correctly establishes \(\mathsf{NP}\)-hardness for rational mass allocations, using one solver call and allowing every valid Pareto-optimal output. The composition replacement, welfare argument, and encoding bounds also check out.
The only issue is a minor algorithmic exposition gap: the claimed running time and sparse output require an exact polynomial-time LP procedure that returns an optimal vertex. The write-up establishes the existence of such a vertex but does not explicitly state the algorithmic result used to obtain it.
I interpret “binary-rational intensities” as rational numbers represented by binary-encoded numerators and denominators, consistent with the task’s explicit allowance of rational intensities. A requirement that intensities themselves be dyadic would require separate treatment.
The preprocessing preserves the decision answer:
Thus the restricted decision problem remains \(\mathsf{NP}\)-complete. Distinct proper subsets ensure that the constructed candidate types and universal type are all distinct.
Assessment: Correct.
Since \(D>kn(n-1)\), the rounding definition gives
\(\frac{k-1}{kn}<\alpha\leq\frac{k-1}{kn}+\frac1D\).
The endpoint difference is correctly computed:
\(\frac{k-1}{k(n-1)}-\frac{k-1}{kn}=\frac{k-1}{kn(n-1)}\).
Because \(k\geq2\), that difference is strictly greater than \(1/D\). Hence the claimed strict upper bound on \(\alpha\) follows.
The positivity calculation also holds:
\(n\alpha<\frac{n(k-1)}{k(n-1)}<1\), where the final inequality is equivalent to \(n>k\). Therefore \(\beta>0\).
The lower bound gives \(n\alpha>(k-1)/k\), so \(\beta<1/k\).
Both \(\alpha\) and \(\beta\) are dyadic. Under \(k<n\), the denominator \(D\) has \(O(\log n)\) bits, validating the mass encoding bound and the overall bound \(L=O(nm+n\log n)\).
Assessment: Correct; all inequalities and bit bounds check out.
Summing the feasibility constraints gives \(\sum_q|q|y_q=1\).
The displayed bound on member mass in compositions containing \(h\) is valid:
Consequently, member mass in such compositions is at most \(k\beta<1\). Some positive composition must therefore omit \(h\).
Repeated types cause no difficulty. A composition omitting \(h\) contains at most \(k\) distinct candidate types, because its total size is at most \(k\).
Assessment: Correct.
For the forward implication, a positive composition without \(h\) must exist. If the allocation is full-utility, its candidate types cover \(E\), yielding a cover of size at most \(k\).
For the reverse implication:
The residual intensity calculation is correct:
\(r=1-\frac{k(n-1)\alpha}{k-1}>0\).
Every composition respects capacity, and every composition has utility \(m\). The resulting intensities are rational with finite encodings.
The equivalence between full-utility compositions and measures \(\nu_t=\mu_t\delta_m\) also holds: every positive composition has at least one member, so a submaximal composition would place positive mass below \(m\) in some type’s measure.
Assessment: Correct.
The proposed coupling has first marginal \(\nu_t^y\) and second marginal \(\mu_t\delta_m\). Its support satisfies \(v\geq u\).
Its total strict-improvement mass is exactly
\(\sum_{q:U(q)<m}|q|y_q\),
which is positive precisely when \(y\) is not full-utility.
Therefore, on a yes-instance, every Pareto-optimal allocation is full-utility. On a no-instance, no composition without \(h\) can have utility \(m\).
The decoder can select any listed positive composition without \(h\), whose existence was proved independently of Pareto optimality. Computing its utility is polynomial in its explicit encoding and the input size.
The reduction correctly uses polynomial output length only when assuming a polynomial-time solver. It does not assume that all possible Pareto-optimal allocations have short representations.
Assessment: Correct. This establishes the central hardness claim.
For a composition with support \(A\), support size \(d\), and total size \(s\), the case \(\kappa=d\) indeed forces \(s=d\) and \(q=\mathbf1_A\).
When \(\kappa>d\), each \(\theta_a\) is nonnegative because \(\kappa q_a/s\geq1\). Summing the displayed formula gives \(\sum_a\theta_a=1\).
The vector identity checks componentwise. For \(b\in A\), the replaced member mass is
\(\frac{ys}{\kappa}\bigl(1+(\kappa-d)\theta_b\bigr)=yq_b\).
For \(b\notin A\), both sides are zero.
Each replacement composition has exactly the same support as \(q\), so it has the same utility. The replacement preserves each type’s mass at each utility, not merely aggregate feasibility.
The bound \(N\leq\tau2^{\tau-1}\) is correct. When \(d=\kappa\), different choices of \(a\) produce duplicate compositions; this only makes the stated count an overestimate.
Assessment: Correct.
The welfare identity follows directly from the utility measures.
For a dominating allocation, each integrand \(v-u\) is nonnegative. On strictly improving pairs it is at least one, since utilities are integers. Positive total strict-improvement mass therefore implies a strict welfare increase.
Thus every welfare maximizer is Pareto optimal. Utility-profile preservation justifies optimizing over \(\mathcal R\) while retaining Pareto optimality against all original compositions.
The restricted LP is:
Its feasible region is also closed. The existence of a rational optimal vertex is justified.
The support bound is correct: more than \(\tau\) positive columns would be linearly dependent, allowing sufficiently small feasible perturbations in both directions and contradicting extremality.
Assessment: Mathematically correct. Obtaining the optimal vertex algorithmically needs the minor clarification below.
Each column has entries bounded by \(\kappa\), so its coefficient encoding depends on \(\log(\kappa+1)\). Utilities are integers between zero and \(m\). The explicit LP therefore has encoding length polynomial in \(N,m,\tau,L\).
Given an exact polynomial-time procedure returning an optimal vertex, the claimed bounds follow:
The determinant estimate \(r!\kappa^r\) is valid. Clearing input denominators uses \(O(L)\) bits, and choosing an invertible minor for the positive columns supports the stated Cramer’s-rule bound. Consequently, the per-intensity and complete-output encoding bounds are valid.
The general algorithm also handles \(\kappa=1\), \(\tau=1\), and \(m=0\). None of these cases introduces a zero denominator into the replacement argument.
The finite-agent attribution is accurate: Theorem 7 states the cited hardness results for binary expertise. It is contextual and is not used to justify the continuous reduction. [Hedonic Expertise Games](https://arxiv.org/pdf/2011.01778)
Minor — Sections 4–5, exact LP solution and vertex output.
“Solving the rational linear program” does not explicitly specify an optimal-vertex output guarantee. Existence of an optimal vertex alone does not specify how the algorithm produces the claimed output with at most \(\tau\) positive compositions.
Minimum clarification: State the exact polynomial-time rational LP result being invoked, including its guarantee of an optimal basic feasible solution, or specify the standard polynomial-time vertex extraction procedure. Express its running time in the total explicit LP encoding length. All required feasibility, boundedness, and coefficient-size hypotheses are already established.
This is an expositional omission requiring no new mathematics. It does not affect the independently complete hardness reduction.
⟨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.