Answer: \(\mathrm{NP}\text{-hard}\)
Lemma 29 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe colored-ads algorithm finds the optimal solution with probability 1 − e−restarts eK , where restarts is the number of random restarts, with a runtime complexity of O(2K N) per restart and an overall memory complexity of O(2K + N). It can be easily observed that an exponential number of restarts is necessary to assure a strictly positive success probability. Furthermore, notice that in the derandomized version, the algorithm is exact and requires O((2e)KKO(log K)N log N) time when paired with the derandomization technique presented by Naor, Schulman, and Srinivasan (1995).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given advertiser types \(t=(q_t,v_t,c_t)\) with rational masses \(\mu_t\) summing to \(1\), \(K\) ordered slots per page, rational position factors \(\lambda_s\), and an inventory ratio \(\rho\in(0,1]\), consider a continuum of pages of total mass \(\rho/K\), each assigned a full integral slate. For each ordered slate \(\sigma\in T^K\), choose its page mass \(y_\sigma\geq 0\), subject to \(\sum_\sigma y_\sigma=\rho/K\) and \(\sum_\sigma n_t(\sigma)y_\sigma\leq\mu_t\) for every type \(t\), where \(n_t(\sigma)\) counts that type in the slate. Maximize \(\sum_\sigma y_\sigma\sum_{s=1}^K q_{t_s}v_{t_s}\Lambda_s\prod_{r<s}c_{t_r}\), with \(\Lambda_s=\prod_{j<s}\lambda_j\), and find an optimal rational slate-mass distribution.
A society is given by its support: a list \(T\) of \(\tau\) advertiser types \(t=(q_t,v_t,c_t)\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. All type parameters are rational, with \(q_t,c_t\in[0,1]\) and \(v_t\geq0\).
There are \(m=K\geq1\) ordered slots per page, rational position factors \(\lambda_s\in[0,1]\) with \(\lambda_K=0\), and a rational inventory ratio \(\rho\in(0,1]\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Pages have total mass \(\rho/K\). Every page receives a full integral ordered slate \(\sigma=(t_1,\ldots,t_K)\in T^K\); repeated types represent distinct advertisers of that type, and each advertiser is used at most once overall. Define \(n_t(\sigma)=|\{s:t_s=t\}|\) and \(\Lambda_s=\prod_{j<s}\lambda_j\), with empty products equal to \(1\).
Choose slate masses \(y_\sigma\geq0\) satisfying \(\sum_{\sigma\in T^K}y_\sigma=\rho/K\) and \(\sum_{\sigma\in T^K}n_t(\sigma)y_\sigma\leq\mu_t\) for every \(t\). Maximize \(W(y)=\sum_{\sigma\in T^K}y_\sigma\sum_{s=1}^K q_{t_s}v_{t_s}\Lambda_s\prod_{r<s}c_{t_r}\). An optimal rational distribution is represented by its positive slate masses, with all omitted masses zero.
Is exact welfare maximization, including finding an optimal rational slate-mass distribution, solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For a finite list of \(N\geq K\) advertisers, randomized exact search takes \(O(2^K N)\) time per restart, with reported success bound \(1-\exp(-R/e^K)\) after \(R\) restarts; a deterministic exact variant takes \(O((2e)^K K^{O(\log K)}N\log N)\) time. [Farina and Gatti](https://www.mit.edu/~gfarina/2017/adopting-cascade-model-truthful-jair17/adopting-cascade-model-truthful-jair17.pdf).
The literature search located no verified discrete NP-hardness or W[1]-hardness result, and no result settling exactly the mass formulation above.
Exact welfare maximization is \(\mathrm{NP}\text{-hard}\), including finding an optimal rational slate-mass distribution. The associated decision problem with a binary rational welfare threshold is \(\mathrm{NP}\text{-complete}\).
Hardness holds even under the restrictions
\(\displaystyle \rho=1,\qquad \tau=2m,\qquad \mu_t=\frac{1}{2m},\qquad \lambda_s=1\ \text{for }s<m,\qquad q_tv_t=1-c_t.\)
We can additionally require that \(m\) is a power of two, so all masses are dyadic. Here \(\tau\) counts distinct types in the supplied support.
We reduce from monotone exact-two-in-four satisfiability: every clause contains four positive variable occurrences, and every clause must have exactly two true occurrences. This problem is \(\mathrm{NP}\text{-complete}\), as established in [Lemma 2 of *On the complexity of the balanced vertex ordering problem*](https://dmtcs.episciences.org/383/pdf).
Let the source formula have variables \(x_1,\ldots,x_{n_0}\) and clauses \(C_1,\ldots,C_h\). Add unconstrained variables until the number \(n\) of variables is a power of two. This preserves satisfiability and increases the variable count by less than a factor of two.
Let \(a_{ji}\) be the number of occurrences of \(x_i\) in clause \(C_j\). Thus
\(\displaystyle \sum_{i=1}^{n}a_{ji}=4\quad\text{for every }j.\)
Choose pairwise distinct primes
\(\displaystyle p_1,\ldots,p_n,r_1,\ldots,r_h.\)
For each variable \(x_i\), create two types \(t_{i,0}\) and \(t_{i,1}\), with
\(\displaystyle c_{i,0}=\frac1{p_i},\qquad c_{i,1}=\frac1{p_i\prod_{j=1}^{h}r_j^{a_{ji}}}.\)
Set
\(\displaystyle q_{i,b}=\frac{b+1}{2},\qquad v_{i,b}=\frac{1-c_{i,b}}{q_{i,b}}\quad\text{for }b\in\{0,1\}.\)
Consequently, \(q_{i,b}v_{i,b}=1-c_{i,b}\). All parameters satisfy the required ranges; indeed, \(0<c_{i,b}<1\) and \(0<v_{i,b}<2\).
These are \(2n\) distinct types. Types belonging to different variables have different continuation probabilities because their denominators contain different private primes \(p_i\). The two types belonging to one variable have different qualities, even when that variable is unconstrained.
Finally, set
\(\displaystyle m=K=n,\qquad \rho=1,\qquad \mu_{i,b}=\frac1{2n},\)
and set \(\lambda_s=1\) for \(s<n\), with \(\lambda_n=0\). Therefore \(\Lambda_s=1\) for every slot \(s\leq n\).
Define the integer and rational threshold
\(\displaystyle D=\left(\prod_{i=1}^{n}p_i\right)\left(\prod_{j=1}^{h}r_j^2\right),\qquad B=\frac{1-D^{-1}}{n}.\)
We will prove that the optimum welfare equals \(B\) exactly when the source formula is satisfiable.
For a slate \(\sigma=(t_1,\ldots,t_n)\), write
\(\displaystyle P_\sigma=\prod_{s=1}^{n}c_{t_s}.\)
Its welfare telescopes:
\(\displaystyle F_\sigma=\sum_{s=1}^{n}(1-c_{t_s})\prod_{r<s}c_{t_r}=1-P_\sigma.\)
Indeed, each summand is the difference between the prefix products ending immediately before and immediately after slot \(s\).
Now let \(y\) be any feasible distribution. Since every slate contains exactly \(n\) entries,
\(\displaystyle \sum_t\sum_\sigma n_t(\sigma)y_\sigma=n\sum_\sigma y_\sigma=1.\)
The capacities also sum to one. Because every capacity constraint is an upper bound, all of them must therefore be tight:
\(\displaystyle \sum_\sigma n_t(\sigma)y_\sigma=\mu_t=\frac1{2n}\quad\text{for every }t.\)
Normalize the slate masses to probabilities by setting \(\pi_\sigma=ny_\sigma\). Then \(\sum_\sigma\pi_\sigma=1\), and
\(\displaystyle \sum_\sigma\pi_\sigma n_t(\sigma)=\frac12\quad\text{for every }t.\)
The product of all continuation probabilities is
\(\displaystyle \prod_{i=1}^{n}c_{i,0}c_{i,1}=\left(\prod_i p_i^{-2}\right)\left(\prod_j r_j^{-4}\right)=D^{-2}.\)
It follows that
\(\displaystyle \sum_\sigma\pi_\sigma\log P_\sigma=\sum_t\left(\sum_\sigma\pi_\sigma n_t(\sigma)\right)\log c_t=\frac12\sum_t\log c_t=-\log D.\)
Apply Jensen’s inequality to the strictly convex exponential function:
\(\displaystyle \sum_\sigma\pi_\sigma P_\sigma\geq \exp\!\left(\sum_\sigma\pi_\sigma\log P_\sigma\right)=D^{-1}.\)
All products are positive, so the logarithms are defined. Strict convexity also gives the exact equality condition: equality holds if and only if
\(\displaystyle P_\sigma=D^{-1}\quad\text{for every slate with }y_\sigma>0.\)
Therefore
\(\displaystyle W(y)=\frac1n\left(1-\sum_\sigma\pi_\sigma P_\sigma\right)\leq \frac{1-D^{-1}}n=B.\)
Suppose a slate satisfies \(P_\sigma=D^{-1}\).
The exponent of the private prime \(p_i\) in the denominator of \(P_\sigma\) is
\(\displaystyle n_{t_{i,0}}(\sigma)+n_{t_{i,1}}(\sigma).\)
Its exponent in \(D\) is one. Unique prime factorization therefore implies
\(\displaystyle n_{t_{i,0}}(\sigma)+n_{t_{i,1}}(\sigma)=1\quad\text{for every }i.\)
Thus the slate chooses exactly one Boolean value for each variable. In particular, the equality condition excludes repetitions, although repetitions are permitted by the formulation.
Let \(b_i\) be the selected value. The exponent of the clause prime \(r_j\) in the denominator of \(P_\sigma\) is then
\(\displaystyle \sum_{i=1}^{n}a_{ji}b_i.\)
Its exponent in \(D\) is two. Hence
\(\displaystyle \sum_{i=1}^{n}a_{ji}b_i=2\quad\text{for every }j.\)
The assignment therefore satisfies every exact-two-in-four clause. Conversely, any satisfying assignment yields an equality slate by choosing its corresponding types.
It remains to show that a satisfying assignment yields a *feasible distribution*, rather than merely one useful slate.
Let \(\sigma\) contain the types selected by a satisfying assignment, and let \(\bar\sigma\) contain the complementary choices. Complementation preserves exact-two-in-four satisfaction because every clause has four occurrences. Consequently,
\(\displaystyle P_\sigma=P_{\bar\sigma}=D^{-1}.\)
Assign masses
\(\displaystyle y_\sigma=y_{\bar\sigma}=\frac1{2n},\)
with all other masses zero. Their total mass is \(1/n\). Every type appears exactly once across these two slates, so its consumption is exactly \(1/(2n)=\mu_t\). This distribution is feasible and has welfare \(B\).
Conversely, a feasible distribution of welfare \(B\) must, by the equality condition from Section 2, contain an equality slate. That slate gives a satisfying assignment.
The feasible region is nonempty and compact: homogeneous slates with masses \(\mu_t/n\) give a feasible distribution, and every coordinate lies between zero and \(1/n\). Thus an optimum is attained. We have proved
\(\displaystyle \operatorname{OPT}=B\quad\Longleftrightarrow\quad\text{the source formula is satisfiable}.\)
If the source formula is unsatisfiable, then \(\operatorname{OPT}<B\). Therefore testing whether \(\operatorname{OPT}\geq B\) decides the source problem.
Take the first \(n+h\) primes. The standard bound on the \(k\)-th prime, \(p_k=O(k\log(k+1))\), allows their deterministic construction by a sieve in polynomial time. Each prime has \(O(\log(n+h))\) bits.
Across all true-choice denominators, the total number of clause-prime factors, counted with multiplicity, is
\(\displaystyle \sum_i\sum_j a_{ji}=4h.\)
Thus the total encoding length of the constructed parameters, including their numerators, masses and position factors, is
\(\displaystyle L=O\!\left((n+h)\log(n+h)\right).\)
The threshold \(B=(D-1)/(nD)\) has the same polynomial bit-length bound. All products and rational parameters can be constructed in polynomial time.
Hence this is a polynomial-time many-one reduction. Exact optimization is \(\mathrm{NP}\text{-hard}\); a polynomial-time algorithm returning an optimal rational distribution would also decide the source formula by evaluating that distribution’s welfare.
The hardness is not an output-size obstruction. Every instance has an optimal rational distribution using at most \(\tau+1\) positive slates, with polynomial-size masses.
To prove this, first note that the homogeneous slate consisting of \(m\) copies of type \(t\), assigned mass \(\rho\mu_t/m\), gives a feasible distribution. The feasible region is finite-dimensional and compact, so an optimum exists.
Add nonnegative slack variables to the capacity inequalities. The resulting system has \(\tau+1\) equality rows. Its coefficient matrix is integral, with entries of absolute value at most \(m\).
Choose an optimal solution with the fewest positive variables, counting both slate masses and slacks. Its positive-variable columns must be linearly independent. Otherwise a nonzero dependence would permit sufficiently small feasible perturbations in both directions. Optimality forces the objective to be constant along that dependence, and moving until a positive variable becomes zero contradicts minimality. Therefore there are at most \(\tau+1\) positive variables, and hence at most \(\tau+1\) positive slate masses.
For their bit lengths, select an invertible square subsystem on those columns and apply Cramer’s rule. A common denominator for the right-hand side has \(O(L+\log(m+1))\) bits. Hadamard’s determinant bound then gives each positive mass bit length
\(\displaystyle O\!\left(L+\log(m+1)+(\tau+1)\log((m+1)(\tau+1))\right).\)
A certificate listing these slates and masses can therefore be verified using exact rational arithmetic in time polynomial in \(m,\tau,L\) and the threshold’s bit length. This proves membership in \(\mathrm{NP}\), and the reduction proves that the rational-threshold decision problem is \(\mathrm{NP}\text{-complete}\).
For an unconditional exact algorithm, enumerate all \(\tau^m\) slates and solve the resulting rational linear program. Its coefficients have polynomial bit length, so this takes
\(\displaystyle \tau^{O(m)}\operatorname{poly}(m,\tau,L)\)
deterministic time and returns an optimal rational distribution. For fixed \(m\), this is polynomial; a bound polynomial simultaneously in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated mass formulation. The reduction is valid, the equality condition correctly encodes satisfying assignments, and the argument establishes polynomial-size rational certificates. I found no major or minor mathematical issues.
The cited result is accurate: Lemma 2 establishes NP-completeness of exact-two-in-four satisfiability for formulas without negations. Its definition requires four literal occurrences per clause and exactly two true occurrences, matching the source problem used here. [Cited paper, Lemma 2](https://dmtcs.episciences.org/383/pdf).
Counting occurrences through \(a_{ji}\) handles repeated variables correctly. Padding with unconstrained variables preserves satisfiability and, for a positive original variable count, increases that count by less than a factor of two. Restricting the source reduction to nonempty instances does not affect its hardness.
The construction sets \(m=K=n\), \(\rho=1\), and gives each of the \(2n\) types mass \(1/(2n)\). These masses are positive and sum to one.
Every continuation probability is the reciprocal of an integer greater than one, so \(0<c_{i,b}<1\). The qualities are \(1/2\) and \(1\), and the specified values are positive rationals satisfying \(v_{i,b}<2\). Thus all parameter restrictions hold, including \(q_{i,b}v_{i,b}=1-c_{i,b}\).
Different variables have different continuation probabilities because their denominators contain different private primes and none of those primes is a clause prime. For a single variable, its two types remain distinct through their qualities, including when the variable is unconstrained. Consequently, the supplied support really has \(\tau=2n=2m\) distinct types.
The position factors also satisfy the task: \(\lambda_n=0\), while every factor entering \(\Lambda_s\) for \(s\leq n\) equals one. Hence \(\Lambda_s=1\), including at the final slot. When \(n=1\), this follows from the empty-product convention.
With these parameters, the slate welfare telescopes to \(F_\sigma=1-P_\sigma\). This remains valid for repeated types and arbitrary slate orders.
Summing type consumption gives total consumption one. Since the capacities also sum to one and each consumption is bounded above by its capacity, every capacity constraint must be tight. Normalization by \(\pi_\sigma=ny_\sigma\) therefore gives a probability distribution with expected count \(1/2\) for each type.
The product calculation is correct: each private prime has total exponent two across the two types of its variable, and each clause prime has total exponent four because \(\sum_i a_{ji}=4\). Thus the product of all continuation probabilities is \(D^{-2}\), and the expected logarithm of \(P_\sigma\) is \(-\log D\).
Jensen’s inequality is applicable as written: the distribution is finite, its weights are nonnegative and sum to one, every \(P_\sigma\) is positive, and the exponential function is strictly convex. Its equality condition requires all positive-weight logarithms to coincide. Their prescribed mean then forces \(P_\sigma=D^{-1}\) on every positive-mass slate. The resulting bound \(W(y)\leq B\) and its equality characterization are valid.
All continuation probabilities have numerator one, so the denominator products have no cancellation. Unique prime factorization therefore applies directly.
Matching the exponent of each private prime forces the slate to select exactly one type for each variable. Matching the exponent of each clause prime then forces exactly two true occurrences in that clause. This proves the claimed implication from an equality slate to a satisfying assignment, including the exclusion of repeated selections.
Conversely, a satisfying assignment gives an equality slate. Its complement is also satisfying because each clause has four occurrences. The two slates are distinct and together contain each type exactly once. Assigning each mass \(1/(2n)\) gives the required page mass \(1/n\), satisfies every capacity exactly, and attains welfare \(B\).
The converse distribution argument is also sound: a distribution of welfare \(B\) has positive total mass, so it contains a positive-mass slate; the equality condition makes that slate satisfying.
The homogeneous-slate construction supplies a feasible distribution. There are finitely many slate coordinates, the feasible set is closed, and each coordinate is bounded by the prescribed total page mass. Therefore the feasible set is compact and the linear objective attains its maximum.
Attainment matters here: it validates the strict conclusion \(\operatorname{OPT}<B\) for unsatisfiable source instances. Together with the universal upper bound, the established equivalence is exactly the one required for the threshold decision reduction.
A polynomial-time algorithm returning an optimal rational distribution would also decide the source instance by evaluating its returned welfare. A polynomial-time output algorithm necessarily produces a polynomial-length output, so this implication has no hidden output-reading obstruction.
Choosing the first \(n+h\) primes gives polynomial-time construction and \(O(\log(n+h))\) bits per prime. The total clause-prime multiplicity in all true-choice denominators is \(4h\), as claimed.
The private-prime factors, rational values, masses, and position factors fit within the stated total bound \(O((n+h)\log(n+h))\). Forming \(v_{i,b}\) does not introduce a larger asymptotic encoding requirement. The integer \(D\) and threshold \(B=(D-1)/(nD)\) also have polynomial bit length.
Hence the construction is a polynomial-time many-one reduction, rather than a reduction relying on exponentially long numerical parameters.
For general instances, the homogeneous slate masses \(\rho\mu_t/m\) give total page mass \(\rho/m\) and consumption \(\rho\mu_t\leq\mu_t\), establishing feasibility.
Adding capacity slacks produces \(\tau+1\) equality rows with integral coefficients bounded in absolute value by \(m\). The minimum-positive-support argument correctly establishes linear independence of the positive-variable columns: a dependence permits perturbations in both directions; optimality forces zero objective change; and moving to a boundary contradicts minimal support.
Thus at most \(\tau+1\) slate masses are positive. Selecting an invertible subsystem is justified by that column independence. Cramer’s rule applies, and the stated common-denominator and Hadamard bounds yield polynomial bit length for the masses.
The resulting certificates have polynomial length in \(m,\tau,L\). Their feasibility and welfare can be checked exactly with rational arithmetic, including when general-instance continuation or position factors are zero. This establishes NP membership for the rational-threshold decision problem and, with the reduction, NP-completeness.
Finally, enumerating \(\tau^m\) slates and solving the explicit rational linear program gives the claimed \(\tau^{O(m)}\operatorname{poly}(m,\tau,L)\) bound. The coefficients have polynomial bit length, and a rational optimal solution exists as established above.
No repair or additional mathematical clarification is required. The proof directly addresses the continuous mass formulation and does not depend on an unverified hardness assertion for the finite-advertiser problem.
⟨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.