Answer: Exactly solvable with \(\operatorname{poly}(m,L)\) exact demand queries and bit operations, returning at most \(m+1\) supported bundles; hence admits a PTAS.
Theorem 2 — class: hardness
Given \(m\) goods categories, rational per-capita supplies \(b_j\in[0,1]\), and one agent type with a common normalized, monotone, subadditive valuation \(v:2^{[m]}\to\mathbb{Q}_+\) accessible by demand queries, find a finite-support distribution \(x_S\ge0\) over integral bundles \(S\subseteq[m]\) maximizing \(\sum_S x_Sv(S)\), subject to \(\sum_Sx_S=1\) and \(\sum_{S\ni j}x_S=b_j\) for every category \(j\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here \(\tau=1\), with mass \(1\).
Given \(m\geq1\) goods categories, supplies \(b_j\in\mathbb{Q}\cap[0,1]\), and a common monotone, subadditive valuation \(v:2^{[m]}\to\mathbb{Q}_{\geq0}\) normalized by \(v(\emptyset)=0\), an exact demand query at signed rational prices \(r\in\mathbb{Q}^m\) returns \(\max_{S\subseteq[m]}(v(S)-\sum_{j\in S}r_j)\).
An allocation is an explicitly listed finite-support distribution with rational masses \(x_S\geq0\), satisfying \(\sum_Sx_S=1\) and \(\sum_{S\ni j}x_S=b_j\) for every \(j\in[m]\); empty bundles are allowed. Its welfare is \(W(x)=\sum_Sx_Sv(S)\).
Let \(L\) bound the explicit input length and the binary encoding length of every valuation value. Count demand queries and bit operations separately; running times are measured in \(m,\tau,L\) and the approximation parameter.
Does maximizing \(W(x)\) admit a PTAS using polynomially many exact demand queries and polynomially many bit operations in \(m,\tau,L\) for each fixed \(\varepsilon\in(0,1)\), or is it NP-hard to approximate within some fixed factor \(c>1\), even for valuations with polynomial-time demand implementations?
Discrete average-welfare maximization for identical subadditive valuations is APX-hard even with demand access, and admits a polynomial-time \(40\)-approximation. [Barman–Sundaram](https://arxiv.org/pdf/2005.00504)
On the continuous side, polynomial-time demand-oracle computation of the concave closure—the optimum value of the displayed distribution problem—is already stated in [Shioura’s slides](https://repository.gatech.edu/server/api/core/bitstreams/f178ac64-a159-4d95-865c-2511892ef865/content).
Result. The problem is exactly solvable using polynomially many exact demand queries and polynomially many bit operations in \(m,L\). The algorithm outputs an optimal rational allocation supported on at most \(m+1\) bundles. Consequently, it admits a PTAS.
The argument below includes allocation recovery, since computing only the optimum value would not satisfy the required output model.
1. The allocation LP and its dual. For each bundle \(S\subseteq[m]\), define
\[
\]
\(a_S=(1,\mathbf 1_S)\in\{0,1\}^{m+1}\), and let \(c=(1,b_1,\ldots,b_m)\).
The problem is the finite linear program
\(\displaystyle \mathrm{OPT}=\max\left\{\sum_{S\subseteq[m]}v(S)x_S:\ \sum_{S\subseteq[m]}a_Sx_S=c,\quad x_S\geq0\right\}.\)
Although it has exponentially many variables, it has only \(m+1\) equality constraints.
It is feasible, including when some supplies equal \(0\) or \(1\). To verify this explicitly, order the categories so that
\(b_{\pi(1)}\geq\cdots\geq b_{\pi(m)}\). Put \(\beta_0=1\), \(\beta_i=b_{\pi(i)}\) for \(1\leq i\leq m\), and \(\beta_{m+1}=0\). For \(0\leq k\leq m\), let
\(\displaystyle S_k=\{\pi(1),\ldots,\pi(k)\},\qquad x_{S_k}=\beta_k-\beta_{k+1}.\)
These masses are nonnegative and sum to \(1\). Category \(\pi(i)\) has marginal
\(\displaystyle \sum_{k=i}^{m}(\beta_k-\beta_{k+1})=\beta_i=b_{\pi(i)}.\)
The feasible region is a closed subset of the probability simplex, hence compact. Thus an optimum exists.
The dual LP is
\(\displaystyle \min_{\alpha\in\mathbb R,\ r\in\mathbb R^m}\left\{\alpha+\sum_{j=1}^{m}b_jr_j:\ \alpha+\sum_{j\in S}r_j\geq v(S)\ \text{for every }S\subseteq[m]\right\}.\)
The variables \(\alpha,r_j\) are unrestricted because the primal constraints are equalities.
Write
\(\displaystyle D(r)=\max_{S\subseteq[m]}\left(v(S)-\sum_{j\in S}r_j\right).\)
For fixed \(r\), dual feasibility is exactly \(\alpha\geq D(r)\). Finite-dimensional LP strong duality therefore gives
\(\displaystyle \mathrm{OPT}=\min_{r\in\mathbb R^m}\left(D(r)+\sum_{j=1}^{m}b_jr_j\right).\)
This is the demand-oracle formulation of concave-closure computation mentioned on page 29 of [Shioura’s slides](https://repository.gatech.edu/server/api/core/bitstreams/f178ac64-a159-4d95-865c-2511892ef865/content).
2. Recovering a maximizing bundle from scalar demand values. The stipulated oracle returns a value. A separation oracle must also identify a violated constraint. Signed prices allow us to recover the corresponding bundle without assuming an additional oracle.
The encoding bound implies \(0\leq v(S)\leq V:=2^L\). Given rational prices \(r\), choose
\(\displaystyle M=V+\sum_{j=1}^{m}|r_j|+1.\)
For disjoint sets \(I,O\subseteq[m]\), define modified prices
\(\displaystyle r^{I,O}_j= \begin{cases} r_j-M,&j\in I,\\ r_j+M,&j\in O,\\ r_j,&j\notin I\cup O. \end{cases}\)
Every maximizing bundle at these prices contains \(I\) and avoids \(O\). Indeed, if \(j\in I\) is absent, adding it increases the objective by at least
\(\displaystyle -V-|r_j|+M>0.\)
If \(j\in O\) is present, removing it increases the objective by at least the same positive quantity. These inequalities use only \(0\leq v(S)\leq V\).
Consequently,
\(\displaystyle D(r^{I,O})-M|I| =\max_{\substack{I\subseteq S\subseteq[m]\\S\cap O=\emptyset}} \left(v(S)-\sum_{j\in S}r_j\right).\)
Now query \(F=D(r)\), initialize \(I=O=\emptyset\), and process the categories one at a time. Maintain the invariant that an original maximizing bundle contains \(I\) and avoids \(O\). For an unprocessed category \(j\), compute the restricted maximum with \(j\) additionally excluded:
\(\displaystyle F_0=D(r^{I,O\cup\{j\}})-M|I|.\)
If \(F_0=F\), add \(j\) to \(O\). Otherwise \(F_0<F\), so every original maximizer satisfying the current restrictions contains \(j\); add \(j\) to \(I\). Both choices preserve the invariant.
After all categories have been processed, the unique bundle satisfying the restrictions is \(S=I\). Hence
\(\displaystyle v(S)-\sum_{j\in S}r_j=F,\qquad v(S)=F+\sum_{j\in S}r_j.\)
This procedure uses \(m+1\) scalar demand queries and also recovers the bundle’s valuation.
All modified prices have encoding length polynomial in \(m,L\) and the encoding length of \(r\). Each demand response is the utility of one bundle, involving one valuation value and at most \(m\) rational prices; its encoding length is therefore polynomial in these parameters as well. Exact comparisons and arithmetic take polynomially many bit operations.
3. Exact separation and allocation recovery. Let \(P\subseteq\mathbb R^{m+1}\) be the dual feasible polyhedron. At a rational candidate \((\alpha,r)\), query \(D(r)\).
If \(D(r)\leq\alpha\), the candidate belongs to \(P\). Otherwise, use the preceding procedure to recover a maximizing bundle \(S\). Then
\(\displaystyle \alpha+\sum_{j\in S}r_j<v(S),\)
so the algorithm returns the actual violated defining inequality
\(\displaystyle \alpha+\sum_{j\in S}r_j\geq v(S).\)
This implements strong separation using at most \(m+1\) demand queries per call.
We use the following standard rational oracle-LP theorem, including its certificate conclusion:
*Let \(P=\{z\in\mathbb R^d:a_i^\mathsf Tz\geq h_i,\ i\in\mathcal I\}\), where \(\mathcal I\) is finite, possibly exponentially large. Suppose a known bound \(\phi\) bounds the encoding length of every defining inequality, and a strong separation oracle returns violated inequalities from this system. For rational \(c\), if minimizing \(c^\mathsf Tz\) over \(P\) has a finite optimum, an oracle-polynomial algorithm returns an optimal point \(z^*\) and a basic optimal dual certificate: indices \(i_1,\ldots,i_t\), with \(t\leq d\), and nonnegative rational multipliers \(\lambda_1,\ldots,\lambda_t\) such that*
\(\displaystyle \sum_{\ell=1}^{t}\lambda_\ell a_{i_\ell}=c,\qquad \sum_{\ell=1}^{t}\lambda_\ell h_{i_\ell}=c^\mathsf Tz^*.\)
*Both the number of oracle calls and the additional bit complexity are polynomial in \(d,\phi\) and the encoding length of \(c\).* This is the strong optimization and dual-certificate framework of Grötschel–Lovász–Schrijver; the certificate result, Lemma 6.5.15, is discussed in Section 1.2 of [Dadush–Végh–Zambelli](https://ir.cwi.nl/pub/35149/35149.pdf).
Every hypothesis holds here:
Apply the theorem. Its certificate consists of bundles \(S_1,\ldots,S_t\), with \(t\leq m+1\), and nonnegative rational masses \(\lambda_1,\ldots,\lambda_t\) satisfying
\(\displaystyle \sum_{\ell=1}^{t}\lambda_\ell=1,\qquad \sum_{\ell:\,j\in S_\ell}\lambda_\ell=b_j\quad(1\leq j\leq m), \)
and
\(\displaystyle \sum_{\ell=1}^{t}\lambda_\ell v(S_\ell)=\mathrm{OPT}.\)
Thus the certificate itself is the required explicitly listed optimal allocation.
There is also a direct bound on the output masses. Because the certificate is basic, its positive columns \(a_{S_\ell}\) are linearly independent. Select a nonsingular square submatrix \(B\) of those columns, of order \(t\leq m+1\). Its entries belong to \(\{0,1\}\). Let \(Q\) be the product of the supply denominators, so \(\log_2 Q\leq L\). Cramer’s rule expresses each mass as an integer divided by \(Q\det B\). The determinant bounds
\(\displaystyle |\det B|\leq t!,\qquad |\det B_\ell|\leq Q\,t!,\)
where \(B_\ell\) replaces one column by the corresponding entries of \(Qc\), show that each mass has encoding length
\(\displaystyle O\!\left(L+m\log(m+1)\right).\)
In particular, the exponentially many possible bundles do not cause an exponential output.
4. Complexity and approximation consequence. The rational oracle-LP algorithm makes polynomially many separation calls in \(m,L\), at points of polynomial encoding length. Each call requires at most \(m+1\) demand queries and polynomial additional bit operations. Therefore both resources requested in the question are polynomially bounded separately.
The resulting allocation has welfare exactly \(\mathrm{OPT}\), so it satisfies every fixed approximation requirement \(\varepsilon\in(0,1)\). With polynomial-time implementations of demand at signed rational prices, the entire computation is polynomial-time. A fixed-factor NP-hardness result for this continuous problem would therefore imply \(\mathrm P=\mathrm{NP}\).
The support parameter is \(\tau=1\) throughout. The algorithm never enumerates a universe of possible society types.
5. Why discrete hardness does not transfer. The discrete allocation model in [Barman–Sundaram](https://arxiv.org/pdf/2005.00504) requires a partition of the goods among finitely many agents. The continuous model imposes only bundle probabilities and category marginals. The difference can produce a strict welfare gap even for a valuation with an elementary demand implementation.
Take six categories \(a_0,a_1,b_0,b_1,c_0,c_1\), and the four bundles
\(\displaystyle \mathcal E= \bigl\{ \{a_0,b_0,c_0\}, \{a_0,b_1,c_1\}, \{a_1,b_0,c_1\}, \{a_1,b_1,c_0\} \bigr\}. \)
Define
\(\displaystyle v(S)=\max_{E\in\mathcal E}|S\cap E|.\)
This valuation is normalized and monotone. It is subadditive because, for every \(E\),
\(\displaystyle |(A\cup B)\cap E|\leq|A\cap E|+|B\cap E|\leq v(A)+v(B),\)
and taking the maximum preserves the inequality. Its demand value is computable by enumerating four additive clauses:
\(\displaystyle D(r)=\max_{E\in\mathcal E} \sum_{j=1}^{6}\max\{0,\mathbf 1_{\{j\in E\}}-r_j\}.\)
Set every supply to \(1/2\). Giving mass \(1/4\) to each bundle in \(\mathcal E\) satisfies every marginal, since each category occurs in exactly two bundles. Its welfare is \(3\), which is optimal because \(v(S)\leq3\).
For two discrete agents, every pair of bundles in \(\mathcal E\) intersects. Thus two disjoint allocated bundles cannot both have value \(3\); their average welfare is at most \(5/2\). This bound is attained by allocating \(\{a_0,b_0,c_0\}\) to one agent and its complement to the other.
Hence the continuous marginal problem can have optimum \(3\) when the corresponding discrete partition problem has optimum \(5/2\). The LP algorithm above resolves the continuous problem.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the continuous problem under the stated input and oracle model. It establishes exact optimization, including an explicitly listed optimal rational allocation with at most \(m+1\) supported bundles. I found no mathematical error or gap requiring clarification.
The primal LP exactly represents the required allocations: the first coordinate enforces total mass \(1\), and the remaining coordinates enforce the category marginals. Including the empty bundle correctly accommodates unused goods.
The proposed feasibility construction is valid. Sorting the supplies makes every mass \(\beta_k-\beta_{k+1}\) nonnegative. Both the total-mass identity and the marginal identity telescope correctly. Supplies equal to \(0\) or \(1\), repeated supplies, and \(m=1\) cause no difficulty; zero masses are permitted.
The feasible region is nonempty and compact, and the objective is a finite linear function. Therefore an optimal allocation exists and has finite welfare.
The dual has the correct objective, inequality direction, and unrestricted variables. Finite LP strong duality applies because the primal is feasible and bounded. Eliminating \(\alpha\) gives precisely the stated minimization involving \(D(r)\). Dual attainment also follows from the same finite LP theorem.
The bound \(0\leq v(S)\leq 2^L\) follows from the valuation encoding bound under the ordinary binary encoding of rational numbers.
The forcing constant
\[
M=V+\sum_j|r_j|+1
\]
is sufficient. For either operation used in the argument—adding a forced-in category or removing a forced-out category—the valuation change is at least \(-V\), and the adverse original-price contribution is at least \(-|r_j|\). Thus the displayed improvement is strictly positive.
Consequently, every maximizing bundle at the modified prices satisfies the restrictions. The correction term \(M|I|\) has the correct sign: each forced-in category contributes an additional \(M\) to modified utility.
The sequential recovery invariant is valid:
After all categories are processed, the restrictions identify the unique bundle \(I\), and the invariant guarantees that its original utility is \(F\). The recovered valuation formula is correct.
The query count is \(m+1\). In the separation procedure, its initial query supplies the same \(F\), so that query can be reused.
The bit-complexity claims also hold. Modified prices involve polynomially many rational arithmetic operations. A demand response equals one valuation value minus a sum of at most \(m\) supplied prices, so its rational encoding length is polynomial in the stated parameters. Exact comparisons therefore require only polynomial additional bit operations.
The separation test is exact: \((\alpha,r)\) is feasible if and only if \(D(r)\leq\alpha\). When this fails, the recovered maximizing bundle supplies an actual violated defining inequality.
The oracle-LP theorem is stated with the relevant hypotheses, including bounded inequality encoding and an oracle that returns inequalities from the defining system. Its certificate conclusion is supported by the cited discussion of rational polyhedra and GLS Lemma 6.5.15: bounded-encoding oracle inequalities permit recovery of optimal dual solutions. [Dadush–Végh–Zambelli, Section 1.2](https://ir.cwi.nl/pub/35149/35149.pdf)
The application satisfies the hypotheses:
The polyhedron’s unboundedness does not invalidate the stated rational oracle-LP theorem. The prover invokes the rational GLS framework, rather than relying on the separate real-arithmetic theorem in the cited paper.
The certificate equations translate directly into total mass, exact marginals, nonnegativity, and optimal welfare. Thus allocation recovery is established, rather than merely optimum-value computation. The basic certificate supplies the claimed support bound.
The determinant calculation is correct.
Linear independence of the positive certificate columns permits the stated nonsingular square submatrix. The common denominator \(Q\) clears the selected entries of \(c\), and its logarithm is bounded by the explicit input length.
The bound \(|\det B|\leq t!\) follows because \(B\) has binary entries. In \(B_\ell\), only one column has been replaced, and its entries lie between \(0\) and \(Q\). Therefore every determinant-expansion term has absolute value at most \(Q\), giving the stated bound \(Q\,t!\).
Cramer’s rule consequently yields polynomial encoding length for each mass. Together with at most \(m+1\) bundles, this establishes polynomial output size.
Polynomially many separation calls, each using polynomially many demand queries and polynomial additional arithmetic, give the two resource bounds requested in USER_TASK separately.
Exact optimality implies every requested fixed-\(\varepsilon\) approximation guarantee. The zero-optimum case is also covered because the algorithm remains exact.
When signed-price demand has a polynomial-time implementation, the entire algorithm is polynomial-time. The stated consequence for fixed-factor NP-hardness is therefore valid.
The argument consistently uses the supported-type parameter \(\tau=1\).
The illustrative valuation is normalized, monotone, and subadditive by the inequalities written in the output. The demand formula correctly maximizes over four additive clauses and then selects each positive-utility category independently.
Each category occurs in exactly two listed bundles, so the proposed continuous allocation has the required marginals and welfare \(3\). The global bound \(v(S)\leq3\) proves optimality.
All distinct listed triples intersect. Moreover, value \(3\) requires containing one listed triple. Hence disjoint discrete bundles cannot both have value \(3\). Since values are integral and at most \(3\), their average welfare is at most \(5/2\). The proposed partition attains this bound: its complementary bundle has value \(2\).
The reference to page 29 of Shioura’s slides is accurate under ordinary one-based PDF pagination: that page states the demand-oracle and ellipsoid computation claim. [Shioura’s slides](https://repository.gatech.edu/server/api/core/bitstreams/f178ac64-a159-4d95-865c-2511892ef865/content)
Actionable feedback: None required. The write-up establishes its claimed 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.