Answer: —
Corollary 1 — class: hardness
Given iid samples from an unknown two-candidate society \(\mu\) over ballot types, estimate the mass-transfer margin \(\rho_r(\mu)\), the infimum mass whose ballot types must change for the winner set under \(r\) to change, within additive error \(c\rho_r(\mu)+\epsilon\) with failure probability at most \(\delta\). Determine the minimum sample complexity for rules \(r\) that reduce to plurality on two candidates.
Let \(C=\{a,b\}\), with ballot types the two strict rankings. A society is represented by its support: the list of its \(\tau\) positive-mass types, each mass a binary rational, summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The support representation is hidden: an estimator accesses the unknown society \(\mu\) only through independent samples revealing complete ballots. The rule \(r\) agrees with plurality on every two-candidate mass profile and returns all tied winners.
Arbitrary fractions of existing mass may be reassigned to either ballot type, including an initially absent type, at unit cost per unit mass. Define \(\rho_r(\mu)=\inf_{\nu:r(\nu)\ne r(\mu)}\frac12\sum_t|\mu(t)-\nu(t)|\), where \(\nu\) ranges over probability distributions on these types.
For rational \(0\le c<1\), \(0<\epsilon<1\), and \(0<\delta<1/2\), let \(N^*(c,\epsilon,\delta)\) be the least integer sample budget permitting a randomized estimator satisfying \(\Pr[|\widehat\rho-\rho_r(\mu)|\le c\rho_r(\mu)+\epsilon]\ge1-\delta\) for every such \(\mu\), with no restriction on its encoding length. Probability includes sampling and estimator randomness.
State any running times in \(m=2\), \(\tau\), total binary encoding length \(L\), sample budget, and accuracy parameters.
What is the minimum worst-case sample complexity \(N^*(c,\epsilon,\delta)\) for estimating this mass-transfer margin?
For finite elections, a verified sampling lower bound is \(\Omega((1-c)^2\epsilon^{-2}\log(1/\delta))\) in the small-error regime, while plurality admits an additive-error estimator using \(O(\epsilon^{-2}\log(1/\delta))\) samples. [Source](https://www.ijcai.org/Proceedings/15/Papers/162.pdf)
No source located establishes the exact minimum sample budget for the continuous oracle problem defined here.
The exact minimum can be determined by a finite procedure throughout the regime
$$
\epsilon\ge \frac{(1-c)^2}{8}.
$$
Below this threshold, the exact minimum remains unresolved here.
In addition, the arguments below completely characterize when the minimum is zero, two, or three samples. They improve the exact regimes in the supplied notes.
Set
$$
\alpha=1-c,\qquad \beta=1+c,\qquad h=\frac{2\epsilon}{\alpha}.
$$
Allowing a budget of zero samples,
$$
N^*(c,\epsilon,\delta)=0
\quad\Longleftrightarrow\quad
\epsilon\ge\frac{\alpha}{4}.
$$
Suppose henceforth that
$$
0<\epsilon<\frac{\alpha}{4},
$$
so that $0<h<1/2$. Define
$$
d_2(h)=\frac{1}{2+4h^2}
$$
and
$$
d_3(h)=
\begin{cases}
\dfrac{1-4h^2}{2-4h^2},&h^2\le\dfrac16,\\[6pt]
\dfrac{1}{2+12h^2},&h^2\ge\dfrac16.
\end{cases}
$$
The two expressions defining $d_3$ agree at $h^2=1/6$.
The following are exact:
$$
N^*(c,\epsilon,\delta)=2
\quad\Longleftrightarrow\quad
\epsilon\ge\frac{\alpha^2}{8}
\ \text{and}\
\delta\ge d_2(h),
$$
and
$$
N^*(c,\epsilon,\delta)=3
\quad\Longleftrightarrow\quad
\epsilon\ge\frac{\alpha^2}{8}
\ \text{and}\
d_3(h)\le\delta<d_2(h).
$$
One sample never suffices in the regime under consideration.
In particular,
$$
0<\epsilon<\frac{\alpha^2}{8}
\quad\Longrightarrow\quad
N^*(c,\epsilon,\delta)\ge4.
$$
For example, when $c=0$ and $\epsilon=1/8$,
$$
N^*(0,1/8,\delta)=
\begin{cases}
2,&4/9\le\delta<1/2,\\
3,&3/7\le\delta<4/9,
\end{cases}
$$
and smaller confidence parameters require at least four samples.
Section 4 gives an exact finite decision procedure for every sample budget when
$$
\frac{\alpha^2}{8}\le\epsilon<\frac{\alpha}{4}.
$$
Thus that entire parameter regime is settled algorithmically, including budgets larger than three.
Let $p$ denote the mass of the ballot $a\succ b$. The mass of the other ballot is $1-p$. For a second society with parameter $q$, the mass-transfer distance is
$$
\frac12\bigl(|p-q|+|(1-p)-(1-q)|\bigr)=|p-q|.
$$
When $p>1/2$, changing the winning set requires reaching $q\le1/2$, and the nearest such profile is the tied profile. The argument for $p<1/2$ is symmetric. At $p=1/2$, arbitrarily small nonzero perturbations change the winning set. Consequently,
$$
\rho_r(\mu)=\left|p-\frac12\right|.
$$
Write
$$
t=\left|p-\frac12\right|\in[0,1/2].
$$
An output $y$ succeeds exactly when
$$
y\in A(t):=[\alpha t-\epsilon,\ \beta t+\epsilon].
$$
If $\epsilon\ge\alpha/4$, the constant output $\epsilon$ belongs to every $A(t)$, since
$$
\alpha t-\epsilon\le\frac{\alpha}{2}-\epsilon\le\epsilon
\le\beta t+\epsilon.
$$
If $\epsilon<\alpha/4$, the intervals
$$
A(0)=[-\epsilon,\epsilon]
\quad\text{and}\quad
A(1/2)=
\left[\frac{\alpha}{2}-\epsilon,\frac{\beta}{2}+\epsilon\right]
$$
are disjoint. A common output distribution cannot assign probability at least $1-\delta>1/2$ to both. This proves the zero-sample characterization.
More generally, suppose an estimator uses at most $N\ge1$ samples. It may be padded to use exactly $N$ samples. Under each unanimous society, successful estimation requires output greater than $\epsilon$. Therefore, conditional on either constant sample sequence, the probability of output greater than $\epsilon$ is at least $1-\delta$.
Under the tied society, these two sequences each have probability $2^{-N}$, and output greater than $\epsilon$ is a failure. Hence
$$
\delta\ge2^{1-N}(1-\delta),
$$
so
$$
N\ge1+\log_2\frac{1-\delta}{\delta}.
$$
Since $\delta<1/2$, this excludes one sample.
In the nonzero-sample regime, define
$$
y_{\mathrm{low}}=\epsilon,\qquad
y_{\mathrm{high}}=\frac{\alpha}{2}-\epsilon.
$$
Clipping any output to $[y_{\mathrm{low}},y_{\mathrm{high}}]$ cannot turn a success into a failure:
Thus outputs may be written as
$$
y=\epsilon+\beta X,\qquad X\in[0,g],
$$
where
$$
R=\frac{\beta}{\alpha},
\qquad
g=\frac{\alpha/2-2\epsilon}{\beta}.
$$
The defining relations give
$$
Rg+h=\frac12.
$$
The success condition becomes
$$
X\le t\le RX+h.
$$
The intervals overlap in the useful sense $g\le h$ exactly when
$$
\epsilon\ge\frac{\alpha^2}{8}.
$$
In that regime:
This decomposition is the basis of the exact decision procedure.
The hidden support representation does not affect the sample distribution: each sample is Bernoulli with parameter $p$.
An estimator can be symmetrized by randomly permuting its samples and randomly interchanging $a$ and $b$. This preserves its guarantee because the target $t$ is unchanged and the guarantee applies to both parameters $p$ and $1-p$.
For a symmetrized estimator using $N$ samples, the conditional output distribution depends only on
$$
Z=\left|2K-N\right|,
$$
where $K$ is the number of samples ranking $a$ first.
Let the possible values be
$$
z_0<z_1<\cdots<z_d.
$$
For $p=1/2+t$, their probabilities are the rational polynomials
$$
w_i(t)=
\sum_{\substack{0\le k\le N\\|2k-N|=z_i}}
\binom Nk
\left(\frac12+t\right)^k
\left(\frac12-t\right)^{N-k}.
$$
Define
$$
F_j(t)=\sum_{i=0}^{j}w_i(t),
\qquad F_{-1}(t)=0.
$$
For every $t<1/2$, all the $w_i(t)$ are positive.
For $t<1/2$, introduce $\theta\ge0$ by
$$
\frac12+t=\frac{e^\theta}{2\cosh\theta}.
$$
For suitable positive constants $b_i$,
$$
w_i(t)=
b_i\frac{\cosh(z_i\theta)}{(2\cosh\theta)^N}.
$$
If $\theta_2>\theta_1$, the likelihood ratio is increasing in $z_i$. Indeed,
$$
\frac{\partial}{\partial\theta}\log\cosh(z\theta)
=z\tanh(z\theta),
$$
and this is increasing in $z\ge0$. Integrating between $\theta_1$ and $\theta_2$ proves the assertion.
Consequently, $Z$ is stochastically increasing in $t$. Also, for $u>x$, among all tests $\phi_i\in[0,1]$ satisfying
$$
\sum_i w_i(x)\phi_i\ge\gamma,
$$
the minimum of
$$
\sum_i w_i(u)\phi_i
$$
is attained by filling the smallest $z_i$ first, with at most one fractional value. This follows directly by exchanging test mass from a larger likelihood ratio to a smaller one until the constraint is tight.
Here and below,
$$
\gamma=1-\delta.
$$
Assume
$$
\frac{\alpha^2}{8}\le\epsilon<\frac{\alpha}{4}.
$$
For $x\in[0,g]$, let $\phi_x$ be the randomized lower-tail test having probability exactly $\gamma$ under parameter $x$. Explicitly,
$$
\phi_x(i)=
\min\left\{
1,\,
\max\left\{
0,\,
\frac{\gamma-F_{i-1}(x)}{w_i(x)}
\right\}
\right\}.
$$
Define
$$
T_N(x)=\sum_i w_i(Rx+h)\phi_x(i).
$$
Exact feasibility criterion. A budget of $N$ samples is feasible if and only if
$$
T_N(x)\le\delta
\qquad\text{for every }x\in[0,g].
$$
First, a guarantee for every admissible binary-rational society also gives the guarantee for every real parameter.
To see this, fix an estimator and a sample budget. Conditional on each of the finitely many sample sequences, its output has a fixed probability distribution. Since $A(t)$ is closed and its endpoints vary continuously, its success probability is upper semicontinuous in $p$. Approaching any real $p$ through binary rationals therefore preserves the lower bound $\gamma$ on success probability.
After symmetrization and clipping, let $G_i(x)$ be the conditional distribution function of $X$ given $Z=z_i$.
For $x<g$, success at parameter $t=x$ implies
$$
\sum_i w_i(x)G_i(x)\ge\gamma.
$$
For any $v>Rx+h$, output with $X\le x$ fails. Taking $v$ down to $Rx+h$, continuity of the sample probabilities gives
$$
\sum_i w_i(Rx+h)G_i(x)\le\delta.
$$
The likelihood-ratio argument in Section 3 shows that replacing the test $G_i(x)$ by $\phi_x(i)$ can only decrease the latter probability. Thus $T_N(x)\le\delta$ for $x<g$. The functions $\phi_x(i)$ are continuous in $x$, so the inequality also holds at $x=g$.
For each observation $z_i$, prescribe the conditional distribution function of $X$ by
$$
\Pr[X\le x\mid Z=z_i]=\phi_x(i),
\qquad 0\le x<g,
$$
and put the remaining probability at $X=g$.
These are valid distribution functions. To verify monotonicity, note that randomized lower-tail tests are totally ordered pointwise. Stochastic monotonicity implies that a test of probability $\gamma$ at a larger parameter must be at least as large pointwise as the corresponding test at a smaller parameter. Thus $\phi_x(i)$ is nondecreasing in $x$. Its displayed formula also proves continuity.
At $0\le t<g$, success probability is
$$
\sum_i w_i(t)\phi_t(i)=\gamma.
$$
At $g\le t\le h$, success probability is one.
For $h<t<1/2$, put $x=(t-h)/R$. Continuity of the conditional distribution functions gives success probability
$$
1-\sum_i w_i(t)\phi_x(i)
=1-T_N(x)\ge\gamma.
$$
At $t=1/2$, the atom at $g$ gives the same formula with $x=g$. This proves sufficiency.
If the quantile cutoff is $j$, then
$$
F_{j-1}(x)\le\gamma\le F_j(x)
$$
and
$$
T_N(x)=
F_{j-1}(Rx+h)
+
\frac{\gamma-F_{j-1}(x)}{w_j(x)}
w_j(Rx+h).
$$
Since $w_j(x)>0$ on $[0,g]$, the exact criterion is equivalent to requiring
$$
\begin{aligned}
&[\delta-F_{j-1}(Rx+h)]w_j(x)\\
&\qquad-
[\gamma-F_{j-1}(x)]w_j(Rx+h)
\ge0
\end{aligned}
$$
for every $x\in[0,g]$ satisfying the cutoff inequalities, for each $j$.
These are finitely many univariate polynomial sign conditions with rational coefficients. They can be decided exactly by isolating their real roots, partitioning $[0,g]$ at those roots, and checking the signs on every resulting interval and boundary point.
Section 7 supplies a finite upper bound on the budget. Testing budgets up to that bound therefore determines the exact integer $N^*$ throughout the overlap regime. This is a finite algebraic procedure, rather than an optimization over unspecified estimators.
For two samples, the symmetrized experiment has two outcomes: agreement and disagreement. Agreement has probability
$$
q(t)=\frac12+2t^2.
$$
For three samples, the two outcomes are unanimity and non-unanimity. Unanimity has probability
$$
q(t)=\frac14+3t^2.
$$
Both experiments have the form
$$
q(t)=a+bt^2,\qquad b=4(1-a),
$$
with $a=1/2$ or $a=1/4$. Call the outcome of probability $q(t)$ the high observation.
Let $u$ and $v$ be the probabilities of output greater than $\epsilon$ conditional on the high and low observations, respectively.
At the tie,
$$
au+(1-a)v\le\delta.
$$
At every parameter $t>h$, successful output must be greater than $\epsilon$. Taking $t$ down to $h$ gives
$$
q(h)u+[1-q(h)]v\ge1-\delta.
$$
Write $q=q(h)$. For fixed $\delta$, the largest possible left side of the second inequality, subject to the first, is
$$
\begin{cases}
q\delta/a,&\delta\le a,\\[4pt]
q+(1-q)(\delta-a)/(1-a),&\delta\ge a.
\end{cases}
$$
Indeed, spending the allowed probability on $u$ first is optimal because
$$
\frac qa>\frac{1-q}{1-a}.
$$
Solving for the smallest feasible $\delta$ gives
$$
d(a,q)=
\begin{cases}
\dfrac{a}{a+q},&a+q\ge1,\\[6pt]
\dfrac{1-q}{2-a-q},&a+q\le1.
\end{cases}
$$
Substituting $a=1/2$ gives $d_2(h)$; substituting $a=1/4$ gives $d_3(h)$.
Suppose $g\le h$ and $Rg+h=1/2$. For either of these experiments,
$$
\frac{q(Rx+h)}{q(x)}
\ge\frac{q(h)}a
\qquad(0\le x\le g).
$$
Here is a proof. Differentiation shows that the sign of the derivative of the ratio is the sign of
$$
aRh+\bigl[a(R^2-1)-bh^2\bigr]x-bRhx^2.
$$
This quadratic has positive constant term and negative leading coefficient, and therefore exactly one positive root. The ratio first increases and then decreases; its minimum on $[0,g]$ is at an endpoint.
At $x=0$, its value is $q(h)/a$. At $x=g$, its value is $1/q(g)$. It remains to show
$$
q(h)q(g)\le a.
$$
Since $R\ge1$,
$$
h+g\le\frac12.
$$
Put $H=1/2-g\ge h$ and $z=gH\le1/16$. Then
$$
q(h)q(g)\le q(H)q(g)
=a+bz(bz-2a)\le a.
$$
The last inequality follows from
$$
bz\le\frac b{16}=\frac{1-a}{4}\le2a,
$$
which holds for both $a=1/2$ and $a=1/4$.
Let $d=d(a,q(h))$ and $\gamma=1-d$.
If $a+q(h)\ge1$, set
$$
w=1,\qquad A=d.
$$
If $a+q(h)\le1$, set
$$
w=\frac{\gamma}{1-a},
\qquad A=aw.
$$
In both cases,
$$
0<w\le1,\qquad
w-A=\gamma,\qquad
1-w+A\frac{q(h)}a=\gamma.
$$
Conditional on the low observation, output $X=0$ with probability $w$ and $X=g$ otherwise.
Conditional on the high observation, use the distribution function
$$
L(x)=w-\frac{A}{q(x)}
\qquad(0\le x<g),
$$
with the remaining probability placed at $g$. This is valid: $L(0)\ge0$, it is nondecreasing, and $L(g)<1$.
For $0\le t<g$, its success probability is
$$
q(t)L(t)+[1-q(t)]w=w-A=\gamma.
$$
For $g\le t\le h$, every output succeeds.
For $h<t\le1/2$, write $x=(t-h)/R$. The success probability is
$$
1-w+A\frac{q(t)}{q(x)}
\ge
1-w+A\frac{q(h)}a
=\gamma.
$$
Thus the necessary testing bound is attained whenever $g\le h$.
Suppose $h<g$. Choose a dyadic $t_1$ with
$$
h<t_1<g.
$$
Then $A(t_1)$ is disjoint from both $A(0)$ and $A(1/2)$.
For either the two- or three-sample experiment, its distribution at $t_1$ is a convex combination of its distributions at $0$ and $1/2$, because the experiment has just two outcomes and
$$
a<q(t_1)<1.
$$
At each endpoint, the probability of output in $A(t_1)$ is at most $\delta$. The same is therefore true at $t_1$, contradicting required success probability $1-\delta>\delta$.
Consequently, neither two nor three samples can suffice when $h<g$.
Combining necessity, attainability, and the exclusion of smaller budgets proves the exact characterizations in Section 1. Finally, direct algebra gives
$$
d_3(h)<d_2(h)
\qquad(0<h<1/2),
$$
so the stated three-sample regime is nonempty.
The preceding distributions can also be replaced by distributions on countably many rational outputs, sampled with finitely many fair random bits almost surely. Thus their exact attainability does not depend on physically producing an arbitrary real number.
Retain $a,b,w,A,L$ from Section 5 and define
$$
U(x)=w-\frac{Aq(h)}{a\,q(Rx+h)}.
$$
It suffices to replace the high-observation distribution function by any distribution function $D$ satisfying
$$
L(x)\le D(x)\le U(x)
\qquad(0<x<g),
$$
with $D(0)=L(0)$ and $D(g-)=L(g)$.
The ratio inequality proves $U(x)\ge L(x)$. More precisely, set
$$
J=\min\left\{
2aRh,\,
2aRh+\bigl[a(R^2-1)-bh^2\bigr]g
\right\}>0.
$$
Positivity follows from the strict endpoint inequality in the ratio proof. A direct calculation gives
$$
U(x)-L(x)\ge\frac{AbJ}{a}\,x.
$$
Also,
$$
L(s)-L(r)\le\frac{Ab}{a^2}(s^2-r^2)
\qquad(0\le r\le s\le g).
$$
Choose the rational number
$$
\eta=\min\left\{\frac12,\frac{aJ}{6g}\right\},
\qquad
r_j=g(1+\eta)^{-j}.
$$
For $x\in[r_{j+1},r_j)$, define
$$
D(x)=L(r_j).
$$
Set $D(0)=L(0)$ and $D(g)=1$.
The preceding bounds imply
$$
L(r_j)-L(r_{j+1})
\le U(r_{j+1})-L(r_{j+1}).
$$
Since $U$ is increasing, this proves $L\le D\le U$ on every such interval.
The resulting rational atom probabilities are:
They sum to one. The conditional tail probability of the index $j$ is at most
$$
\frac1a(1+\eta)^{-2(j-1)}.
$$
Consequently, sequential sampling of these rational atoms terminates almost surely and has finite moments of every fixed order.
For completeness, an exact rational coin with probability $s/t$ is sampled by drawing a uniform integer from $0$ through $2^\ell-1$, where $\ell=\lceil\log_2 t\rceil$, rejecting integers at least $t$, and accepting the event that the remaining integer is less than $s$. Each batch is accepted with probability greater than $1/2$.
Let
$$
s=\frac{\epsilon}{\alpha},
\qquad
H(\delta)=(1-2\delta)\log\frac{1-\delta}{\delta},
$$
and
$$
D(x)=
\left(\frac12+x\right)\log(1+2x)
+
\left(\frac12-x\right)\log(1-2x).
$$
Throughout the nonzero-sample regime,
$$
\max\left\{
1+\log_2\frac{1-\delta}{\delta},
\frac{H(\delta)}{D(2s)}
\right\}
\le N^*
\le
\left\lceil
\frac{1}{2s^2}\log\frac2\delta
\right\rceil.
$$
With $N$ samples, let $\widehat p$ be their empirical proportion ranking $a$ first and output
$$
\widehat\rho=\alpha\left|\widehat p-\frac12\right|.
$$
The reverse triangle inequality gives
$$
|\widehat\rho-t|
\le\alpha|\widehat p-p|+ct.
$$
Thus $|\widehat p-p|\le s$ implies success.
The indicators are independent Bernoulli variables, so Hoeffding’s inequality gives
$$
\Pr[|\widehat p-p|>s]\le2e^{-2Ns^2}.
$$
This proves the upper bound.
Choose dyadic $t>2s$ with $t<1/2$. The event that output exceeds $\epsilon$ has probability at most $\delta$ at the tie and at least $1-\delta$ at parameter $1/2+t$.
The relative entropy between their $N$-sample distributions is $ND(t)$. Passing to that event by the log-sum inequality yields
$$
ND(t)\ge H(\delta).
$$
Indeed, binary relative entropy increases in its first probability and decreases in its second when the first is larger, so its minimum over these probability constraints occurs at $1-\delta$ and $\delta$.
Dyadic alternatives can approach $2s$ from above. Continuity therefore gives
$$
N\ge\frac{H(\delta)}{D(2s)}.
$$
This use of arbitrarily close alternatives is valid because society encoding lengths are unrestricted.
The elementary relative-entropy bound by chi-squared divergence gives $D(x)\le4x^2$. For $\delta\le1/4$,
$$
H(\delta)\ge\frac14\log\frac1\delta.
$$
Hence, uniformly in that confidence range,
$$
N^*(c,\epsilon,\delta)
=
\Theta\left(
\frac{(1-c)^2}{\epsilon^2}\log\frac1\delta
\right)
$$
whenever $\epsilon<(1-c)/4$.
This order does not extend uniformly to $\delta<1/2$. For example, take
$$
\alpha=2^{-j},\qquad
c=1-\alpha,\qquad
\epsilon=\alpha^2,\qquad
\delta=\frac12-\alpha^2,
\qquad j\ge3.
$$
Here $h=2\alpha$ and $\delta\ge d_2(h)$, so the exact minimum is two samples, while
$$
\frac{\alpha^2}{\epsilon^2}\log\frac1\delta
=\alpha^{-2}\log\frac1\delta\longrightarrow\infty.
$$
Let $B$ be the total binary encoding length of $c,\epsilon,\delta$.
A sufficient budget can be selected using rational arithmetic: compute
$$
M=\min\{j:2^j\ge2/\delta\},
\qquad
\overline N=\left\lceil\frac{M}{2s^2}\right\rceil.
$$
Since $M\ge\log(2/\delta)$, this budget satisfies the upper bound’s requirement. Its computation takes time polynomial in $B$.
For a supplied budget $N$, the empirical estimator takes
$$
O\!\left(
N\log(N+1)+\operatorname{poly}(B+\log(N+1))
\right)
$$
bit operations and $O(B+\log(N+1))$ working bits.
The rational implementations in Section 6 use exactly two or three ballots and expected time polynomial in $B$ and $\eta^{-1}$.
For the exact offline feasibility procedure, each budget produces $O(N)$ rational polynomials of degree at most $2N$, with coefficient encoding lengths
$$
O\bigl(N(B+\log(N+1))\bigr).
$$
Exact root isolation gives a terminating decision procedure; no sharper bit complexity bound is asserted here.
All sampling and estimation costs exclude the oracle’s sample-generation cost. Here $m=2$ and $\tau\le2$. The estimators never read the hidden society representation, so their sample requirements and computation have no dependence on its encoding length $L$.
The continuous-model bounds above are proved directly; the related [finite-election sampling results](https://www.ijcai.org/Proceedings/15/Papers/162.pdf) provide context rather than an exact solution to this oracle problem.
The exact integer minimum is not determined here when
$$
0<\epsilon<\frac{(1-c)^2}{8}.
$$
In that region, the proof establishes $N^*\ge4$ and the general quantitative bounds, but the overlap-based feasibility criterion does not apply: intermediate parameters require simultaneous control of both tails of the output distribution.
⟨structured verdict parsed — rendered above⟩
The output is a correct partial resolution, with no mathematical error found in the claimed partial results. It does not determine the exact minimum sample budget throughout the parameter range requested in USER_TASK. The remaining issue is explicitly acknowledged by the prover.
1. Reduction to the margin estimation problem
The reduction is correct. With $p$ denoting the mass of $a\succ b$, mass-transfer distance between two profiles is $|p-q|$. Because the rule returns all tied winners, the nearest winning-set change from a strict majority occurs at $q=1/2$. At a tie, arbitrarily small perturbations change the winning set. Thus, including the unanimous and tied profiles,
$$
\rho_r(\mu)=\left|p-\frac12\right|.
$$
The acceptable-output interval
$$
A(t)=[\alpha t-\epsilon,\ \beta t+\epsilon]
$$
is exactly equivalent to the requested estimation guarantee.
2. Zero samples, one sample, and clipping
The zero-sample characterization is correct. When $\epsilon\ge\alpha/4$, the stated constant output succeeds for every $t$. Below that threshold, $A(0)$ and $A(1/2)$ are disjoint, so a single output distribution cannot give both intervals probability exceeding $1/2$.
The constant-sequence argument correctly yields
$$
\delta\ge 2^{1-N}(1-\delta).
$$
Padding an estimator to a fixed budget preserves its output law, and the conditional output distributions on the two constant sequences are the same under the unanimous and tied societies. This excludes one sample under the stated restrictions.
Clipping preserves success for the reasons supplied. Substituting $y=\epsilon+\beta X$ gives precisely
$$
X\le t\le RX+h.
$$
The identities defining $g$, $R$, and $h$, and the equivalence
$$
g\le h
\quad\Longleftrightarrow\quad
\epsilon\ge\frac{\alpha^2}{8},
$$
are correct.
3. Symmetrization and likelihood ratios
The symmetrization is valid because the target and acceptance intervals depend only on $|p-1/2|$. After permutation and candidate-swap averaging, the conditional output law depends only on $Z=|2K-N|$.
The displayed probabilities $w_i(t)$ are correct and strictly positive for $t<1/2$. Their hyperbolic-cosine representation establishes the claimed likelihood-ratio order: $z\tanh(z\theta)$ is increasing in $z$ for $\theta\ge0$.
The testing optimization is justified. At parameters $u>x$, minimizing the probability under $u$ subject to a specified lower probability under $x$ fills observations in increasing likelihood-ratio order. Positivity of the weights permits tightening the constraint and performing the stated exchanges. The parameter endpoint $u=1/2$ follows by continuity.
4. Exact feasibility criterion in the overlap regime
Both directions of the criterion are valid.
For necessity:
For sufficiency, the lower-tail tests are pointwise ordered, and stochastic monotonicity makes $\phi_x(i)$ nondecreasing in $x$. Together with continuity, this gives valid conditional distribution functions after adding the remaining mass at $g$.
The success calculations correctly treat the three parameter regions. At $t=1/2$, the relevant probability is the atom at $g$, whose mass is determined by the left limit $\phi_g(i)$. Thus the endpoint calculation is also valid.
The polynomial reduction correctly clears a strictly positive denominator. Root isolation and sign checks, including boundary points, provide a finite exact decision procedure. Combined with the finite sufficient budget in Section 7, this determines $N^*$ throughout the claimed overlap regime. No polynomial running-time claim is made for this procedure.
5. Exact two- and three-sample results
The experiment probabilities
$$
q(t)=\frac12+2t^2
\qquad\text{and}\qquad
q(t)=\frac14+3t^2
$$
are correct.
The necessary testing bound correctly optimizes the high-observation output probability first. Solving its two branches yields the displayed $d(a,q)$, and substitution gives precisely $d_2(h)$ and $d_3(h)$, including agreement at $h^2=1/6$.
I rechecked the critical algebra in the ratio inequality. The derivative numerator is
$$
2b\left(
aRh+[a(R^2-1)-bh^2]x-bRhx^2
\right),
$$
so the claimed derivative-sign expression is correct. Its endpoint-minimum argument is valid. The identity
$$
q(H)q(g)=a+bz(bz-2a)
$$
uses $b=4(1-a)$ and $H+g=1/2$; it checks out. The final inequality holds for both experiment values of $a$.
The proposed output distributions are valid, and their success probabilities attain the necessary bound. The endpoint $t=1/2$ is covered by their atoms at $g$.
When $h<g$, the selected dyadic $t_1$ has an acceptance interval disjoint from both endpoint acceptance intervals. The two-outcome observation law at $t_1$ is a convex combination of the endpoint laws. Applying the same conditional output kernel preserves that mixture, giving the stated contradiction.
Consequently, the two- and three-sample characterizations, their boundary inclusions, and the numerical example are correct. The strict comparison $d_3(h)<d_2(h)$ also holds throughout $0<h<1/2$.
6. Finite-coin implementation
The discretization argument is sound.
The strict endpoint product inequality implies the stated positivity of $J$. Direct algebra gives
$$
U(x)-L(x)
=
\frac{Abx\left(2aRh+[a(R^2-1)-bh^2]x\right)}
{a\,q(x)q(Rx+h)},
$$
which supports the claimed lower bound. The bound on increments of $L$ and the choice of $\eta$ imply the staircase inequalities.
The staircase is right-continuous, has the stated nonnegative rational atom masses, and those masses telescope to one. Its jumps do not invalidate the success guarantee: upper bounds using $D(x)$ also bound the failure probability involving $D(x-)$.
The geometric tail ensures almost-sure termination and finite moments. Rational rejection sampling implements each required coin exactly. The expected-time statement allows dependence on $\eta^{-1}$, so it does not incorrectly claim a bound polynomial solely in the parameter encoding length.
7. General bounds and computational claims
The empirical estimator’s deterministic error bound is correct:
$$
\left|\alpha\left|\widehat p-\frac12\right|-t\right|
\le\alpha|\widehat p-p|+ct.
$$
Hoeffding’s inequality applies to independent indicators taking values in $[0,1]$ and gives the stated sufficient sample budget.
The entropy lower bound correctly uses parameters with disjoint acceptance requirements. The sample-distribution relative entropy is $ND(t)$; including estimator randomness and passing to the output event cannot increase it. The constrained binary relative entropy is minimized at event probabilities $1-\delta$ and $\delta$, giving $H(\delta)$.
Unrestricted encoding length permits dyadic alternatives approaching $2s$ from above. The bounds $D(x)\le4x^2$ and $H(\delta)\ge\frac14\log(1/\delta)$ on the stated confidence range justify the claimed uniform asymptotic order.
The example showing failure of that order uniformly as $\delta$ approaches $1/2$ satisfies the exact two-sample conditions.
The stated empirical-estimator costs, rational sufficient-budget computation, polynomial degrees and coefficient sizes are consistent with the constructions. The independence from hidden society encoding length $L$ is justified: the estimators access only sampled ballots.
8. Blocking issue and minimum additional work
Major issue — incomplete resolution of USER_TASK. Section 8 leaves the exact integer minimum undetermined when
$$
0<\epsilon<\frac{(1-c)^2}{8}.
$$
The lower bound of four samples and the quantitative upper and lower bounds do not determine that minimum.
This is a limitation of scope, not a false step in the partial proof. No additional clarification is needed to verify the established results. To complete the assigned task, the prover must supply an exact characterization or finite exact decision procedure for the remaining region, with necessity and sufficiency proved for the permitted randomized estimators.
⟨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.