Answer: Obtaining the $1.0042$-approximation is $\mathrm{NP}$-hard, already for $\tau=1$ and identical supplies $2/5$, with deterministically polynomial-time computable value oracles.
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor fair division instances with (identical) binary $\XOS$ valuations, it is $\mathrm{NP}$-hard to approximate the maximum Nash social welfare within a factor of $1.0042$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of good classes \(G\), rational per-capita supplies \(\sigma_g\), and a shared binary \mathrm{XOS} valuation \(v:2^G\to\mathbb{Z}_{\ge 0}\) with value-oracle access, assign masses \(\lambda_B\ge 0\) to integral bundles \(B\subseteq G\) subject to \(\sum_{B\subseteq G}\lambda_B=1\) and \(\sum_{B\ni g}\lambda_B\le \sigma_g\) for every \(g\). Compute or approximate \(\operatorname{NSW}_\infty(\lambda)=\exp\!\left(\sum_{B:v(B)>0}\lambda_B\log v(B)\right)\), assigning value \(0\) whenever positive mass receives a zero-valued bundle.
Let \(G\) be a set of \(m\ge 1\) good classes, with supplies \(\sigma_g\in\mathbb{Q}_{\ge 0}\) per unit of population. Each individual may receive at most one good from each class; unused supply is allowed.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here there is one type, with mass \(1\), so \(\tau=1\).
The shared valuation \(v:2^G\to\mathbb{Z}_{\ge 0}\) is \(\mathrm{XOS}\), normalized by \(v(\varnothing)=0\), and has binary marginals: \(v(S\cup\{g\})-v(S)\in\{0,1\}\). Access is through unit-cost value queries; an explicit list of additive clauses is not supplied.
An allocation assigns masses \(\lambda_B\ge 0\) to integral bundles \(B\subseteq G\), with \(\sum_B\lambda_B=1\) and \(\sum_{B\ni g}\lambda_B\le\sigma_g\) for every \(g\). Its welfare is \(\operatorname{NSW}_\infty(\lambda)=\exp(\sum_{B:v(B)>0}\lambda_B\log v(B))\), unless some zero-valued bundle receives positive mass, in which case its welfare is \(0\).
Let \(\mathrm{OPT}\) be the maximum feasible welfare, and let \(L\) be the bit length of the explicitly supplied input. Computational allocations are represented by their positive bundle masses as binary rationals.
Is finding a feasible allocation with \(\operatorname{NSW}_\infty(\lambda)\ge\mathrm{OPT}/1.0042\) possible in time and value-query count polynomial in \(m,\tau,L\), or is obtaining this approximation \(\mathrm{NP}\)-hard?
For discrete agents, approximation within \(1.0042\) is \(\mathrm{NP}\)-hard even with identical, succinctly represented binary \(\mathrm{XOS}\) valuations; a polynomial-time \(288\)-approximation exists with value queries. [Barman–Verma](https://arxiv.org/html/2106.02656v2)
For additive valuations, the related configuration relaxation maximizing expected log value admits a polynomial-time \((1+\varepsilon)\)-approximation for every \(\varepsilon>0\), with runtime polynomial in input size and \(1/\varepsilon\). [Feng–Li](https://theoretics.episciences.org/16348/pdf)
No result settling the stated binary \(\mathrm{XOS}\) mass-allocation problem was identified in the literature search.
Obtaining a feasible allocation with welfare at least $\mathrm{OPT}/1.0042$ is $\mathrm{NP}$-hard, already with one type and supply $2/5$ for every good.
The reduction below constructs valuations whose value queries are computable deterministically in polynomial time. Its main ingredient is an encoding of satisfying assignments into balanced bundles. A polynomial interpolation argument makes it possible to evaluate the valuation without finding a satisfying assignment first.
Let $N$ be a positive multiple of $60$. Partition the goods into public sets $A,B$, each of size $N$, and give every good supply $2/5$. Define
$$ h=\frac N4,\qquad a=\frac{7N}{10},\qquad b=\frac{14N}{15},\qquad c=\frac{2N}{5}. $$
The baseline valuation is
$$ v_0(S)= \max\left\{ \min(|S|,h), \min(|S\cap A|,a), |S\cap B| \right\}. $$
A truncated cardinality function $\min(|S\cap U|,k)$ is the maximum of the binary additive functions $S\mapsto |S\cap F|$ over all $k$-element subsets $F\subseteq U$. Thus $v_0$ is $\mathrm{XOS}$. Its constituents are normalized, integer-valued, monotone, and increase by at most one when a good is added. Their maximum therefore has binary marginals. Every nonempty bundle has positive value.
We first prove
$$ \mathrm{OPT}_0=a^{4/7}b^{3/7}. $$
Set
$$ \eta=\log b-1,\qquad \alpha=\frac{1+\log(a/b)}{a},\qquad \beta=\frac1b. $$
Since $a/b=3/4$, we have $0<\alpha<1/a$ and $\beta>0$.
For $0<k\le a$, the tangent inequality for the logarithm gives
$$ \log k \le \log a+\frac{k-a}{a} \le \log a+\alpha(k-a) =\eta+\alpha k. $$
The second inequality holds because $k-a\le0$ and $\alpha<1/a$. For every $t>0$, the tangent inequality at $b$ gives
$$ \log t\le\log b+\frac{t-b}{b}=\eta+\beta t. $$
Also,
$$ \frac bh=\frac{56}{15}>e, $$
so $\log h<\eta$. Applying these bounds to whichever constituent realizes $v_0(S)$ shows that every nonempty $S$ satisfies
$$ \log v_0(S) \le \eta+\alpha|S\cap A|+\beta|S\cap B|. $$
In a feasible allocation, the expected consumption from each group is at most $c$. Consequently, every positive-welfare feasible allocation satisfies
$$ \log\operatorname{NSW}_\infty(\lambda) \le \eta+c\alpha+c\beta. $$
Using $c/a=4/7$ and $c/b=3/7$, direct substitution gives
$$ \eta+c\alpha+c\beta = \frac47\log a+\frac37\log b. $$
Zero-welfare allocations also satisfy the resulting welfare upper bound.
Arrange each group cyclically. Assign mass $4/(7N)$ to each of the $N$ cyclic windows of length $a$ in $A$, and mass $3/(7N)$ to each of the $N$ cyclic windows of length $b$ in $B$.
The masses sum to one. Each good in $A$ lies in exactly $a$ of its group's windows, and each good in $B$ lies in exactly $b$ of its group's windows. Their respective consumptions are
$$ a\frac4{7N}=\frac25, \qquad b\frac3{7N}=\frac25. $$
The window values are $a$ and $b$, respectively. This feasible allocation attains $a^{4/7}b^{3/7}$ and proves the asserted formula. Its support and rational masses have polynomial encoding length.
Suppose we add five binary additive clauses supported on sets $T_0,\ldots,T_4$ such that
$$ |T_i|=\frac{4N}{5} $$
and every good belongs to exactly two of these sets.
Mass $1/5$ on each $T_i$ is feasible and gives every individual value $4N/5$. Conversely, normalization and binary marginals imply $v(S)\le |S|$ for every bundle. Jensen's inequality therefore bounds the welfare of every positive-welfare feasible allocation by
$$ \exp\left(\sum_S\lambda_S\log v(S)\right) \le \sum_S\lambda_Sv(S) \le \sum_S\lambda_S|S| \le \frac{4N}{5}. $$
Thus any valuation containing such five clauses has optimum exactly $4N/5$.
This exceeds $1.0042\,\mathrm{OPT}_0$. To prove the inequality without numerical approximation, let
$$ H(x)=-x\log x-(1-x)\log(1-x). $$
The baseline formula gives
$$ \log\mathrm{OPT}_0=\log c+H(4/7). $$
Moreover,
$$ H(1/2)=\log2,\qquad H'(1/2)=0,\qquad H''(x)=-\frac1{x(1-x)}\le-4. $$
Integrating the last inequality twice from $1/2$ to $4/7$ yields
$$ H(4/7) \le \log2-2\left(\frac47-\frac12\right)^2 = \log2-\frac1{98}. $$
Since $4N/5=2c$, it follows that
$$ \log\frac{4N/5}{\mathrm{OPT}_0}\ge\frac1{98}. $$
Finally,
$$ \log(1.0042) = \log\left(1+\frac{21}{5000}\right) \le\frac{21}{5000}<\frac1{98}. $$
Therefore,
$$ \frac{4N/5}{1.0042}>\mathrm{OPT}_0. $$
We will encode assignments by low-degree polynomials. The following elementary lemma supplies the required recovery algorithm.
Lemma. Let $d\ge1$, let
$$ \ell\ge10^{11}d, $$
and let $\mathbb F_q$ be a finite field with $q\ge\ell$. Let $\xi_1,\ldots,\xi_\ell$ be distinct field elements. Given lists $L_j\subseteq\mathbb F_q$ with $|L_j|\le9600$, one can deterministically list, in time polynomial in $q,\ell,d$, all polynomials $P\in\mathbb F_q[X]$ satisfying
$$ \deg P<d $$
and
$$ \left|\{j:P(\xi_j)\in L_j\}\right|\ge\frac{\ell}{200}. $$
Proof. Put
$$ W=\left\lfloor\frac{\ell}{400}\right\rfloor. $$
Seek a nonzero bivariate polynomial $Q(X,Y)$, using only monomials $X^rY^s$ with
$$ 0\le r\le\left\lfloor\frac W2\right\rfloor, \qquad 0\le s\le\left\lfloor\frac{W}{2d}\right\rfloor, $$
such that
$$ Q(\xi_j,x)=0 \quad \text{for every }j\text{ and every }x\in L_j. $$
These are at most $9600\ell$ homogeneous linear equations.
Because $\ell\ge800$, we have $W\ge\ell/800$. The number of available monomials is at least
$$ \frac{W^2}{4d} \ge \frac{\ell^2}{2560000d} > 9600\ell, $$
where the strict inequality follows from $\ell/d\ge10^{11}$. Hence a nonzero $Q$ exists and can be found by Gaussian elimination over $\mathbb F_q$.
Every available monomial satisfies
$$ r+(d-1)s\le W. $$
Consequently, for $\deg P<d$, the univariate polynomial $Q(X,P(X))$ has degree at most $W$. If $P$ has at least $\ell/200$ list agreements, this polynomial vanishes at more than $W$ distinct points. The polynomial root bound implies
$$ Q(X,P(X))\equiv0. $$
It remains to enumerate all polynomial solutions of this identity in deterministic polynomial time. We give the enumeration explicitly.
At any stage, remove the largest common power of $X$ from the current nonzero bivariate polynomial $R(X,Y)$. After this normalization,
$$ R(0,Y)\not\equiv0. $$
Enumerate its roots $\alpha\in\mathbb F_q$ by testing all $q$ field elements. For each root, substitute
$$ Y=\alpha+XY' $$
and normalize again by removing the largest common power of $X$. Repeating this procedure for $d$ stages enumerates possible coefficient sequences of polynomial solutions of degree less than $d$.
Indeed, if $P$ is a solution, then $P(0)$ is a root of $R(0,Y)$. Writing
$$ P(X)=P(0)+XP_1(X) $$
shows that $P_1$ is a solution of the corresponding substituted and normalized polynomial. Repetition preserves every genuine solution.
We next bound the branching. Give a normalized node the weight $\deg_Y R(0,Y)$. Suppose $\alpha$ has multiplicity $t$ in $R(0,Y)$. Expand around $\alpha$:
$$ R(X,\alpha+Z)=\sum_{u,v}c_{u,v}X^uZ^v. $$
Here $c_{0,v}=0$ for $v<t$, while $c_{0,t}\ne0$. After $Z=XY'$, the smallest occurring exponent $\rho$ of $X$ satisfies $\rho\le t$. Its coefficient has degree at most $\rho$ in $Y'$. Thus the normalized child has weight at most $t$.
The sum of root multiplicities is at most the parent's weight. Therefore the sum of the positive child weights never exceeds the parent weight. Nodes of weight zero have no possible completion and are discarded. If $D=\deg_Y Q$, there are at most $D$ retained nodes at each depth.
The degree in $Y$ never exceeds $D$, and each substitution increases the degree in $X$ by at most $D$. Thus all intermediate polynomial sizes remain polynomially bounded. After $d$ stages, check each resulting $P$ directly for the identity $Q(X,P(X))\equiv0$ and for the required list agreements.
This deterministic procedure has polynomial running time and lists every required polynomial. $\square$
Let $\varphi$ be a Boolean satisfiability instance with $d\ge1$ variables. Padding with an unused variable handles the case of no variables.
Choose
$$ \ell=12\left\lceil\frac{10^{11}d}{12}\right\rceil, $$
and let $q$ be the smallest power of $5$ satisfying $q\ge\ell$. Then
$$ \ell\le q<5\ell. $$
We use $\mathbb F_q$ and its trace to $\mathbb F_5$:
$$ \operatorname{Tr}(x) = x+x^5+\cdots+x^{5^{r-1}}, \qquad q=5^r. $$
The standard finite-field existence theorem applies because $5$ is prime and $r$ is a positive integer. A representation of $\mathbb F_q$ can be constructed deterministically in time polynomial in $q$: enumerate monic degree-$r$ polynomials over $\mathbb F_5$ until finding an irreducible one, testing reducibility by division by all monic polynomials of degree at most $r/2$. Both enumerations have size polynomial in $q$.
The trace is an $\mathbb F_5$-linear surjection onto $\mathbb F_5$. For completeness, its values lie in $\mathbb F_5$ because taking fifth powers leaves the displayed sum unchanged. Its defining polynomial is nonzero and has degree $5^{r-1}<q$, so it cannot vanish on all of $\mathbb F_q$. A nonzero linear map into the one-dimensional space $\mathbb F_5$ is surjective.
Choose distinct $\xi_1,\ldots,\xi_\ell\in\mathbb F_q$. Encode an assignment $a=(a_0,\ldots,a_{d-1})\in\{0,1\}^d$ by
$$ P_a(X)=\sum_{k=0}^{d-1}a_kX^k. $$
The field elements $0,1$ here encode the corresponding Boolean values.
Each of $A$ and $B$ contains goods indexed by
$$ (j,z,y)\in \{1,\ldots,\ell\}\times\mathbb F_q\times\mathbb F_5. $$
Hence
$$ N=5q\ell. $$
Since $\ell$ is divisible by $12$, $N$ is divisible by $60$, as required in Section 1. Give every good supply $2/5$.
For any polynomial $P$ of degree less than $d$, label a good in either group by
$$ \operatorname{Tr}(P(\xi_j)z)+y\in\mathbb F_5. $$
For $i\in\mathbb F_5$, define $T_i(P)$ to contain, from both groups, precisely the goods with labels in $\{i,i+1\}$, with addition in $\mathbb F_5$.
For each fixed $j,z$, varying $y$ produces each of the five labels exactly once. Therefore,
$$ |T_i(P)\cap A|=|T_i(P)\cap B|=2q\ell=\frac{2N}{5}, $$
and
$$ |T_i(P)|=\frac{4N}{5}. $$
Every good belongs to exactly two of the five sets $T_i(P)$.
Define
$$ v_\varphi(S)= \max\left( v_0(S), \max_{\substack{a\in\{0,1\}^d\\\varphi(a)=1}} \max_{i\in\mathbb F_5}|S\cap T_i(P_a)| \right). $$
If $\varphi$ has no satisfying assignment, the second collection is absent and $v_\varphi=v_0$.
This is a maximum of binary additive clauses, including the clauses representing the truncated terms of $v_0$. It is therefore $\mathrm{XOS}$, normalized, nonnegative, integer-valued, and has binary marginals.
If $\varphi$ is satisfiable, any satisfying assignment supplies five sets satisfying Section 2. Hence
$$ \mathrm{OPT}_\varphi= \frac{4N}{5}. $$
If it is unsatisfiable, then
$$ \mathrm{OPT}_\varphi=\mathrm{OPT}_0. $$
To complete the reduction, we must prove that $v_\varphi(S)$ is computable in polynomial time.
Fix a query bundle $S$, and write
$$ s=|S\cap A|, \qquad t=|S\cap B|, \qquad f=v_0(S). $$
If $s+t\le h$, then $f=s+t$, and no intersection-cardinality clause can exceed $f$.
Suppose $s+t>h$. We claim
$$ f-\frac25(s+t)\ge\frac N{50}. $$
If $s\le a$, then $f\ge\max(s,t)$ and $f\ge h$. Thus
$$ \frac25(s+t)\le\frac45f, $$
and
$$ f-\frac25(s+t)\ge\frac15f\ge\frac N{20}. $$
If $s>a$ and $t\le a$, then $s\le N$ and $f\ge a$, giving
$$ f-\frac25(s+t) \ge a-\frac25(N+a) = \frac N{50}. $$
If $s>a$ and $t\ge a$, then $f\ge t$, giving
$$ f-\frac25(s+t) \ge t-\frac25(N+t) \ge \frac35a-\frac25N = \frac N{50}. $$
These cases exhaust the possibilities.
Consequently, whenever a clause indexed by $P,i$ exceeds the baseline,
$$ |S\cap T_i(P)|>f, $$
it satisfies
$$ |S\cap T_i(P)|-\frac25|S|>\frac N{50}. $$
The following section turns this correlation into short local lists.
Fix $i\in\mathbb F_5$. A block $j$ consists of its goods in both $A$ and $B$, and has size
$$ M=10q. $$
For $x\in\mathbb F_q$, let $u_x$ be the real vector on one block whose coordinate at $(z,y)$, in either copy, is
$$ u_x(z,y) = \mathbf 1_{\{\operatorname{Tr}(xz)+y\in\{i,i+1\}\}} -\frac25. $$
Exactly $2/5$ of the coordinates have their indicator equal to one. Therefore,
$$ \|u_x\|^2=\frac6{25}M. $$
The vectors $u_x$ are pairwise orthogonal. To verify this, take $x\ne x'$. For each pair of desired labels $u,v\in\mathbb F_5$, the equations
$$ \operatorname{Tr}(xz)+y=u, \qquad \operatorname{Tr}(x'z)+y=v $$
are equivalent to
$$ \operatorname{Tr}((x-x')z)=u-v $$
and one uniquely determined choice of $y$. Surjectivity of the nonzero trace functional gives exactly $q/5$ choices of $z$. Thus, over all $5q$ coordinates in one copy, the pair of labels is uniform on $\mathbb F_5^2$. Its two indicators have joint mean $4/25$ and individual means $2/5$, so their centered product has mean zero. The same holds in the second copy.
Let $r_j$ be the indicator vector of the query goods in block $j$, and define the rational score
$$ D_{j,x}=\langle r_j,u_x\rangle. $$
Orthogonality gives Bessel's inequality in the form
$$ \sum_{x\in\mathbb F_q}D_{j,x}^2 \le \frac6{25}M\|r_j\|^2 \le \frac6{25}M^2. $$
Put
$$ \theta=\frac1{200}, \qquad L_j=\{x\in\mathbb F_q:D_{j,x}\ge\theta M\}. $$
Then
$$ |L_j|\,\theta^2M^2 \le \frac6{25}M^2, $$
so
$$ |L_j|\le\frac{6}{25\theta^2}=9600. $$
All scores and lists can be computed exactly by enumerating field elements and block coordinates. Their rational comparisons require no approximation.
Now suppose $T_i(P)$ exceeds the baseline on $S$. By Section 5 and $N=M\ell/2$,
$$ \sum_{j=1}^{\ell}D_{j,P(\xi_j)} = |S\cap T_i(P)|-\frac25|S| > \frac{M\ell}{100} = 2\theta M\ell. $$
Let $r$ be the number of indices with $P(\xi_j)\in L_j$. Every score is at most $M$, while every score outside its list is less than $\theta M$. Hence
$$ \sum_jD_{j,P(\xi_j)} \le rM+(\ell-r)\theta M. $$
Combining the last two inequalities gives
$$ r(1-\theta)>\theta\ell, $$
and therefore
$$ r>\frac{\ell}{200}. $$
Thus every clause exceeding the baseline is indexed by a polynomial that the recovery lemma lists.
Here is a deterministic evaluator for $v_\varphi(S)$.
Every additional value considered by this evaluator is an actual clause of $v_\varphi$, because its assignment has been checked against $\varphi$. Therefore the returned value cannot exceed $v_\varphi(S)$.
Conversely, every clause exceeding $v_0(S)$ is recovered by Sections 5–6 and the recovery lemma. Its satisfying assignment passes the checks. Thus every improvement over the baseline is considered, and the returned value equals $v_\varphi(S)$ exactly.
This evaluator also produces a satisfying assignment whenever it detects a strict improvement over the baseline.
The size and running-time bounds are polynomial. Specifically,
$$ \ell=O(d),\qquad q=O(d),\qquad m=2N=10q\ell=O(d^2). $$
The constants are large but fixed. Field construction, score computation, interpolation, polynomial recovery, and assignment verification all take time polynomial in $m$ and the length of $\varphi$.
Accordingly, the reduction supplies a succinct deterministic polynomial-time value evaluator, rather than an explicit exponential list of clauses. The explicitly supplied society has one type of mass one and identical rational supplies $2/5$, so its input length is polynomially bounded as well.
Suppose a deterministic algorithm, using polynomial time and polynomially many value queries, always returns a feasible allocation $\lambda$ satisfying
$$ \operatorname{NSW}_\infty(\lambda) \ge \frac{\mathrm{OPT}}{1.0042}. $$
Given $\varphi$, construct the instance above and simulate every value query with the evaluator from Section 7.
If $\varphi$ is satisfiable, Sections 2 and 4 imply
$$ \operatorname{NSW}_\infty(\lambda) \ge \frac{4N/5}{1.0042} > \mathrm{OPT}_0. $$
The allocation consequently has positive welfare.
There must be a positive-mass output bundle $S$ for which
$$ v_\varphi(S)>v_0(S). $$
Otherwise the valuation of every supported bundle would equal its baseline valuation. The allocation is feasible for the baseline instance because the supplies are identical, so its welfare would be at most $\mathrm{OPT}_0$, contradicting the strict inequality.
Scan the positive-mass bundles in the output. Their number is polynomially bounded by the algorithm's running time, because the required output representation lists those bundles and their rational masses. For each bundle, run the evaluator. On a bundle with a strict improvement, the evaluator produces a satisfying assignment.
If $\varphi$ is unsatisfiable, no candidate can pass the assignment check, so this procedure never produces a false satisfying assignment. Thus:
This decides Boolean satisfiability in polynomial time. Since Boolean satisfiability is $\mathrm{NP}$-complete, obtaining the stated approximation is $\mathrm{NP}$-hard.
The same witness extraction shows that a randomized polynomial-time algorithm succeeding with probability at least $2/3$ on every instance would place satisfiability in $\mathrm{RP}$: it could return a satisfying witness with that probability and could never accept an unsatisfiable formula.
The reduction establishes the requested hardness directly for mass allocations, with $\tau=1$, equal supplies, binary $\mathrm{XOS}$ valuations, and exact polynomial-time value evaluation.
⟨structured verdict parsed — rendered above⟩
The proof establishes the claimed $\mathrm{NP}$-hardness. I found no false step, missing substantive lemma, or unresolved representation issue. The reduction applies to the stated mass-allocation problem with value-query access.
All thresholds are integers because $N$ is a positive multiple of $60$. Each truncated cardinality constituent has the stated representation by binary additive clauses. Taking their maximum preserves normalization, integrality, monotonicity, and binary marginals. Every nonempty bundle has positive baseline value.
The upper-bound coefficients satisfy
$$
\frac ab=\frac34,\qquad
0<\alpha<\frac1a,\qquad
\beta>0.
$$
The logarithmic tangent inequalities have the correct directions. In particular, replacing $1/a$ by the smaller $\alpha$ increases the expression when $k-a\le0$.
The three constituents are all covered by the proposed bound: the total-cardinality constituent is bounded by $h$, the truncated $A$ constituent by the inequality for $k\le a$, and the $B$ constituent by the tangent inequality at $b$. The additional consumption terms are nonnegative. Also,
$$
\frac bh=\frac{56}{15}>e
$$
gives the required $\log h<\eta$.
Summing against allocation masses is valid for positive-welfare allocations, and the supply constraints give expected consumption at most $c$ in each group. The substitution
$$
\eta+c\alpha+c\beta
=
\frac47\log a+\frac37\log b
$$
is correct.
The cyclic-window allocation attains this bound. Its masses sum to one, each good receives consumption exactly $2/5$, and its bundle values are respectively $a$ and $b$. Its support and rational masses have polynomial encoding length. Thus the claimed exact baseline optimum is established.
If the five sets have the stated incidence properties, assigning mass $1/5$ to each consumes exactly $2/5$ of every good. Each supported bundle has value $4N/5$: its own additive clause attains its cardinality, and binary marginals bound its value by that cardinality.
For any positive-welfare feasible allocation, Jensen’s inequality applies because the masses sum to one and all supported values are positive. The total expected cardinality is at most $4N/5$. Consequently, the upper bound matches the exhibited allocation.
The entropy identity and curvature calculation are correct:
$$
\log\mathrm{OPT}_0=\log c+H(4/7),
\qquad
H''(x)=-\frac1{x(1-x)}\le-4.
$$
The integration interval lies inside $(0,1)$, so the asserted bound applies. The constants give
$$
2\left(\frac47-\frac12\right)^2=\frac1{98},
\qquad
\frac{21}{5000}<\frac1{98}.
$$
Therefore the strict gap
$$
\frac{4N/5}{1.0042}>\mathrm{OPT}_0
$$
is established without numerical approximation.
The interpolation system has at most $9600\ell$ equations. Its monomial count exceeds this number under the stated hypothesis, since
$$
\frac{\ell^2}{2560000d}>9600\ell
$$
follows from $\ell/d\ge10^{11}$. Hence Gaussian elimination produces a nonzero interpolating polynomial.
Every permitted monomial has substituted degree at most $W$. A polynomial with at least $\ell/200$ agreements therefore gives more than $W$ distinct roots of $Q(X,P(X))$. The univariate root bound applies and forces the stated polynomial identity.
The enumeration procedure preserves genuine solutions at every stage. Normalization permits evaluation at $X=0$, and the constant coefficient of a solution must be one of the enumerated roots.
The branching argument is valid. For a root of multiplicity $t$, the displayed expansion gives $\rho\le t$ and normalized child weight at most $t$. Summing root multiplicities bounds the total child weight by the parent weight. A weight-zero normalized node cannot have a polynomial solution, because its specialization at $X=0$ is a nonzero constant.
Thus there are at most $D$ retained nodes at every depth. The degree bounds ensure polynomially sized intermediate polynomials, and the final identity and agreement checks eliminate spurious candidates. The lemma provides deterministic polynomial-time recovery as claimed.
The selected parameters satisfy
$$
\ell\ge10^{11}d,\qquad
\ell\le q<5\ell.
$$
A field of order $5^r$ exists, and the proposed exhaustive construction is polynomial in $q$, which is the relevant bound here. Testing divisibility by all monic polynomials through degree $\lfloor r/2\rfloor$ suffices to test reducibility.
The trace argument correctly establishes an $\mathbb F_5$-linear surjection. Its defining polynomial is nonzero and has degree below $q$, so the root bound excludes its vanishing everywhere.
The goods count is
$$
N=5q\ell,
$$
and divisibility of $\ell$ by $12$ ensures divisibility of $N$ by $60$.
For each fixed $(j,z)$, varying $y$ produces every label exactly once. This proves both the cardinalities of the five sets and the fact that every good belongs to exactly two of them.
The resulting valuation has all required properties. Unsatisfiable formulas produce exactly the baseline valuation; satisfiable formulas supply the balanced clauses required for the larger optimum.
The case $s+t\le h$ is handled correctly: the baseline equals the bundle’s cardinality, so no additional intersection clause can improve it.
When $s+t>h$, the three cases cover every possibility. The lower bounds are respectively $N/20$, $N/50$, and $N/50$. In particular, both critical endpoint calculations are correct:
$$
a-\frac25(N+a)=\frac N{50},
\qquad
\frac35a-\frac25N=\frac N{50}.
$$
A clause strictly exceeding the baseline therefore has the asserted strict correlation surplus.
The centered vectors have squared norm $6M/25$. For distinct field elements, multiplication by their difference is invertible, and the trace functional is surjective. The stated pair-label counts follow, establishing orthogonality.
Bessel’s inequality consequently gives
$$
\sum_x D_{j,x}^2\le\frac6{25}M^2.
$$
The threshold $\theta=1/200$ yields the exact list bound
$$
|L_j|\le9600.
$$
The relation $N=M\ell/2$ is correct. Combining the correlation surplus with the upper bounds on individual scores gives
$$
r(1-\theta)>\theta\ell,
$$
which implies more than $\ell/200$ agreements. Every improving clause therefore satisfies the recovery lemma’s hypotheses.
The evaluator considers only genuine clauses after checking Boolean coefficients and satisfaction of the formula. Conversely, every clause improving on the baseline is recovered and checked. These two directions establish exact evaluation.
The construction satisfies
$$
\ell=O(d),\qquad q=O(d),\qquad m=O(d^2).
$$
All enumeration, interpolation, recovery, and formula-checking steps are polynomial in the formula length and the constructed instance size. The large constants are fixed.
This addresses the value-oracle model: the reduction can simulate every oracle query in polynomial time. An explicit additive-clause list is unnecessary.
On a satisfiable instance, the approximation guarantee forces output welfare strictly above the baseline optimum. If every positive-mass output bundle had its baseline value, feasibility for the unchanged supplies would contradict that strict inequality. Hence an improving output bundle exists.
The required output representation bounds the number of listed bundles by the algorithm’s running time. Scanning them and invoking the evaluator is therefore polynomial. An improving bundle yields a satisfying assignment; an unsatisfiable formula can never yield a falsely accepted assignment because satisfaction is checked directly.
The extraction avoids any need to compare products of irrational welfare values computationally. It proves that the proposed deterministic approximation algorithm would decide satisfiability in polynomial time. The additional randomized conclusion also follows: witness checking prevents acceptance on unsatisfiable formulas, while successful approximation yields acceptance on satisfiable formulas with the stated probability.
No repair or additional clarification is needed. The argument resolves the assigned continuous problem directly; it does not rely on transferring the discrete-agent hardness 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.