Answer: Polynomial-time solvable exactly: a feasible allocation attaining \(\mathrm{OPT}\) can be computed in time polynomial in \(m,\tau,D,L\).
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is a setting of CAs with submodular bidders, for which the problem of computing payments for Algorithm 2 is solvable in polynomial time, but the problem of finding a social welfare maximizing allocation is NP-hard to approximate within a factor 2e/(2e −1) −ε for any ε > 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given goods \(U\), \(\tau\) normalized monotone submodular valuation types \(v_t:2^U\to\mathbb{Q}_{\ge 0}\), rational masses \(\mu_t\ge 0\) summing to \(1\), and per-capita supplies \(q_e\ge 0\), choose fractions \(x_{t,S}\ge 0\) of each type assigned each integral bundle \(S\subseteq U\), with \(\sum_{S\subseteq U}x_{t,S}=1\) for each \(t\) and \(\sum_t\mu_t\sum_{S\ni e}x_{t,S}\le q_e\) for each good \(e\). Compute the maximum per-capita welfare \(\sum_t\mu_t\sum_{S\subseteq U}x_{t,S}v_t(S)\), with complexity measured in \(m=|U|\), \(\tau\), the rational bit length, and the valuation-description length.
Let \(U\) be a set of \(m\ge 1\) goods. A society is given by its support: \(\tau\ge 1\) valuation types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts listed types, not possible types.
Each type is a normalized monotone submodular valuation \(v_t:2^U\to\mathbb Q_{\ge 0}\), represented by a listed set \(B_t\subseteq U\) and an explicit binary-rational table \(w_t:2^{B_t}\to\mathbb Q_{\ge 0}\), with \(v_t(S)=w_t(S\cap B_t)\). The sets \(B_t\) may equal \(U\).
Supplies \(q_e\in\mathbb Q_{\ge 0}\) are per capita. An allocation assigns fractions \(x_{t,S}\ge 0\) to integral bundles \(S\subseteq U\), satisfying \(\sum_{S\subseteq U}x_{t,S}=1\) and \(\sum_t\mu_t\sum_{S\ni e}x_{t,S}\le q_e\).
Its welfare is \(W(x)=\sum_t\mu_t\sum_{S\subseteq U}x_{t,S}v_t(S)\); write \(\mathrm{OPT}=\max_x W(x)\). Let \(D\) be the total valuation-description length and \(L\) the total bit length of rational input data; measure running time in \(m,\tau,D,L\).
For each fixed \(0<\varepsilon<1/(2e-1)\), does finding a feasible allocation with \(W(x)\ge\mathrm{OPT}/(2e/(2e-1)-\varepsilon)\) admit a polynomial-time algorithm, or is achieving this approximation NP-hard?
For finitely many bidders receiving disjoint integral bundles, achieving this approximation is NP-hard, even when each valuation is an explicit table on a constant number of relevant goods. [Discrete result](https://repository.essex.ac.uk/22023/1/document.pdf); [underlying hardness construction](https://theory.stanford.edu/~jvondrak/data/submod-comm.pdf).
The standard configuration relaxation for discrete welfare can be optimized with demand-oracle access; that result assumes a different input model and unit item capacities. [Fractional result](https://theoryofcomputing.org/articles/v006a011/v006a011.pdf).
The problem is polynomial-time solvable exactly in \(m,\tau,D,L\). Consequently, the requested approximation admits a polynomial-time algorithm for every stated \(\varepsilon\).
We represent the output allocation by listing its nonzero fractions, with all unlisted fractions understood to be zero.
For each type \(t\), only its listed set \(B_t\) affects its valuation. Given any feasible allocation \(x\), define, for every \(T\subseteq B_t\),
\(\displaystyle z_{t,T}=\sum_{\substack{S\subseteq U\\S\cap B_t=T}}x_{t,S}.\)
These numbers are nonnegative and satisfy
\(\displaystyle \sum_{T\subseteq B_t}z_{t,T}=\sum_{S\subseteq U}x_{t,S}=1.\)
Interpret \(z_{t,T}\) as the fraction of type \(t\) receiving exactly the bundle \(T\).
This transformation preserves welfare, since
\(\displaystyle \sum_{T\subseteq B_t}z_{t,T}w_t(T)=\sum_{S\subseteq U}x_{t,S}w_t(S\cap B_t)=\sum_{S\subseteq U}x_{t,S}v_t(S).\)
It also preserves feasibility. If \(e\in B_t\), then
\(\displaystyle \sum_{\substack{T\subseteq B_t\\e\in T}}z_{t,T}=\sum_{\substack{S\subseteq U\\e\in S}}x_{t,S}.\)
If \(e\notin B_t\), the transformed allocation gives no units of \(e\) to type \(t\). Thus consumption of every good weakly decreases.
Conversely, any feasible allocation using only bundles \(T\subseteq B_t\) is an allocation allowed by the original problem. Hence restricting each type to these bundles leaves the optimal welfare unchanged.
Introduce variables \(y_{t,T}\) for all listed types \(t\) and all \(T\subseteq B_t\). The variable \(y_{t,T}\) is the total population mass of type \(t\) receiving \(T\); thus \(y_{t,T}=\mu_t z_{t,T}\).
Consider the following rational linear program:
\(\displaystyle \text{maximize}\quad \sum_{t=1}^{\tau}\sum_{T\subseteq B_t}w_t(T)y_{t,T},\)
subject to
\(\displaystyle \sum_{T\subseteq B_t}y_{t,T}=\mu_t\qquad(t=1,\ldots,\tau),\)
\(\displaystyle \sum_{t=1}^{\tau}\sum_{\substack{T\subseteq B_t\\e\in T}}y_{t,T}\le q_e\qquad(e\in U),\)
\(\displaystyle y_{t,T}\ge 0\qquad(t=1,\ldots,\tau,\ T\subseteq B_t).\)
Because every \(\mu_t\) is positive, the transformations \(y_{t,T}=\mu_t z_{t,T}\) and \(z_{t,T}=y_{t,T}/\mu_t\) are inverse to each other. The equalities enforce the required conditional allocation fractions, the inequalities enforce supplies, and the objective equals welfare. By Section 1, this linear program therefore has optimal value exactly \(\mathrm{OPT}\).
The program is feasible: take \(y_{t,\varnothing}=\mu_t\) and all other variables zero. It is bounded, since nonnegativity and the type equalities imply \(0\le y_{t,T}\le\mu_t\le1\). Its feasible region is closed and bounded, so an optimum is attained.
Let \(N=\sum_{t=1}^{\tau}2^{|B_t|}\), the number of variables. Each of these variables corresponds to an explicitly listed table entry. Since every entry occupies at least one bit, \(N=O(D)\).
The program has \(\tau\) equality constraints, \(m\) supply inequalities, and \(N\) nonnegativity constraints. Its constraint coefficients are zero or one; its remaining rational data are precisely the table values, masses, and supplies. Enumerating the table entries and constructing their incidence coefficients therefore produces a linear program whose total binary encoding length is polynomial in \(m,\tau,D,L\).
We apply the standard rational linear-programming theorem: an explicitly encoded rational linear program can be solved in time polynomial in its binary encoding length, and a feasible program with finite optimum admits an exact rational optimal solution of polynomial encoding length. Polynomial-time solvability is established by [Khachiyan’s linear-programming algorithms](https://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=eng&paperid=5239&wshow=paper). The preceding paragraphs verify the required rational encoding, feasibility, and boundedness.
Let \(y^*\) be the resulting optimal solution. Output
\(\displaystyle x^*_{t,S}=\begin{cases}y^*_{t,S}/\mu_t,&S\subseteq B_t,\\0,&S\not\subseteq B_t.\end{cases}\)
There are at most \(N\) nonzero entries to list. Division by a positive input rational increases encoding length by at most a polynomial amount, so the output also has polynomial length. The correspondence proved above gives feasibility and \(W(x^*)=\mathrm{OPT}\).
This remains valid when \(B_t=U\): its entire table is already included in \(D\), and the running-time bound is polynomial in that description length.
Write \(\alpha_\varepsilon=2e/(2e-1)-\varepsilon\). The assumed bound \(\varepsilon<1/(2e-1)\) gives \(\alpha_\varepsilon>1\). Since welfare is nonnegative,
\(\displaystyle W(x^*)=\mathrm{OPT}\ge\frac{\mathrm{OPT}}{\alpha_\varepsilon}.\)
The discrete hardness result concerns assigning disjoint integral bundles, as stated in [Dobzinski and Vondrák’s Theorem 1.1](https://theory.stanford.edu/~jvondrak/data/submod-comm.pdf). That extra restriction is absent here.
Indeed, for a discrete instance with \(n\) bidders, setting \(\mu_i=1/n\) and \(q_e=1/n\) turns our supply constraints into \(\sum_i\sum_{S\ni e}x_{i,S}\le1\). These are fractional configuration constraints. A discrete assignment additionally requires each bidder’s distribution to concentrate on a single bundle. Optimizing over fractional distributions does not impose that requirement.
The cited [fractional paper, Section 1](https://theoryofcomputing.org/articles/v006a011/v006a011.pdf), likewise observes that explicit tables on relevant goods yield only polynomially many relevant configuration variables. Our direct formulation verifies this for the stated input model and arbitrary rational per-capita supplies.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The explicit-table representation yields a linear program of polynomial encoding length whose optimum equals the original allocation optimum. No major or minor mathematical issues were found.
For each type \(t\), the sets of bundles satisfying \(S\cap B_t=T\), as \(T\) ranges over \(2^{B_t}\), partition \(2^U\). Thus the defined \(z_{t,T}\) are nonnegative and sum to one.
The welfare identity follows directly from the given representation \(v_t(S)=w_t(S\cap B_t)\). For \(e\in B_t\), membership of \(e\) in \(S\cap B_t\) is equivalent to membership in \(S\), so the stated consumption equality is correct. For \(e\notin B_t\), the transformed bundles consume no \(e\). Multiplying by the positive masses and summing over types therefore preserves every supply inequality.
Conversely, bundles contained in \(B_t\) are permitted original bundles. These two directions establish equality of the restricted and original optimum values.
Positivity of every \(\mu_t\) justifies division by \(\mu_t\) and makes the changes of variables inverse. The type equalities give conditional fractions summing to one. The supply inequalities measure precisely the per-capita consumption in the task, and the objective is precisely welfare.
The empty-bundle solution is feasible because every supply is nonnegative. Each coordinate satisfies \(0\le y_{t,T}\le\mu_t\le1\), so the feasible region is bounded. It is also closed and nonempty. The linear objective therefore attains a finite maximum.
The variable count is
\[
N=\sum_{t=1}^{\tau}2^{|B_t|}.
\]
Every such variable corresponds to an explicitly encoded table entry, so \(N=O(D)\). Constructing at most \((m+\tau)N\) incidence coefficients, together with the rational objective and right-hand-side data, takes polynomial time and produces polynomial encoding length in \(m,\tau,D,L\).
This argument remains valid when \(B_t=U\): the full table already contributes to \(D\). The prover does not incorrectly claim a running time polynomial in \(m\) alone.
The invoked standard theorem provides polynomial-time exact optimization for explicitly encoded rational linear programs, including a rational optimal solution of polynomial encoding length when the optimum is finite and attained. The write-up verifies the relevant hypotheses: explicit rational data, polynomial encoding length, feasibility, and boundedness. The cited [Khachiyan reference](https://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=eng&paperid=5239&wshow=paper) is correctly identified as a foundational polynomial-time linear-programming result.
No demand-oracle assumption or unit-capacity restriction is needed for this application.
The displayed definition of \(x^*\) assigns the recovered conditional fractions to bundles contained in \(B_t\), with all other fractions zero. The established correspondence verifies normalization, nonnegativity, supplies, and welfare \(W(x^*)=\mathrm{OPT}\).
There are at most \(N\) listed nonzero entries. Division by a positive input rational preserves rationality and increases numerator and denominator bit lengths by at most the combined operand lengths. Bundle descriptions require at most \(m\) bits each. Consequently, the complete allocation output has polynomial length.
The assumed strict upper bound on \(\varepsilon\) gives
\[
\alpha_\varepsilon=\frac{2e}{2e-1}-\varepsilon>1.
\]
Since \(\mathrm{OPT}\ge0\), the exact optimum satisfies the requested approximation inequality. This also covers \(\mathrm{OPT}=0\).
Empty relevant sets, zero supplies, a single type, and supplies greater than one introduce no exception to the preceding argument.
Substituting \(\mu_i=1/n\) and \(q_e=1/n\) gives exactly the stated fractional configuration constraints. Requiring each bidder’s distribution to concentrate on one bundle supplies the additional integrality restriction needed for a discrete assignment.
The description of [Dobzinski and Vondrák’s Theorem 1.1](https://theory.stanford.edu/~jvondrak/data/submod-comm.pdf) is consistent with its discrete welfare setting. The supporting observation about polynomially many relevant configuration variables also appears in Section 1 of the [fractional paper](https://theoryofcomputing.org/articles/v006a011/v006a011.pdf). Neither citation substitutes for the direct equivalence and encoding arguments, which are complete.
No additional clarification is needed to make the argument verifiable.
⟨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.