Answer: The welfare guarantee \((1-\gamma)W_0\) is attainable with one oracle call and polynomial expected bit overhead. Tagged truthfulness, IR, and no positive transfers characterize the expected externality payment proved above. For fixed data, convergence requires the stated stability and payment-tail conditions; a reduction guaranteeing finite-price convergence and convergent expectations for every admissible oracle family exists exactly when \(\gamma\geq 1/2\).
Theorem 5.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateConsider a multi-parameter PPC auction where a bidder’s value-per-click vi,j depends on the bidder and the slot. Let APPC be an allocation rule that chooses the advertiser-slot assignment returned by the welfare-maximizing oracle described above. Then the mechanism MIDRtoMech(APPC, γ) is truthful in expectation and approximates the welfare of APPC to within a factor of (1 −γ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite advertiser-type set \(T\), rational background masses \(\mu_t\), slot classes \(S\), per-capita capacities \(q_s\), and bounded valuation vectors, add a tagged advertiser of mass \(\epsilon\) and scale capacities with total population. For a fixed MIDR oracle over lotteries on feasible mass assignments, determine whether a measurable reduction can thin the background at rate \(\gamma\), make one oracle call, and set a per-advertiser transfer so the tagged advertiser is truthful in expectation with the paper’s individual-rationality and no-positive-transfer guarantees and expected welfare at least \(1-\gamma\) times baseline; characterize the transfer and incentive behavior as \(\epsilon\to0\), including whether per-advertiser transfers can have a finite limit.
A society is given by its support: \(\tau\) advertiser types with positive binary-rational masses \(\mu_t\), not the number of possible types; normalize \(\sum_t\mu_t=1\). There are \(m\geq1\) slot classes, rational capacities \(q_s\geq0\) with \(\sum_s q_s>0\), and rational per-advertiser expected-value vectors \(v_t\in[0,V]^m\), where \(V>0\); being unassigned has value zero.
Represent each background type by an atomless interval of length \(\mu_t\). Add a separately identified advertiser controlling an interval of rational mass \(\epsilon>0\), reporting one vector in \([0,V]^m\) for its whole interval. Each unit of mass receives at most one slot; slot-class capacity is \(q_s(1+\epsilon)\). Welfare is the integral of assigned values.
For each \(\epsilon\), a black-box MIDR oracle has a nonempty, report-independent range of lotteries over feasible measurable assignments, with a fixed measurable tie-breaking rule. The range and capacities remain unchanged under zeroing queries; the oracle realizes one sampled assignment and returns its aggregate assignments on the queried retained and zeroed cells.
A reduction samples a jointly measurable, report-independent retained set \(K\): every background point has retention probability \(1-\gamma\), and the tagged interval is retained wholly with probability \(1-\gamma\), where rational \(0<\gamma<1\). Correlations are permitted. Thinning means zeroing reported values outside \(K\), without removing mass or preventing its assignment.
The reduction makes exactly one zeroing query, implements its returned outcome, and computes a finite, integrable tagged payment \(P_\epsilon\) using only the reports, its randomness, and the returned aggregates. It is normalized: if everyone receives zero reported value, the payment is zero.
Write \(x_{*,s}\) for tagged mass assigned to class \(s\) and \(p_\epsilon=P_\epsilon/\epsilon\) for its per-advertiser charge. Tagged utility is \(\sum_s v_{*,s}x_{*,s}/\epsilon-p_\epsilon\). Truthfulness is dominant-strategy truthfulness in expectation; IR requires nonnegative expected truthful utility, and no positive transfers requires \(\mathbb E[p_\epsilon]\geq0\), for every background report profile.
Let \(W_0\) be expected welfare from the oracle on the unmodified truthful profile. Use finitely encoded rational zeroing cells and returned aggregates; state reduction overhead in \(m,\tau,L\) and returned-answer length, where \(L\) includes all rational input parameters, with oracle cost separate.
Does this oracle model admit a polynomial-overhead single-call reduction guaranteeing tagged truthfulness, IR, no positive transfers, and expected welfare at least \((1-\gamma)W_0\) for every admissible oracle, or is this approximation guarantee unattainable?
Which payment and incentive conditions characterize such reductions, and, with background data and \(\gamma\) fixed, when can \(p_\epsilon\) converge to a finite limit in distribution and its expectation converge as \(\epsilon\to0\)?
For finite advertisers, a single-call MIDR transformation guarantees truthfulness in expectation and welfare factor \(1-\gamma\) in multi-parameter slot auctions; its IR and no-positive-transfer guarantees are in expectation. [Verified discrete result](https://arxiv.org/pdf/1011.6134).
No verified result was located for the specified atomless-background model with a tagged mass and population-scaled capacities.
The approximation guarantee is attainable. Correlations permit us to retain or zero each entire background-type interval, giving a finite description with size polynomial in the support size \(\tau\).
For every admissible oracle, a single-call reduction can guarantee tagged truthfulness, IR, no positive transfers, and expected welfare at least \((1-\gamma)W_0\). Its sampled payments can be negative; the payment guarantees are in expectation.
The vanishing-mass question has a different answer. Expected per-advertiser charges are uniformly bounded, but convergence does not follow from the stated oracle assumptions. Moreover:
We prove these statements directly. The [cited finite-advertiser paper](https://arxiv.org/pdf/1011.6134) provides the relevant single-call context.
Throughout, polynomial sampling overhead means exact rational sampling in expected polynomial bit time. The distinction from bounded worst-case fair-bit sampling is explained in Section 5.
Fix \(\epsilon\), the background reports, and a report-independent thinning law. Write \(r=1-\gamma\). Let \(B\in\{0,1\}\) indicate retention of the whole tagged interval, so \(\Pr(B=1)=r\). Let \(S\) describe the retained background cells, and let \(\nu_1,\nu_0\) be its conditional laws given \(B=1,B=0\), respectively.
For a lottery \(D\) in the oracle’s fixed range, define:
Feasibility and bounded values give \(\sum_s a_{\epsilon,s}(D)\leq\epsilon\) and \(0\leq H_\epsilon(S,D)\leq V\).
For a tagged report \(b\in[0,V]^m\), put
\(\displaystyle F_{\epsilon,S}(b)=\max_{D\in\mathcal R_\epsilon}\bigl[H_\epsilon(S,D)+b\cdot a_\epsilon(D)\bigr].\)
The maximum is attained because the stipulated MIDR oracle selects a maximizer. Let \(D_{\epsilon,S}(b)\) denote its selected lottery when the tag is retained.
Define
\(\displaystyle f_\epsilon(b)=\mathbb E_{S\sim\nu_1}[F_{\epsilon,S}(b)],\qquad a_\epsilon^1(b)=\mathbb E_{\nu_1}[a_\epsilon(D_{\epsilon,S}(b))].\)
When the tag is zeroed, the queried profile is independent of its original report. Let \(a_\epsilon^0\) be its expected tagged assignment vector in that branch, averaging over \(\nu_0\) and oracle randomness. Consequently, the implemented expected assignment is
\(\displaystyle X_\epsilon(b)=r\,a_\epsilon^1(b)+\gamma a_\epsilon^0.\)
The second term is necessary: a zeroed tagged interval may still receive slots.
Set
\(\displaystyle G_\epsilon(b)=r f_\epsilon(b)+\gamma b\cdot a_\epsilon^0.\)
For any reports \(b,c\), maximality gives
\(\displaystyle F_{\epsilon,S}(c)\geq F_{\epsilon,S}(b)+(c-b)\cdot a_\epsilon(D_{\epsilon,S}(b)).\)
Taking expectations yields
\(\displaystyle G_\epsilon(c)\geq G_\epsilon(b)+(c-b)\cdot X_\epsilon(b).\)
Thus \(G_\epsilon\) is convex and \(X_\epsilon(b)\) is a subgradient at every report, including reports at ties.
Let \(Q_\epsilon(b)=\mathbb E[P_\epsilon(b)]\), and define total expected truthful utility
\(\displaystyle U_\epsilon(b)=b\cdot X_\epsilon(b)-Q_\epsilon(b).\)
Tagged truthfulness is exactly the condition
\(\displaystyle U_\epsilon(c)\geq U_\epsilon(b)+(c-b)\cdot X_\epsilon(b)\)
for all reports \(b,c\). We now verify that this forces \(U_\epsilon-G_\epsilon\) to be constant.
Fix \(b,c\), write \(d=c-b\), and partition their segment into \(b_j=b+jd/n\). Applying the supporting inequalities to consecutive points shows that both \(U_\epsilon(c)-U_\epsilon(b)\) and \(G_\epsilon(c)-G_\epsilon(b)\) lie between
\(\displaystyle \frac1n\sum_{j=0}^{n-1}d\cdot X_\epsilon(b_j)\quad\text{and}\quad\frac1n\sum_{j=1}^{n}d\cdot X_\epsilon(b_j).\)
The difference between these bounds is
\(\displaystyle \frac1n d\cdot\bigl(X_\epsilon(c)-X_\epsilon(b)\bigr),\)
which tends to zero because both assignment vectors have total mass at most \(\epsilon\). Hence the two increments agree.
At the zero tagged type, IR implies \(-Q_\epsilon(0)\geq0\), while no positive transfers implies \(Q_\epsilon(0)\geq0\). Therefore \(Q_\epsilon(0)=0\), and
\(\displaystyle U_\epsilon(b)=G_\epsilon(b)-G_\epsilon(0).\)
It follows that the necessary and sufficient expected-payment identity for truthfulness, IR, and no positive transfers is
\(\displaystyle Q_\epsilon(b)=r\bigl[F_\epsilon^1(0)-F_\epsilon^1(b)+b\cdot a_\epsilon^1(b)\bigr],\qquad F_\epsilon^1=f_\epsilon.\)
Equivalently, writing \(D_{\epsilon,S}(0)\) for any maximizer of retained-background welfare,
\[\displaystyle Q_\epsilon(b)=r\,\mathbb E_{\nu_1}\!\left[H_\epsilon(S,D_{\epsilon,S}(0))-H_\epsilon(S,D_{\epsilon,S}(b))\right].\tag{1}\]
The background-welfare value at the zero tagged report is independent of which maximizing lottery tie-breaking selects.
For sufficiency, the potential inequality proves truthfulness. Also, \(f_\epsilon(b)\geq f_\epsilon(0)\), so truthful utility is nonnegative.
Finally, maximality at reports \(0\) and \(b\) gives, for each \(S\),
\(\displaystyle 0\leq H_\epsilon(S,D_{\epsilon,S}(0))-H_\epsilon(S,D_{\epsilon,S}(b))\leq b\cdot a_\epsilon(D_{\epsilon,S}(b)).\)
Consequently,
\[\displaystyle 0\leq Q_\epsilon(b)\leq r\epsilon V,\qquad 0\leq\mathbb E[p_\epsilon(b)]\leq rV.\tag{2}\]
These are statements about expectations. They do not determine the distribution of sampled payments.
Represent the background intervals by \(I_1,\ldots,I_\tau\), of lengths \(\mu_1,\ldots,\mu_\tau\), and the tagged interval by \(T_\epsilon\).
Independently sample retention bits for the \(\tau\) background intervals and the tagged interval, each with retention probability \(r\). Retain an interval wholly when its bit is one.
This is jointly measurable and report-independent. Every background point has retention probability \(r\), even though points within a type interval are perfectly correlated.
Make exactly one query, zeroing the reports on nonretained intervals. Keep the population, capacities, and oracle range unchanged, and implement the sampled assignment returned by the oracle.
Let \(z_{t,s}\) be the returned assigned mass from retained background interval \(I_t\) to class \(s\). Compute the realized retained-background welfare
\(\displaystyle H=\sum_{t:\,I_t\text{ retained}}\sum_{s=1}^m v_{t,s}z_{t,s}.\)
Charge the tagged advertiser
\[\displaystyle P_\epsilon=\begin{cases}-H,&B=1,\\[2pt]\dfrac r\gamma H,&B=0.\end{cases}\tag{3}\]
Because the background retention law is the same in both tagged branches,
\(\displaystyle \mathbb E[P_\epsilon]=r\,\mathbb E_S\!\left[H_\epsilon(S,D_{\epsilon,S}(0))-H_\epsilon(S,D_{\epsilon,S}(b))\right].\)
This is precisely (1), proving tagged truthfulness, IR, and no positive transfers.
The payment is finite and integrable: \(H\leq V\), so
\(\displaystyle |P_\epsilon|\leq V\max\{1,r/\gamma\}.\)
It is also normalized. If everyone receives zero reported value, every retained-background contribution is zero, and hence \(H=P_\epsilon=0\).
For this construction, all other integrable payments with the same incentive guarantees have the form \(P_\epsilon+Z_\epsilon\), where
\(\displaystyle \mathbb E[Z_\epsilon]=0\)
for every tagged report, background profile, and admissible oracle. Normalization additionally requires \(Z_\epsilon=0\) on the outcomes where everyone receives zero reported value.
For a general correlated law, a useful sufficient condition is \(\nu_1\ll\nu_0\). If \(h=d\nu_1/d\nu_0\), then the estimator
\[\displaystyle P_\epsilon=\begin{cases}-H,&B=1,\\[2pt]\dfrac r\gamma h(S)H,&B=0\end{cases}\tag{4}\]
also has expectation (1). It is integrable because
\(\displaystyle \mathbb E|P_\epsilon|\leq rV+rV\int h\,d\nu_0=2rV.\)
For finitely supported masks, this condition is simply \(\nu_1(S)>0\Longrightarrow\nu_0(S)>0\), with \(h(S)=\nu_1(S)/\nu_0(S)\).
Absolute continuity is sufficient, but not necessary: when retained-background welfare is identically zero in the tagged-retained branch, the required expected payment can be zero without it.
Consider the thinning law that retains everyone with probability \(r\) and zeroes everyone with probability \(\gamma\).
Take one background type of mass one, one class with \(q_1=1\), and rational values \(0<c<b\leq V\). Fix \(0<\epsilon<1\). Consider deterministic assignments:
Compare oracle ranges \(\{C,D\}\) and \(\{C,A,D\}\), with fixed tie-breaking selecting \(C\) when all reports are zero.
At the queried truthful profile, both oracles select \(D\), because \(b\epsilon>c\epsilon\). At the all-zero query, both select \(C\). Thus the reduction observes identical transcripts under both oracles.
Nevertheless, (1) requires expected payment zero for the first oracle and \(rc\epsilon\) for the second. Hence no single-call payment rule based on these transcripts can satisfy the required guarantees for both.
The characterization is therefore the expected externality identity (1), together with integrability and normalization; prescribed retention marginals alone do not make every correlation usable.
This proof applies to every report-independent thinning law with the prescribed pointwise marginals.
Let \(D^0_\epsilon\) be the oracle’s selected lottery on the unmodified truthful profile, whose expected welfare is \(W_0\). Let \(w_K(D)\) denote expected welfare using the zeroed profile.
For every realization of \(K\), \(D^0_\epsilon\) remains in the same feasible range. MIDR maximality therefore gives
\(\displaystyle w_K(D_K)\geq w_K(D^0_\epsilon).\)
Actual truthful welfare of the implemented assignment is at least its zeroed-profile welfare, since all values are nonnegative. Thus
\(\displaystyle \mathbb E[W_{\mathrm{implemented}}]\geq\mathbb E_K[w_K(D^0_\epsilon)].\)
Joint measurability and bounded welfare permit interchange of expectations and the mass integral. Every point, including every tagged point, is retained with probability \(r\). Therefore
\(\displaystyle \mathbb E_K[w_K(D^0_\epsilon)]=rW_0.\)
Consequently,
\(\displaystyle \mathbb E[W_{\mathrm{implemented}}]\geq(1-\gamma)W_0.\)
No independence between background points is used here.
Let \(A\) be the bit length of the returned rational aggregates.
The construction uses exactly \(\tau+1\) rational intervals. Their endpoints are cumulative sums of the input masses, followed by the tagged endpoint \(1+\epsilon\). Forming these endpoints and the capacities \(q_s(1+\epsilon)\) takes polynomial bit time.
The reduction uses:
All intermediate rational bit lengths are polynomial in \(m,\tau,L,A\). Hence reduction overhead is \(\operatorname{poly}(m,\tau,L,A)\), with oracle computation and realization cost separate. No individual background advertiser is enumerated.
For exact rational coins, rejection sampling from binary integers has expected polynomial bit cost. If \(\gamma\) is non-dyadic, an algorithm using a uniformly bounded number of fair bits cannot realize its probability exactly: every such algorithm has dyadic output probabilities. Thus a strict bounded worst-case fair-bit interpretation would already make the prescribed marginals impossible. The substantive result uses exact rational sampling with expected polynomial bit overhead, or a rational-coin primitive.
Fix background reports, \(\gamma\), and the tagged vector \(b\). The oracle range may vary with \(\epsilon\), as the question permits.
For a general thinning law, define
\(\displaystyle d_\epsilon(S)=\frac{H_\epsilon(S,D_{\epsilon,S}(0))-H_\epsilon(S,D_{\epsilon,S}(b))}{\epsilon}.\)
The argument in Section 2 gives \(0\leq d_\epsilon(S)\leq V\). Every reduction satisfying the incentive requirements must obey
\[\displaystyle \mathbb E[p_\epsilon]=r\,\mathbb E_{\nu_{1,\epsilon}}[d_\epsilon(S)].\tag{5}\]
Therefore expected-price convergence holds exactly when the right-hand side converges. Boundedness alone does not imply convergence.
For the independent whole-type construction, the background mask law \(\pi\) is fixed and finite. A useful sufficient condition is convergence of \(d_\epsilon(S)\) for every mask. Then
\(\displaystyle \lim_{\epsilon\to0}\mathbb E[p_\epsilon]=r\sum_S\pi(S)d_0(S).\)
For example, this follows if expected retained-background welfare has first-order expansions with a common leading term:
\(\displaystyle H_\epsilon(S,D_{\epsilon,S}(i))=h(S)+\epsilon h_i(S)+o(\epsilon),\qquad i\in\{0,b\}.\)
In that case, \(d_0(S)=h_0(S)-h_b(S)\). These expansions are additional stability assumptions, not consequences of MIDR.
Let \(H_\epsilon^1\) and \(H_\epsilon^0\) denote the realized retained-background welfare conditional on \(B=1\) and \(B=0\). Set \(Z_\epsilon^i=H_\epsilon^i/\epsilon\). Both variables are nonnegative.
The law of \(p_\epsilon\) is the mixture
\[\displaystyle p_\epsilon\sim\begin{cases}-Z_\epsilon^1,&\text{with probability }r,\\[2pt]\dfrac r\gamma Z_\epsilon^0,&\text{with probability }\gamma.\end{cases}\tag{6}\]
Because both mixture weights and both nonzero scaling coefficients are fixed:
Payment (3) converges in distribution to a finite random variable if and only if both conditional laws \(Z_\epsilon^0,Z_\epsilon^1\) converge weakly to finite nonnegative random variables.
Sufficiency follows immediately from (6). For necessity, tightness of the mixture implies tightness of each conditional law. Moreover, for every \(t>0\),
\(\displaystyle \Pr(Z_\epsilon^0>t)=\gamma^{-1}\Pr\!\left(p_\epsilon>\frac r\gamma t\right),\qquad \Pr(Z_\epsilon^1>t)=r^{-1}\Pr(p_\epsilon<-t).\)
Thus any subsequential conditional limits are uniquely determined by the positive and negative tails of the limiting price law. Their remaining probability is the atom at zero, proving convergence of both conditional laws.
In particular, finite distributional convergence requires \(H_\epsilon^i=O_{\mathsf P}(\epsilon)\). If either branch has background welfare bounded below by a positive constant with probability bounded away from zero along a sequence, the prices are not tight.
If \(p_\epsilon\) converges weakly to an integrable \(p_0\), uniform integrability is sufficient for
\(\displaystyle \mathbb E[p_\epsilon]\longrightarrow\mathbb E[p_0].\)
For (3), uniform integrability is equivalent to uniform integrability of both nonnegative families \(Z_\epsilon^0,Z_\epsilon^1\), since
\(\displaystyle \mathbb E\!\left[|p_\epsilon|\mathbf1_{\{|p_\epsilon|>M\}}\right]=r\,\mathbb E\!\left[Z_\epsilon^1\mathbf1_{\{Z_\epsilon^1>M\}}\right]+r\,\mathbb E\!\left[Z_\epsilon^0\mathbf1_{\{Z_\epsilon^0>(\gamma/r)M\}}\right].\)
Uniform integrability is not necessary for signed payments. An exact condition uses the clipping function \(T_M(x)=\max\{-M,\min\{M,x\}\}\): assuming weak convergence to an integrable \(p_0\), convergence of expectations to \(\mathbb E[p_0]\) is equivalent to
\(\displaystyle \lim_{M\to\infty}\limsup_{\epsilon\to0}\left|\mathbb E[p_\epsilon-T_M(p_\epsilon)]\right|=0.\)
Indeed, bounded continuity gives \(\mathbb E[T_M(p_\epsilon)]\to\mathbb E[T_M(p_0)]\), and integrability gives \(\mathbb E[T_M(p_0)]\to\mathbb E[p_0]\).
Bounded expectations with no finite distributional limit.
Take a singleton range assigning all background mass to the one class and assigning no tagged mass. Let the background value be \(c>0\).
Under (3), \(p_\epsilon=-c/\epsilon\) with probability \(r^2\), and \(p_\epsilon=rc/(\gamma\epsilon)\) with probability \(\gamma r\); otherwise it is zero. Its expectation is zero for every \(\epsilon\), but its laws are not tight.
A finite, nonzero limit.
Instead let the range contain two assignments: one assigns only a background interval of length \(\epsilon\), and the other assigns only the tagged interval. Choose \(0<c<b\leq V\).
Payment (3) then satisfies \(p_\epsilon=rc/\gamma\) with probability \(\gamma r\), and is zero otherwise. Its distribution is independent of \(\epsilon\), and its expectation is \(r^2c\).
Distributional behavior also depends on the payment estimator. For example, independently multiplying any admissible payment by \(J_\epsilon/\delta_\epsilon\), where \(J_\epsilon\) is Bernoulli with mean \(\delta_\epsilon\to0\), preserves expected payments and normalization while making the resulting per-advertiser charge converge to zero in probability. Its expected charge still obeys (5). This illustrates why weak convergence and convergence of expectations must be checked separately.
Here \(r\leq1/2\). Choose
Every background point and the whole tagged interval have retention probability \(r\). Make the one query and set \(P_\epsilon=0\).
When \(K=T_\epsilon\), the oracle maximizes \(b\cdot a_\epsilon(D)\) over its fixed range. Reporting the true vector therefore maximizes tagged utility in this branch. In the other branches, the queried profile and resulting assignment are independent of the tagged report.
This proves tagged truthfulness. Nonnegative values give IR, and zero payments give no positive transfers and normalization. Section 4 proves the welfare guarantee.
Moreover, \(p_\epsilon=0\) identically. Thus both its distribution and expectation converge for every admissible oracle family.
Fix one background type on \(I=[0,1)\), one class with \(q_1=1\), and rational values \(0<c<b\leq V\).
For \(0<\epsilon<1\), let \(J_\epsilon=[0,\epsilon)\). Define assignments:
Both assign total mass one, within capacity \(1+\epsilon\).
Consider the deterministic range \(\{A_\epsilon,D_\epsilon\}\), with ties selecting \(A_\epsilon\). For any retained background set \(K\cap I\), write
\(\displaystyle \ell_\epsilon(K)=|K\cap J_\epsilon|.\)
When the tag is retained, the zeroed-profile welfare advantage of \(D_\epsilon\) is
\(\displaystyle b\epsilon-c\ell_\epsilon(K)\geq(b-c)\epsilon>0.\)
Thus the oracle selects \(D_\epsilon\). When the tag is zeroed, it selects \(A_\epsilon\). The retained-background externality is exactly \(c\ell_\epsilon(K)\).
By (1), every reduction satisfying the incentive requirements must therefore have
\(\displaystyle \mathbb E[p_\epsilon]=\frac c\epsilon\,\mathbb E\!\left[\mathbf1_{\{B=1\}}\ell_\epsilon(K)\right].\)
For each background point \(u\), the prescribed marginals imply
\(\displaystyle \Pr(B=1,\ u\in K)\geq\Pr(B=1)+\Pr(u\in K)-1=2r-1.\)
Joint measurability permits integration over \(J_\epsilon\), yielding
\(\displaystyle \mathbb E\!\left[\mathbf1_{\{B=1\}}\ell_\epsilon(K)\right]\geq(2r-1)\epsilon.\)
Hence, independently of all thinning correlations,
\[\displaystyle \mathbb E[p_\epsilon]\geq c(2r-1)=c(1-2\gamma)>0.\tag{7}\]
By contrast, for the singleton range \(\{A_\epsilon\}\), the tagged allocation is identically zero. The characterization in Section 2 forces expected payment zero.
Now define an admissible oracle family using the singleton range at \(\epsilon=2^{-2n}\), and the two-assignment range at \(\epsilon=2^{-(2n+1)}\); define its range arbitrarily at other positive rational masses. Each range is report-independent and unchanged under zeroing.
Along the first sequence, every qualifying reduction has expected per-advertiser charge zero. Along the second, (7) bounds that expectation below by the fixed positive constant \(c(1-2\gamma)\). Therefore expectations cannot converge as \(\epsilon\to0\).
This obstruction applies to every reduction satisfying the stipulated incentive requirements, regardless of its payment estimator or thinning correlations. Thus universal finite distributional convergence together with convergent expectations is possible exactly when \(\gamma\geq1/2\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved, under the explicitly stated expected-polynomial-bit-time convention. The construction establishes the requested single-call welfare and incentive guarantees. The payment characterization and the vanishing-mass results are also correct. I found no major or minor mathematical issues.
The polynomial conclusion concerns reduction overhead, with oracle computation and realization costs excluded, as required by the task.
The proposed construction uses the support size \(\tau\), rather than enumerating individual background advertisers. Retaining entire type intervals is permitted because the task allows correlations and prescribes only pointwise retention probabilities.
The construction makes exactly one zeroing query, preserves population mass, capacities, and the oracle range, and implements the returned assignment. Its payment uses only reports, retention randomness, and returned aggregates.
The proof does not assume that zeroed points become ineligible for assignment. In particular, the term \(\gamma a_\epsilon^0\) correctly accounts for assignments to the zeroed tagged interval.
The [cited finite-advertiser paper](https://arxiv.org/pdf/1011.6134) supplies context; the argument does not rely on transferring its theorem to the atomless model.
The definition of \(F_{\epsilon,S}\) is valid: the stipulated MIDR oracle supplies an attained maximizer. Feasibility gives \(\sum_s a_{\epsilon,s}(D)\leq\epsilon\), and normalized background mass gives \(0\leq H_\epsilon(S,D)\leq V\). Thus all expectations used here are finite.
The supporting inequality follows directly by evaluating the maximizer at report \(b\) under report \(c\). Averaging it and adding the linear contribution from the tagged-zeroed branch correctly establishes that \(X_\epsilon(b)\) is a subgradient of \(G_\epsilon\). This remains valid at ties.
The truthfulness inequality is correctly expressed using total tagged utility. Multiplication by the positive mass \(\epsilon\) preserves the original per-advertiser incentive inequalities.
The segment-partition argument is sound. Both potential increments lie between the stated lower and upper sums, whose difference telescopes to \(\frac1n d\cdot(X_\epsilon(c)-X_\epsilon(b))\). Bounded assignment mass makes this difference tend to zero. Consequently, the two potentials differ by a constant throughout the report domain, including its boundary.
At tagged value zero, IR and no positive transfers correctly force \(Q_\epsilon(0)=0\). Substitution then yields the stated expected-payment identity.
The equivalence between the potential formula and equation (1) is correct: the tagged-value term cancels using the maximizing lottery’s objective value.
The two maximization comparisons justify both bounds on the background externality. In particular, the externality is nonnegative and at most \(b\cdot a_\epsilon(D_{\epsilon,S}(b))\leq\epsilon V\). Equation (2), including its constants, follows.
For sufficiency, the supporting inequality establishes truthfulness. Nonnegative values imply both \(f_\epsilon(b)\geq f_\epsilon(0)\) and \(b\cdot a_\epsilon^0\geq0\), giving IR. The externality bound gives no positive transfers in expectation.
This is an exact characterization of expected payments. Samplewise normalization and integrability remain separate requirements, as the output acknowledges.
Independence of background retention from tagged retention makes the two conditional background-mask laws identical. Therefore payment (3) has expected value equal to equation (1). Its coefficients and signs are correct.
The integrability bound is valid because retained-background welfare is at most \(V\). Normalization also holds: whenever everyone receives zero reported value, every term contributing to \(H\) vanishes.
The characterization of alternative payments as \(P_\epsilon+Z_\epsilon\), with zero expected \(Z_\epsilon\), follows from expected-payment uniqueness. The additional samplewise normalization requirement is correctly stated.
For correlated thinning, the density estimator in equation (4) correctly changes the tagged-zeroed branch’s background-mask law from \(\nu_0\) to \(\nu_1\). The bound \(\mathbb E|P_\epsilon|\leq2rV\) is correct. This is a mathematical sufficient condition; the output does not claim that an arbitrary density is efficiently computable.
The indistinguishability example in Section 3.2 is valid. Both ranges produce the same observable assignments at the two possible queries, but their required expected payments differ by \(rc\epsilon>0\). Thus the example correctly rules out a universal payment rule for that particular thinning law.
Every step of the welfare comparison is justified:
No independence between background points is needed. The conclusion applies to both the independent construction and the later correlated zero-payment construction.
The whole-interval masks have rational endpoints derived from the input masses. Computing those endpoints, population-scaled capacities, the query entries, and payment (3) requires polynomially many rational operations. Intermediate bit lengths are polynomial in \(m,\tau,L,A\).
Exact rational Bernoulli sampling has expected polynomial bit cost by the stated rejection-sampling method. The distinction from bounded worst-case fair-bit sampling is correctly identified: bounded fair-bit computation cannot produce a non-dyadic probability exactly.
Accordingly, the claimed expected polynomial overhead is established. The proof does not establish bounded worst-case fair-bit overhead, and explicitly says so.
Equation (5) follows from the previously established payment characterization. The bound \(0\leq d_\epsilon(S)\leq V\) is correct.
Expected-price convergence is therefore equivalent to convergence of the specified averaged externality. For a fixed finite mask law, convergence for each mask is a sufficient condition. The stated first-order expansions also imply the claimed limit, with the correct sign.
The mixture formula (6) is correct.
Its claimed equivalence is sound. Fixed positive mixture weights ensure that tightness of the price laws implies tightness of each conditional nonnegative family. Positive price tails identify the tagged-zeroed conditional limit, and negative price tails identify the tagged-retained conditional limit. Their masses at zero are then determined by total probability.
The requirement \(H_\epsilon^i=O_{\mathsf P}(\epsilon)\) and the stated failure of tightness when background welfare stays positively bounded away from zero are valid consequences.
Uniform integrability is correctly presented as sufficient, rather than necessary, for convergence of signed-payment expectations.
The displayed tail identity correctly establishes equivalence between uniform integrability of the price family and of both conditional nonnegative families.
The clipping criterion is also necessary and sufficient under the stated assumptions of weak convergence and an integrable limit. Bounded continuity handles fixed clipping levels, and integrability handles the subsequent limit in the clipping threshold.
The example probabilities and expectations check out:
Independent multiplication by the sparse mean-one factor preserves expected payments and normalization. The probability of a nonzero resulting payment is at most \(\delta_\epsilon\), validating convergence to zero in probability.
For \(\gamma\geq1/2\), the three stated mask probabilities are nonnegative and sum to one. Their retention marginals are correct.
In the tagged-only branch, maximizing tagged reported value with zero payment gives truthfulness. In the other branches, allocation is independent of the tagged report. IR, no positive transfers, normalization, and the welfare guarantee follow as stated. Identically zero prices give both forms of convergence.
For \(\gamma<1/2\), the lower-bound construction is valid:
Alternating these ranges with the singleton range along the two rational sequences produces incompatible expected-price subsequences. The obstruction is independent of payment estimator and thinning correlations.
Thus the claimed threshold concerns exactly what is proved: universal finite distributional convergence together with convergent expectations.
No mathematical repair is required. Preserve the qualifications that sampling time is expected polynomial, oracle costs are separate, and the distributional criterion in Section 6.2 applies specifically to payment (3).
⟨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.