Answer: Continuous welfare optimization is \(\mathrm{NP}\)-hard, and pricing is \(\mathrm{NP}\)-complete. Both hardness results hold already for \(\tau=1\) with deterministic success; pricing remains hard at zero prices.
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe GTBM task allocation problem is NP-complete and cannot be approximated to a ratio n1−ǫ in polynomial time unless P = ZPP, where n is the total number of bids and valuations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite task catalogue \(D\), complete requester and performer types \(\mathcal Z\) with rational masses \(\mu_z\), and a fixed trust rule aggregating type-level EQOS reports over those masses, define feasible patterns \(a\) that assign one requester unit to a valuation and cover its tasks using performer units, each selecting at most one XOR cost bid. Let \(r(a)\) be the requester type, \(q_z(a)\) the number of performer units of type \(z\) used, and \(w_a\) the pattern's expected welfare under the trust rule. Find a rational mass assignment \(x_a\geq 0\) maximizing \(\sum_a w_a x_a\), subject to \(\sum_{a:r(a)=z}x_a\leq\mu_z\) and \(\sum_a q_z(a)x_a\leq\mu_z\) for each \(z\). Determine the complexity in the task catalogue size \(M\), support size \(\tau=|\mathcal Z|\), and rational input bit length \(L\), including whether the implicit pattern LP admits efficient pricing.
Let \(D\) be a task catalogue with \(M\geq1\). A society is given by its support: the list \(\mathcal Z\) of \(\tau\) types with positive binary rational masses \(\mu_z\), normalized by \(\sum_z\mu_z=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type \(z\) explicitly lists XOR requester valuations \(v_z(S)>0\) and XOR performer bids \((B,c_z(B))\), for nonempty subsets of \(D\), with nonnegative rational costs. Unlisted valuations, including \(v_z(\varnothing)\), are zero; unlisted cost bids are unavailable. A unit may select at most one valuation and, independently, at most one cost bid.
The input also lists rational EQOS reports \(\eta_h(r,z,t)\in[0,1]\): reporter type \(h\)'s success estimate for performer type \(z\) doing task \(t\) for requester type \(r\). Fix the mass-weighted trust rule \(p_{rzt}=\sum_h\mu_h\eta_h(r,z,t)\), and assume independent task successes.
A pattern \(a\) selects one requester unit of type \(r(a)\), one of its listed bundles \(S_a\), and performer units indexed by \(j\), of types \(z_j\). The nonempty sets \(T_j\) partition \(S_a\); unit \(j\) selects one listed bid \(B_j\supseteq T_j\), paying its full cost. Surplus tasks in \(B_j\) may be discarded. Multiple performer units may have the same type. Put \(q_z(a)=|\{j:z_j=z\}|\), and let \(\sigma_a(t)\) be the type assigned task \(t\).
The pattern welfare is \(w_a=\sum_{U\subseteq S_a}v_{r(a)}(U)\prod_{t\in U}p_{r(a),\sigma_a(t),t}\prod_{t\in S_a\setminus U}(1-p_{r(a),\sigma_a(t),t})-\sum_j c_{z_j}(B_j)\); costs are incurred irrespective of success.
Optimize \(\max_{x\geq0}\sum_a w_ax_a\), subject to \(\sum_{a:r(a)=z}x_a\leq\mu_z\) and \(\sum_a q_z(a)x_a\leq\mu_z\) for every \(z\), allowing unused mass. Patterns are implicit. Pricing, for nonnegative rational dual prices \(u_z,d_z\), asks whether \(\max_a\{w_a-u_{r(a)}-\sum_z d_zq_z(a)\}>0\).
Is this continuous welfare optimization problem solvable in polynomial time in \(M,\tau,L\), or is it NP-hard? Is its pricing problem polynomial-time solvable or NP-hard, including the bit length of the supplied prices?
The discrete GTBM allocation decision problem is NP-complete, and its welfare optimization is NP-hard ([Ramchurn et al., 2009](https://eprints.soton.ac.uk/267288/1/ramchurn09a.pdf)).
No result settling exactly this mass-pattern formulation was located in the literature search.
The continuous welfare optimization problem is \(\mathrm{NP}\)-hard. Its pricing decision problem is \(\mathrm{NP}\)-complete, including the bit length of the supplied prices.
Both hardness results hold already with \(\tau=1\), mass \(1\), deterministic success, one listed requester valuation, and all performer bids having cost \(1\).
We use the standard \(\mathrm{NP}\)-complete Set Cover problem: given a nonempty universe \(D\), explicitly listed nonempty subsets \(B_1,\ldots,B_n\), and a nonnegative integer \(K\), decide whether at most \(K\) of these sets cover \(D\). See [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may restrict to instances satisfying \(\bigcup_i B_i=D\). Indeed, empty sets can be deleted, and an uncovered element certifies a no-instance, which can be mapped to the fixed coverable no-instance consisting of one element, its singleton set, and budget \(0\). An empty universe can similarly be mapped to a fixed yes-instance.
Let \(M=|D|\), and let \(\kappa\) denote the minimum number of sets covering \(D\). Construct the following society:
Thus \(p_{zzt}=1\) for every task. These are valid EQOS reports under the specified mass-weighted trust rule, and deterministic successes satisfy the independence assumption.
The construction has polynomial size. In particular, the numerator of \(V=(2K+1)/2\) has bit length linear in the bit length of \(K\).
Every pattern requests \(D\). If it uses \(q\) performer units, all tasks succeed and its welfare is
\[ w_a=V-q. \]
Here and below, each performer unit selects just one bid; different units of the same type may select different bids, as expressly permitted in the question.
Lemma. The minimum number of performer units in a pattern is exactly \(\kappa\).
Proof. Suppose a pattern uses bids \(B_{i_1},\ldots,B_{i_q}\), assigned respective nonempty sets \(T_1,\ldots,T_q\). Since these assigned sets partition \(D\) and \(T_j\subseteq B_{i_j}\), we have
\[ D=\bigcup_{j=1}^{q}T_j\subseteq\bigcup_{j=1}^{q}B_{i_j}. \]
Consequently, its selected bids cover \(D\). Removing repetitions gives a cover using at most \(q\) listed sets, so \(q\geq\kappa\).
Conversely, choose a minimum cover \(B_{i_1},\ldots,B_{i_\kappa}\). Each selected set has a private element: for every \(j\), there is some
\[ t_j\in B_{i_j}\setminus\bigcup_{\ell\ne j}B_{i_\ell}. \]
Otherwise that set could be deleted while preserving coverage, contradicting minimality. These private elements are distinct.
Assign \(t_j\) to performer unit \(j\), and assign each remaining task to any selected set containing it. This produces a partition into nonempty sets \(T_j\subseteq B_{i_j}\), hence a valid pattern with exactly \(\kappa\) performer units. Surplus bid tasks are discarded, as allowed. \(\square\)
Supply the nonnegative prices \(u_z=d_z=0\). By the lemma,
\[ \max_a\left\{w_a-u_{r(a)}-\sum_zd_zq_z(a)\right\} =V-\kappa. \]
Because \(\kappa\) and \(K\) are integers,
\[ V-\kappa>0 \quad\Longleftrightarrow\quad K+\frac12-\kappa>0 \quad\Longleftrightarrow\quad \kappa\leq K. \]
Thus the pricing decision answers the Set Cover instance. This proves \(\mathrm{NP}\)-hardness even when all supplied prices are zero and therefore have constant bit length.
We now analyze the continuous program directly.
There is only one type, so its two capacity constraints are
\[ \sum_a x_a\leq1, \qquad \sum_a q(a)x_a\leq1, \]
where \(q(a)\) is the number of performer units in pattern \(a\). Every pattern has \(q(a)\geq\kappa\geq1\).
Define
\[ R=\max\left\{0,\frac{V}{\kappa}-1\right\}. \]
For every pattern, since \(V>0\) and \(q(a)\geq\kappa\),
\[ \frac{w_a}{q(a)} =\frac{V}{q(a)}-1 \leq\frac{V}{\kappa}-1 \leq R. \]
Therefore every feasible allocation satisfies
\[ \sum_a w_ax_a \leq R\sum_a q(a)x_a \leq R. \]
This upper bound also controls every mixture of patterns.
If \(V>\kappa\), use the pattern with \(\kappa\) performer units supplied by the lemma, and give it mass \(x_a=1/\kappa\). Its requester usage is \(1/\kappa\leq1\), and its performer usage is \(\kappa(1/\kappa)=1\). Its welfare is
\[ (V-\kappa)\frac1\kappa =\frac{V}{\kappa}-1 =R. \]
If \(V\leq\kappa\), all pattern welfares are nonpositive, and the zero allocation attains \(R=0\).
Hence the exact continuous optimum is
\[ \operatorname{OPT} =\max\left\{0,\frac{K+\frac12}{\kappa}-1\right\}. \]
In particular,
\[ \operatorname{OPT}>0 \quad\Longleftrightarrow\quad \kappa\leq K. \]
Thus even deciding whether the continuous optimum is positive is \(\mathrm{NP}\)-hard. Exact welfare optimization is consequently \(\mathrm{NP}\)-hard.
Consider an arbitrary instance, and let \(H\) be the total bit length of the supplied prices.
A certificate for a yes-instance is a pattern. Its performer units receive nonempty disjoint sets, so it has at most \(|S_a|\leq M\) performer units. The certificate specifies the requester and valuation indices, each performer’s type and bid index, and the assigned task sets. Its length is polynomial in \(M,\tau,L\).
The verifier checks that the requester valuation and all bids are listed, that the assigned sets partition the requested bundle, and that each assigned set is contained in its selected bid.
Let \(\mathcal V_r\) denote the explicitly listed valuation bundles of requester type \(r\). Since unlisted valuations vanish, the expected value can be evaluated as
\[ \sum_{\substack{U\in\mathcal V_{r(a)}\\U\subseteq S_a}} v_{r(a)}(U) \prod_{t\in U}p_{r(a),\sigma_a(t),t} \prod_{t\in S_a\setminus U} \left(1-p_{r(a),\sigma_a(t),t}\right). \]
This enumerates only explicitly listed valuations. Each probability is a sum of \(\tau\) rational products, and each summand in the displayed expression has at most \(M\) probability factors.
All arithmetic is exact and has polynomial bit complexity. Products have numerator and denominator bit lengths bounded by the sums of the corresponding input bit lengths; sums of polynomially many rationals likewise admit polynomial bit-length bounds using products of their denominators. Subtracting the costs and supplied prices preserves these bounds. The verifier can therefore check strict positivity of the reduced welfare in time polynomial in \(M,\tau,L,H\).
Pricing is in \(\mathrm{NP}\), and Section 3 proves its \(\mathrm{NP}\)-hardness. Hence it is \(\mathrm{NP}\)-complete.
The reduction and the exact optimum calculation settle the specified mass-pattern formulation. Neither problem admits the requested polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions correctly: continuous welfare optimization is \(\mathrm{NP}\)-hard, and pricing is \(\mathrm{NP}\)-complete with the supplied prices included in the input length. No major or minor mathematical issues were found.
The prover states the standard Set Cover decision problem precisely: an explicitly represented universe and family of sets, together with an integer budget, asking whether a cover within that budget exists. Its cited NP-completeness theorem is appropriate. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
The restriction to nonempty, coverable universes preserves hardness:
Consequently, the minimum cover size \(\kappa\) exists and satisfies \(1\leq\kappa\leq M\).
The constructed society satisfies the task’s requirements. Its mass is positive and normalized; its sole valuation \(V=K+\frac12\) is positive, including when \(K=0\); all bids have nonempty bundles and admissible costs; and the reports give success probability one. Deterministic successes satisfy independence.
The construction is polynomial in the source input length. Encoding \(V\) requires only the bit length of \(K\) plus a constant overhead.
Every pattern requests \(D\), since it is the only listed valuation bundle. With deterministic success, the welfare expression contributes exactly \(V\) in expected requester value. Each of the \(q\) performer units incurs cost one, so \(w_a=V-q\).
This calculation respects the stipulated XOR restrictions: each performer unit chooses one bid, while distinct units may share a type.
Both directions of the lemma are valid.
A pattern’s selected bids cover \(D\), because its assigned sets partition \(D\) and lie within those bids. Removing repeated bids therefore yields a cover with at most \(q\) sets, proving \(q\geq\kappa\).
Conversely, every set in a minimum-cardinality cover has an element absent from all other selected sets. Otherwise that set could be removed, contradicting minimum cardinality. Those private elements are distinct. The described assignment therefore gives every performer a nonempty assigned set and assigns every remaining task to a containing bid.
Thus the minimum feasible performer count is exactly \(\kappa\). No additional lemma is needed.
At zero prices, the maximum reduced welfare is \(V-\kappa\). Since \(K\) and \(\kappa\) are integers,
\[ K+\frac12-\kappa>0 \quad\Longleftrightarrow\quad \kappa\leq K. \]
The strict inequality and its boundary cases are handled correctly. This establishes a polynomial reduction to pricing with constant-length prices.
The two capacity constraints are exactly those specified by the task for its single type.
For each pattern, division by \(q(a)\) is valid because \(q(a)\geq\kappa\geq1\). The inequality
\[ \frac{w_a}{q(a)} \leq\frac{V}{\kappa}-1 \leq R \]
is correct because \(V>0\). Multiplication by nonnegative allocation weights and summation give the asserted upper bound. The final inequality uses \(R\geq0\), so it remains valid when all pattern welfares are nonpositive.
When \(V>\kappa\), the allocation of mass \(1/\kappa\) to a minimum-performer pattern satisfies both constraints and attains \(R\). When \(V\leq\kappa\), the zero allocation attains the upper bound zero.
The exact optimum formula and its positivity equivalence therefore follow. This directly establishes continuous optimization hardness without relying on an unproved connection between pricing and optimization.
The certificate bound is valid: disjoint, nonempty assigned sets imply at most \(M\) performer units. All selected indices and task assignments have polynomial encoding length, and every structural condition can be checked in polynomial time.
The expected-value calculation correctly enumerates only listed valuation bundles contained in the requested bundle. Every omitted valuation is zero by the task’s definition, so exponential enumeration of success subsets is unnecessary.
There are polynomially many rational operations. Each trust probability uses at most \(\tau\) products, and each expected-value term uses at most \(M\) probability factors. The stated denominator-product bounds justify polynomial intermediate bit lengths. Including costs and supplied prices preserves polynomial complexity in \(M,\tau,L,H\). Strict positivity is therefore exactly verifiable in polynomial time.
Together with the reduction, this proves pricing is \(\mathrm{NP}\)-complete.
None. The claimed restricted hardness results and both complexity conclusions are established as written.
⟨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.