Answer: \(\mathrm{NP}\)-complete, even for \(N=1\), values in \(\{0,1\}\), and equal positive dyadic activation costs.
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven multiple sellers with cost functions that are constant over non-empty subsets, it is NP-hard to find an assignment that maximizes gains from trade. We provide the proof of this Proposition in the appendix. 3 Efficient Mechanism In this section we describe the main mechanism for most of the settings we study.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite seller set \(J\), buyer types \(T\) with rational masses \(\mu_t\geq 0\) summing to \(1\), per-type values \(v_{tj}\), fixed activation costs \(\kappa_j\), and cohort size \(N\), choose assigned masses \(x_{tj}\geq 0\) and activation variables \(y_j\in\{0,1\}\), with \(\sum_j x_{tj}\leq\mu_t\) and \(x_{tj}\leq\mu_ty_j\), to maximize \(N\sum_{t,j}v_{tj}x_{tj}-\sum_j\kappa_jy_j\).
Let \(J\) be a set of \(m\geq1\) uncapacitated sellers. A society is given by its support: a list \(T\) of \(\tau\geq1\) buyer types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has binary-rational values \(v_{tj}\in[0,1]\). Each seller has a nonnegative binary-rational activation cost \(\kappa_j\), independent of the positive mass served; an inactive seller incurs zero cost. The cohort size \(N\geq1\) is a binary-encoded integer.
An allocation consists of divisible masses \(x_{tj}\geq0\) and activation variables \(y_j\in\{0,1\}\), satisfying \(\sum_{j\in J}x_{tj}\leq\mu_t\) and \(x_{tj}\leq\mu_ty_j\). Mass may remain unserved. Its welfare is \(W(x,y)=N\sum_{t\in T,j\in J}v_{tj}x_{tj}-\sum_{j\in J}\kappa_jy_j\).
Given a binary-rational threshold \(B\), let \(L\) denote the total input bit length, including \(N\) and \(B\).
Is deciding whether some feasible allocation has \(W(x,y)\geq B\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite unit-demand buyers, maximizing gains from trade is NP-hard even when each seller's cost is constant on nonempty buyer sets and zero on the empty set ([source](https://arxiv.org/abs/1809.02718v2)). That result concerns indivisible buyers and does not state a complexity classification for the divisible-mass formulation above.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when \(N=1\), every value belongs to \(\{0,1\}\), and all activation costs are equal positive dyadic rationals.
For an active seller set \(S\subseteq J\), define
\[
a_t(S)=\max\bigl(\{0\}\cup\{v_{tj}:j\in S\}\bigr),
\qquad
F(S)=N\sum_{t\in T}\mu_ta_t(S)-\sum_{j\in S}\kappa_j.
\]
For any allocation whose active set is \(S\), inactive sellers receive no mass. Consequently, for each type \(t\),
\[
\sum_{j\in J}v_{tj}x_{tj}
\leq a_t(S)\sum_{j\in S}x_{tj}
\leq a_t(S)\mu_t.
\]
Thus its welfare is at most \(F(S)\).
This bound is attainable. Whenever \(a_t(S)>0\), assign all of type \(t\)'s mass to a seller attaining that maximum; otherwise leave the type unserved. These assignments are jointly feasible because sellers are uncapacitated. Therefore,
\[
\max_{(x,y)\text{ feasible}}W(x,y)=\max_{S\subseteq J}F(S).
\]
Divisibility hence leaves a discrete optimization problem over active seller sets.
A certificate is the active set \(S\), encoded by \(m\) bits. The verifier computes \(F(S)\) and checks whether \(F(S)\geq B\).
Computing all maxima takes \(O(m\tau)\) rational comparisons. The subsequent products, sums, and threshold comparison can be performed exactly in polynomial time: multiplying denominators gives a common denominator with polynomial bit length, and the binary encoding of \(N\) contributes only its input bit length. By Section 1, the verifier accepts exactly those instances admitting a feasible allocation of welfare at least \(B\).
We use the standard \(\mathrm{NP}\)-complete Vertex Cover problem: given an explicitly represented finite simple graph \(G=(V,E)\) and an integer \(k\), decide whether some \(S\subseteq V\) with \(|S|\leq k\) contains an endpoint of every edge. This is Karp’s “Node Cover” problem. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Write \(m=|V|\) and \(n=|E|\). We may restrict to \(n\geq1\) and \(0\leq k\leq m\): instances outside these restrictions are immediately decidable and can be replaced by fixed yes- or no-instances satisfying them.
Choose powers of two \(q\) and \(r\) such that \(q\) is the smallest power of two at least \(n\), and \(r\) is the smallest power of two strictly greater than \(m\).
Construct the welfare instance as follows:
All masses are positive dyadic rationals, each is at least \(1/q\), and their sum is
\[
\frac{n-1}{q}+\frac{q-n+1}{q}=1.
\]
Every value belongs to \(\{0,1\}\). Distinct edges have distinct endpoint sets, so the constructed types are distinct even if “support” requires distinct value vectors.
The construction has polynomial size. Indeed, \(q<2n\) and \(r\leq2m\); all numerical parameters require \(O(\log(n+1)+\log(m+1))\) bits, and the value matrix has \(mn\) entries.
For \(S\subseteq V\), let \(C(S)\) be the set of edges having at least one endpoint in \(S\). Section 1 gives
\[
F(S)=\sum_{i:e_i\in C(S)}\mu_i-\varepsilon|S|.
\]
If the graph has a vertex cover of size at most \(k\): activate that cover \(S\). Every type then has an active seller of value \(1\), so
\[
F(S)=1-\varepsilon|S|
\geq1-\varepsilon k=B.
\]
The attaining allocation from Section 1 is a feasible witness.
If the welfare instance admits welfare at least \(B\): let \(S\) be the active set of such an allocation. Section 1 implies \(F(S)\geq B\).
Suppose some edge is uncovered. Its type has mass at least \(1/q\), so nonnegative activation costs imply
\[
F(S)\leq1-\frac1q.
\]
But \(k\leq m<r\), and therefore
\[
1-\frac1q
<
1-\frac{k}{qr}
=B.
\]
This contradicts \(F(S)\geq B\). Hence \(S\) covers every edge.
For a cover, \(F(S)=1-\varepsilon|S|\). Comparing this with \(B=1-\varepsilon k\), and using \(\varepsilon>0\), gives \(|S|\leq k\).
Thus the graph has a vertex cover of size at most \(k\) if and only if the constructed welfare instance admits welfare at least \(B\).
The reduction proves \(\mathrm{NP}\)-hardness, and the active-set certificate proves membership in \(\mathrm{NP}\). Therefore the divisible-mass decision problem is \(\mathrm{NP}\)-complete. A polynomial-time algorithm in \(m,\tau,L\) exists if and only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The argument establishes \(\mathrm{NP}\)-completeness for the stated divisible-mass formulation, including the claimed restriction to \(N=1\), values in \(\{0,1\}\), and equal positive dyadic activation costs.
No major or minor mathematical issues were found.
The definition of \(a_t(S)\) is valid for every active set. Including zero in the maximum handles \(S=\varnothing\). The task’s nonnegative values ensure \(a_t(S)\geq0\).
The welfare upper bound is correct. For an inactive seller, \(y_j=0\) and the feasibility constraints force \(x_{tj}=0\). For active sellers, \(v_{tj}\leq a_t(S)\); multiplying by nonnegative allocations and summing preserves this inequality. The type-mass constraint then gives the claimed bound. Multiplication by \(N\geq1\) also preserves it.
Attainability is justified. Whenever \(a_t(S)>0\), a maximizing seller exists because \(S\) is finite. Assigning that seller the entire mass \(\mu_t\) satisfies both allocation constraints. Assignments for different types do not compete for capacity. Leaving types with zero maximum unserved achieves their zero contribution.
The construction may activate sellers that receive no mass. This is permitted by the formal constraints, and their activation costs are included in \(F(S)\). Thus it does not invalidate attainability.
Consequently, the equality between the continuous allocation optimum and the maximum over active sets is established, including the empty-set case.
The certificate is sufficient. An active set has an encoding of \(m\) bits. Section 1 establishes both necessary directions: any feasible allocation is bounded by its active-set value, and every active-set value is attainable. Therefore an allocation certificate is unnecessary.
Exact verification has polynomial bit complexity. The number of rational comparisons and arithmetic operations is polynomial. Each selected maximum is an input value or zero. Products of input denominators have bit length bounded by the sum of their bit lengths; multiplication by the binary-encoded \(N\) increases bit length by at most its encoding length. Summation and comparison with \(B\) therefore remain polynomial-time operations.
This argument covers arbitrary permitted rational inputs, rather than only the dyadic instances used for hardness.
The invoked theorem is appropriate. The prover states the standard decision version of Vertex Cover precisely: an explicitly represented finite simple graph and an integer bound, with the question whether at most that many vertices cover every edge. Its \(\mathrm{NP}\)-completeness is the cited classical Node Cover result. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
The restrictions preserve hardness. Instances with no edges or with the bound outside \(0\leq k\leq m\) are immediately decidable, as stated. Their replacement by fixed instances of the appropriate answer is a routine valid preprocessing step. With at least one edge in a simple graph, the construction has sufficiently many vertices to satisfy the seller requirement.
Masses satisfy the task exactly. Since \(q\geq n\), the final numerator \(q-n+1\) is positive. Every mass is at least \(1/q\), and the displayed sum is exactly one. For \(n=1\), the construction gives a single type of mass one.
The numerical restrictions hold. Both \(q\) and \(r\) are powers of two, so all masses and the common positive cost \(1/(qr)\) are dyadic. The threshold is dyadic as well. Values and \(N\) satisfy the claimed restrictions.
Support size is handled correctly. In a simple graph, distinct edges have distinct endpoint sets, hence distinct value vectors. Thus the construction remains valid if support types must be distinct.
Polynomial size is justified. The bounds \(q<2n\) and \(r\leq2m\) hold, including when \(n\) or \(m\) is a power of two. The encoded numerical parameters have logarithmic bit length, and the explicit value matrix has \(mn\) entries. These are polynomial in the explicitly represented source input.
For a vertex cover, every type has maximum value one among active sellers. Its benefit is therefore exactly the total mass, namely one. Subtracting the activation costs gives the displayed expression for \(F(S)\).
The inequality resulting from \(|S|\leq k\) has the correct direction because \(\varepsilon>0\). Section 1 supplies the feasible attaining allocation.
Passing from an allocation to \(F(S)\) is valid. The allocation’s welfare cannot exceed \(F(S)\), so welfare at least \(B\) implies \(F(S)\geq B\).
The uncovered-edge bound is correct. An uncovered type contributes zero and has mass at least \(1/q\). All other types together contribute at most \(1-1/q\). Nonnegative activation costs can only decrease welfare.
The strict separation is correct. The condition \(k\leq m<r\) implies \(k/(qr)<1/q\), giving exactly the strict threshold inequality written in the proof. It remains strict when \(k=0\) and when \(k=m\).
Thus every qualifying active set covers all edges. For a cover, comparison with the threshold and positivity of \(\varepsilon\) correctly imply \(|S|\leq k\).
The construction is a polynomial-time many-one reduction with both directions established. Together with membership in \(\mathrm{NP}\), it proves the claimed classification. The final conditional statement about polynomial-time solvability and \(\mathrm{P}=\mathrm{NP}\) follows.
No repair or additional mathematical clarification is required. The result directly addresses the divisible-mass problem; it does not rely on transferring the cited indivisible-buyer hardness result.
⟨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.