Answer: —
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 can correctly solve the Program (3).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) auction slots, a finite set \(T\) of advertiser types, rational masses \(\mu_t\) summing to \(1\), rational budget and ROI targets \((\widehat B_t,\widehat\gamma_t)\), rational piecewise-polynomial value densities \(f_t\), rival shading parameters \(\bar\beta_t>0\), and precision \(\varepsilon>0\), each auction slot is drawn independently from \(\mu\), and a type-\(s\) advertiser with value \(V_s\sim F_s\) bids \(\bar\beta_s V_s\). For each supported type \(t\), compute an interval of width at most \(\varepsilon\) containing an optimal shading parameter \(\beta_t>0\) maximizing \(U_t(\beta_t)=\mathbb E[(V_t-D_t)\mathbf 1\{\beta_tV_t\ge D_t\}]\), subject to \(\mathbb E[D_t\mathbf 1\{\beta_tV_t\ge D_t\}]\le\widehat B_t\) and \(\mathbb E[((1+\widehat\gamma_t)D_t-V_t)\mathbf 1\{\beta_tV_t\ge D_t\}]\le0\), where \(D_t\) is the maximum rival bid and has CDF \(H(z)^{n-1}\), with \(H(z)=\sum_{s\in T}\mu_sF_s(z/\bar\beta_s)\).
A society is given by its support: the list of the \(\tau\) advertiser types \(T\) with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has binary-rational targets \(\widehat B_t>0\), \(\widehat\gamma_t>0\), a fixed rival shading parameter \(\bar\beta_t>0\), and a continuous, nonnegative piecewise-polynomial density \(f_t\) integrating to \(1\) on a common interval \([0,\bar v]\), where \(\bar v>0\) is rational. Breakpoints and polynomial coefficients are binary rationals; coefficients are listed densely. Let \(m\) count all polynomial pieces, \(d\) be their maximum degree, and \(L\) be the total input bit length.
There is one second-price auction without a reserve and \(n\ge2\) bidder positions, with \(n\) encoded in binary. Conditional on a focal bidder having type \(t\), its value \(V_t\sim F_t\) is independent of the \(n-1\) rivals, whose types are independently drawn from \(\mu\) and whose values are independently drawn from their type distributions; a type-\(s\) rival bids \(\bar\beta_sV_s\). Ties are broken arbitrarily.
Extend \(F_s\) by \(0\) below \(0\) and by \(1\) above \(\bar v\). The maximum rival bid \(D_t\) has CDF \(\Pr(D_t\le z)=H(z)^{n-1}\), where \(H(z)=\sum_{s\in T}\mu_sF_s(z/\bar\beta_s)\).
For \(\beta>0\), define \(P_t(\beta)=\mathbb E[D_t\mathbf1\{\beta V_t\ge D_t\}]\) and \(U_t(\beta)=\mathbb E[(V_t-D_t)\mathbf1\{\beta V_t\ge D_t\}]\). A shading parameter is feasible when \(0<P_t(\beta)\le\widehat B_t\) and \(\mathbb E[((1+\widehat\gamma_t)D_t-V_t)\mathbf1\{\beta V_t\ge D_t\}]\le0\). Promise that each supported type has a feasible parameter.
Given binary-rational \(0<\varepsilon\le1\), compute for every supported type a rational interval of width at most \(\varepsilon\) containing some feasible parameter maximizing \(U_t\).
Is this interval-computation problem solvable in polynomial time in \(m,\tau,d,L,\log n,\log(1/\varepsilon)\), or is it NP-hard?
For a finite list of independent bidders, a verified result establishes correctness of an efficient algorithm for the same budget- and ROI-constrained best-response optimization; it does not establish bit complexity for this input encoding ([source](https://www.ijcai.org/proceedings/2023/0314.pdf)). No complexity classification for the precise support-encoded problem above was located.
The general complexity classification remains unresolved. I prove a new result for the full class of piecewise-polynomial densities, including densities with support gaps:
At every rational bisection query, exact constraint comparisons become polynomial-time computable once $n$ exceeds an explicitly computable threshold whose bit length is polynomial in the society description and the query precision.
Consequently, the interval-computation problem is polynomial-time solvable whenever $n$ is sufficiently large relative to the other input parameters. The remaining range can still contain exponentially large numerical values of $n$, so this does not settle the requested classification.
As in the previous round, I interpret the fixed rival parameters $\bar\beta_s$ as binary rationals included in the input. Without a specified encoding for these parameters, their bit complexity is undefined.
The supplied [IJCAI paper](https://www.ijcai.org/proceedings/2023/0314.pdf) studies the budget- and ROI-constrained problem for independent bidders. No complexity result from that paper is used below.
Put $N=n-1$. All focal types face the same rival maximum, denoted by $D$, with CDF $H(z)^N$.
For each supported type $s$, let
$$
a_s=\operatorname{ess\,inf}V_s,
\qquad
b_s=\operatorname{ess\,sup}V_s.
$$
Define
$$
a=\min_s\bar\beta_s a_s,
\qquad
M=\max_s\bar\beta_s b_s.
$$
These endpoints are rational and computable from the input. Indeed, a nonzero polynomial has finitely many zeros. A nonnegative polynomial density is therefore positive almost everywhere on each piece where its polynomial is nonzero. The first and last nonzero pieces determine its essential support endpoints.
In particular, $b_s>0$ and $M>0$. Each rival bid, and hence $D$, is absolutely continuous. Its density almost everywhere is
$$
g_N(z)=N H(z)^{N-1}H'(z).
$$
For each fixed input, this density is bounded and supported on $[a,M]$.
The following payment threshold will be useful:
$$
P_t(\beta)>0
\quad\Longleftrightarrow\quad
\beta b_t>a.
$$
To prove it, first observe that $D>a$ almost surely. If $\beta b_t\le a$, winning has probability zero. Conversely, if $\beta b_t>a$, choose $z$ strictly between these quantities. Then
$$
\Pr(V_t>z/\beta)>0,
\qquad
\Pr(D\le z)=H(z)^N>0.
$$
The second inequality holds because some rival type has positive probability of bidding below every $z>a$. Independence gives positive winning probability. Since $D>0$ almost surely, payment is positive.
Fix a focal type and abbreviate
$$
b=b_t,\qquad c=1+\widehat\gamma_t,\qquad B=\widehat B_t.
$$
Thus $c>1$ and $B>0$. Write
$$
A(\beta)=\mathbb E[V_t\mathbf1\{\beta V_t\ge D\}],
\qquad
h(\beta)=cP(\beta)-A(\beta).
$$
The utility is $U=A-P$, and the ROI constraint is $h\le0$.
A feasible parameter exists exactly when
$$
\frac ab<\frac1c.
$$
For necessity, if $ca\ge b$, then
$$
cD-V_t>ca-b\ge0
$$
almost surely. Positive payment implies positive winning probability, so the ROI residual is strictly positive.
For sufficiency, any parameter satisfying
$$
\frac ab<\beta<\frac1c
$$
has positive payment and satisfies
$$
cD-V_t\le(c\beta-1)V_t<0
$$
on the winning event. Moreover, $P$ is continuous and tends to zero as $\beta$ decreases to $a/b$. Continuity follows by dominated convergence, because ties have probability zero. Parameters sufficiently close to $a/b$ therefore also meet the positive budget bound.
Define
$$
J(\beta)=\int_0^{\bar v}v^2f_t(v)g_N(\beta v)\,dv.
$$
Then
$$
A'(\beta)=J(\beta),
\qquad
P'(\beta)=\beta J(\beta),
$$
and consequently
$$
U'(\beta)=(1-\beta)J(\beta),
\qquad
h'(\beta)=(c\beta-1)J(\beta).
$$
For justification, use
$$
A(\beta)=\int_0^{\bar v}vf_t(v)H(\beta v)^N\,dv
$$
and
$$
P(\beta)=
\int_0^{\bar v}f_t(v)
\left(\int_0^{\beta v}zg_N(z)\,dz\right)dv.
$$
Boundedness of $g_N$ supplies integrable bounds for the difference quotients on every compact interval of positive $\beta$. For a fixed $\beta$, its finitely many breakpoints affect only finitely many values of $v$, so differentiation under these integrals is valid.
Since $J\ge0$, payment is nondecreasing, utility is nondecreasing up to $1$, and $h$ decreases up to $1/c$ and increases thereafter.
Extend the functions continuously to zero. It follows that
$$
C=\{\beta\in[0,1]:P(\beta)\le B,\ h(\beta)\le0\}
=[0,b^*]
$$
for some $b^*\in[0,1]$.
The feasibility promise supplies a feasible parameter strictly above $a/b$ and below $1/c$. Hence $b^*>a/b$, so $P(b^*)>0$. Thus $b^*$ satisfies the original constraints and maximizes utility on $[0,1]$.
If a parameter $\beta>1$ is feasible, monotonicity gives
$$
P(1)\le P(\beta),\qquad h(1)\le h(\beta),\qquad U(1)\ge U(\beta).
$$
Also $P(1)>0$, because $a/b<1/c<1$. Therefore $b^*$ is a feasible global maximizer.
It remains to implement membership queries for $C$. Exact membership tests permit ordinary bisection from $[0,1]$, including at query points with zero payment.
The next lemma supplies exact signs without evaluating exponentially small quantities.
Lemma. Let $r>0$, and suppose:
Then an integer threshold $T$ can be constructed using rational arithmetic such that, for every $N\ge T$,
$$
\operatorname{sign}\left(
\int_0^r G(z)g_N(z)\,dz
\right)
$$
equals the sign of $Q$ immediately to the left of $r$.
When the rational data and polynomial degrees have polynomial encoding length, the construction takes polynomial time and $T$ has polynomial bit length.
Choose rational $\eta>0$ such that $H$ is strictly increasing on $[r-\eta,r]$ and $G=Q$ there. Expand
$$
Q(r-x)=\sum_{j=0}^e a_jx^j.
$$
Let $k$ be the smallest index with $a_k\ne0$, and put
$$
\sigma=\operatorname{sign}(a_k).
$$
Choose a rational $\delta$ with $0<\delta\le\min\{\eta/2,1\}$ such that
$$
\delta\sum_{j>k}|a_j|\le\frac{|a_k|}{2}.
$$
If the sum is zero, this last condition imposes no restriction. For $0<x\le\delta$,
$$
\sigma Q(r-x)\ge\frac{|a_k|}{2}x^k.
$$
In particular, on
$$
[r-\delta/2,\ r-\delta/4]
$$
we have
$$
\sigma G(z)\ge w,
\qquad
w=\frac{|a_k|}{2}\left(\frac{\delta}{4}\right)^k>0.
$$
Set
$$
p_0=H(r-\delta),\qquad
p_1=H(r-\delta/2),\qquad
p_2=H(r-\delta/4).
$$
Strict increase gives
$$
0\le p_0<p_1<p_2.
$$
The integrand has the desired sign throughout $[r-\delta,r]$. Its contribution below that interval is bounded in magnitude by $C_0p_0^N$. Therefore
$$
\sigma\int_0^rG(z)g_N(z)\,dz
\ge
w(p_2^N-p_1^N)-C_0p_0^N.
$$
Writing $s=p_1/p_2$ and $\kappa=1-s>0$, this implies
$$
\sigma\int_0^rG(z)g_N(z)\,dz
\ge
p_2^N\left[w-(w+C_0)s^N\right].
$$
For $0\le s<1$,
$$
s\le\frac1{1+\kappa}.
$$
Indeed, $s(1+\kappa)=s(2-s)\le1$. The binomial theorem then gives
$$
s^N\le\frac1{(1+\kappa)^N}
\le\frac1{1+N\kappa}.
$$
Consequently, the displayed lower bound is strictly positive whenever
$$
N>\frac{C_0}{w\kappa}.
$$
One valid threshold is
$$
T=1+\left\lfloor\frac{C_0}{w\kappa}\right\rfloor.
$$
All these operations are rational. Polynomial evaluation and translation require only powers bounded by the polynomial degree. The quantities $\delta,w,p_1,p_2,\kappa$ consequently have polynomial bit length, as does $T$. This proves the lemma.
Fix a rational query $q>0$. Define the focal tail probability and tail first moment by
$$
S(y)=\int_y^b f_t(v)\,dv,
\qquad
W(y)=\int_y^b vf_t(v)\,dv,
$$
with both set to zero for $y\ge b$.
Independence gives
$$
P(q)=\int_0^M zS(z/q)g_N(z)\,dz
$$
and
$$
h(q)=\int_0^M
\left[czS(z/q)-W(z/q)\right]g_N(z)\,dz.
$$
If $qb\le a$, both quantities vanish and the weak constraints hold. Assume henceforth that $qb>a$.
Let $r$ be the largest rival-support point at or below $qb$. More explicitly, partition the bid axis by all scaled rival breakpoints. On each open piece, the mixture density $H'$ is a nonnegative polynomial. Select the last piece with a nonzero polynomial whose left endpoint is below $qb$, and truncate its right endpoint at $qb$.
This construction gives rational $r$ satisfying
$$
0<r\le\min\{qb,M\},
\qquad
H(r)=H(qb)>0.
$$
There is an interval immediately to the left of $r$ on which $H$ is strictly increasing. Above $r$ and below $qb$, the rival distribution has no mass. Above $qb$, the focal tail functions vanish. Thus
$$
h(q)=\int_0^r G_q(z)g_N(z)\,dz,
\qquad
G_q(z)=czS(z/q)-W(z/q).
$$
A valid global bound is
$$
|G_q(z)|\le cM+b.
$$
On a sufficiently short interval immediately to the left of $r$, the function $G_q$ is a rational polynomial of degree at most $d+2$.
The essential issue is whether that polynomial could vanish identically.
Suppose $q>1/c$. Write $y=z/q$. On the relevant focal piece, $S$ and $W$ are polynomials satisfying
$$
W'(y)=yS'(y).
$$
If the local polynomial $G_q$ were identically zero, then
$$
cq\,yS(y)-W(y)=0.
$$
Differentiating yields
$$
cq\,S(y)+(cq-1)yS'(y)=0.
$$
Write $S(y)=\sum_j s_jy^j$. The coefficient of $y^j$ in this identity is
$$
\bigl(cq+(cq-1)j\bigr)s_j.
$$
Every factor in parentheses is strictly positive because $cq>1$. Therefore every $s_j$ would vanish.
This is impossible: immediately to the left of $r/q\le b$, the tail probability $S$ is positive, by the definition of the essential upper endpoint $b$.
The endpoint-dominance lemma therefore applies. It produces a polynomial-bit-length threshold $T_{\mathrm{ROI}}(q)$ and an exact eventual sign for $h(q)$.
For $q\le1/c$, no threshold is needed:
$$
cD-V_t\le(cq-1)V_t\le0
$$
on the winning event. Hence the ROI constraint holds for every $N$.
This handles support gaps and also cases where the local polynomial vanishes at $r$: its first nonzero Taylor coefficient still determines the eventual sign.
Continue with $qb>a$, and put
$$
p=H(r)=H(qb).
$$
Winning requires $D\le qb$, so
$$
P(q)\le M p^N.
$$
The same elementary inequality used above gives
$$
p^N\le\frac1{1+N(1-p)}.
$$
Thus, for example,
$$
N\ge
\left\lceil\frac{M}{B(1-p)}\right\rceil
$$
implies $P(q)<B$. This threshold has polynomial bit length and is computable without taking a large power.
Here $r=M$, and all rival mass is included in the integral. Therefore
$$
P(q)-B
=
\int_0^M\left[zS(z/q)-B\right]g_N(z)\,dz.
$$
The integrand has absolute value at most $M+B$.
Its polynomial expression immediately to the left of $M$ cannot be identically zero. Otherwise, on the corresponding focal piece,
$$
q\,yS(y)=B
$$
would be a polynomial identity. Its left-hand side has zero constant coefficient, whereas $B>0$.
The endpoint-dominance lemma consequently gives an exact eventual sign for $P(q)-B$, beyond a polynomial-bit-length threshold $T_{\mathrm{budget}}(q)$.
Let $L_{\mathrm{soc}}$ denote the encoding length of the society data, excluding $n$ and $\varepsilon$. Define
$$
K=\min\{k\in\mathbb Z_{\ge0}:2^{-k}\le\varepsilon\}.
$$
Every midpoint in $K$ steps of bisection from $[0,1]$ has bit length at most $K+1$.
The constructions above use only:
They do not expand $H^N$.
For completeness, their bit bounds follow from elementary rational-arithmetic estimates. Integrating a density coefficient introduces a divisor at most $d+2$. Evaluating or scaling a degree-$d+2$ polynomial uses powers with exponent at most $d+2$. Sums of polynomially many rationals can be placed over the product of their denominators, whose bit length is at most the sum of the denominator bit lengths. Translating a polynomial introduces binomial coefficients of bit length at most $O(d)$.
These estimates apply successively to $H,S,W$, the endpoint $r$, the translated local polynomial, $\delta,w,\kappa$, and the threshold. The number of construction stages is fixed, so their composition remains a polynomial bound.
It follows that there is an effectively obtainable polynomial $R$ such that every threshold arising from a query of bit length at most $K+1$ is less than
$$
2^{R(m,\tau,d,L_{\mathrm{soc}},K)}.
$$
The bound is uniform over all supported focal types.
Theorem. Under the rational rival-parameter interpretation, the requested intervals can be computed in time polynomial in
$$
m,\tau,d,L,\log n,\log(1/\varepsilon)
$$
whenever
$$
n-1\ge
2^{R(m,\tau,d,L_{\mathrm{soc}},K)}.
$$
Proof. For each focal type, initialize $[\ell,u]=[0,1]$. At each midpoint $q$, determine weak feasibility using Sections 4 and 5. Under the displayed hypothesis, every applicable threshold is satisfied, so every comparison is exact.
If $q$ satisfies both weak constraints, replace $\ell$ by $q$; otherwise replace $u$ by $q$. Section 2 shows that the weak feasible set is $[0,b^*]$, so every update preserves
$$
b^*\in[\ell,u].
$$
After $K$ steps,
$$
u-\ell=2^{-K}\le\varepsilon.
$$
The interval contains the feasible global maximizer $b^*$.
There are $\tau K$ queries. Each uses polynomial-time rational calculations and a binary comparison of $N$ with the constructed threshold. Hence the claimed running time follows. For $K=0$, the initial interval already suffices.
The algorithm can also operate without first constructing a uniform bound: it computes the thresholds at its actual queries and uses the exact comparison rules whenever $N$ exceeds them.
The new result removes the exponentially small residual obstacle for the sufficiently large-$n$ regime of the entire supported density class. It requires neither strict positivity throughout the supports nor nonzero limiting residuals.
It does not resolve the full binary-encoded problem. If $N$ falls below a constructed threshold, the endpoint rule makes no assertion about the finite-$N$ sign. Such a threshold has polynomial bit length but may have exponentially large numerical value.
For comparison, exact dense expansion still gives an algorithm polynomial in numerical $n$: $H^N$ has degree at most $N(d+1)$ on each rival piece, and the expectation integrands have polynomial degree and coefficient bit length in $n$ and the remaining parameters. Rational piecewise integration followed by the bisection of Section 2 therefore terminates in polynomial time in numerical $n$. This remains insufficient when $n$ is binary encoded.
The unresolved range is thus a genuine intermediate range: numerical $n$ can be exponential in the society description, while not yet large enough for the proved endpoint-dominance comparisons. No polynomial-time treatment of that range, and no NP-hardness reduction, is established here.
⟨structured verdict parsed — rendered above⟩
The output establishes a sound partial result: exact bisection comparisons, and hence the requested intervals, can be computed in polynomial time in a sufficiently large-$n$ regime. It also correctly reduces the optimization problem to weak-constraint bisection and describes an algorithm polynomial in numerical $n$.
It does not classify the full binary-encoded problem as polynomial-time solvable or NP-hard. The prover explicitly acknowledges this limitation. I found no false central step in the large-$n$ argument, but its endpoint lemma needs a small clarification of its effective hypotheses.
The interpretation that the rival parameters $\bar\beta_s$ are binary rationals is explicitly stated. This is a natural completion of the task’s encoding specification, but the result is conditional on that interpretation.
The support-endpoint calculation is correct. On an interval where a nonnegative polynomial is not identically zero, its zeros are finite, so it is positive almost everywhere. Thus the first and last nonzero density pieces determine rational essential support endpoints.
The claims $b_s>0$ and $M>0$ follow from normalization of the densities and positivity of the rival parameters.
The rival bid distribution is absolutely continuous. Taking a finite maximum preserves absolute continuity, and differentiation of its CDF gives, almost everywhere,
$$
g_N(z)=N H(z)^{N-1}H'(z).
$$
For each fixed input and fixed $N$, this density is bounded. This assertion is sufficient for the analytic arguments; the prover does not claim a bound independent of $N$.
The payment threshold
$$
P_t(\beta)>0\quad\Longleftrightarrow\quad \beta b_t>a
$$
is correct. Absolute continuity implies $D>a$ almost surely, including when $a=0$. Conversely, the two positive-probability events used in the proof are independent, and their intersection gives positive payment because $D>0$ almost surely.
The feasibility characterization
$$
\frac ab<\frac1c
$$
is correct, including the boundary case $ca=b$.
For necessity, $D>a$ and $V_t\le b$ almost surely imply
$$
cD-V_t>ca-b.
$$
If payment is positive, the winning event has positive probability, so the ROI residual is strictly positive when $ca\ge b$.
For sufficiency, choosing
$$
\frac ab<\beta<\frac1c
$$
makes payment positive and makes the ROI integrand strictly negative on the winning event. Continuity of payment and its limit of zero at $a/b$ then allow the positive budget constraint to be met. Ties have probability zero by independence and absolute continuity, so the dominated-convergence justification is valid.
The derivative formulas are correct:
$$
A'(\beta)=J(\beta),\qquad
P'(\beta)=\beta J(\beta),
$$
and therefore
$$
U'(\beta)=(1-\beta)J(\beta),\qquad
h'(\beta)=(c\beta-1)J(\beta).
$$
The difference-quotient bounds are available because the relevant CDF and payment primitive are Lipschitz for fixed $N$. For a fixed positive $\beta$, density breakpoints exclude only finitely many focal values from pointwise differentiation.
The ensuing monotonicity conclusions are justified:
Together with continuity and $h(0)=P(0)=0$, these facts justify
$$
C=[0,b^*].
$$
Flat portions and support gaps do not invalidate this conclusion.
The argument that $b^*>a/b$ is also valid: the feasibility characterization supplies a feasible parameter strictly between $a/b$ and $1/c$, after choosing it sufficiently close to $a/b$ to meet the budget.
Thus $b^*$ has positive payment and is a feasible maximizer on $[0,1]$. For a feasible parameter above $1$, the stated comparisons with the parameter $1$ follow from the same monotonicity formulas. Consequently, $b^*$ is a global feasible maximizer.
This section genuinely establishes the optimization reduction, independently of whether the constraint comparisons can be implemented efficiently.
The quantitative sign argument is correct under the effective rational-data assumptions used in the applications.
The Taylor estimate is valid: since $\delta\le1$, the higher-order terms satisfy the stated bound relative to the first nonzero coefficient. It follows that the integrand has the desired sign throughout the final interval and has magnitude at least $w$ on the selected subinterval.
The mass calculation gives
$$
\sigma\int_0^rG(z)g_N(z)\,dz
\ge w(p_2^N-p_1^N)-C_0p_0^N.
$$
Using $p_0\le p_1$ yields the displayed lower bound in terms of $s=p_1/p_2$.
The elementary estimate is correct:
$$
s(2-s)\le1,\qquad
s^N\le\frac1{1+N\kappa}.
$$
Substitution shows that strict positivity follows when
$$
N>\frac{C_0}{w\kappa}.
$$
Accordingly,
$$
T=1+\left\lfloor\frac{C_0}{w\kappa}\right\rfloor
$$
is valid even when the ratio is an integer.
There is a minor statement-level gap: the lemma initially assumes only $r>0$ and the existence of suitable left neighborhoods. Its computational conclusion needs a rationally encoded $r$, an available rational bound $C_0$, and effective access to the neighborhood on which the polynomial and strict-increase conditions hold. The surrounding distributional setup supplies a piecewise-polynomial $H$, and the later applications use rational endpoints and bounds, so this does not invalidate those applications.
Minimum clarification: restrict the computational version of the lemma to these effective rational hypotheses and identify how the required left neighborhood is obtained from the supplied piece partition.
The expressions for payment and the ROI residual follow correctly by conditioning on $D$ and using independence.
When $qb\le a$, payment and the ROI residual vanish, so weak feasibility holds.
When $qb>a$, the construction of $r$ correctly handles rival-support gaps and queries beyond the maximum rival bid. It gives
$$
H(r)=H(qb)>0.
$$
Discarding the region above $r$ is justified: before $qb$ it contains no rival mass, and after $qb$ the focal tails vanish.
The bound
$$
|G_q(z)|\le cM+b
$$
is valid. The local polynomial degree is at most $d+2$.
The nonvanishing argument for $q>1/c$ is correct. An identically zero local residual would imply
$$
cq\,S(y)+(cq-1)yS'(y)=0.
$$
Every coefficient multiplier
$$
cq+(cq-1)j
$$
is positive. Hence the local polynomial $S$ would be zero, contradicting positivity of the tail immediately below the essential upper endpoint.
This reasoning also covers a local focal-support gap, where $S$ may be a positive constant.
For $q\le1/c$, the pointwise ROI inequality directly establishes feasibility for every $N$. No asymptotic comparison is needed.
Thus the eventual exact ROI comparison is justified.
Both cases are correct.
If $p<1$, the bound
$$
P(q)\le Mp^N
$$
follows from the winning condition and $D\le M$. The proposed threshold gives
$$
P(q)\le\frac{M}{1+N(1-p)}<B.
$$
The strict inequality follows from the additional $1$ in the denominator, including when the threshold ratio is an integer.
If $p=1$, the construction indeed gives $r=M$, and normalization of $g_N$ justifies writing $P(q)-B$ as the stated integral.
The local polynomial cannot vanish identically: the polynomial $q\,yS(y)$ has zero constant coefficient, whereas the constant polynomial $B$ does not. Although the local interval need not contain zero, equality on that interval would be a polynomial identity, so this coefficient argument is legitimate.
The endpoint lemma therefore supplies the claimed eventual exact budget comparison.
The rational-arithmetic estimates are sound in substance. The constructions use polynomially many density pieces and polynomial degrees, with powers whose exponents depend on $d$, rather than on $N$.
Translation, integration, substitution, and evaluation produce rational quantities of polynomial bit length. In particular, taking the power involved in $w$ uses an exponent at most the local polynomial degree. Computing the threshold does not require expanding $H^N$.
Subject to the effective-neighborhood clarification above, these estimates justify a uniform, effectively obtainable polynomial bound $R$ on threshold bit lengths. An explicit formula for $R$ is unnecessary for the claimed existence theorem.
Under the large-$n$ hypothesis, all bisection comparisons are exact. The invariant
$$
b^*\in[\ell,u]
$$
is correct, including equality queries and queries with zero payment. After $K$ steps, the width is at most $\varepsilon$.
The edge case $K=0$ is correctly handled: the initial interval $[0,1]$ already contains the feasible maximizer.
The theorem therefore establishes the requested computation in its stated restricted regime.
The final description of dense expansion also supports an algorithm polynomial in numerical $n$: the degrees grow linearly with $N$, and exact coefficient bit lengths remain polynomial in numerical $N$ and the other input parameters. This provides genuine additional progress, but does not meet the requested dependence on $\log n$.
The major unresolved issue is coverage of the full input class. A threshold with polynomial bit length may have exponentially large numerical value. Consequently, the dense-expansion algorithm and the large-$n$ endpoint algorithm leave a range where neither has established polynomial running time in the binary encoding.
The prover accurately identifies this obstruction. There is no justification for promoting the restricted theorem to a general polynomial-time classification, and no hardness reduction is presented.
The minimum further work needed is:
⟨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.