Answer: —
Proposition 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateOCPA provides the consumer with the maxi- mum expected utility that any BIC and interim IR auction could provide.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(N\), \(V\), \(D\), rational masses \(\mu_{q,c}\) over provider service classes \(q\) and costs \(c\), known cost priors, and rationally represented duration CDFs \(G_q\), compute an \(\epsilon\)-optimal direct procurement auction. The auction chooses finite-stage invocation schedules of real-valued provider mass, conditional on prior noncompletion, and payments to maximize expected consumer utility subject to BIC and interim IR; ask whether the stronger DSIC and ex-post IR guarantees also hold.
A society is given by its support: the list of the \(\tau\) types \((q,c)\) with positive mass, each mass \(\mu_{q,c}\) a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(m\) is the number of publicly observable service classes. The population is nonatomic, with total mass \(N=\sum_{q,c}\mu_{q,c}>0\), not necessarily one.
Costs are private and nonnegative. For class \(q\), let its possible costs be \(c_{q,1}<\cdots<c_{q,h_q}\), its mass be \(M_q\), and its common cost prior be \(p_{q,j}=\mu_{q,c_{q,j}}/M_q\). Assume regularity: \(\phi_{q,1}=c_{q,1}\) and \(\phi_{q,j}=c_{q,j}+(c_{q,j}-c_{q,j-1})\sum_{\ell<j}p_{q,\ell}/p_{q,j}\) are nondecreasing in \(j\).
The consumer has binary-rational value \(V>0\), deadline \(D>0\), and tolerance \(0<\epsilon<1\). Each commonly known duration CDF \(G_q\) is continuous piecewise linear on \([0,D]\), specified by rational breakpoints and values, with \(G_q(0)=0\). Completion by \(D\) earns \(V\), otherwise zero; additional completions earn nothing.
A direct auction accepts only cost reports from the reporting provider’s class cost set. At each reported mass histogram \(r\), with \(\sum_b r_{q,b}=M_q\), it chooses finitely many times \(0\le t_1\le\cdots\le t_K\le D\), recruitment fractions \(a_{q,b,k}\ge0\) with \(\sum_k a_{q,b,k}\le1\), and nonnegative per-unit payments \(\pi_{q,b,k}\). Recruitment within each reported type is anonymous; no provider is recruited twice, and the empty schedule is permitted.
Stage \(k\) recruits mass \(x_{q,b,k}=r_{q,b}a_{q,b,k}\) only if no completion has occurred. Invoked providers incur their entire cost immediately, receive payment upon invocation, and continue working without cancellation. Define the mass completion law by \(S_r(t)=\prod_{k:t_k\le t}\prod_{q,b}(1-G_q(t-t_k))^{x_{q,b,k}}\), with \(0^0=1\); \(S_r(t)\) is the probability of no completion by \(t\).
An individual deviation leaves the histogram unchanged. A class-\(q\) provider of true cost \(c\), reporting \(b\), has expected utility \(u_q(c,b;r)=\sum_k a_{q,b,k}S_r(t_k)(\pi_{q,b,k}-c)\). BIC and interim IR require \(u_q(c,c;\mu)\ge u_q(c,b;\mu)\) and \(u_q(c,c;\mu)\ge0\) for every possible \(q,c,b\). DSIC requires the same incentive inequality at every histogram \(r\); ex-post IR requires \(\pi_{q,c,k}\ge c\) whenever a truthful provider can actually be invoked.
Rules may randomize, with incentive inequalities and objectives evaluated in expectation over that randomization. The truthful consumer objective is \(U=V(1-S_\mu(D))-\sum_{q,c,k}\mu_{q,c}a_{q,c,k}S_\mu(t_k)\pi_{q,c,k}\). An \(\epsilon\)-optimal auction has utility within additive \(\epsilon\) of the supremum over these BIC, interim-IR auctions. Auction rules must have finite descriptions permitting evaluation to requested numerical precision; \(L\) denotes total input bit length.
Is computing an \(\epsilon\)-optimal auction polynomial-time in \(m,\tau,L,1/\epsilon\), or NP-hard?
Can the same BIC, interim-IR utility supremum be approached arbitrarily closely by DSIC, ex-post-IR auctions?
For finitely many providers with independent durations and independent regular cost priors, an optimal contingent procurement auction is claimed to maximize consumer utility among all BIC, interim-IR auctions and also satisfy DSIC and ex-post IR; no polynomial-time guarantee is established. [Verified discrete result](https://publications.aston.ac.uk/id/eprint/45193/1/Fahradietal_2023_VoR.pdf)
No result settling this explicitly specified mass model was identified in the literature searches.
The DSIC, ex-post-IR approximation question has an affirmative answer.
The general computational classification remains unresolved here. I prove two additional results about it:
The second result rules out a polynomial-time algorithm that always outputs an explicit list of polynomially many stages. It does not establish NP-hardness under the task’s more general finite-description requirement, which permits compact descriptions of large schedules.
For a class $q$, suppress its subscript and write its supported costs as $c_1<\cdots<c_h$, with masses $\mu_j>0$.
At the truthful histogram, define the expected invocation probability and expected payment per provider by
$$
A_j=\mathbb E\left[\sum_k a_{j,k}S_\mu(t_k)\right],
\qquad
T_j=\mathbb E\left[\sum_k a_{j,k}S_\mu(t_k)\pi_{j,k}\right].
$$
Expectations include auction randomization. Since an individual deviation leaves the histogram unchanged, a cost-$c_i$ provider reporting $c_j$ has utility $T_j-c_iA_j$.
It suffices to consider auctions with finite expected payments: nonnegative payments with infinite total expectation give consumer utility $-\infty$.
For $i<j$, adding the two incentive inequalities gives
$$
(c_j-c_i)(A_i-A_j)\ge0.
$$
Thus BIC requires
$$
A_1\ge\cdots\ge A_h\ge0.
$$
Put $u_j=T_j-c_jA_j$. The incentive constraint against reporting $c_{j+1}$ gives
$$
u_j\ge u_{j+1}+(c_{j+1}-c_j)A_{j+1}.
$$
Together with $u_h\ge0$, this implies
$$
T_j\ge c_jA_j+
\sum_{\ell=j+1}^{h}(c_\ell-c_{\ell-1})A_\ell.
$$
Multiplying by masses and summing yields
$$
\begin{aligned}
\sum_j\mu_jT_j
&\ge
\sum_j\mu_jc_jA_j+
\sum_{\ell=2}^{h}(c_\ell-c_{\ell-1})A_\ell
\sum_{j<\ell}\mu_j\\
&=\sum_j\mu_j\phi_jA_j.
\end{aligned}
$$
The last equality uses exactly the virtual-cost formula in the question; it requires no normalization of population mass.
Conversely, for any nonincreasing allocation vector, define
$$
T_j=c_jA_j+
\sum_{\ell=j+1}^{h}(c_\ell-c_{\ell-1})A_\ell.
$$
These payments satisfy every incentive inequality and interim IR. Indeed, for $i<j$,
$$
u_i-u_j=
\sum_{\ell=i+1}^{j}(c_\ell-c_{\ell-1})A_\ell,
$$
and monotonicity gives
$$
(c_j-c_i)A_j
\le u_i-u_j
\le(c_j-c_i)A_i.
$$
The lower bound is the incentive constraint for type $i$ against report $j$; the upper bound is the reverse constraint. Also, every $u_j$ is nonnegative.
A deterministic schedule $\sigma$ consists of times $t_k$ and recruitment masses $x_{q,j,k}$ satisfying
$$
x_{q,j,k}\ge0,
\qquad
\sum_kx_{q,j,k}\le\mu_{q,j}.
$$
Define its virtual surplus by
$$
\mathcal F(\sigma)
=
V\bigl(1-S_\mu(D)\bigr)
-
\sum_{q,j,k}\phi_{q,j}x_{q,j,k}S_\mu(t_k).
$$
Let
$$
z_{q,k}=\sum_jx_{q,j,k},
\qquad
R_{q,k}=\sum_{\ell\le k}z_{q,\ell},
\qquad
R_{q,0}=0,
$$
and let
$$
B_{q,j}=\sum_{i<j}\mu_{q,i}.
$$
Replace the assignment within class $q$ by
$$
\widehat x_{q,j,k}
=
\left|
[B_{q,j},B_{q,j}+\mu_{q,j})
\cap
[R_{q,k-1},R_{q,k})
\right|,
$$
where the bars denote interval length.
This preserves every class’s recruitment mass at every stage. It therefore preserves the survival law. It is feasible because the recruited intervals are disjoint and have total length at most $M_q$.
Write $s_k=S_\mu(t_k)$. Since each CDF is nondecreasing,
$$
1\ge s_1\ge\cdots\ge s_K\ge0.
$$
Tied invocation times cause no difficulty because $G_q(0)=0$.
For a class $q$, let $C_q(R)$ be the minimum virtual cost of selecting mass $R$. Regularity means that $\phi_{q,j}$ is nondecreasing in $j$. Consequently, filling the cost intervals in increasing order attains $C_q(R)$: replacing selected mass of a higher virtual cost by available mass of a lower virtual cost weakly reduces cost, and such exchanges terminate at the cheapest-first assignment.
For the original assignment, put
$$
b_{q,k}=\sum_j\phi_{q,j}x_{q,j,k}.
$$
Every recruitment prefix satisfies
$$
\sum_{\ell\le k}b_{q,\ell}\ge C_q(R_{q,k}).
$$
Setting $s_{K+1}=0$, summation by parts gives
$$
\sum_{k=1}^{K}s_kb_{q,k}
=
\sum_{k=1}^{K}(s_k-s_{k+1})
\sum_{\ell\le k}b_{q,\ell}.
$$
All coefficients are nonnegative. The sorted assignment attains $C_q(R_{q,k})$ for every prefix simultaneously, so it weakly reduces expected virtual costs. Hence
$$
\mathcal F(\widehat\sigma)\ge\mathcal F(\sigma).
$$
For the sorted schedule, define fractions
$$
\widehat a_{q,j,k}=\frac{\widehat x_{q,j,k}}{\mu_{q,j}},
\qquad
F_{q,j,k}=\sum_{\ell\le k}\widehat a_{q,j,\ell}.
$$
At each recruitment prefix, earlier cost intervals are full, at most one interval is partial, and later intervals are empty. Thus
$$
F_{q,1,k}\ge\cdots\ge F_{q,h_q,k}.
$$
Use these same times and fractions at every reported histogram $r$. They remain feasible because each type’s fractions sum to at most one. Define
$$
A_{q,j}(r)=\sum_k\widehat a_{q,j,k}S_r(t_k).
$$
With $s_k(r)=S_r(t_k)$ and $s_{K+1}(r)=0$,
$$
A_{q,j}(r)
=
\sum_{k=1}^{K}
\bigl(s_k(r)-s_{k+1}(r)\bigr)F_{q,j,k}.
$$
The coefficients are nonnegative, so
$$
A_{q,1}(r)\ge\cdots\ge A_{q,h_q}(r)
$$
at every histogram.
Set
$$
T_{q,j}(r)
=
c_{q,j}A_{q,j}(r)
+
\sum_{\ell=j+1}^{h_q}
(c_{q,\ell}-c_{q,\ell-1})A_{q,\ell}(r).
$$
Pay the same amount at every invocation of reported type $j$:
$$
\pi_{q,j,k}(r)=
\begin{cases}
T_{q,j}(r)/A_{q,j}(r),&A_{q,j}(r)>0,\\
c_{q,j},&A_{q,j}(r)=0.
\end{cases}
$$
If $A_{q,j}(r)=0$, monotonicity forces all higher-cost allocation probabilities to be zero, so $T_{q,j}(r)=0$. Thus these invocation payments implement the specified expected payments in both branches.
The pairwise verification in Section 1 applies at every fixed $r$, proving DSIC. This uses the stipulated assumption that a deviation leaves $r$ unchanged.
Moreover, whenever $A_{q,j}(r)>0$,
$$
c_{q,j}
\le\pi_{q,j,k}(r)
=
c_{q,j}+
\sum_{\ell>j}
(c_{q,\ell}-c_{q,\ell-1})
\frac{A_{q,\ell}(r)}{A_{q,j}(r)}
\le c_{q,h_q}.
$$
Thus truthful invocation payments satisfy ex-post IR.
At truth, these payments attain the payment bound exactly, so the constructed auction’s consumer utility is $\mathcal F(\widehat\sigma)$.
For rational schedules and rational numerical histograms, the rule has a finite description permitting arbitrary-precision evaluation. Survival factors have rational bases and rational exponents; zero factors can be identified from the encoded data. Positive factors, sums, and the displayed payment ratios are computable to any requested precision. This does not assert a polynomial evaluation bound.
Assume in this section that
$$
G_q(D)<1
$$
for every populated class. Define
$$
H_q(u)=-\log(1-G_q(u)),
\qquad 0\le u\le D.
$$
Then
$$
S_\mu(t)=
\exp\left(-\sum_{q,j,k:t_k\le t}
x_{q,j,k}H_q(t-t_k)\right).
$$
Let $b_q$ be the maximum slope of a linear segment of $G_q$, and put
$$
B=\max_q\frac{b_q}{1-G_q(D)}.
$$
Each $H_q$ is $B$-Lipschitz. Indeed, on its linear segments,
$$
H_q'(u)=\frac{G_q'(u)}{1-G_q(u)}
\le\frac{b_q}{1-G_q(D)},
$$
and integrating across the finitely many segments gives the claimed bound.
Also define
$$
\overline H=
\max_q\frac{G_q(D)}{1-G_q(D)},
\qquad
W=\sum_{q,j}\mu_{q,j}\phi_{q,j},
\qquad
\Phi=\max_{q,j}\phi_{q,j}.
$$
The inequality
$$
-\log(1-g)=\int_0^g\frac{du}{1-u}
\le\frac{g}{1-g}
$$
shows that $H_q(u)\le\overline H$.
If $B=0$, all CDFs vanish on $[0,D]$, and the empty schedule is optimal. Hence suppose $B>0$.
Fix an accuracy $\eta>0$.
Choose
$$
J=
\max\left\{
1,\left\lceil
\frac{4D(V+W)NB}{\eta}
\right\rceil
\right\},
\qquad
\Delta=\frac DJ.
$$
Round every invocation time downward to the grid
$$
0,\Delta,\ldots,J\Delta.
$$
For any pair of stages, rounding changes their time difference by at most $\Delta$. Extend $H_q(u)$ to be zero for $u<0$; this extension is still $B$-Lipschitz because $H_q(0)=0$.
At corresponding evaluation times, the survival exponents therefore differ by at most
$$
NB\Delta.
$$
This statement includes stages that become tied after rounding: their newly coincident recruitment contributes $H_q(0)=0$.
Since $z\mapsto e^{-z}$ is $1$-Lipschitz on the nonnegative real line,
$$
|S_\mu(t_k)-S_\mu^{\mathrm{round}}(t_k^{\mathrm{round}})|
\le NB\Delta.
$$
The same bound holds at the deadline. Consequently,
$$
|\mathcal F(\sigma)-\mathcal F(\sigma^{\mathrm{round}})|
\le(V+W)NB\Delta
\le\frac{\eta}{4}.
$$
All recruitment at a common grid time can now be merged without changing the objective.
There are at most $Q=J+1$ grid times. Put
$$
C=\Phi+(V+W)\overline H.
$$
Here $C>0$ because $B>0$ implies that some terminal completion probability is positive.
Choose a positive rational $h$ such that
$$
h\le\frac{\eta}{4\tau Q C}.
$$
At every type and grid time, round recruitment mass downward to a multiple of $h$.
Let $\xi$ be the total removed mass. Then
$$
\xi\le\tau Qh.
$$
At any time, removing this mass changes the survival exponent by at most $\overline H\xi$, hence changes survival by at most $\overline H\xi$.
The virtual-cost difference is bounded by the removed virtual cost plus the effect on survival:
$$
\left|
\sum_{q,j,k}\phi_{q,j}x_{q,j,k}S(t_k)
-
\sum_{q,j,k}\phi_{q,j}x'_{q,j,k}S'(t_k)
\right|
\le\Phi\xi+W\overline H\xi.
$$
Together with the completion-value term, this gives
$$
|\mathcal F(\sigma^{\mathrm{round}})
-\mathcal F(\sigma^{\mathrm{grid}})|
\le C\xi
\le\frac{\eta}{4}.
$$
Thus every finite real schedule has a feasible grid schedule satisfying
$$
\mathcal F(\sigma^{\mathrm{grid}})
\ge\mathcal F(\sigma)-\frac{\eta}{2}.
$$
The bound is uniform over the original number of stages.
The grid family is finite: every recruitment entry is a nonnegative integer multiple of $h$, and each type’s total is at most its available mass.
Evaluate each grid objective within $\eta/8$, and choose a schedule maximizing the approximate values. Its exact objective is within $\eta/4$ of the best grid objective. Therefore it satisfies
$$
\mathcal F(\sigma_{\mathrm{chosen}})
\ge\sup_\sigma\mathcal F(\sigma)-\frac{3\eta}{4}.
$$
Sorting and applying Section 2 produce a DSIC, ex-post-IR auction with at least this utility.
For rationally encoded numerical input, including supported costs, all grid parameters can be chosen effectively and the finite search terminates. Its running time is not asserted to be polynomial. In particular, the number $J$ depends on numerical magnitudes, rather than only their bit lengths.
Let $U_{\mathrm{BIC}}^*$ and $U_{\mathrm{DSIC}}^*$ denote the utility suprema under the respective incentive and IR requirements.
For any BIC, interim-IR auction, Section 1 gives
$$
U\le\mathbb E[\mathcal F(\sigma)]
\le\sup_\sigma\mathcal F(\sigma).
$$
Also, DSIC and ex-post IR imply BIC and interim IR. Hence
$$
U_{\mathrm{DSIC}}^*
\le U_{\mathrm{BIC}}^*
\le\sup_\sigma\mathcal F(\sigma).
$$
If all $G_q(D)<1$, Section 3 approximates the last supremum arbitrarily closely using finitely described rational schedules. Section 2 implements their sorted versions by DSIC, ex-post-IR auctions. Thus all three quantities are equal.
The remaining case has a direct construction. If some populated class satisfies $G_q(D)=1$, recruit mass $\delta>0$ of its cheapest type at time zero and pay $c_{q,1}$ upon invocation. Use the same recruitment fraction at every histogram and recruit no other report.
This rule is DSIC: the cheapest type has zero truthful utility, and every higher-cost type receives negative utility from claiming that report. It is ex-post IR. At truth,
$$
S_\mu(D)=(1-G_q(D))^\delta=0,
\qquad
U=V-c_{q,1}\delta.
$$
Taking $\delta$ arbitrarily small proves that its utility approaches $V$. Nonnegative payments imply $U\le V$, and nonnegative virtual costs imply $\mathcal F(\sigma)\le V$.
Therefore, in all cases,
$$
\boxed{
U_{\mathrm{BIC}}^*
=
U_{\mathrm{DSIC}}^*
=
\sup_\sigma\mathcal F(\sigma).
}
$$
In particular, for every $\eta>0$, a finitely described DSIC, ex-post-IR auction has utility at least $U_{\mathrm{BIC}}^*-\eta$. Randomization does not increase this supremum.
This section supplies the new obstruction to a polynomial bound on the number of stages.
For an integer $n\ge4$, take one class, one supported cost, and total mass one:
$$
m=\tau=1,
\qquad
\mu=1,
\qquad
c=2^n,
\qquad
V=4c,
\qquad
D=1.
$$
Regularity is automatic because there is one cost type.
Let
$$
d_n=2^{-2n},
$$
and specify the continuous piecewise-linear CDF
$$
G(u)=
\begin{cases}
u/(2d_n),&0\le u\le d_n,\\
1/2,&d_n\le u\le1.
\end{cases}
$$
All input numbers are binary rational. The total input bit length is $\Theta(n)$, and $G(D)=1/2$, so this family avoids the zero-survival degeneracy.
Write
$$
\lambda=\log2,
\qquad
\mathcal U_n=\frac12\left(V-\frac c\lambda\right).
$$
The integral representation of $\log2$ gives
$$
\frac12<\lambda<1.
$$
The number $\mathcal U_n$ will be an upper benchmark; I do not claim it is the exact supremum for a fixed $n$.
Consider a deterministic schedule with $K\ge1$ positive recruitment stages. Write its masses as $x_k$, and let
$$
X=\sum_kx_k\le1,
\qquad
y_k=\lambda x_k,
\qquad
z_k=\sum_{\ell<k}y_\ell.
$$
Because $G(u)\le1/2$ throughout the horizon,
$$
S(t_k)\ge e^{-z_k},
\qquad
S(D)\ge e^{-\lambda X}.
$$
The first inequality remains valid for tied invocation times.
Set
$$
P=1-e^{-\lambda X}.
$$
Then $0\le P\le1/2$. Expected virtual costs satisfy
$$
c\sum_kx_kS(t_k)
\ge\frac c\lambda\sum_ky_ke^{-z_k}.
$$
For every $y\ge0$,
$$
y-1+e^{-y}\ge\frac12(1-e^{-y})^2.
$$
To verify this, subtract the right side from the left. The resulting function is zero at $y=0$ and has derivative $(1-e^{-y})^2\ge0$.
Consequently,
$$
\begin{aligned}
\sum_ky_ke^{-z_k}
&\ge
\sum_ke^{-z_k}(1-e^{-y_k})
+\frac12\sum_ke^{-z_k}(1-e^{-y_k})^2.
\end{aligned}
$$
Define
$$
\Delta_k=e^{-z_k}(1-e^{-y_k}).
$$
These increments telescope:
$$
\sum_k\Delta_k=P.
$$
Since $e^{-z_k}\le1$,
$$
e^{-z_k}(1-e^{-y_k})^2\ge\Delta_k^2.
$$
Cauchy–Schwarz therefore gives
$$
\sum_ky_ke^{-z_k}
\ge P+\frac12\sum_k\Delta_k^2
\ge P+\frac{P^2}{2K}.
$$
Combining the completion-value and cost bounds,
$$
\mathcal F(\sigma)
\le
\left(V-\frac c\lambda\right)P
-\frac{cP^2}{2\lambda K}.
$$
The right side is increasing for $0\le P\le1/2$. Its derivative is at least
$$
c\left(4-\frac1\lambda-\frac1{2\lambda K}\right)
\ge c\left(4-\frac3{2\lambda}\right)>0.
$$
It follows that
$$
\boxed{
\mathcal F(\sigma)
\le\mathcal U_n-\frac{c}{8\lambda K}
\le\mathcal U_n-\frac{c}{8K}.
}
$$
Let
$$
K_n=2^{2n}=\frac1{d_n}.
$$
Recruit mass $1/K_n$ at each time
$$
t_k=(k-1)d_n,
\qquad
1\le k\le K_n,
$$
and pay $c$ upon invocation. With one possible report, this auction is DSIC and ex-post IR.
At stage $k$, every earlier batch has reached the CDF plateau. Thus
$$
S(t_k)=e^{-\lambda(k-1)/K_n},
\qquad
S(D)=e^{-\lambda}=\frac12.
$$
Its expected payment is the geometric sum
$$
P_n^{\mathrm{pay}}
=
\frac c{K_n}
\sum_{i=0}^{K_n-1}e^{-\lambda i/K_n}
=
\frac{c}{2K_n(1-e^{-\lambda/K_n})}.
$$
For $y>0$,
$$
0\le\frac1{1-e^{-y}}-\frac1y\le1.
$$
The lower bound follows from $1-e^{-y}\le y$. The upper bound is equivalent to $e^y\ge1+y$.
Applying this with $y=\lambda/K_n$ gives
$$
0\le P_n^{\mathrm{pay}}-\frac c{2\lambda}
\le\frac c{2K_n}.
$$
Hence this auction has utility at least
$$
\mathcal U_n-\delta_n,
\qquad
\delta_n=\frac c{2K_n}=2^{-n-1}.
$$
Together with the preceding upper bound,
$$
\mathcal U_n-\delta_n
\le U_{\mathrm{BIC}}^*
\le\mathcal U_n.
$$
Let an arbitrary randomized BIC, interim-IR auction operate on this instance, and let $K$ be its random number of positive recruitment stages.
With one cost type, interim IR implies that expected payment is at least $c$ times expected invocation mass. Therefore
$$
U\le\mathbb E[\mathcal F(\sigma)].
$$
For nonempty schedules, Section 5.2 implies
$$
\mathcal F(\sigma)
\le\mathcal U_n-\frac{c}{8(K+1)}.
$$
This inequality also holds for the empty schedule: its virtual surplus is zero, whereas $\lambda>1/2$ implies $\mathcal U_n>c$.
Thus
$$
U\le\mathcal U_n-\frac c8
\mathbb E\left[\frac1{K+1}\right].
$$
If the auction is $\epsilon$-optimal, then
$$
U\ge U_{\mathrm{BIC}}^*-\epsilon
\ge\mathcal U_n-\delta_n-\epsilon.
$$
Consequently,
$$
\mathbb E\left[\frac1{K+1}\right]
\le\frac{8(\epsilon+\delta_n)}c.
$$
If $\mathbb E[K]$ is finite, Cauchy–Schwarz gives
$$
1
\le
\mathbb E[K+1]\,
\mathbb E\left[\frac1{K+1}\right].
$$
Hence
$$
\boxed{
\mathbb E[K]\ge
\frac{c}{8(\epsilon+\delta_n)}-1.
}
$$
If $\mathbb E[K]$ is infinite, the claimed lower bound holds automatically.
Take the fixed tolerance $\epsilon=1/16$. For $n\ge4$,
$$
8(\epsilon+\delta_n)\le\frac34,
$$
so
$$
\mathbb E[K]\ge\frac43\,2^n-1\ge2^n.
$$
Proved conclusion: for this family of input length $\Theta(n)$, every $1/16$-optimal BIC, interim-IR auction uses exponentially many positive recruitment stages in expectation. In particular, every deterministic such auction requires exponentially many stages.
The unrestricted optimization is effectively approximable by finite search on rational inputs, and its incentive constraints can be implemented without losing utility.
However, polynomially many explicitly listed stages cannot suffice in general. The preceding family proves this even with one class and one supported cost.
The task permits more general finite descriptions. Indeed, the large schedule in Section 5.3 itself has a compact description:
$$
K_n=2^{2n},
\qquad
t_k=(k-1)2^{-2n},
\qquad
a_k=2^{-2n}.
$$
Therefore the stage lower bound alone neither rules out a polynomial-time algorithm producing suitable compact rules nor supplies an NP-hardness reduction.
The remaining target is to classify optimization under that permitted representation. No polynomial-time algorithm or NP-hardness proof for it is established here.
⟨structured verdict parsed — rendered above⟩
The output establishes the equality of the BIC, interim-IR and DSIC, ex-post-IR utility suprema, subject to a minor clarification about numerical encoding. Its discretization and exponential stage lower bound are mathematically sound. It does not settle the requested computational classification under the permitted finite-description representation, and it expressly acknowledges this limitation.
No false central mathematical step was found. The appropriate overall status is partial.
The definitions of $A_j$ and $T_j$ correctly incorporate both invocation probabilities and auction randomization. Because deviations leave the histogram unchanged, the reporting utility is indeed $T_j-c_iA_j$.
Adding the two incentive inequalities for $i<j$ correctly yields
$$
(c_j-c_i)(A_i-A_j)\ge0.
$$
Since supported costs are strictly increasing, this establishes the required monotonicity.
The adjacent incentive constraints and highest-cost interim IR correctly imply
$$
T_j\ge c_jA_j+\sum_{\ell=j+1}^{h}(c_\ell-c_{\ell-1})A_\ell.
$$
Summing against the masses gives exactly the stated virtual-cost bound. The computation uses
$$
\frac{\sum_{i<j}p_i}{p_j}
=
\frac{\sum_{i<j}\mu_i}{\mu_j},
$$
so no population normalization is required.
The converse verification is also correct: monotonicity bounds the utility difference between the two relevant allocation probabilities, establishing both directions of every pairwise incentive constraint. All constructed truthful utilities are nonnegative.
Restricting attention to finite expected payments is justified: completion value is bounded by $V$, so infinite expected nonnegative payments yield utility $-\infty$.
The interval construction preserves each class’s recruited mass at each stage. Since duration distributions depend only on class, it therefore preserves the entire survival law.
Feasibility follows from disjoint recruitment intervals contained in the class’s total mass interval. This works for arbitrary positive total population mass.
The survival weights are nonincreasing. In particular, simultaneous stages do not alter survival at their common invocation time because $G_q(0)=0$.
Regularity supplies the precise ordering needed for cheapest-first selection to minimize virtual cost at every recruitment prefix. The summation-by-parts identity is correct, and its coefficients are nonnegative. Consequently, simultaneous prefix minimization implies the claimed weak improvement in virtual surplus.
No substantive gap was found here.
The sorted recruitment fractions have nonincreasing cumulative fractions across supported costs. Keeping those fractions fixed at every histogram preserves feasibility.
The identity
$$
A_{q,j}(r)=
\sum_{k=1}^{K}
\bigl(s_k(r)-s_{k+1}(r)\bigr)F_{q,j,k}
$$
is correct with $s_{K+1}(r)=0$. Survival is nonincreasing at every histogram, so the identity establishes allocation monotonicity everywhere.
The payment formula then satisfies all incentive constraints by the already verified pairwise calculation. This proves DSIC according to the task’s stipulated meaning, including its assumption that individual deviations leave $r$ unchanged.
The zero-allocation branch is handled correctly: $A_{q,j}(r)=0$ forces every higher-cost allocation probability to vanish, hence $T_{q,j}(r)=0$.
When allocation is positive, the payment bounds follow from
$$
0\le\frac{A_{q,\ell}(r)}{A_{q,j}(r)}\le1
\qquad(\ell>j).
$$
Thus payments are at least the truthful cost and at most the highest supported class cost. The zero-allocation branch also pays the reported cost, so it causes no ex-post IR problem.
At truth, the construction attains the virtual payment bound exactly.
Minor encoding issue: the computability discussion establishes evaluation for rational schedules and rational numerical histograms, and later explicitly assumes rationally encoded supported costs. The task explicitly specifies rational masses but does not explicitly specify the encoding of costs. Interpreting numerical costs as binary rationals is a natural clarification, but the final computational and finite-description claims should retain that qualification.
Minimum clarification: state the assumed cost encoding once and carry it through the final conclusions. The supplied evaluation argument should also retain its stated numerical-histogram convention.
The Lipschitz bound for $H_q$ is valid. The denominator is uniformly bounded below by $1-G_q(D)>0$, and the finitely many linear segments permit the stated global bound.
The upper bound $\overline H$ follows from the displayed integral inequality. The case $B=0$ is handled correctly: every CDF then vanishes throughout the horizon, and nonnegative costs make the empty schedule optimal.
For time rounding, downward rounding changes any pairwise time difference by at most $\Delta$. Extending $H_q$ by zero to negative arguments is valid because $H_q(0)=0$. This also handles stages becoming simultaneous.
Since total recruited mass is at most $N$, the exponent error is at most $NB\Delta$. The exponential Lipschitz bound then gives the survival error used in the objective estimate. The virtual-cost coefficient sum is at most $W$, so the stated $\eta/4$ bound is correct.
For mass rounding, the removed mass is at most $\tau Qh$. Its contribution to any survival exponent is at most $\overline H\xi$. The payment difference correctly includes both removed virtual cost and changed survival probabilities:
$$
\Phi\xi+W\overline H\xi.
$$
Adding the completion-value error gives exactly $C\xi$.
The constants and accumulated errors are consistent: grid approximation loses at most $\eta/2$, and approximate maximization loses at most another $\eta/4$.
The search family is genuinely finite, and the stated objective evaluations are effective under the rational encoding assumptions. This proves effective additive approximation, without a polynomial running-time guarantee.
For randomized BIC auctions, the payment bound correctly gives
$$
U\le\mathbb E[\mathcal F(\sigma)]
\le\sup_\sigma\mathcal F(\sigma).
$$
It does not require incentive compatibility separately for each realized schedule.
When every terminal CDF value is below one, the uniform discretization and DSIC implementation together approximate the schedule supremum arbitrarily closely.
When some populated class has $G_q(D)=1$, the small-mass construction correctly gives certain completion at truth:
$$
(1-G_q(D))^\delta=0
\qquad(\delta>0).
$$
Its incentive analysis is correct. The cheapest type has zero utility from recruitment, and higher-cost types cannot gain by reporting that type. Payments equal truthful recruited cost.
Minor feasibility omission: the construction says to recruit mass $\delta>0$ of the cheapest type without explicitly restricting $\delta$ to its available mass.
Minimum clarification: require
$$
0<\delta\le\mu_{q,c_{q,1}},
$$
and take $\delta$ to zero within this range. If rational descriptions are intended, explicitly choose rational $\delta$.
With that routine clarification, the construction approaches $V$, which is an upper bound because payments are nonnegative. The equality of all three suprema and the conclusion that randomization does not increase the supremum follow.
The input family satisfies the stated assumptions: positive mass, nonnegative cost, automatic regularity, and a continuous rational piecewise-linear CDF. Its bit length is $\Theta(n)$.
The schedule bounds
$$
S(t_k)\ge e^{-z_k},
\qquad
S(D)\ge e^{-\lambda X}
$$
are valid because every duration completion probability is at most $1/2$. They remain valid with simultaneous invocation times.
The scalar inequality used to bound costs is correct: the derivative of the difference between its two sides is $(1-e^{-y})^2$. The telescoping calculation, comparison with $\Delta_k^2$, and Cauchy–Schwarz application all have the stated signs and constants.
The resulting upper-bound expression is increasing throughout $0\le P\le1/2$. Substitution at $P=1/2$ gives exactly
$$
\mathcal F(\sigma)
\le\mathcal U_n-\frac{c}{8\lambda K}
\le\mathcal U_n-\frac{c}{8K}.
$$
In the constructed comparison schedule, every earlier batch has reached the plateau at each invocation, and the final batch reaches it by the deadline. The geometric payment sum and its error estimate are correct.
The randomized argument correctly uses interim IR only in expectation. Its extension to empty schedules is valid, and the reciprocal-moment inequality yields the stated expected stage bound. For $\epsilon=1/16$ and $n\ge4$, the final numerical constants check out.
Thus the exponential lower bound on the expected number of positive recruitment stages is established.
Major incompleteness relative to the task: neither a polynomial-time algorithm nor an NP-hardness result is established for auctions represented by general finite descriptions.
The stage lower bound does not fill this gap. The prover correctly explains that exponentially many stages may have a compact description and explicitly supplies one. Accordingly, the lower bound obstructs polynomial-size explicit stage lists, but does not classify the representation allowed by the task.
Minimum additional work: resolve the computational question for that permitted representation. This requires substantive new results, not an expositional repair. The present output should retain its partial status until then.
⟨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.