Answer: —
Theorem 3.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen agents have {0, 1, 2}-valuations, computing an MNW allocation is APX-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For finite type and item-class sets \(T\) and \(Q\), rational type masses \(\mu_\theta\) with \(\sum_{\theta\in T}\mu_\theta=1\), rational per-capita supplies \(\rho_q\), and values \(v_\theta(q)\in\{0,1,2\}\), choose \(x_{\theta,B}\ge0\) for whole bundles \(B\subseteq Q\) such that \(\sum_{B\subseteq Q}x_{\theta,B}=\mu_\theta\) and \(\sum_{\theta\in T,\,B\ni q}x_{\theta,B}=\rho_q\); maximize \(\exp\left(\sum_{\theta\in T,\,B\subseteq Q}x_{\theta,B}\log u_\theta(B)\right)\), where \(u_\theta(B)=\sum_{q\in B}v_\theta(q)\), with any positive-mass zero-utility bundle yielding welfare \(0\).
Given finite sets of types \(T\) and item classes \(O\), rational masses \(\mu_t\ge0\), rational per-capita supplies \(0\le\rho_o\le1\), and fixed \(0\le a<b<c\) with \(v_{t,o}\in\{a,b,c\}\), split each type's mass among integral bundles \(B\subseteq O\). A feasible allocation has \(x_{t,B}\ge0\), \(\sum_Bx_{t,B}=\mu_t\), and \(\sum_{t,B:o\in B}x_{t,B}=\rho_o\). Its objective is \(\operatorname{NW}_\infty(x)=\exp(\sum_{t,B}x_{t,B}\log u_t(B))\), where \(u_t(B)=\sum_{o\in B}v_{t,o}\) and \(\log0=-\infty\).
Is maximizing \(\operatorname{NW}_\infty\) for this mass-distribution problem NP-hard, or solvable in polynomial time?
For finite-agent indivisible allocation with additive \(\{a,b,c\}\)-valuations and \(0\le a<b<c\), computing a maximum-Nash-welfare allocation is APX-hard. No verified result is stated here for the mass-distribution formulation above.
Let \(m=|O|\) and \(\tau=|T|\). The exponentially many bundle variables admit an exact extended formulation with \(O(\tau m^4)\) variables and constraints. Consequently:
\(\operatorname{NW}_\infty(x)\geq e^{-\varepsilon}\operatorname{NW}_\infty^\star\).
In particular, the mass problem admits a fully polynomial-time approximation scheme.
Thus the finite-agent APX-hardness does not survive in the usual approximation or exact-real sense. Under a strict exact Turing interpretation, the requested dichotomy is not completely settled by the argument below.
Put \(M=\sum_{t\in T}\mu_t\). An allocation is feasible if and only if:
Necessity follows because at most the total population mass \(M\) can receive a given item class.
For sufficiency, set \(p_o=\rho_o/M\). Independently include \(o\) in a random bundle with probability \(p_o\), and assign this bundle distribution to every type. Explicitly, one may take
\[ x_{t,B}=\mu_t\prod_{o\in B}p_o\prod_{o\notin B}(1-p_o). \]
Then \(\sum_Bx_{t,B}=\mu_t\), while the total mass receiving \(o\) is \(Mp_o=\rho_o\).
This construction may have exponential support, but the polynomial-support construction below avoids that issue.
For \(r\in\{a,b,c\}\), define
\[ O_{t,r}=\{o\in O:v_{t,o}=r\},\qquad n_{t,r}=|O_{t,r}|. \]
For a bundle \(B\), its count profile for type \(t\) is
\[ \kappa_t(B)=\bigl(|B\cap O_{t,a}|,\ |B\cap O_{t,b}|,\ |B\cap O_{t,c}|\bigr). \]
Let
\[ K_t=\{0,\ldots,n_{t,a}\}\times \{0,\ldots,n_{t,b}\}\times \{0,\ldots,n_{t,c}\}. \]
For \(k=(k_a,k_b,k_c)\in K_t\), all bundles having profile \(k\) give type \(t\) the same utility
\[ q_{t,k}=ak_a+bk_b+ck_c. \]
There are at most \((m+1)^3\) profiles per type.
For every \(t\), profile \(k\), and item \(o\), introduce:
For positive Nash welfare, retain only
\[ K_t^+=\{k\in K_t:q_{t,k}>0\}. \]
Consider the following linear program:
\[ \max\ \sum_{t\in T}\sum_{k\in K_t^+}y_{t,k}\log q_{t,k}, \]
subject to
\[ \sum_{k\in K_t^+}y_{t,k}=\mu_t \qquad\text{for every }t, \]
\[ \sum_{t\in T}\sum_{k\in K_t^+}z_{t,k,o}=\rho_o \qquad\text{for every }o, \]
\[ \sum_{o\in O_{t,r}}z_{t,k,o}=k_r y_{t,k} \qquad\text{for every }t,k,r, \]
and
\[ 0\leq z_{t,k,o}\leq y_{t,k},\qquad y_{t,k}\geq0. \]
The number of \(y\)-variables is \(O(\tau m^3)\), and the number of \(z\)-variables and constraints is \(O(\tau m^4)\). All constraint coefficients are rational; logarithms occur only in the objective.
Given a positive-welfare allocation \(x\), define
\[ y_{t,k}=\sum_{\kappa_t(B)=k}x_{t,B} \]
and
\[ z_{t,k,o}=\sum_{\substack{\kappa_t(B)=k\\o\in B}}x_{t,B}. \]
The stated constraints follow immediately. Moreover,
\[ \sum_{\kappa_t(B)=k}x_{t,B}\log u_t(B) =y_{t,k}\log q_{t,k}. \]
Therefore the linear-program objective is exactly the original logarithmic Nash-welfare objective.
Fix \(t,k\) with \(y_{t,k}>0\), and set
\[ p_o=\frac{z_{t,k,o}}{y_{t,k}}. \]
For each \(r\in\{a,b,c\}\),
\[ 0\leq p_o\leq1,\qquad \sum_{o\in O_{t,r}}p_o=k_r. \]
The polytope
\[ H(n,k)=\left\{p\in[0,1]^n:\sum_i p_i=k\right\} \]
is the convex hull of incidence vectors of \(k\)-element subsets. Indeed, if an extreme point had two fractional coordinates, one could perturb them in opposite directions while preserving the sum. An extreme point cannot have exactly one fractional coordinate because its coordinate sum is the integer \(k\). Hence every extreme point is integral.
Thus, separately for each value class \(O_{t,r}\), the marginal vector \((p_o)\) is a distribution over subsets having exactly \(k_r\) elements. Taking the product of the three distributions gives a distribution over bundles with profile exactly \(k\) and item marginals \(p_o\). Multiplying that distribution by \(y_{t,k}\) constructs the required \(x_{t,B}\).
Summing over all \(t,k\) proves that every feasible point of the extended formulation corresponds to an original allocation with exactly the same objective value.
The preceding decomposition can be made constructive with polynomial support.
For \(p\in H(n,k)\), put \(s_0=0\) and \(s_i=\sum_{j=1}^ip_j\). Partition \([0,k)\) into intervals \(I_i=[s_{i-1},s_i)\). For \(\theta\in[0,1)\), select \(i\) exactly when \(I_i\) contains one of
\[ \theta,\theta+1,\ldots,\theta+k-1. \]
Exactly \(k\) distinct indices are selected, and index \(i\) is selected on a set of \(\theta\)-values having measure \(p_i\). The selected subset changes only at the fractional parts of the \(s_i\), so this produces a convex combination of at most \(n\) subsets.
Applying this to each of the three value classes and taking products gives at most \(O(m^3)\) bundles per profile. Since there are \(O(\tau m^3)\) profiles, an allocation with support \(O(\tau m^6)\) can be reconstructed in polynomial time.
The positive-profile linear program is feasible exactly when there exists an allocation in which no positive mass receives zero utility.
If it is infeasible but the original allocation problem is feasible, every feasible allocation assigns positive mass to a zero-utility bundle. By the convention \(\log0=-\infty\), every allocation then has
\[ \operatorname{NW}_\infty=0. \]
Hence any feasible allocation is optimal. Such an allocation can be obtained by solving the same rational extended formulation with all profiles \(K_t\), including those with \(q_{t,k}=0\), and then applying the polynomial-support decomposition.
Thus the zero boundary causes no computational hardness.
Assume \(a,b,c\) are fixed polynomial-time computable constants, in particular fixed rationals. Let \(\Phi^\star\) denote the optimum logarithmic objective, and suppose the positive-profile program is feasible.
Approximate every coefficient \(\log q_{t,k}\) by a rational number \(\widetilde{\ell}_{t,k}\) satisfying
\[ |\widetilde{\ell}_{t,k}-\log q_{t,k}|\leq\delta. \]
Because every feasible solution satisfies \(\sum_{t,k}y_{t,k}=M\), its true and approximate objectives differ by at most \(M\delta\). Let \(\widetilde y\) maximize the rational approximate objective, and let \(y^\star\) be a true optimum. Then
\[ \Phi(y^\star)-\Phi(\widetilde y) \leq 2M\delta. \]
Choosing \(\delta=\varepsilon/(2M)\) gives
\[ \Phi(\widetilde y)\geq\Phi^\star-\varepsilon \]
and therefore
\[ \operatorname{NW}_\infty(\widetilde y) \geq e^{-\varepsilon}\operatorname{NW}_\infty^\star. \]
The required logarithmic precision has polynomial bit length, and the resulting rational linear program has polynomial encoding length. Hence this algorithm runs in time polynomial in the input length and \(\log(1/\varepsilon)\).
Taking \(\varepsilon=\eta\) and using \(e^{-\eta}\geq1-\eta\) gives a \((1-\eta)\)-approximation.
In an exact-real comparison model, the displayed linear program immediately gives an exact polynomial-time algorithm.
For a strict Turing-machine claim, however, one must justify exact comparisons between candidate vertex values. Such a comparison has the form
\[ \sum_i r_i\log q_i\mathrel{\gtrless}0 \]
with rational \(r_i\). After clearing denominators, this becomes comparison of products such as
\[ \prod_i q_i^{e_i}\mathrel{\gtrless}1 \]
with binary-encoded integer exponents. For a variable number of bases, polynomial-time comparison of general product-of-exponentials representations is a recognized unresolved arithmetic-complexity issue; known unconditional polynomial-time results cover a fixed number of bases, while stronger general results follow from number-theoretic conjectures. See [Etessami, Stewart, and Yannakakis](https://arxiv.org/abs/1304.5429).
This observation does not prove that exact optimization here is hard. It shows that a polynomial-size LP with logarithmic costs, by itself, is not a complete exact Turing-polynomial proof.
The substantive combinatorial question is tractable: mass splitting collapses the exponential configuration formulation to a polynomial-size profile LP. Therefore the finite-agent APX-hardness does not transfer, and the mass problem is polynomial-time solvable under exact-real arithmetic and polynomial-time approximable to arbitrary precision in the standard bit model.
What remains open from the statement as literally written is only the strict exact Turing classification, because no model for exact logarithmic comparisons was specified.
⟨structured verdict parsed — rendered above⟩
The profile-based extended formulation and its equivalence to bundle allocations are sound. The prover also establishes a polynomial-time multiplicative approximation scheme, subject to an additional computability assumption on \(a,b,c\).
However, the requested exact complexity dichotomy is not resolved. The discussion of product-of-exponentials comparison explains why the displayed LP does not automatically yield an exact Turing-polynomial algorithm, but it does not prove that the present optimization problem has the full difficulty of general product-of-exponentials comparison or that its exact complexity is open.
Accordingly, the output contains genuine and substantial progress but is only partial.
For \(M>0\), the necessity of \(\rho_o\leq M\) is correct. The independent inclusion construction has the required type masses and item marginals, so sufficiency is also correct.
For \(M=0\), feasibility indeed requires every \(\rho_o=0\). The corresponding allocation is implicitly \(x_{t,B}=0\), though this should have been stated.
The partition into the three value classes is valid, and utility depends only on the three counts. The bound
\[ |K_t|\leq (m+1)^3 \]
is correct.
The constraints correctly express:
The stated \(O(\tau m^4)\) size bound is correct.
Calling this an “exact extended formulation” is justified for the feasible allocation polytope and objective values. It does not, by itself, establish exact Turing-polynomial optimization because the objective coefficients need not be rational.
The definitions of \(y_{t,k}\) and \(z_{t,k,o}\) satisfy all constraints. Since every bundle in a profile has utility \(q_{t,k}\), the objective identity is correct.
This direction tacitly uses the convention that zero-mass variables supported on zero-utility bundles contribute nothing. The task states \(\log 0=-\infty\), but does not explicitly define the product \(0\log 0\). The intended measure-theoretic convention is evident, but it should be stated.
For \(y_{t,k}>0\), the normalized vector \(p_o=z_{t,k,o}/y_{t,k}\) lies in the relevant hypersimplex. The extreme-point proof that
\[ H(n,k)=\operatorname{conv}\{\text{incidence vectors of $k$-subsets}\} \]
is correct.
Decomposing each of the three classwise marginal vectors and taking the product of the three distributions produces bundles with profile exactly \(k\) and preserves every item marginal. Thus the reverse construction is valid.
Profiles with \(y_{t,k}=0\) are not explicitly handled, but assigning zero bundle mass to them is immediate.
The interval construction selects exactly \(k\) distinct indices:
The marginal measure of index \(i\) is \(p_i\). The selected subset changes only at the relevant fractional endpoints, yielding at most \(n\) support sets. The resulting \(O(\tau m^6)\) support bound is correct.
If the positive-profile formulation is infeasible, no allocation can place all positive mass on positive-utility bundles. Hence every feasible allocation has some positive mass on a zero-utility bundle and logarithmic objective \(-\infty\), so Nash welfare is \(0\).
Conversely, including all profiles gives a rational feasibility formulation from which an allocation can be reconstructed. This part is correct, subject again to the implicit convention about zero-mass occurrences of \(\log 0\).
For every feasible \(y\),
\[ \left|\Phi(y)-\widetilde{\Phi}(y)\right|\leq M\delta. \]
Optimality for the approximate objective therefore gives the claimed loss bound \(2M\delta\). With \(\delta=\varepsilon/(2M)\), exponentiation yields the stated \(e^{-\varepsilon}\) multiplicative guarantee.
There are three qualifications:
Subject to these qualifications, the approximation result is valid.
The cited paper does support the statements that general product-of-exponentials inequality testing has no known unconditional polynomial-time algorithm for a variable number of bases, that fixed-number cases are polynomial-time decidable, and that stronger general conclusions follow from number-theoretic conjectures. [Etessami, Stewart, and Yannakakis](https://arxiv.org/abs/1304.5429)
Nevertheless, the citation concerns the general comparison problem. The prover does not show that arbitrary instances of that problem arise from vertices of this particular profile LP, nor that every exact optimization algorithm must perform such comparisons. Therefore the argument supports only:
It does not support the stronger assertion that the exact complexity classification of this mass-distribution problem is itself known to be open.
Also, “exact-real arithmetic model” is not defined precisely. Standard real-arithmetic models do not uniformly include exact evaluation of logarithms. The claimed exact-real polynomial algorithm is verifiable only after specifying that exact access to the coefficients \(\log q_{t,k}\) and exact comparisons of their linear combinations are primitive operations or supplied by an oracle.
The task asks whether exact maximization is NP-hard or polynomial-time solvable. The prover explicitly leaves exact Turing complexity unsettled. An exact-real algorithm and an approximation scheme do not answer that dichotomy in the ordinary Turing model.
The finite-agent APX-hardness comparison should also be qualified: an FPTAS precludes APX-hardness only under the standard assumption that \(\mathrm{P}\neq\mathrm{NP}\).
To make the established portion fully verifiable, the prover must:
⟨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.