Answer: For every fixed \(c\ge 1\), no polynomial-time algorithm produces an explicitly represented feasible mass allocation with \(W(x)\ge\mathrm{OPT}/2^{m^c}\), assuming \(\mathrm{NP}\not\subseteq\bigcap_{\varepsilon>0}\mathrm{BPTIME}(2^{n^\varepsilon})\).
Theorem 17 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFix any constant c ≥1, and let α(n) = 2nc. There is no polynomial time α(n)- approximation algorithm for maximizing a monotone supermodular function f subject to a cardinality constraint, unless NP has randomized subexponential time algorithms, i.e., unless NP ⊆∩ϵ>0BPTIME 2nϵ , where n = log2 | dom(f)| is the size of the groundset V .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many consumer types \(t\) with rational masses \(\mu_t\), finite goods sets \(V_t\), compactly represented monotone supermodular utilities \(F_t:2^{V_t}\to\mathbb{R}_+\), prices \(p_t\), and budgets \(b_t\), compute a utility-maximizing mass allocation \(x_{t,S}\) over integral bundles \(S\subseteq V_t\) satisfying \(p_t(S)\le b_t\), with \(\sum_{S:p_t(S)\le b_t}x_{t,S}=\mu_t\) and \(x_{t,S}\ge0\). In the one-type, unit-price case with \(b_t=k\), determine the complexity of maximizing \(\sum_{S:|S|\le k}x_{t,S}F_t(S)\).
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a nonempty goods set \(V_t\), strictly positive rational item prices \(p_{t,v}\), a nonnegative rational budget \(b_t\), and a weakly monotone supermodular utility \(F_t:2^{V_t}\to\mathbb{Q}_{\ge0}\). Utilities are supplied as Boolean circuits mapping bundle incidence vectors to binary numerators and positive denominators; monotonicity and supermodularity are promises, and no normalization of \(F_t(\varnothing)\) is imposed.
Write \(m=|\bigcup_t V_t|\), \(p_t(S)=\sum_{v\in S}p_{t,v}\), and let \(L\) be the total input bit length, including the circuits. State running times in \(m,\tau,L\), and the budget parameter \(k\) below.
An allocation assigns nonnegative real masses \(x_{t,S}\) to integral bundles affordable individually, with \(\sum_{S:p_t(S)\le b_t}x_{t,S}=\mu_t\). Its welfare is \(W(x)=\sum_t\sum_{S:p_t(S)\le b_t}x_{t,S}F_t(S)\); these are the only constraints. Represent a computed allocation by its nonzero bundle masses as binary rationals.
Consider the restriction \(\tau=1\), \(\mu_1=1\), unit item prices, and integer budget \(1\le k\le m\). Let \(\mathrm{OPT}\) be the maximum welfare over feasible allocations.
For each fixed constant \(c\ge1\), is there a polynomial-time algorithm producing a feasible mass allocation with \(W(x)\ge\mathrm{OPT}/2^{m^c}\), or is such an approximation impossible assuming \(\mathrm{NP}\not\subseteq\bigcap_{\varepsilon>0}\mathrm{BPTIME}(2^{n^\varepsilon})\)?
For a single integral bundle, monotone supermodular maximization under a cardinality constraint has no polynomial-time \(2^{m^c}\)-approximation for any fixed \(c\ge1\), under that assumption ([source](https://www.cs.cmu.edu/~dgolovin/papers/revealpref.pdf)).
No result settling this precise mass-allocation formulation was identified in the literature search.
For every fixed constant \(c\ge 1\), the requested polynomial-time approximation is impossible under the stated assumption. Explicitly represented mass allocations and single integral bundles are equivalent for this approximation problem: a feasible allocation always contains a listed bundle whose utility is at least the allocation’s welfare.
Here \(k\) is allowed to vary with the input. Fixed \(k\), and the endpoint \(k=m\), admit exact polynomial-time algorithms.
Under the restriction in the question, define the finite feasible family \(\mathcal B_k=\{S\subseteq V:|S|\le k\}\) and let \(M=\max_{S\in\mathcal B_k}F(S)\).
A feasible allocation satisfies \(x_S\ge 0\) and \(\sum_{S\in\mathcal B_k}x_S=1\). Consequently,
\(\displaystyle W(x)=\sum_{S\in\mathcal B_k}x_SF(S)\le\sum_{S\in\mathcal B_k}x_SM=M.\)
Conversely, choose a maximizing bundle \(S^\star\in\mathcal B_k\). Assigning mass \(1\) to \(S^\star\) is feasible and has welfare \(M\). Thus \(\mathrm{OPT}=M\).
This argument uses only the allocation constraints. It does not require monotonicity, supermodularity, or normalization at the empty bundle.
Lemma. From an explicitly represented feasible allocation, one can compute an affordable integral bundle \(S^\dagger\) with \(F(S^\dagger)\ge W(x)\), in time polynomial in the input and allocation lengths.
Proof. Write the allocation’s nonzero entries as \((S_i,a_i)\), for \(1\le i\le r\). Feasibility gives \(|S_i|\le k\), \(a_i>0\), and \(\sum_{i=1}^r a_i=1\). In particular, \(r\ge 1\).
Evaluate the utility circuit on every listed bundle and choose \(S^\dagger\) with maximum utility. Then
\(\displaystyle W(x)=\sum_{i=1}^r a_iF(S_i)\le\sum_{i=1}^r a_iF(S^\dagger)=F(S^\dagger).\)
All comparisons are exact. If two circuit outputs represent \(u/v\) and \(u'/v'\), their positive denominators permit comparison by the integer products \(uv'\) and \(u'v\). Each circuit output has bit length \(O(L)\), so schoolbook arithmetic takes \(O(L^2)\) time per comparison.
If the allocation encoding has length \(B\), extraction takes \(O(B+r(m+L^2))\) bit operations. This proves the lemma.
Now suppose an allocation algorithm runs in polynomial time \(T(m,1,L,k)\). Its explicit output length satisfies \(B\le T(m,1,L,k)\), up to the fixed machine-model overhead. Running that algorithm and applying the lemma therefore takes polynomial time in \(m,L,k\).
If its guarantee were \(W(x)\ge\mathrm{OPT}/2^{m^c}\), the extracted bundle would satisfy
\(\displaystyle F(S^\dagger)\ge W(x)\ge\frac{\max_{|S|\le k}F(S)}{2^{m^c}}.\)
Thus it would be an integral-bundle approximation with exactly the forbidden factor. The extraction also preserves any per-run approximation success event of a randomized algorithm.
We use the integral-bundle hardness given in the question, stated as Theorem 17 of [Echenique, Golovin, and Wierman](https://www.cs.cmu.edu/~dgolovin/papers/revealpref.pdf). Its hard construction uses \(F(S)=2^{e_G(S)^d}\), where \(e_G(S)\) counts edges induced by \(S\), and \(d\) is a fixed positive integer chosen for the desired approximation exponent.
These utilities meet the promises. The edge-count function is nonnegative and monotone. Its marginal for adding a vertex counts neighbors already present, so its marginals increase under inclusion. For \(g(z)=2^{z^d}\), convexity and monotonicity on \(z\ge 0\) imply that \(g(z+a)-g(z)\) is nondecreasing in both \(z\) and \(a\ge 0\). Hence the composition also has increasing marginals and is supermodular.
The encoding is polynomial: compute \(q=e_G(S)^d\), then output the integer having its sole nonzero bit at position \(q\), with denominator \(1\). Since \(q\le\binom m2^d\), both circuit size and construction time are \(m^{O(d)}\). Thus \(L=m^{O(d)}\), and a polynomial-time circuit-input algorithm would run in polynomial time on this hard family. Also \(F(\varnothing)=1\), which is expressly permitted here.
Therefore Section 2 contradicts the supplied hardness theorem under \(\mathrm{NP}\not\subseteq\bigcap_{\varepsilon>0}\mathrm{BPTIME}(2^{n^\varepsilon})\).
The contradiction already occurs at support size \(\tau=1\); no dependence on larger \(\tau\) can avoid it. More generally, because types have no coupling constraints, their optimum is \(\sum_{t=1}^{\tau}\mu_t\max_{p_t(S)\le b_t}F_t(S)\), achieved by one bundle per type.
For the restricted instance, monotonicity ensures that some optimum has exactly \(k\) items: every smaller feasible bundle extends to a \(k\)-item bundle without decreasing utility. Enumerating all such bundles therefore computes an exact allocation in time \(O\!\left(\binom mk(m+L^2)\right)\).
This is polynomial when \(k\), or \(m-k\), is a fixed constant. For \(k=m\), assigning mass \(1\) to \(V\) is optimal and requires only \(O(m)\) output time. These cases do not settle the problem with unrestricted input parameter \(k\), for which the impossibility above applies.
⟨structured verdict parsed — rendered above⟩
The prover resolves the intended mass-allocation question in substance. The allocation-to-bundle reduction is correct and preserves the approximation factor exactly. The cited hardness applies to the stated utility family. One minor clarification is needed in the Boolean-circuit encoding argument; no major mathematical issue was found.
The feasible family \(\mathcal B_k\) is finite and nonempty, so its maximum utility \(M\) exists.
Every feasible allocation has nonnegative weights summing to \(1\). Therefore its welfare is a weighted average of feasible bundle utilities and cannot exceed \(M\). Assigning mass \(1\) to a maximizing bundle attains \(M\).
Thus the claimed equality \(\mathrm{OPT}=M\) is correct. It includes empty bundles, zero utilities, and utilities with positive value at the empty bundle. No utility promise is needed for this step.
The extraction lemma is correct:
The algorithm need not compute welfare or verify feasibility: it receives the output of an algorithm assumed to produce feasible allocations.
The exact-comparison argument is also correct. Positive denominators justify cross multiplication, and circuit outputs have bit length bounded by the input encoding length. The stated extraction bound \(O(B+r(m+L^2))\) accommodates reading the allocation, evaluating the circuits, and comparing their rational outputs under a standard bit model.
A polynomial-time algorithm producing an explicit allocation has polynomial output length. Hence extraction remains polynomial in \(m,L,k\), with \(\tau=1\). The observation about randomized success events is correct for a per-run guarantee; no success probability is lost during extraction.
The citation is accurate. Theorem 17 states the required inapproximability for each fixed exponent, measures the factor using ground-set size, and uses the stated randomized subexponential-time assumption. Its proof uses the claimed exponentiated induced-edge-count utilities and polynomial-length integer values. [Echenique, Golovin, and Wierman, Theorem 17](https://www.cs.cmu.edu/~dgolovin/papers/revealpref.pdf).
The prover correctly checks the relevant hypotheses:
There is no normalization mismatch or change in the meaning of \(m\).
Minor issue — circuit construction detail. The description “output the integer having its sole nonzero bit at position \(q\)” specifies the desired output, but does not explicitly explain the fixed-width Boolean-circuit implementation. Boolean circuits have a fixed number of output wires, whereas the significant length varies with the bundle.
The numerical bound \(q\le \binom{m}{2}^{d}\) is correct, and the required maximum numerator width is polynomial for fixed \(d\). This is an expositional omission, not an obstacle to the reduction.
Minimum clarification requested: specify the fixed numerator-output width, its padding convention, and briefly justify that the circuit and its description can be constructed uniformly in \(m^{O(d)}\) time. No new hardness argument is needed.
The supplementary claims are correct.
For general support, the absence of constraints coupling types makes the optimum separable. Each type has a finite nonempty affordable family because the empty bundle is affordable. One maximizing bundle per type therefore attains the displayed optimum, with the given binary-rational masses.
For the restricted instance, every bundle smaller than \(k\) extends to a \(k\)-item bundle because \(k\le m\). Weak monotonicity ensures that an optimum exists among those bundles. Enumeration and exact utility comparison justify the stated running time.
The fixed-\(k\), fixed-\((m-k)\), and \(k=m\) conclusions are valid. The endpoint’s \(O(m)\) claim is explicitly an output-time claim, so it does not incorrectly assert that the entire input can be read in that time.
The write-up establishes conditional approximation hardness for explicitly represented mass allocations with unrestricted input budget \(k\). The only requested repair concerns routine circuit-encoding detail. There is no false central step, missing substantive lemma, or unresolved distinction between the allocation and integral-bundle formulations.
⟨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.