Answer: Exactly solvable in deterministic \((m\tau+L)^{O(1)}\) bit time; hence welfare at least \(\mathrm{OPT}/r^{1-\epsilon}\) is achievable for every fixed \(0<\epsilon<1\).
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is no r/2O(√log r) approximation algorithm2 for welfare maximization with hypergraph-r valuations, unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given goods \(M\), types \(t\) with rational masses \(\mu_t\), hypergraph-\(r\) valuations \(v_t(S)=\sum_{j\in S}w_{tj}+\sum_{e\in E_t:e\subseteq S}w_{te}\), and rational per-capita supplies \(q_j\), choose masses \(y_{t,S}\) assigned to integral bundles \(S\subseteq M\). Maximize \(\sum_t\sum_{S\subseteq M} y_{t,S}v_t(S)\), subject to \(\sum_S y_{t,S}\le\mu_t\) for each type and \(\sum_{t,S:j\in S}y_{t,S}\le q_j\) for each good; unassigned mass is allowed.
Let \(M\) contain \(m\ge2\) goods, and let \(1\le r\le m\) be an input parameter. A society is given by its support: the list of its \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type explicitly lists a hypergraph \(E_t\) of nonempty edges of size at most \(r\), with nonnegative binary-rational vertex and edge weights, defining \(v_t(S)=\sum_{j\in S}w_{tj}+\sum_{e\in E_t:e\subseteq S}w_{te}\). Supplies \(q_j\) are nonnegative binary rationals per unit of society mass. Let \(L\) be the total input bit length, including the hypergraphs.
An allocation consists of nonnegative real masses \(y_{t,S}\) for integral bundles \(S\subseteq M\), satisfying \(\sum_S y_{t,S}\le\mu_t\) and \(\sum_{t,S:j\in S}y_{t,S}\le q_j\). Unassigned mass is allowed. Its welfare is \(\sum_{t,S}y_{t,S}v_t(S)\); let \(\mathrm{OPT}\) denote the maximum welfare.
Is achieving welfare at least \(\mathrm{OPT}/r^{1-\epsilon}\) NP-hard for every fixed \(0<\epsilon<1\), or does a polynomial-time approximation algorithm achieve this guarantee for some such \(\epsilon\)? State running times in \(m,\tau,r,L\).
For finite bidders and one copy of each good, an \(r/2^{O(\sqrt{\log r})}\)-approximation is impossible unless \(\mathrm{P}=\mathrm{NP}\), even for single-minded valuations; a randomized polynomial-time \(r\)-approximation is known. [Source](https://arxiv.org/html/1205.4104v1#S4).
A related fractional configuration problem with unit bidder capacities and uniform integer good supplies is exactly solvable in polynomial time for these valuations; the verified statement does not explicitly address arbitrary rational type masses and supplies. [Source](https://arxiv.org/html/1205.4104v1#S5).
The problem is exactly solvable in deterministic polynomial time, for arbitrary rational type masses and supplies and with \(r\) as an input parameter. The running time is \((m\tau+L)^{O(1)}\) bit operations. Consequently, the requested guarantee holds for every fixed \(0<\epsilon<1\).
The essential property is that, within each type, nested integral bundles simultaneously maximize the mass receiving every hyperedge for prescribed good marginals.
Write \(H=\sum_t|E_t|\) and \(I=\sum_t\sum_{e\in E_t}|e|\).
Introduce variables \(x_{tj}\), representing the mass of type \(t\) receiving good \(j\), and variables \(z_{te}\), representing the mass receiving every good of edge \(e\). Consider the linear program
\[ \begin{aligned} \text{maximize}\quad& \sum_{t,j}w_{tj}x_{tj}+\sum_t\sum_{e\in E_t}w_{te}z_{te},\\ \text{subject to}\quad& 0\le x_{tj}\le\mu_t &&\text{for every }t,j,\\ &\sum_t x_{tj}\le q_j &&\text{for every }j,\\ &z_{te}\ge0 &&\text{for every }t,e,\\ &z_{te}\le x_{tj} &&\text{for every }t,e,\ j\in e. \end{aligned} \]
Denote its optimal value by \(V_{\mathrm{LP}}\).
This program is feasible because the zero vector is feasible. It is bounded: each \(x_{tj}\) is bounded by \(\mu_t\), and, because edges are nonempty, every \(z_{te}\) is also bounded by \(\mu_t\).
For any feasible allocation \(y\), define
\[ x_{tj}=\sum_{S:j\in S}y_{t,S}, \qquad z_{te}=\sum_{S:e\subseteq S}y_{t,S}. \]
The type-mass constraints imply \(x_{tj}\le\mu_t\), and the supply constraints imply \(\sum_t x_{tj}\le q_j\). If \(j\in e\), every bundle containing \(e\) contains \(j\), so \(z_{te}\le x_{tj}\).
Expanding the valuation formula and interchanging finite sums shows that the LP objective equals the allocation’s welfare. Therefore,
\[ \mathrm{OPT}\le V_{\mathrm{LP}}. \]
Fix any feasible LP solution \((x,z)\). For each type \(t\), list the distinct positive values among its marginals in increasing order:
\[ 0=a_{t,0}<a_{t,1}<\cdots<a_{t,k_t}. \]
If all marginals are zero, allocate nothing to this type. Otherwise, for each \(\ell\in\{1,\ldots,k_t\}\), define the integral bundle
\[ S_{t,\ell}=\{j\in M:x_{tj}\ge a_{t,\ell}\} \]
and allocate mass \(a_{t,\ell}-a_{t,\ell-1}\) to it. Set all other allocation masses to zero.
These bundles are nested, and their total allocated mass is
\[ \sum_{\ell=1}^{k_t}(a_{t,\ell}-a_{t,\ell-1}) =a_{t,k_t} =\max_jx_{tj} \le\mu_t. \]
The remaining type mass can stay unassigned.
Good marginals. If \(x_{tj}=a_{t,h}>0\), then \(j\) belongs exactly to the bundles with \(\ell\le h\). Its allocated mass is consequently
\[ \sum_{\ell=1}^{h}(a_{t,\ell}-a_{t,\ell-1}) =a_{t,h} =x_{tj}. \]
If \(x_{tj}=0\), it belongs to none of the bundles. Thus the construction preserves every good marginal and satisfies all supply constraints.
Edge masses. For a nonempty edge \(e\), set \(b_{te}=\min_{j\in e}x_{tj}\). If this minimum is zero, no constructed bundle contains the edge. Otherwise, \(b_{te}=a_{t,h}\) for some \(h\), and the edge is contained exactly in the bundles with \(\ell\le h\). Its allocated mass is therefore
\[ \sum_{\ell=1}^{h}(a_{t,\ell}-a_{t,\ell-1}) =b_{te} =\min_{j\in e}x_{tj}. \]
The LP constraints give \(z_{te}\le\min_{j\in e}x_{tj}\). Because every edge weight is nonnegative, the constructed allocation has welfare
\[ \sum_{t,j}w_{tj}x_{tj} +\sum_t\sum_{e\in E_t}w_{te}\min_{j\in e}x_{tj} \ \ge\ \sum_{t,j}w_{tj}x_{tj} +\sum_t\sum_{e\in E_t}w_{te}z_{te}. \]
Apply this construction to an optimal LP solution. It gives a feasible allocation of welfare at least \(V_{\mathrm{LP}}\). Together with the previous inequality, this proves
\[ \mathrm{OPT}=V_{\mathrm{LP}}, \]
and the constructed allocation is optimal. It uses at most \(m\tau\) nonempty bundles.
The LP has \(m\tau+H\) variables and \(2m\tau+m+H+I\) inequalities. Its coefficients are rational and explicitly available from the input.
We use the standard rational linear-programming theorem: a feasible rational LP with bounded objective can be solved exactly in deterministic time polynomial in its explicit binary encoding length, returning an optimal rational solution of polynomial bit length. Feasibility and boundedness were checked above.
Because the hypergraphs are explicitly listed, \(H\) and \(I\) are \(O(L)\). Repeating type masses in the marginal bounds increases the encoding length only polynomially. Hence the whole LP has encoding length polynomial in \(m\tau+L\), and exact optimization takes
\[ (m\tau+L)^{O(1)} \]
bit operations.
Reconstruction requires \(O(\tau m\log m)\) rational comparisons for sorting and at most \(O(\tau m^2)\) membership operations to write all bundles explicitly. The masses are differences of polynomial-bit-length rationals, so this step also takes polynomial bit time.
Thus the algorithm is polynomial in \(m,\tau,r,L\), with no dependence on \(r\) beyond reading its input and the explicitly listed hypergraphs. It does not expand rational masses or supplies into individual agents or copies.
The cited hardness theorem concerns integral assignments to finite bidders. [Source, Section 4](https://arxiv.org/html/1205.4104v1#S4). The present model allows each type’s mass to be divided among several integral bundles, subject to aggregate supply constraints.
For example, take three goods and three equally weighted single-minded types. Their desired pairs are \(\{1,2\}\), \(\{2,3\}\), and \(\{1,3\}\); each type has mass \(1/3\), each desired pair has value \(1\), and every good has supply \(1/3\). Allocating mass \(1/6\) of each type its desired pair is feasible and yields welfare \(1/2\).
This is optimal: every unit of rewarded mass consumes at least two goods, while total supply is \(1\). In contrast, the corresponding finite instance with three bidders and one copy of each good can satisfy only one bidder, giving normalized welfare \(1/3\). Thus the finite integral optimum differs from the optimum asked for here.
Finally, \(\mathrm{OPT}\ge0\) and \(r^{1-\epsilon}\ge1\), so the exact algorithm achieves welfare at least \(\mathrm{OPT}/r^{1-\epsilon}\) for every fixed \(0<\epsilon<1\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes exact deterministic polynomial-time optimization for the stated model, including arbitrary rational type masses and supplies. No major or minor mathematical issues were found.
The proof addresses the allocation model in USER_TASK: bundles remain integral subsets of goods, while the masses assigned to those bundles may be fractional. It correctly uses the support size \(\tau\), without enumerating additional types or expanding rational masses into individual bidders.
The construction respects aggregate supply constraints. The task imposes no additional requirement that allocations arise from a single integral assignment of goods across finite bidders.
The proposed constraints correctly bound each marginal \(x_{tj}\) by the available type mass and each edge variable \(z_{te}\) by every marginal belonging to that edge.
Feasibility follows from nonnegative supplies and the zero solution. Boundedness is correctly justified: \(0\le x_{tj}\le\mu_t\), and nonemptiness of every edge ensures \(0\le z_{te}\le\mu_t\). Thus the feasible region is nonempty and bounded, and the linear objective attains an optimum.
The map from allocations to LP solutions is valid:
Consequently, \(\mathrm{OPT}\le V_{\mathrm{LP}}\) is justified.
The reconstruction is correct for every feasible LP solution.
For each type, the distinct positive marginal values are well defined and number at most \(m\). Each constructed mass is positive, and each constructed bundle is nonempty. The telescoping sum of masses equals \(\max_j x_{tj}\le\mu_t\), so the type constraint is satisfied.
For a good with marginal \(a_{t,h}\), membership in exactly the bundles indexed by \(\ell\le h\) follows directly from the threshold definition. The resulting telescoping sum equals its prescribed marginal. Goods with zero marginal occur in no constructed bundle. Hence every supply constraint is preserved exactly.
For a nonempty edge, its minimum marginal is either zero or one of the listed thresholds. The same membership calculation correctly yields edge mass \(\min_{j\in e}x_{tj}\). This holds simultaneously for all edges, including overlapping edges; the construction does not make incompatible choices for different edges.
The proof correctly claims domination of the LP objective, rather than realization of every specified \(z_{te}\). Nonnegative edge weights justify that domination. Applying it to an LP optimum, together with the established upper bound, proves equality of the two optimal values and optimality of the reconstructed allocation.
The bound of at most \(m\tau\) nonempty bundles is also correct.
The variable count \(m\tau+H\) and inequality count \(2m\tau+m+H+I\) are correct, counting nonnegativity constraints explicitly.
The rational linear-programming theorem is stated with the needed conclusions: deterministic polynomial bit complexity, exact optimization, and an optimal rational solution of polynomial bit length. Its hypotheses are satisfied by the explicitly encoded rational LP and the preceding feasibility and boundedness checks.
Explicit listing of the hypergraphs gives \(H,I=O(L)\). Repeated occurrences of type masses and the additional marginal constraints increase the encoding size only polynomially in \(m\tau+L\). Therefore the stated bound \((m\tau+L)^{O(1)}\) bit operations is justified. The task does not require a specific polynomial exponent.
The reconstruction bounds are valid: sorting uses \(O(\tau m\log m)\) rational comparisons, and explicitly writing at most \(m\) bundles per type takes \(O(\tau m^2)\) membership operations. Polynomial bit lengths make these operations polynomial in bit time; differences of the returned rational marginals retain polynomial bit length.
No enumeration of all bundles, dependence exponential in \(r\), or expansion proportional to rational denominators is hidden in the algorithm.
The proof handles all-zero marginals explicitly. Its reasoning also covers empty hypergraph lists, singleton edges, zero weights, zero supplies, and supplies exceeding available society mass.
For \(r=1\), the requested guarantee is exact optimality, which the algorithm provides. When \(\mathrm{OPT}=0\), the guarantee remains valid. For every permitted \(r\) and fixed \(0<\epsilon<1\), the inequalities \(\mathrm{OPT}\ge0\) and \(r^{1-\epsilon}\ge1\) justify the final approximation claim.
The source indeed formulates the finite problem through integral assignments represented by ordered partitions of goods. Its hardness statement therefore concerns a different feasible allocation set. [Source, Section 4](https://arxiv.org/html/1205.4104v1#S4).
The example’s arithmetic is correct. Each good is consumed by two rewarded masses of \(1/6\), totaling its supply \(1/3\); welfare is \(3(1/6)=1/2\). The stated consumption bound establishes optimality. In the finite instance, every two desired pairs intersect, so at most one bidder can be satisfied, giving normalized welfare \(1/3\).
This comparison supports the distinction without being needed for the LP equivalence proof.
No repair or additional clarification is needed. The output resolves the target through an exact algorithm, a valid reconstruction, and a polynomial bit-complexity bound.
⟨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.