Answer: —
Theorem 4.6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose the adversary has some (unknown) violation rate 𝑓∈[0, 1]. Furthermore, for any 0 < 𝜖,𝛿< 1, we execute Algorithm 3 using the NaivePerm approach.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), mass distribution \(\mu\), monotone piecewise-\(C^1\) scalable characteristic function \(V\), focal type \(h\), accuracy parameters \(\epsilon,\delta\), and \(G\ge\Gamma_h^\infty\), where \(D_h(z)=\partial_hV(z)\), \(a_h(\mu)=\int_0^1D_h(\lambda\mu)\,d\lambda\), and \(\Gamma_h^\infty=\sup_{z\le\mu}D_h(z)/a_h(\mu)\), construct a type-level random-order sampling protocol and stopping rule under the paper's rushing adversary and unknown detectable violation-rate model that returns \((\widehat a_h,\widehat\epsilon)\) satisfying \(\Pr[\widehat\epsilon\le\max\{\epsilon,4f\Gamma_h^\infty\}]=1\) and \(\Pr[\widehat a_h\ge(1-\widehat\epsilon)a_h(\mu)]\ge1-\delta\), while minimizing permutation-sample count independently of clone count.
A society is given by its support \(T\): the \(\tau\) types of positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is support size, not the number of possible types; let \(m\) be the maximum type-description length and \(L\) the total binary input length.
The characteristic function \(V:[0,\mu]\to\mathbb R_{\ge0}\) is continuous, coordinatewise monotone and piecewise-\(C^1\), with \(V(0)=0\). Scalability means that coalition value depends only on its type masses, independently of how those masses are divided into clones; no homogeneity is assumed.
Use an ideal real-oracle model with exact evaluations of \(V\) and its bounded, nonnegative partial derivatives \(D_t\), and exact continuous random draws. At nondifferentiable points, a fixed one-sided derivative convention is part of the oracle; all radial derivative functions are integrable.
For focal type \(h\in T\), define \(a_h(\mu)=\int_0^1D_h(\lambda\mu)\,d\lambda\) and \(\Gamma_h^\infty=\sup_{0\le z\le\mu}D_h(z)/a_h(\mu)\). Set this ratio to \(1\) when numerator and denominator vanish, and to \(+\infty\) when only the denominator vanishes. Inputs include binary rational \(0<\epsilon,\delta<1\) and finite \(G\ge\Gamma_h^\infty\); the actual ratio is not supplied.
A type-level random-order sample represents the predecessor masses of a tagged infinitesimal unit of type \(h\) in the limit of uniformly ordering equal-mass clones. Without violations its predecessor vector is \(U\mu\), with fresh independent \(U\sim\mathrm{Unif}[0,1]\); its observed reward is \(D_h(z)\) at its actual predecessor vector \(z\).
Types have communicating representatives with independent local randomness; the focal representative is honest. Communication uses synchronous public broadcast and ideal perfectly hiding, binding, non-malleable commitments. An unbounded rushing adversary controls the other representatives and sees honest messages before acting in each round.
Refusing a required commitment opening is publicly detected and counts as one violation; multiple refusals in one sample count separately. Violations may change the generated order but cannot change the characteristic function or the marginal-reward rule. For every integer \(r\ge1\), the first \(r\) samples contain at most \(fr\) violations, for an unknown \(f\in[0,1]\).
The returned \(\widehat a_h\) must average actual marginal rewards over a completed sample prefix, which may precede termination; the empty-prefix value is \(0\). The protocol must terminate almost surely and return \(\widehat\epsilon\in[0,1]\).
What is the optimal worst-case permutation-sample complexity of a distributed sampling protocol and stopping rule satisfying \(\Pr[\widehat\epsilon\le\max\{\epsilon,4f\Gamma_h^\infty\}]=1\) and \(\Pr[\widehat a_h\ge(1-\widehat\epsilon)a_h(\mu)]\ge1-\delta\) against every admissible adversary?
Can these guarantees be achieved with sample count independent of clone count? State sample, oracle and arithmetic complexity in \(m,\tau,L,G,\epsilon,\delta\), and any dependence on \(f\).
For finite monotone coalitional games, adaptive permutation sampling achieves the corresponding guarantees with the supplied discrete max-to-mean ratio \(\Gamma\), using \(O(\Gamma\epsilon^{-2}\log(1/(\epsilon\delta)))\) samples in the worst case. [Verified discrete result](https://arxiv.org/html/2412.19192#S4.SS3)
No result settling this precise continuous distributed sampling model was located in the literature search.
The optimal worst-case sample complexity is determined below for the entire parameter range $G\ge 2$, $0<\epsilon,\delta<1$:
$$ \boxed{ \Theta\!\left( 1+\frac{G-1}{\epsilon^2} \log\!\left(1+\frac{\epsilon(1-\delta)}{\delta}\right) \right). } $$
The protocol is independent of clone count and of the unknown violation rate $f$. For $G=1$, exactly one sample is sufficient and necessary in the worst case.
For $1<G<2$, I prove improved upper bounds and additional lower bounds, but do not determine the optimal complexity throughout that range. In particular, the displayed formula cannot be extended uniformly to that range.
Throughout, “worst-case sample complexity” means a uniform cap on the number of completed samples, rather than expected sample count. The supplied [discrete result](https://arxiv.org/html/2412.19192#S4.SS3) is not used in the proofs.
The construction uses the stipulated honest focal representative. It protects that focal type; it does not construct a common order that simultaneously protects every possible focal representative.
For each sample, use three synchronous rounds:
$$
U=(R+C)\bmod 1,
$$
where $C$ is the sum modulo $1$ of the accepted contributions.
The sample has actual predecessor vector $U\mu$ and actual reward
$$ X=D_h(U\mu). $$
All contributions and defaults are fixed before $R$ is drawn. Conditional on the entire history preceding that draw, addition modulo $1$ preserves the uniform distribution. Consequently, $U$ is conditionally uniform, whatever the adversary’s earlier actions.
Applying this conditional-distribution statement successively proves that the sample rewards are independent and identically distributed, with
$$ X_i=D_h(U_i\mu), \qquad \mathbb E[X_i]=a_h(\mu). $$
The expectation identity follows from the assumed integrability of the radial derivative. Later adversarial messages do not change the completed sample.
Thus refusals cannot bias this construction. Every refused required opening is still counted separately, but the violation budget is unnecessary for the proof.
Write $a=a_h(\mu)$. If $a=0$, finite $G$ forces $D_h(z)=0$ everywhere: any positive numerator would make the ratio infinite. All rewards then vanish, and the reward guarantee is automatic.
If $a>0$, define, only for analysis,
$$ Y_i=\frac{X_i}{a}. $$
Then
$$ 0\le Y_i\le G, \qquad \mathbb E[Y_i]=1. $$
Every feasible input has $G\ge 1$: for positive mean this follows by integrating the upper bound, and for zero mean the prescribed ratio is $1$.
Set
$$ A=G-1, \qquad B=A+\epsilon, \qquad W_i=Y_i-1+\epsilon. $$
Thus $\mathbb E[W_i]=\epsilon$, and $W_i\le B$. Define
$$ S_n=\sum_{i=1}^n W_i, \qquad H=\inf\{n\ge 1:S_n\ge 0\}. $$
The event $H\le n$ means that some completed prefix of length at most $n$ has average reward at least $(1-\epsilon)a$.
Let $q_n=\Pr[H>n]$. For every positive integer $n$,
$$ \boxed{ q_n\le \frac{A}{A+\epsilon n}. } $$
To prove this, observe that on $\{H\le n\}$ the crossing overshoot satisfies $S_H\le B$, while on $\{H>n\}$ we have $S_n<0$. Hence
$$ S_{H\wedge n}\le B\,\mathbf 1_{\{H\le n\}}. $$
Also,
$$ S_{H\wedge n} = \sum_{i=1}^n \mathbf 1_{\{H\ge i\}}W_i. $$
The indicator depends only on previous increments and is independent of $W_i$. Taking expectations therefore gives
$$ \epsilon\,\mathbb E[H\wedge n] = \mathbb E[S_{H\wedge n}] \le B(1-q_n). $$
Because $H\wedge n$ equals $n$ on $\{H>n\}$ and is at least $1$ otherwise,
$$ \mathbb E[H\wedge n]\ge 1+(n-1)q_n. $$
Combining the inequalities yields
$$ \epsilon\bigl(1+(n-1)q_n\bigr) \le B(1-q_n), $$
and rearrangement gives the claimed bound.
This strengthens the previous bound $q_n\le A/(\epsilon n)$ and handles $\delta$ close to $1$ correctly.
For $A>0$, a second bound is
$$ \boxed{ q_n \le \frac{3A}{\epsilon n} \exp\!\left(-\frac{n\epsilon^2}{8(A+\epsilon)}\right). } $$
Here is a complete change-of-measure proof.
First,
$$ \operatorname{Var}(W_i) = \operatorname{Var}(Y_i) \le A, $$
because $Y_i^2\le GY_i$, so $\mathbb E[Y_i^2]-1\le G-1$.
Put
$$ t=\frac{\epsilon}{4(A+\epsilon)}, \qquad M=\mathbb E[e^{-tW_i}]. $$
We have $t\le 1/4$. For $Z=Y_i-1$, the inequalities $Z\ge -1$, $\mathbb E[Z]=0$, and $\mathbb E[Z^2]\le A$ give
$$ \mathbb E[e^{-tZ}] \le 1+\frac{t^2e^t}{2}\mathbb E[Z^2]. $$
Indeed, Taylor’s formula with integral remainder bounds the second derivative along the segment between $0$ and $Z$ by $e^tZ^2$. Consequently,
$$ M \le \exp\!\left(-t\epsilon+\frac{t^2e^tA}{2}\right) \le \exp\!\left(-\frac{\epsilon^2}{8(A+\epsilon)}\right). $$
For the last inequality, substitution of $t$ gives
$$ -t\epsilon+\frac{t^2e^tA}{2} \le -\frac{\epsilon^2}{A+\epsilon} \left(\frac14-\frac{e^{1/4}}{32}\right) \le -\frac{\epsilon^2}{8(A+\epsilon)}. $$
Define the tilted increment distribution by
$$ \frac{d\mathbb P_t}{d\mathbb P}(w) = \frac{e^{-tw}}{M}, $$
and let $\nu=\mathbb E_t[W_i]$. We next prove
$$ \nu\ge \frac{\epsilon}{2}, \qquad B-\nu\le \frac{3A}{2}. $$
The function $w\mapsto e^{-tw}$ is decreasing and has Lipschitz constant at most $te^t$ on the support, since $w\ge -1$. For an independent copy $W_i'$, the covariance identity gives
$$ -\operatorname{Cov}(W_i,e^{-tW_i}) = -\frac12 \mathbb E\!\left[ (W_i-W_i') (e^{-tW_i}-e^{-tW_i'}) \right] \le te^tA. $$
Jensen’s inequality gives $M\ge e^{-t\epsilon}$. Therefore
$$ 0\le \epsilon-\nu = -\frac{\operatorname{Cov}(W_i,e^{-tW_i})}{M} \le te^{t(1+\epsilon)}A \le 2tA. $$
It follows that
$$ \nu\ge \epsilon-2tA\ge \frac{\epsilon}{2}, $$
and, using $t\le 1/4$,
$$ B-\nu=A+\epsilon-\nu\le A+2tA\le \frac{3A}{2}. $$
The stopped-sum proof from Section 2 applies to any independent increments with positive mean $\nu$ and upper bound $B$. Under the tilted law it yields
$$ \mathbb P_t(H>n) \le \frac{B-\nu}{B+\nu(n-1)} \le \frac{B-\nu}{\nu n} \le \frac{3A}{\epsilon n}. $$
Finally, the likelihood ratio for the first $n$ increments is
$$ \frac{d\mathbb P}{d\mathbb P_t} = M^n e^{tS_n}. $$
On $\{H>n\}$, $S_n<0$, so $e^{tS_n}\le 1$. Thus
$$ q_n = M^n\mathbb E_t[e^{tS_n}\mathbf 1_{\{H>n\}}] \le M^n\mathbb P_t(H>n), $$
which proves the exponential refinement.
After a deterministic number $N$ of completed samples, return the largest completed-prefix average:
$$ \widehat a_h = \max_{1\le k\le N} \frac1k\sum_{i=1}^kX_i, \qquad \widehat\epsilon=\epsilon. $$
A fixed tie-breaking rule selects the returned prefix. This obeys the restriction that the output average actual rewards over a completed prefix.
For $A>0$, define
$$ Q_1=\frac{A(1-\delta)}{\epsilon\delta}, $$
and
$$ Q_2= \frac{16(A+\epsilon)}{\epsilon^2} \log\!\left( 1+\frac{A\epsilon}{(A+\epsilon)\delta} \right). $$
Either $N\ge Q_1$ or $N\ge Q_2$ is sufficient.
The first assertion follows immediately from Section 2. For the second, put
$$ x=\frac{A\epsilon}{(A+\epsilon)\delta}. $$
At $n\ge Q_2$, Section 3 gives
$$ q_n \le \delta\, \frac{3x}{16\log(1+x)(1+x)^2} \le \delta. $$
The last inequality uses $\log(1+x)\ge x/(1+x)$.
Hence a deterministic budget of order
$$ \boxed{ 1+\min\left\{ \frac{(G-1)(1-\delta)}{\epsilon\delta}, \; \frac{G-1+\epsilon}{\epsilon^2} \log\!\left( 1+\frac{(G-1)\epsilon}{(G-1+\epsilon)\delta} \right) \right\} } $$
suffices for every feasible $G>1$.
The reward guarantee follows because estimator failure is precisely $H>N$. Furthermore, pathwise,
$$ \widehat\epsilon=\epsilon \le \max\{\epsilon,4f\Gamma_h^\infty\}. $$
The protocol terminates deterministically and satisfies both required guarantees against every admissible adversary, without knowing $f$ or the actual ratio.
When $G=1$ and $a>0$, the normalized radial reward satisfies $Y\le 1$ and $\mathbb E[Y]=1$, so $Y=1$ almost surely. One sample therefore suffices. At least one is necessary in the worst case because an empty prefix fails on a positive constant-derivative instance.
Define
$$ \mathcal D = \frac{A}{\epsilon^2} \log\!\left(1+\frac{\epsilon(1-\delta)}{\delta}\right). $$
I prove that every protocol with a uniform sample cap requires $\Omega(1+\mathcal D)$ when $A\ge 1$.
All lower-bound instances have one type of mass $1$ and use a nonviolating adversary. Thus $f=0$, and the first required guarantee forces $\widehat\epsilon\le\epsilon$ almost surely.
For a distribution taking a high derivative value $v_+$ with probability $p$ and a low value $v_-$ otherwise, use
$$ V(x)=v_+\min\{x,p\}+v_-\max\{x-p,0\}. $$
This function is continuous, monotone, nonnegative, piecewise linear, and satisfies $V(0)=0$. Its sampled derivative has exactly the specified distribution; the breakpoint convention affects only a probability-zero event.
If its mean is $1$ and its maximum derivative is at most $G$, it satisfies the ratio promise.
Take
$$ v_-=\frac{1-\epsilon}{2}, \qquad v_+=G, \qquad p=\frac{1+\epsilon}{2A+1+\epsilon}. $$
Direct substitution gives mean $1$. If all first $N$ samples are low, every permitted output prefix fails. Therefore
$$ N \ge \frac{\log(1/\delta)} {\log\!\left(1+\frac{1+\epsilon}{2A}\right)} \ge A\log\frac1\delta. $$
For $0<\epsilon\le 1/4$, the choice
$$ v_-=1-2\epsilon, \qquad v_+=G, \qquad p=\frac{2\epsilon}{A+2\epsilon} $$
similarly yields
$$ N \ge \frac{\log(1/\delta)} {\log(1+2\epsilon/A)} \ge \frac{A}{2\epsilon}\log\frac1\delta. $$
These arguments remain valid for adaptive stopping: extend the independent sample sequence to the uniform cap $N$. Missing the high value throughout those $N$ draws makes every available prefix fail, regardless of oracle knowledge.
The remaining difficulty is simultaneous small $\epsilon$ and small $\delta$. It is resolved by the next lemma.
There is a universal constant $a_0>0$ such that the following holds.
Let $k\ge 1$ be an integer and $0<\eta\le 1/2$. Let independent increments $J_i$ take values $-1$ and $k$, with
$$ \Pr[J_i=k]=p=\frac{1+\eta}{k+1}. $$
For
$$ q_n^{(k,\eta)} = \Pr\!\left[ \sum_{i=1}^jJ_i<0 \text{ for every }1\le j\le n \right], $$
we have
$$ \boxed{ q_n^{(k,\eta)} \ge a_0 \min\left\{1,\sqrt{\frac{k}{n}}\right\} \exp\!\left(-\frac{3n\eta^2}{k}\right). } $$
Proof of the exact cyclic identity. If $B_n$ counts the positive increments, then
$$ q_n^{(k,\eta)} = \frac1n \mathbb E\!\left[(n-(k+1)B_n)_+\right]. $$
To justify this identity, condition on $B_n=b$. If $r=n-(k+1)b$ is positive, negate the increments. The resulting integer increments are $1$ and $-k$, with total $r$.
Exactly $r$ of the $n$ cyclic shifts have all partial sums strictly positive. Here is a proof that also handles periodic sequences. Extend cumulative sums $s_j$ to all integer indices periodically, so that
$$ s_{j+n}=s_j+r. $$
For each integer level $\ell$, let $j(\ell)$ be the last index with $s_{j(\ell)}\le\ell$. Such an index exists because the cumulative sums tend to opposite infinities in the two directions. Since upward increments are at most $1$, necessarily $s_{j(\ell)}=\ell$. All subsequent sums are larger than $\ell$, so the shift starting there is strictly positive.
Conversely, a strictly positive cyclic shift remains positive through every future period, since each period adds $r>0$. Its starting index is therefore $j(\ell)$ for its starting level $\ell$. Finally,
$$ j(\ell+r)=j(\ell)+n. $$
Thus precisely $r$ such indices occur per period of length $n$. Conditional on $B_n=b$, cyclic invariance now gives survival probability $r/n$. If $r\le 0$, strict survival is impossible. This proves the identity.
Proof of the quantitative bound. First suppose $n\ge k$. Under the critical binomial law with
$$ p_0=\frac1{k+1}, \qquad Z=B_n-np_0, \qquad \sigma^2=np_0(1-p_0), $$
we have $\sigma^2\ge 1/4$. Independence of centered Bernoulli variables gives
$$ \mathbb E[Z^4] = 3\sigma^4+\sigma^2\bigl(1-6p_0(1-p_0)\bigr) \le 7\sigma^4. $$
Hölder’s inequality consequently gives
$$ \mathbb E|Z| \ge \frac{(\mathbb E[Z^2])^{3/2}} {(\mathbb E[Z^4])^{1/2}} \ge \frac{\sigma}{\sqrt7}. $$
Because $\mathbb E[Z]=0$,
$$ \mathbb E[(-Z)_+]\ge\frac{\sigma}{2\sqrt7}. $$
Set $M_0=4\sqrt7$. The tail estimate
$$ \mathbb E[(-Z)_+;\,Z<-M_0\sigma] \le \frac{\mathbb E[Z^2]}{M_0\sigma} = \frac{\sigma}{M_0} $$
shows that
$$ \mathbb E[(-Z)_+;\,-M_0\sigma\le Z<0] \ge \frac{\sigma}{4\sqrt7}. $$
The likelihood ratio from the critical binomial law to the law with parameter $p$ has logarithm
$$ -nK(p_0,p)+Z\beta, $$
where
$$ K(p_0,p) = p_0\log\frac{p_0}{p} + (1-p_0)\log\frac{1-p_0}{1-p}, $$
and
$$ \beta=\log\frac{p(1-p_0)}{p_0(1-p)}. $$
The elementary inequality $\log u\le u-1$ gives
$$ K(p_0,p) \le \frac{(p-p_0)^2}{p(1-p)} \le \frac{2\eta^2}{k}. $$
Also,
$$ \beta = \log(1+\eta)+\log\frac{k}{k-\eta} \le 3\eta. $$
On the truncated negative region, therefore, the likelihood ratio is at least
$$ \exp\!\left( -\frac{2n\eta^2}{k} -3M_0\eta\sqrt{\frac nk} \right) \ge \exp\!\left(-\frac{3n\eta^2}{k}-252\right). $$
The last inequality uses $3M_0\sqrt u\le u+9M_0^2/4$, with $u=n\eta^2/k$.
Applying the exact cyclic identity and observing that
$$ \frac{k+1}{n}\sigma=\sqrt{\frac kn} $$
proves the asserted bound for $n\ge k$, with
$$ a_0=\frac{e^{-252}}{4\sqrt7}. $$
For $n<k$, the event that every increment is $-1$ gives
$$ q_n^{(k,\eta)} \ge (1-p)^n \ge (1-p)^k \ge e^{-3}. $$
Indeed, $\log(1-p)\ge-p/(1-p)$ and
$$ \frac{kp}{1-p} = \frac{k(1+\eta)}{k-\eta} \le 3. $$
This also implies the claimed bound with the same $a_0$. The lemma is proved.
Put $s=1-\epsilon$. Choose $0<d\le s$ and define
$$ k=\left\lfloor\frac{A+\epsilon}{d}\right\rfloor, \qquad v_-=s-d, \qquad v_+=s+kd, \qquad \eta=\frac{\epsilon}{d}. $$
Then $v_-\ge 0$ and $v_+\le G$. With
$$ p=\frac{1+\eta}{k+1}, $$
the mean reward is
$$ v_-+(v_+-v_-)p = s-d+(k+1)dp = s+\epsilon = 1. $$
Moreover, the increments determining prefix success satisfy
$$ \frac{Y_i-s}{d}\in\{-1,k\}, $$
with precisely the probabilities from the lemma. Thus its survival probability is a lower bound on the failure probability of every permitted output rule.
When $A\ge 1$, $\epsilon\le 1/4$, and $d\le s$,
$$ \frac{A}{2d}\le k\le\frac{2A}{d}. $$
This follows from $\lfloor x\rfloor\ge x/2$ for $x\ge1$, together with $A+\epsilon\le 2A$.
Choose universal constants
$$ \delta_*=\frac{a_0}{4}, \qquad c_*=\frac{a_0^2}{128}. $$
Suppose first that $\epsilon,\delta\le\delta_*$.
If $\delta\ge\epsilon$, choose
$$ d=\min\left\{1-\epsilon,\frac{\epsilon}{\delta}\right\}. $$
Then
$$ \delta\le\eta\le\frac{4\delta}{3}\le\frac12. $$
For any positive integer
$$ n\le c_*\frac{A}{\epsilon\delta}, $$
the bounds on $k$ imply
$$ \frac nk\le\frac{2c_*}{\delta^2}, \qquad \frac{n\eta^2}{k}\le\frac{8c_*}{3}. $$
If $n\ge k$, the survival lemma gives
$$ q_n \ge \frac{a_0\delta}{\sqrt{2c_*}}e^{-8c_*} > \delta. $$
If $n<k$, its proof gives $q_n\ge e^{-3}>\delta$. Hence
$$ N=\Omega\!\left(\frac{A}{\epsilon\delta}\right) \qquad (\epsilon\le\delta\le\delta_*). $$
If $\delta<\epsilon$, choose $d=s$ and put $\ell=\log(\epsilon/\delta)$. For
$$ n\le c_*\frac{A}{\epsilon^2}(1+\ell), $$
we have
$$ \frac nk\le \frac{2c_*}{\epsilon^2}(1+\ell), \qquad \frac{n\eta^2}{k}\le \frac{8c_*}{3}(1+\ell). $$
When $n\ge k$, the lemma yields
$$ \frac{q_n}{\delta} \ge \frac{a_0e^{-8c_*}}{\sqrt{2c_*}}\, \frac{e^{(1-8c_*)\ell}}{\sqrt{1+\ell}} > 1. $$
To verify the last inequality, the first factor is $8e^{-8c_*}>1$, and the second is at least $1$: its logarithmic derivative is
$$ 1-8c_*-\frac{1}{2(1+\ell)}>0. $$
For $n<k$, again $q_n\ge e^{-3}>\delta$. Therefore
$$ N= \Omega\!\left( \frac{A}{\epsilon^2} \left(1+\log\frac{\epsilon}{\delta}\right) \right) \qquad (\delta<\epsilon\le\delta_*). $$
These two bounds imply $N=\Omega(\mathcal D)$, since respectively
$$ \mathcal D\le\frac{A}{\epsilon\delta} $$
and
$$ \mathcal D \le \frac{A}{\epsilon^2} \left(1+\log\frac{\epsilon}{\delta}\right). $$
If $\epsilon\ge\delta_*$, Section 5.1 gives
$$ N\ge A\log\frac1\delta, $$
whereas
$$ \mathcal D \le \frac{A}{\epsilon^2}\log\frac1\delta \le \delta_*^{-2}A\log\frac1\delta. $$
If $\epsilon<\delta_*$ and $\delta\ge\delta_*$, the other elementary bound gives
$$ N\ge\frac{A}{2\epsilon}\log\frac1\delta. $$
Using $1-\delta\le\log(1/\delta)$,
$$ \mathcal D \le \frac{A(1-\delta)}{\epsilon\delta} \le \frac{A}{\epsilon\delta_*}\log\frac1\delta. $$
Thus $N=\Omega(\mathcal D)$ in every remaining case. At least one sample is necessary on a positive-mean instance, so the full lower bound is $\Omega(1+\mathcal D)$.
For the matching upper bound, when $\delta\ge1/4$, set
$$ x=\frac{\epsilon(1-\delta)}{\delta}\le3. $$
Then $\log(1+x)\ge x/4$, so $Q_1\le4\mathcal D$.
When $\delta<1/4$, use $A+\epsilon\le2A$ and concavity of the logarithm:
$$ Q_2 \le \frac{32A}{\epsilon^2}\log\left(1+\frac{\epsilon}{\delta}\right) \le \frac{128A}{3\epsilon^2} \log\left(1+\frac{\epsilon(1-\delta)}{\delta}\right). $$
This proves the stated optimal order for all $G\ge2$.
Let $0<A<1$, so $G=1+A$, and define
$$ p=\frac{A}{1+A}, \qquad V(x)=(1+A)\max\{x-p,0\}. $$
Its sampled derivative is $0$ with probability $p$ and $1+A$ otherwise. Its mean is $1$, and its ratio is exactly $G$.
On the event that the first sample is zero, every prefix of length $k$ has average at most
$$ (1+A)\frac{k-1}{k}. $$
This is strictly below $1-\epsilon$ whenever
$$ k<\frac{1+A}{A+\epsilon}. $$
Consequently, if $\delta<p$, every valid uniform sample cap satisfies
$$ \boxed{ N\ge\frac{1+A}{A+\epsilon}. } $$
For example, take $\epsilon\to0$, $A=\epsilon^3$, and $\delta=A/2$. The lower bound is of order $1/\epsilon$, while
$$ 1+\frac{A}{\epsilon^2} \log\left(1+\frac{\epsilon(1-\delta)}{\delta}\right) $$
remains bounded. Thus the optimal formula proved for $G\ge2$ fails uniformly near $G=1$.
One additional regime is settled: if $0<A\le\epsilon$ and $\delta=A/2$, this lower bound and Section 4 give
$$ N_{\mathrm{optimal}}=\Theta\!\left(\frac1\epsilon\right). $$
Indeed, $A+\epsilon\le2\epsilon$, and the logarithm in $Q_2$ has argument between $2$ and $3$.
The general optimal joint dependence for $1<G<2$ remains open here.
The sample budget can be computed without treating logarithm or integer rounding as unit-cost primitives.
For $A>0$, put
$$ x=\frac{A\epsilon}{(A+\epsilon)\delta}. $$
Construct $\ell$ satisfying
$$ \log(1+x)\le\ell\le3\log(1+x) $$
as follows:
For $x\le1$, $x/2\le\log(1+x)\le x$. For $x>1$, the minimality of $j$ gives the stated factor-three bound.
Replace the logarithm in $Q_2$ by $\ell$, take the smaller resulting sufficient budget and $Q_1$, and round upward to a power of two, with minimum $1$. Doubling and exact comparisons implement this rounding. The sample bound changes only by a universal constant factor.
Since $x<1/\delta$, computing $\ell$ costs $O(L)$ exact arithmetic operations and comparisons. Budget rounding costs
$$ O\!\left( 1+\log(1+G)+\log\frac1\epsilon+\log\frac1\delta \right). $$
Because $\epsilon,\delta$ are binary rationals included in $L$, total arithmetic preprocessing is $O(L+\log(1+G))$. If $G$ is also a binary rational encoded in $L$, this is $O(L)$.
For the resulting deterministic sample cap $N$, the resources are:
| Resource | Bound |
|---|---:|
| Completed permutation samples | $N$ |
| Derivative-oracle evaluations | $N$ |
| Value-oracle evaluations | $0$ |
| Exact arithmetic and comparisons | $O(\tau N+L+\log(1+G))$ |
| Commitment and opening operations | $O(\tau N)$ |
| Synchronous rounds | At most $3N$ |
| Input reading | $O(L)$ bit reads |
| Working storage | $O(\tau)$ exact-real words, plus $O(\log N)$ counter bits |
Modulo addition uses one comparison and at most one subtraction per contribution by maintaining a running value in $[0,1)$. Constructing $U\mu$ costs $O(\tau)$ multiplications per sample. Running sums and the maximizing prefix are maintained online.
Type descriptions contribute through the supplied support and input length $L$. There is no enumeration of possible types of description length at most $m$, and no dependence on clone count.
These are ideal exact-real operation counts. The assumptions do not provide finite bit-cost bounds for arithmetic on continuous draws or arbitrary real oracle outputs.
All achieved bounds are independent of $f$. The lower bounds use $f=0$, so they establish optimality for protocols required to work uniformly against every admissible violation rate.
⟨structured verdict parsed — rendered above⟩
The output is partial. Its upper bounds and its matching lower bounds for $G\ge2$ are sound under the stated uniform sample-cap interpretation. It also correctly handles $G=1$. It explicitly leaves the optimal complexity for general $1<G<2$ unresolved, so it does not fully answer USER_TASK.
I found no false central mathematical step. There is one minor omission in the specification of the distributed protocol.
1. Sampling construction and adversarial robustness
The focal representative draws its fresh random variable only after the opening deadline. Conditional on everything fixed before that draw, $C$ is fixed, and
$$
U=(R+C)\bmod1
$$
is uniform. Applying this statement conditional on the full history before each draw establishes independent uniform samples, even when the adversary adapts between samples.
Consequently,
$$
X_i=D_h(U_i\mu),
\qquad
\mathbb E[X_i]=a_h(\mu)
$$
is justified by the radial integrability assumption.
The construction satisfies the sampling behavior stipulated in the task: the generated predecessor vector is $U_i\mu$, and its reward is the actual derivative at that vector. The task does not require a single common order protecting every possible focal type, so the focal-specific construction is within scope.
The violation budget is unnecessary for this construction. The returned value $\widehat\epsilon=\epsilon$ satisfies the first guarantee pathwise for every admissible $f$.
Minor issue: absent commitments. The protocol specifies defaults for refused openings and invalid contributions, but does not explicitly specify what happens when a representative sends no commitment in the first round. An adversary is allowed to do this. The fixed-round termination claim needs a stated deadline and default for this case.
Minimum clarification: state how absent or malformed commitments are handled, whether they create a required opening, and confirm that their absence never delays a sample. This is a routine protocol specification issue; it does not affect the uniformity argument once contributions are fixed before the focal draw.
2. Normalization and degenerate cases
For $a_h(\mu)=0$, finite $G$ indeed forces $D_h(z)=0$ throughout the domain. Any positive derivative would give an infinite ratio. The zero-reward case is therefore handled correctly.
For positive mean, normalization gives
$$
0\le Y_i\le G,
\qquad
\mathbb E[Y_i]=1.
$$
Integrating the upper bound establishes $G\ge1$. The prescribed zero-over-zero convention also gives $G\ge1$ in the zero-mean case.
For $G=1$, these relations force $Y_i=1$ almost surely. One sample suffices. A positive constant-derivative instance shows that the empty prefix cannot satisfy the reward guarantee when $f=0$, establishing necessity.
3. Prefix-hitting bound
The stopped-sum argument is valid.
On a first crossing, the previous sum is negative, except at the initial starting point, and the crossing increment is at most $B$. Thus the stated overshoot bound holds. On survival through $n$, the sum is strictly negative.
The indicator $\mathbf1_{\{H\ge i\}}$ depends only on earlier increments, so independence justifies
$$
\mathbb E[S_{H\wedge n}]
=
\epsilon\,\mathbb E[H\wedge n].
$$
The lower bound
$$
\mathbb E[H\wedge n]\ge1+(n-1)q_n
$$
is correct, and rearranging yields
$$
q_n\le\frac{A}{A+\epsilon n}.
$$
This also handles the equality convention correctly: reaching zero counts as a successful prefix.
4. Exponential refinement
All substantive steps in the change-of-measure argument check out:
The resulting bound
$$
q_n\le
\frac{3A}{\epsilon n}
\exp\!\left(-\frac{n\epsilon^2}{8(A+\epsilon)}\right)
$$
is established.
5. Estimator and general upper bound
Selecting the largest completed-prefix average is permitted: the returned numerical value is the average of a particular completed prefix. Maintaining a fixed tie-breaking rule makes that selection unambiguous.
For positive mean, failure with $\widehat\epsilon=\epsilon$ is exactly $H>N$. The zero-mean case was already handled separately.
Both sufficient budgets are correct. Substitution of $Q_2$ into the exponential bound produces the stated factor involving $(1+x)^{-2}$, and
$$
\log(1+x)\ge\frac{x}{1+x}
$$
proves the final inequality.
Thus the general upper bound is established, subject to the minor protocol completion above. Its sample count is independent of clone count and $f$.
6. Lower bounds for $G\ge2$
The lower-bound functions satisfy the oracle-model hypotheses: they are continuous, monotone, nonnegative, piecewise linear, and vanish at zero. Their breakpoint conventions affect sampled distributions only on probability-zero events.
The elementary two-point instances have the stated means and maximum derivatives. Their low values lie strictly below the required threshold. Hence an all-low sample sequence makes every permitted prefix fail.
These lower bounds survive adaptive stopping: under a uniform cap, an independent sample sequence can be extended to the cap, and survival throughout that sequence rules out every available prefix. Additional oracle knowledge cannot remove this obstruction because the estimator must average actual sampled rewards.
The lattice-walk lemma is also justified:
The reward realization satisfies nonnegativity, the derivative cap, and mean $1$. Its threshold increments are precisely the walk increments.
The choices in the small-parameter regimes satisfy the lemma’s hypotheses. The bounds on $k$, the exponent estimates, and the strict inequalities showing failure probability greater than $\delta$ all check out. The remaining parameter cases and the comparison of the upper budgets with $\mathcal D$ are valid.
Accordingly, the output establishes the claimed optimal order for $G\ge2$ under its uniform sample-cap interpretation.
7. The range $1<G<2$
The example in Section 6 is valid. Conditional on a zero first reward, the upper bound on every subsequent prefix average is correct. It implies the stated cap lower bound whenever $\delta<A/(1+A)$.
The specialization $A=\epsilon^3$ and $\delta=A/2$ correctly shows that the formula proved for $G\ge2$ cannot extend uniformly toward $G=1$.
The additional regime $0<A\le\epsilon$ with $\delta=A/2$ is also correctly settled: the lower bound and $Q_2$ both have order $1/\epsilon$.
Major issue: unresolved requested optimality. The output explicitly does not determine the optimal joint dependence throughout $1<G<2$. USER_TASK requests the optimal worst-case complexity without restricting $G$ to the solved ranges.
Minimum additional work: establish matching bounds throughout the remaining range, or expressly retain a partial answer. This requires further mathematics, rather than an expositional clarification. The prover already accurately labels its answer partial.
8. Resource accounting
The stated derivative-oracle, value-oracle, arithmetic, commitment, and round counts follow from the construction and online prefix maximization.
The logarithm replacement and power-of-two rounding preserve the sample bound within universal constants. Their operation counts are justified.
The output correctly distinguishes exact-real operation counts from bit complexity and explicitly qualifies the encoding-dependent claim concerning $G$. It does not claim a finite bit-cost bound for arbitrary oracle outputs or continuous draws.
The bounds contain no clone-count dependence. Dependence on type descriptions is accounted for through the supplied support and input length, without enumerating possible types.
The deterministic-cap interpretation is explicitly stated. The optimality claims should retain that qualification: the output does not establish optimal expected sample complexity.
⟨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.