Answer: \(\mathrm{NP}\)-complete
Theorem 5.3 — class: hardness
Given goods \(G\), a finite type support \(T\) with rational masses \(\mu_t\), budgets \(b_t\), and desired bundles \(D_t\), rational per-capita supplies \(q_g\), and threshold \(\kappa\), does there exist a price vector \(p\geq 0\) and nonnegative masses \(x_{t,S}\) assigned to integral bundles \(S\subseteq G\) such that \(\sum_S x_{t,S}=\mu_t\), \(\sum_{t,S:g\in S}x_{t,S}\leq q_g\), every bundle receiving positive mass is affordable and utility-maximizing for its type under \(v_t(S)=1\) iff \(D_t\subseteq S\), and \(\sum_{t,S}x_{t,S}v_t(S)\geq\kappa\)?
Let \(G\) contain \(m\geq1\) goods. A society is given by its support: the list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a positive binary-rational per-person budget \(b_t\) and a nonempty desired bundle \(D_t\subseteq G\), with \(v_t(S)=\mathbf{1}\{D_t\subseteq S\}\). Budgets of distinct types are pairwise distinct. Supplies \(q_g\geq0\) and the threshold \(\kappa\in[0,1]\) are binary rationals; \(L\) is the total input bit length.
A feasible outcome consists of finite real prices \(p\in\mathbb{R}_{\geq0}^{m}\) and real masses \(x_{t,S}\geq0\) on integral bundles \(S\subseteq G\), including the empty bundle, satisfying \(\sum_{S\subseteq G}x_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni g}x_{t,S}\leq q_g\) for every good.
Write \(p(S)=\sum_{g\in S}p_g\). Whenever \(x_{t,S}>0\), require \(p(S)\leq b_t\) and \(v_t(S)=\max\{v_t(R):R\subseteq G,\ p(R)\leq b_t\}\). Any utility-maximizing affordable bundle may be assigned; budgets apply separately to each recipient, rather than to average spending. Unused supply is permitted without a restriction on its price, and budgets need not be exhausted.
Is deciding whether such an outcome exists with \(\sum_t\sum_{S\subseteq G}x_{t,S}v_t(S)\geq\kappa\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite agents with pairwise distinct positive budgets, deciding whether a single-minded market admits an equilibrium meeting a welfare threshold is NP-complete ([Lev et al.](https://arxiv.org/html/2012.14838v3)).
For a different continuous model—divisible goods allocated to finitely many single-minded agents with equal budgets—a competitive allocation can be computed in polynomial time ([Brânzei, Lv and Mehta](https://www.ijcai.org/Proceedings/16/Papers/025.pdf)); this does not settle the mass model with integral recipient bundles. No result settling this exact formulation was located.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when all type masses are equal dyadic rationals and every supply is either zero or equal to one type’s mass.
The proof below gives a reduction directly for the stated mass model. Its use of private goods parallels the finite-agent construction in [Lev et al., Appendix B](https://arxiv.org/html/2012.14838v3#A2).
For nonnegative prices \(p\), define the set of affordable types by
\(A(p)=\{t:p(D_t)\leq b_t\}\).
Lemma. At prices \(p\), a feasible outcome exists if and only if
\(\displaystyle \sum_{\substack{t\in A(p)\\g\in D_t}}\mu_t\leq q_g\)
for every good \(g\). Whenever an outcome exists at these prices, its welfare is exactly
\(\displaystyle \sum_{t\in A(p)}\mu_t\).
Proof. If \(t\in A(p)\), the desired bundle \(D_t\) is affordable and gives utility one. Consequently, every bundle assigned positive mass to this type must have utility one and therefore contain \(D_t\). Its entire mass \(\mu_t\) is satisfied and consumes at least \(\mu_t\) units of each good in \(D_t\).
If \(t\notin A(p)\), no affordable bundle can contain \(D_t\): nonnegative prices imply \(p(S)\geq p(D_t)>b_t\) whenever \(D_t\subseteq S\). Thus every recipient of this type has utility zero.
These observations prove the necessary supply inequalities and the welfare formula. Conversely, if the inequalities hold, assign bundle \(D_t\) to the entire mass of each affordable type and the empty bundle to every other type. These assignments are affordable, utility-maximizing, and satisfy every supply constraint. This proves the lemma.
In particular, allowing a type’s allocation to be split among bundles does not allow only part of that type to be satisfied.
We reduce from the standard \(\mathrm{NP}\)-complete Independent Set problem: given a simple undirected graph \(H=(V,E)\) with \(n\geq1\) vertices and an integer \(1\leq K\leq n\), decide whether it has an independent set of size at least \(K\).
Label the vertices \(1,\ldots,n\). Let \(N\) be the smallest power of two satisfying \(N\geq n\). Thus \(N\leq2n\).
Create the following goods:
Create exactly \(N\) types, with
\(\displaystyle \mu_i=\frac1N,\qquad b_i=i.\)
For vertex types \(1\leq i\leq n\), set
\(\displaystyle D_i=\{h_i\}\cup\{a_e:e\text{ is incident to vertex }i\}.\)
For dummy types \(n<i\leq N\), set \(D_i=\{h_i\}\).
Supplies are
\(\displaystyle q_{a_e}=\frac1N,\qquad q_{h_i}=\begin{cases}\frac1N,&i\leq n,\\0,&i>n.\end{cases}\)
Finally, set \(\kappa=K/N\).
Every desired bundle is nonempty. All masses and budgets are positive, the masses sum to one, and the budgets are pairwise distinct. Because \(N\) is a power of two, the masses, supplies, and threshold are dyadic rationals. The construction has \(m=|E|+N\) goods and \(\tau=N\) types, with total encoding length polynomial in the graph’s encoding length.
Suppose \(I\subseteq V\) is independent and \(|I|\geq K\). Set
\(\displaystyle p_{a_e}=0\quad(e\in E),\qquad p_{h_i}=\begin{cases}0,&i\in I,\\N+1,&i\notin I.\end{cases}\)
All prices are finite and nonnegative.
For \(i\in I\), the desired bundle costs zero, so it is affordable. For every other type, its desired bundle contains its private good priced at \(N+1>b_i\), so it is unaffordable. Hence \(A(p)=I\).
Each selected private good is demanded by mass \(1/N\), exactly its supply. Each edge good is demanded by at most one selected endpoint, because \(I\) is independent, so its demand is at most \(1/N\). Dummy private goods have zero demand.
The lemma therefore gives a feasible outcome of welfare
\(\displaystyle \frac{|I|}{N}\geq\frac K N=\kappa.\)
Conversely, suppose the constructed instance has a feasible outcome meeting the threshold, at prices \(p\).
No dummy type can belong to \(A(p)\). If a dummy type were affordable, the lemma would force its entire mass \(1/N\) to consume its private good, whose supply is zero.
Thus \(A(p)\subseteq V\). If two adjacent vertices \(i,j\) both belonged to \(A(p)\), their types would each consume mass \(1/N\) of the good corresponding to their shared edge. Total consumption would be at least
\(\displaystyle \frac2N>\frac1N=q_{a_{\{i,j\}}},\)
contradicting feasibility. Therefore \(A(p)\) is an independent set.
By the lemma, welfare equals \(|A(p)|/N\). Meeting the threshold implies \(|A(p)|\geq K\).
This proves both directions of the reduction and establishes \(\mathrm{NP}\)-hardness.
We use the standard theorem that rational linear programming is solvable in time polynomial in the numbers of variables and constraints and the total coefficient bit length.
A certificate consists only of a subset \(A\) of the input types. The verifier first checks
\(\displaystyle \sum_{t\in A}\mu_t\geq\kappa,\qquad \sum_{\substack{t\in A\\g\in D_t}}\mu_t\leq q_g\quad\text{for every }g.\)
It remains to determine whether some prices make precisely these types affordable.
Let \(B=1+\max_t b_t\). We may restrict every price to the interval \([0,B]\) without changing any attainable affordability pattern. Indeed, replace each price \(p_g>B\) by \(B\):
Now maximize a variable \(\delta\) subject to
\(0\leq p_g\leq B\quad\text{for every }g,\qquad 0\leq\delta\leq1,\)
\(\displaystyle \sum_{g\in D_t}p_g\leq b_t\quad(t\in A),\)
\(\displaystyle \sum_{g\in D_t}p_g\geq b_t+\delta\quad(t\notin A).\)
This rational linear program has \(m+1\) variables, polynomially many constraints, and polynomial coefficient bit length. Its feasible region is bounded and closed.
If the desired affordability pattern exists, cap its prices as above. When there are excluded types, their finitely many strictly positive unaffordability gaps have a strictly positive minimum. Choosing \(\delta\) to be the smaller of that minimum and one makes the program feasible with \(\delta>0\). If there are no excluded types, take \(\delta=1\).
Conversely, any feasible solution with \(\delta>0\) makes every type in \(A\) affordable and every excluded type strictly unaffordable. Thus the verifier accepts exactly when the program is feasible and its optimal value is positive.
The certificate has \(\tau\) bits, and all verification steps take polynomial time in \(m,\tau,L\). Hence the problem belongs to \(\mathrm{NP}\).
The stated mass model is \(\mathrm{NP}\)-complete, and therefore is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\). The decisive property is that affordability forces satisfaction of an entire type’s mass; fractional allocation across recipients does not remove the combinatorial selection problem.
⟨structured verdict parsed — rendered above⟩
The prover’s argument resolves the exact mass model: the decision problem is \(\mathrm{NP}\)-complete, including under the stated restrictions on masses and supplies. I found no major or minor mathematical issues.
If \(p(D_t)\leq b_t\), utility one is attainable. Utility maximization therefore forces every positive-mass assigned bundle to contain \(D_t\). Since the assigned masses sum to \(\mu_t\), the type contributes welfare exactly \(\mu_t\) and consumes at least \(\mu_t\) of each desired good.
If \(p(D_t)>b_t\), nonnegative prices ensure that every bundle containing \(D_t\) is unaffordable. The type consequently contributes zero welfare.
The converse assignment is also valid: affordable types receive \(D_t\), and excluded types receive the empty bundle. The latter is affordable and utility-maximizing because no affordable bundle gives those types utility one. This establishes both the supply characterization and the exact welfare formula. Fractional splitting introduces no exception.
The restricted Independent Set source problem is the standard \(\mathrm{NP}\)-complete decision problem. The restrictions \(n\geq1\) and \(1\leq K\leq n\) exclude only trivial parameter cases.
The chosen power of two satisfies \(n\leq N\leq2n\). There are \(N\) positive masses, each equal to \(1/N\), so normalization holds. Budgets \(b_i=i\) are positive and pairwise distinct. Private goods ensure every desired bundle is nonempty, including for isolated vertices and dummy types.
Every supply is either zero or \(1/N\), and \(\kappa=K/N\) belongs to \([0,1]\). All these quantities have polynomial-length binary encodings. The goods and bundle descriptions also have polynomial size. In particular, \(m\geq1\) and \(\tau\geq1\) hold even when \(n=1\).
At the specified prices, every selected vertex has desired-bundle cost zero. Every unselected vertex and dummy type has desired-bundle cost \(N+1\), which strictly exceeds its budget \(i\leq N\). Thus the affordability set is exactly \(I\).
Each selected private good consumes exactly its supply. Independence ensures that every edge good is consumed by at most one selected endpoint, hence by mass at most \(1/N\). Dummy goods consume no supply.
The lemma applies and gives welfare \(|I|/N\geq K/N\). Positive prices on unused goods are permitted by the task, so the construction violates no additional price condition.
An affordable dummy type would necessarily consume positive mass \(1/N\) of a zero-supply private good. Therefore no dummy is affordable.
Two affordable adjacent vertices would consume at least \(2/N\) of their shared edge good, exceeding its supply \(1/N\). Hence the affordable vertex types form an independent set.
The lemma gives welfare exactly \(|A(p)|/N\), so meeting the threshold forces \(|A(p)|\geq K\). This establishes the required equivalence without assuming any particular allocation for the alleged feasible outcome.
The bound \(B=1+\max_t b_t\) strictly exceeds every budget. An affordable desired bundle cannot contain a good originally priced above \(B\), so capping preserves its cost.
An excluded desired bundle either remains unchanged or contains a capped good whose new price \(B\) alone exceeds its budget. Nonnegativity prevents other goods from offsetting that price. Thus capping preserves the entire affordability pattern, even when multiple goods are capped.
For any attainable pattern, the finitely many excluded types have strictly positive gaps \(p(D_t)-b_t\). Their minimum is positive, so the prover’s choice of \(\delta\) satisfies every exclusion constraint with \(\delta>0\). The case with no excluded types is explicitly handled by taking \(\delta=1\).
Conversely, a feasible solution with \(\delta>0\) makes all excluded types strictly unaffordable while keeping all included types affordable. The bounded, closed feasible region guarantees attainment of the maximum whenever it is nonempty. Consequently, testing whether the optimum is positive is equivalent to testing attainability of the certified pattern.
The invoked theorem concerns rational linear programming in the binary bit model: feasibility and exact optimization are polynomial-time operations in the dimensions and coefficient encoding length. This standard result supports exact sign testing of the optimum, rather than a numerical tolerance test. See [Bienstock, Del Pia, and Hildebrand, introductory discussion](https://optimization-online.org/wp-content/uploads/2020/11/8105.pdf).
Its hypotheses hold here: the program has \(m+1\) variables, polynomially many rational constraints, and polynomial coefficient bit length. Computing \(B\) and checking the rational welfare and supply sums likewise takes polynomial time.
A certificate consisting of \(\tau\) membership bits is sufficient because its deterministic verifier may run this polynomial-time algorithm. Explicit price or allocation certificates are unnecessary. The lemma supplies the allocation-existence equivalence needed for both completeness and soundness.
The reduction proves \(\mathrm{NP}\)-hardness for the exact formulation, and the verifier proves membership in \(\mathrm{NP}\). The conditional statement about polynomial-time solvability follows correctly.
The private-good comparison is supported by the desired sets used in [Lev et al., Appendix B](https://arxiv.org/html/2012.14838v3#A2). The submitted reduction establishes its own correctness and does not depend on transferring the finite-agent theorem to the mass model.
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.