Sample Complexity for Winner Prediction in Elections (d4-conf-atal-2015-0119)

Given candidates \(C\), a voting rule, \(\epsilon,\delta\), and i.i.d. sampling access to an unknown society distribution \(\mu\) over complete rankings, promised \(\mathrm{MOV}_\infty(\mu)\ge\epsilon\), what is the minimum worst-case number of samples needed to output the true winner with probability at least \(1-\delta\)?

Let \(C\) contain \(m\ge 2\) candidates, and fix \(1\le k<m\), rational \(0<\epsilon<1\), rational \(0<\delta<1/2\), and a publicly known priority order for breaking ties.
A society is represented by its support: a list of \(\tau\) strict complete rankings with positive binary rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings, and \(L\) is the representation's total bit length.
For this prediction problem, the support list is hidden: the algorithm receives only independent samples of complete rankings from the unknown society \(\mu\).
Use \(k\)-approval, extending scores to masses, with winner \(w_k(\mu)\) selected using the fixed priority order.
Define \(\mathrm{MOV}_\infty(\mu)=\inf_{\nu:w_k(\nu)\ne w_k(\mu)}\frac12\sum_{\rho\in\mathcal L(C)}|\mu(\rho)-\nu(\rho)|\), where \(\nu\) ranges over all distributions on strict complete rankings, including rankings outside the original support.
Promise \(\mathrm{MOV}_\infty(\mu)\ge\epsilon\). A sample reveals one entire ranking; error probability includes sampling and internal randomness. State running times in \(m,\tau,L,k,\epsilon^{-1},\log(1/\delta)\).

What is the minimum worst-case number of samples needed to output \(w_k(\mu)\) with probability at least \(1-\delta\), as a function of \(m,k,\epsilon,\delta\)?

Discrete winner prediction has an upper bound of \(O(\epsilon^{-2}\log(k/\delta))\). [Primary source](https://arxiv.org/pdf/1502.04354v3).
The claimed discrete lower bound of \(\Omega(\epsilon^{-2}(1-\delta)\log(k+1))\) has an author-issued restriction to \(k<cm\) for fixed \(0<c<1\). [Author's erratum](https://asiaccs2026.cse.iitkgp.ac.in/~palash/).
The primary source already formulates its sampling arguments using vote distributions; no separately verified result establishes the full minimax function for the model stated here.

Minimax sample complexity

Let $N^*(m,k,\epsilon,\delta)$ be the smallest deterministic sample cap under which an algorithm succeeds with probability at least $1-\delta$ on every promised society. Algorithms may randomize and stop early. All logarithms below are natural.

Define
$$ \beta=\frac{m-k}{m}, \qquad \epsilon_{\max}=\frac{m-k}{2(m-1)}, \qquad \Lambda=\log\frac{k+1}{\delta}. $$

The minimax rate for $m\ge3$, throughout the nonempty promise range, is
$$ N^*(m,k,\epsilon,\delta) = \begin{cases} \displaystyle \Theta\!\left(\frac{\beta}{\epsilon^2}\Lambda\right), &0<\epsilon\le\beta/16,\\[6pt] \displaystyle \Theta\!\left( 1+\frac{\Lambda}{\log(1/(1-2\epsilon))} \right), &\beta/16<\epsilon\le\epsilon_{\max}. \end{cases} $$
All implicit constants are universal. At $\epsilon=1/2$, which is feasible only for $k=1$, the denominator in the second line is interpreted as infinite; exactly one sample suffices.

The promise class is empty when $\epsilon>\epsilon_{\max}$, giving sample complexity zero under the vacuous convention. For $m=2$, an exact binomial characterization is given in Section 7.

The cited paper provides the earlier $O(\epsilon^{-2}\log(k/\delta))$ upper bound; the author’s erratum restricts its claimed discrete lower-bound argument. The bounds here are proved directly for the stated distributional model. [Primary source](https://arxiv.org/pdf/1502.04354v3), [author’s erratum](https://asiaccs2026.cse.iitkgp.ac.in/~palash/).

1. Exact margin and feasibility

For a candidate $c$, let $A_c(\rho)$ indicate that $c$ is among the first $k$ positions of ranking $\rho$, and write
$$ s_c=\mathbb E_\mu A_c. $$
Then $0\le s_c\le1$ and $\sum_c s_c=k$.

Lemma 1. If $w=w_k(\mu)$, then
$$ \mathrm{MOV}_\infty(\mu) =\frac12\min_{c\ne w}(s_w-s_c). $$

Proof. For a rival $c$, the function $X=A_w-A_c$ takes values in $[-1,1]$. Consequently,
$$ \left|\mathbb E_\mu X-\mathbb E_\nu X\right| \le2\,\mathrm{TV}(\mu,\nu). $$
Indeed, the positive and negative parts of $\mu-\nu$ each have mass $\mathrm{TV}(\mu,\nu)$.

If $c\ne w$ wins under $\nu$, then $s_c(\nu)\ge s_w(\nu)$. Hence
$$ \mathrm{TV}(\mu,\nu)\ge\frac{s_w-s_c}{2}, $$
which proves the lower bound.

Conversely, choose a rival attaining the smallest gap, and denote that gap by $d$. If $d>0$, put
$$ a=\Pr_\mu(A_w-A_c=1), \qquad b=\Pr_\mu(A_w-A_c=-1). $$
Since $a-b=d$, there is enough mass in the first class to move $d/2+\eta$ of it, for sufficiently small $\eta>0$, to a ranking in the second class. Such a destination ranking exists because $1\le k<m$.

This operation has total variation distance $d/2+\eta$ and changes the score difference to $-2\eta$. Thus $w$ loses. Letting $\eta$ decrease to zero proves the upper bound. If $d=0$, mixing in an arbitrarily small mass on a ranking approving $c$ but not $w$ makes $c$ strictly outscore $w$. ∎

The promise is therefore equivalent to
$$ s_w-s_c\ge2\epsilon \qquad(c\ne w). $$
In particular, the population winner is unique.

Summing these inequalities gives
$$ k\le m s_w-2\epsilon(m-1) \le m-2\epsilon(m-1). $$
Thus $\epsilon\le\epsilon_{\max}$ is necessary.

It is sufficient: always approve a fixed candidate $w$, and choose the other $k-1$ approved candidates uniformly among the remaining $m-1$. Then
$$ s_w=1, \qquad s_c=\frac{k-1}{m-1}\quad(c\ne w), $$
and the margin is exactly $\epsilon_{\max}$. Complete each approval set deterministically into a ranking. This produces a finite society with positive rational masses.

This construction is available for every choice of $w$. Consequently, on a nonempty promise class, a zero-sample algorithm cannot succeed uniformly when $\delta<1/2$.

2. A general upper bound

The algorithm counts approvals in independent samples and returns the empirical winner, using the prescribed priority order.

We prove
$$ N^* \le \min\left\{ \left\lceil4\epsilon^{-2}\log\frac{8k}{\delta}\right\rceil,\; \left\lceil2\beta\epsilon^{-2}\log\frac{m-1}{\delta}\right\rceil \right\}. $$

Approval-count bound

Let $B_1,\ldots,B_n$ be independent Bernoulli variables with mean $p$, and let $S=\sum_i(B_i-p)$. For $0<t\le1$ and $nt^2\ge2\log2$,
$$ \Pr(|S|\ge nt)\le8p\,e^{-nt^2/4}. $$

To verify this, set $\lambda=t/2$. The inequalities
$$ e^\lambda-1-\lambda\le\lambda^2, \qquad e^{-\lambda}-1+\lambda\le\lambda^2 $$
hold for $0\le\lambda\le1/2$. The Bernoulli moment-generating function therefore gives
$$ \mathbb E e^{\lambda S}\le e^{np\lambda^2}, \qquad \mathbb E e^{-\lambda S}\le e^{np\lambda^2}. $$
By convexity in $p$,
$$ \mathbb E\bigl(\cosh(\lambda S)-1\bigr) \le e^{np\lambda^2}-1 \le p(e^{n\lambda^2}-1). $$
For $z\ge\log2$,
$$ \cosh z-1=\frac{e^z}{2}(1-e^{-z})^2\ge\frac{e^z}{8}. $$
Applying Markov’s inequality at $z=\lambda nt=nt^2/2$ proves the assertion.

Apply this bound with $t=\epsilon$ to every candidate. Since $\sum_c s_c=k$,
$$ \Pr\bigl(\exists c:\ |\widehat s_c-s_c|\ge\epsilon\bigr) \le8k\,e^{-n\epsilon^2/4}. $$
When all deviations are strictly smaller than $\epsilon$, every empirical winner–rival gap is positive. This proves the first sample bound; its chosen budget also satisfies the concentration bound’s side condition.

Rejection-count bound

Put $Y_c=1-A_c$ and $q_c=\mathbb E Y_c$. The winner minimizes rejection probability, and $\sum_cq_c=m-k$, so $q_w\le\beta$.

For a rival $c$, let $X=Y_c-Y_w$, and define
$$ a=\Pr(X=1),\qquad b=\Pr(X=-1),\qquad d=a-b. $$
The promise gives $d\ge2\epsilon$, while $b\le q_w\le\beta$. Optimizing the exponential Markov bound gives
$$ \Pr\left(\sum_{i=1}^nX_i\le0\right) \le \left(1-(\sqrt a-\sqrt b)^2\right)^n \le e^{-n(\sqrt a-\sqrt b)^2}. $$
For $b>0$, the optimizing parameter is $\frac12\log(a/b)$; for $b=0$, take its limiting value.

Moreover,
$$ (\sqrt a-\sqrt b)^2 =\frac{d^2}{(\sqrt a+\sqrt b)^2} \ge\frac{d^2}{2(a+b)} \ge\frac{d^2}{2(d+2\beta)}. $$
The final expression increases with $d>0$. Feasibility implies $\epsilon\le\beta$, so
$$ (\sqrt a-\sqrt b)^2 \ge\frac{\epsilon^2}{\epsilon+\beta} \ge\frac{\epsilon^2}{2\beta}. $$
A union bound over rivals proves the second sample bound, counting every empirical tie as a possible failure.

If $k\le m/2$, then $\beta\ge1/2$, and the first bound applies. If $k>m/2$, then $m<2k$, and the second applies. Thus, throughout the feasible range,
$$ N^*=O\!\left(\frac{\beta}{\epsilon^2}\Lambda\right). $$

3. Matching lower bound for small margins

Assume $m\ge3$ and $0<\epsilon\le\beta/16$.

A finite rational family

Choose
$$ M=\min\{m,\max\{3,2k\}\} $$
active candidates. Then $M\ge3$ and $M\ge k+1$. Let $U$ be uniform on their $k$-element approval sets. Complete each set into a ranking using a fixed deterministic rule.

For active candidate $i$, let $I_i$ indicate its inclusion, and put
$$ u=\frac{k}{M}, \qquad V=u(1-u), \qquad \lambda=\frac{2\epsilon(M-1)}{MV}. $$
Define
$$ P_i(S)=U(S)\bigl(1+\lambda(I_i(S)-u)\bigr). $$
These masses sum to one. They are positive because $\lambda\le1/2$:

• If $k=1$, then $M=3$ and $\lambda=6\epsilon\le3/8$.
• If $2\le k\le m/2$, then $M=2k$, $V=1/4$, and $\lambda<8\epsilon\le1/2$.
• If $k>m/2$, then $M=m$, $V=u\beta$, and $\lambda\le1/(8u)<1/4$.

All masses are rational.

Counting subsets gives, for $j\ne i$,
$$ \operatorname{Var}_U(I_i)=V, \qquad \operatorname{Cov}_U(I_i,I_j)=-\frac{V}{M-1}. $$
Indeed,
$$ \mathbb E_U(I_iI_j)=\frac{k(k-1)}{M(M-1)}. $$
Therefore the scores under $P_i$ are
$$ s_i=u+\lambda V, \qquad s_j=u-\frac{\lambda V}{M-1}. $$
Their difference is exactly $2\epsilon$. Inactive candidates have score zero; their gap from $i$ exceeds $2\epsilon$ because $u\ge1/3$ and $2\epsilon\le1/8$. Lemma 1 shows that $P_i$ has winner $i$ and margin $\epsilon$.

Divergence bounds

Write $D(P\|Q)$ for relative entropy. The inequality $\log x\le x-1$ gives
$$ D(P\|Q)\le\sum_x\frac{(P(x)-Q(x))^2}{Q(x)}. $$
In all three cases above, $V\ge\beta/5$. Consequently,
$$ D(P_i\|U) \le\lambda^2V \le\frac{4\epsilon^2}{V} \le\frac{20\epsilon^2}{\beta}. $$
Also $P_j\ge U/2$, and
$$ \mathbb E_U(I_i-I_j)^2=\frac{2VM}{M-1}. $$
Hence
$$ D(P_i\|P_j) \le2\lambda^2\mathbb E_U(I_i-I_j)^2 \le\frac{16\epsilon^2}{V} \le\frac{80\epsilon^2}{\beta}. $$

Dependence on the number of possible winners

Choose $J$ uniformly among the $M$ active candidates, and draw $n$ samples from $P_J$. An algorithm using at most $n$ samples can be padded with unused samples. Independent internal randomness does not increase information about $J$.

The identity relating average divergence to mutual information gives
$$ I(J;\text{samples}) \le\frac1M\sum_iD(P_i^{\otimes n}\|U^{\otimes n}) \le\frac{20n\epsilon^2}{\beta}. $$
For completeness, the average divergence to a fixed reference equals the mutual information plus the nonnegative divergence of the sample marginal to that reference.

Map any inactive output to a fixed active candidate, and call the resulting prediction $\widehat J$. Its success probability $p$ satisfies $p>1/2$. Under the product of the marginals of $J$ and $\widehat J$, the equality event has probability $1/M$. The log-sum inequality and data processing therefore imply
$$ I(J;\text{samples}) \ge I(J;\widehat J) \ge\operatorname{kl}(p\|1/M) \ge\operatorname{kl}(1/2\|1/M), $$
where $\operatorname{kl}$ denotes binary relative entropy. The last inequality follows from its monotonicity in the first argument above $1/M$.

Explicitly,
$$ \operatorname{kl}(1/2\|1/M) =\frac12\log\frac{M^2}{4(M-1)} \ge\frac1{64}\log M. $$
For $M\ge16$, this follows from the lower bound $\frac12\log(M/4)\ge\frac14\log M$. For $3\le M<16$, the left side is at least $\frac12\log(9/8)\ge1/18$, while $\log M<3$.

Since $M\ge k+1$, we obtain
$$ n=\Omega\!\left(\frac{\beta}{\epsilon^2}\log(k+1)\right). $$

Dependence on confidence

For $\delta\le1/4$, choose distinct $i,j$, and let $E$ be the event that the algorithm outputs $i$. Under $P_i$, its probability is at least $1-\delta$; under $P_j$, it is at most $\delta$. Applying the log-sum inequality to this event gives
$$ nD(P_i\|P_j) \ge\operatorname{kl}(1-\delta\|\delta) =(1-2\delta)\log\frac{1-\delta}{\delta} \ge\frac14\log\frac1\delta. $$
Here $1-2\delta\ge1/2$ and $1-\delta\ge\sqrt\delta$.

Thus
$$ n=\Omega\!\left(\frac{\beta}{\epsilon^2}\log\frac1\delta\right). $$
Combining the two lower bounds proves the first line of the theorem when $\delta\le1/4$. When $\delta>1/4$, the confidence logarithm is bounded and is absorbed by $\log(k+1)$. This completes the small-margin lower bound uniformly for all permitted $\delta$.

4. A boundary family with a different information rate

The following family supplies the missing large-margin lower bounds.

Lemma 2. Let $M>k\ge2$, and put
$$ h=\frac{k-1}{M-1}, \qquad a_M=\log\frac1h. $$
For each of $M$ candidates $i$, let $Q_i$ approve $i$ always and choose the other $k-1$ approved candidates uniformly among the remaining $M-1$. Complete approval sets deterministically into rankings.

The minimum worst-case sample budget for identifying $i$ within this family is
$$ \Theta\!\left( 1+\frac{\log((k+1)/\delta)}{a_M} \right), $$
with universal constants.

Proof of the upper bound. Let $T$ be the intersection of the sampled approval sets. It always contains the winner. Every rival survives all $n$ samples with probability $h^n$, so
$$ \Pr(|T|>1)\le(M-1)h^n=(k-1)h^{n-1}. $$
Thus
$$ n=1+\left\lceil\frac{\log((k-1)/\delta)}{a_M}\right\rceil $$
suffices.

Proof of the lower bound. Give the winner index a uniform prior. Every sample sequence has identical likelihood under all indices in $T$ and zero likelihood under other indices. The posterior is therefore uniform on $T$.

Under a fixed true winner, let $X=|T|-1$ and
$$ z=\mathbb E X=(M-1)h^n. $$
The optimal Bayes error is $\mathbb E[X/(1+X)]$.

Two distinct rivals are jointly approved on one sample with probability
$$ h_2=\frac{(k-1)(k-2)}{(M-1)(M-2)} \le h^2. $$
For $n\ge1$, this gives
$$ \mathbb E X^2 =z+(M-1)(M-2)h_2^n \le z+z^2. $$
Cauchy–Schwarz, applied to $\sqrt{X/(1+X)}$ and $\sqrt{X(1+X)}$, yields
$$ \mathbb E\frac{X}{1+X} \ge\frac{(\mathbb E X)^2}{\mathbb E[X(1+X)]} \ge\frac{z}{z+2}. $$
A uniformly successful algorithm must have Bayes error at most $\delta$. Hence
$$ z\le\frac{2\delta}{1-\delta}, \qquad n a_M\ge \log\frac{(M-1)(1-\delta)}{2\delta}. $$

We verify that this implies the claimed rate uniformly, including $\delta$ close to $1/2$.

First, $n\ge1$. Also $\delta<1/2$ implies
$$ n\ge1+\frac{\log((k-1)/2)}{a_M}. $$
For $k\ge4$,
$$ \log((k-1)/2)\ge\frac14\log(k+1). $$
Indeed, $(k-1)^4/(16(k+1))$ is increasing for $k\ge4$ and exceeds one at $k=4$.

For $k=2,3$, we instead use
$$ a_M\ge\log\frac{k}{k-1}\ge\log(3/2); $$
then $n\ge1$ already supplies a universal constant multiple of $\log(k+1)/a_M$.

Finally, if $\delta\le1/4$, then $M-1\ge2$ gives
$$ n a_M \ge\log\frac{1-\delta}{\delta} \ge\frac12\log\frac1\delta. $$
For $\delta>1/4$, the confidence term is absorbed by $\log(k+1)$. Combining these inequalities proves the lower bound. ∎

These societies have finite support and positive rational masses. Their winner–rival gap is $1-h$, so their margin is $(1-h)/2$.

5. Large-margin lower bound

Assume
$$ m\ge3, \qquad \beta/16<\epsilon\le\epsilon_{\max}. $$
Write
$$ g=2\epsilon, \qquad t=1-g, \qquad a=\log\frac1t. $$

The case $k\ge2$

Feasibility gives
$$ t\ge\frac{k-1}{m-1}>0. $$
Choose an active set of size
$$ M=1+\left\lceil\frac{k-1}{t}\right\rceil. $$
Then $k+1\le M\le m$. Place the family from Lemma 2 on these active candidates; inactive candidates are never approved.

Its rival approval probability is
$$ h=\frac{k-1}{M-1}\le t. $$
Thus its active winner–rival gap is at least $1-t=g$, and its gap from inactive candidates is one. Every member belongs to the required promise class.

It remains to compare its information rate with $a$. Since
$$ \frac{M-1}{k-1} \le\frac1t+\frac1{k-1}, $$
we have
$$ a_M \le a+\log\left(1+\frac{t}{k-1}\right) \le a+\frac1{k-1}. $$
Moreover,
$$ (m-k)(k-1)\ge m-2. $$
To check this, set $x=k-1$ and observe that the difference from $m-2$ is $(x-1)(m-2-x)\ge0$. Consequently,
$$ \frac1{k-1}\le\frac{m-k}{m-2}\le3\beta. $$
Our margin assumption gives $g>\beta/8$, and $a=-\log(1-g)\ge g$. Therefore
$$ a_M\le a+3\beta\le a+24g\le25a. $$
Lemma 2 now proves
$$ N^*=\Omega\!\left(1+\frac{\Lambda}{a}\right). $$

The case $k=1$

For $g<1$, consider two societies supported on rankings whose top candidates are $i$ and $j$. Their top-candidate probabilities are respectively
$$ \left(\frac{1+g}{2},\frac{1-g}{2}\right) \quad\text{and}\quad \left(\frac{1-g}{2},\frac{1+g}{2}\right). $$
All remaining candidates have score zero. Both societies have margin $\epsilon$.

Their one-sample affinity, defined as $\sum_x\sqrt{P(x)Q(x)}$, is
$$ B=\sqrt{1-g^2}. $$
For any two distributions with affinity $B$, Cauchy–Schwarz gives
$$ \mathrm{TV}(P,Q) \le\sqrt{1-B^2}. $$
Indeed, apply it to the factors $\sqrt P-\sqrt Q$ and $\sqrt P+\sqrt Q$ in the total-variation sum. Affinity multiplies under independent products. Hence the optimal equal-prior error after $n$ samples is at least
$$ \frac{1-\sqrt{1-B^{2n}}}{2} \ge\frac{B^{2n}}4. $$
Writing
$$ b=-\log(1-g^2)\le-\log(1-g)=a, $$
we obtain
$$ n\ge\frac{\log(1/(4\delta))}{b}. $$
For $\delta\le1/16$, this gives a universal constant multiple of $\Lambda/a$.

For $\delta>1/16$, use $n\ge1$. Here $\beta=(m-1)/m\ge2/3$, so
$$ a\ge g>\beta/8\ge1/12, \qquad \Lambda<\log32. $$
Thus $1+\Lambda/a$ is universally bounded, and $n\ge1$ supplies the required lower bound.

If $g=1$, one sample is necessary and sufficient. This completes the large-margin lower bound.

6. Large-margin upper bound

Again write $g=2\epsilon$, $t=1-g$, and $a=\log(1/t)$.

If $\epsilon=1/2$, feasibility forces plurality, and the promised winner has score one. One sample identifies it. Assume henceforth $\epsilon<1/2$.

Margins at most $3/8$

For $\epsilon\le3/8$,
$$ a=-\log(1-2\epsilon) \le\frac{2\epsilon}{1-2\epsilon} \le8\epsilon. $$
When $\epsilon>\beta/16$, we also have $\beta<16\epsilon$. Therefore
$$ \frac{\beta}{\epsilon^2} \le\frac{128}{a}. $$
The general upper bound from Section 2 proves the desired rate in this range.

Margins larger than $3/8$

Now $0<t<1/4$. The score-gap promise implies
$$ s_w\ge1-t, \qquad s_c\le t\quad(c\ne w). $$
Let $Z_c$ be candidate $c$’s approval count in $n$ samples. It suffices that
$$ Z_w>n/2 \quad\text{and}\quad Z_c<n/2\quad(c\ne w). $$

Set
$$ \lambda=\log\frac{1-t}{t}, \qquad H(t)=-\frac12\log(4t(1-t)). $$
The exponential Markov bound for a binomial variable, together with monotonicity in its success probability, gives
$$ \Pr(Z_w\le n/2)\le e^{-nH(t)}. $$

We need a rival bound weighted by its approval probability. If $Z$ is binomial with success probability $p\le t$, then convexity in $p$ gives
$$ \mathbb E(e^{\lambda Z}-1) =(1+p(e^\lambda-1))^n-1 \le\frac pt\left((1+t(e^\lambda-1))^n-1\right). $$
Provided $\lambda n/2\ge\log2$, Markov’s inequality therefore yields
$$ \Pr(Z\ge n/2) \le\frac{2p}{t} \left(2\sqrt{t(1-t)}\right)^n =\frac{2p}{t}e^{-nH(t)}. $$
Summing over rivals, using $\sum_c s_c=k$, gives
$$ \Pr(\text{prediction fails}) \le\left(1+\frac{2k}{t}\right)e^{-nH(t)}. $$

We claim that
$$ H(t)\ge\frac{a}{16} \qquad(0<t\le1/4). $$
To verify it, regard $H$ as a function of $a$, where $t=e^{-a}$ and $a\ge\log4$. Then
$$ \frac{dH}{da} =\frac12\left(1-\frac{e^{-a}}{1-e^{-a}}\right) \ge\frac13. $$
Thus $H-a/16$ is increasing. At $a=\log4$, it is positive because
$$ \frac12\log(4/3)>\frac{\log4}{16}, $$
equivalently $(4/3)^8>4$.

Since $1+2k/t\le3k/t$, it is enough to take
$$ n= \left\lceil16\left(1+\frac{\log(3k/\delta)}a\right)\right\rceil. $$
This budget also satisfies $\lambda n/2\ge\log2$. Consequently,
$$ N^*=O\!\left(1+\frac{\Lambda}{a}\right). $$
Together with Section 5, this proves the second line of the theorem.

7. Exact binary characterization

For $m=2$, necessarily $k=1$. The promise class is nonempty exactly when $\epsilon\le1/2$.

For $0<\epsilon<1/2$, put $p_0=1/2+\epsilon$. If $B_n$ has distribution $\operatorname{Bin}(n,p_0)$, define
$$ e_n(\epsilon) = \Pr(B_n<n/2) +\frac12\Pr(B_n=n/2). $$
Then the exact answer is
$$ N^*(2,1,\epsilon,\delta) = \min\{n\ge1:\ e_n(\epsilon)\le\delta\}. $$

Proof. Consider the two endpoint societies with probabilities $p_0$ and $1-p_0$ that the first candidate ranks above the second. With equal prior probabilities, their likelihood ratio favors the first society exactly when the observed count exceeds $n/2$. Majority prediction with fair randomization on a tie therefore minimizes average error, attaining $e_n(\epsilon)$ under each endpoint. Every algorithm’s worst-case error is at least this average error.

The same rule works uniformly over the promise class. Its error is nonincreasing as the first candidate’s ranking probability increases above $p_0$: couple the Bernoulli samples using common uniform random variables, and note that the conditional error is nonincreasing in the observed count. Symmetry handles probabilities below $1-p_0$. ∎

At $\epsilon=1/2$, handle the deterministic endpoint societies directly: exactly one sample suffices. In particular, no likelihood ratio is needed on zero-probability observations.

8. Running time and numerical parameters

Let $n$ be the selected sample budget. Streaming full rankings, maintaining approval counters, and selecting the empirical winner takes
$$ O(m(n+1)) $$
word operations. With binary candidate labels and counters, a corresponding bound is
$$ O\!\left(m(n+1)(\log m+\log(n+1))\right) $$
bit operations, using
$$ O\!\left(m(\log m+\log(n+1))\right) $$
bits of working memory.

For $m\ge3$, substitute the theorem’s budget. The resulting word-operation bounds are
$$ O\!\left(m+(m-k)\epsilon^{-2}\Lambda\right) $$
in the small-margin range, and
$$ O\!\left( m\left(1+\frac{\Lambda}{\log(1/(1-2\epsilon))}\right) \right) $$
in the large-margin range.

These costs exclude the sampling oracle’s implementation. The algorithm never reads the hidden representation, so they have no dependence on $\tau$ or $L$.

For complete preprocessing accounting, let $b_\epsilon,b_\delta$ be the encoding lengths of the supplied rational parameters. These are distinct from the hidden society length $L$ and cannot generally be bounded by $\epsilon^{-1}$ and $\log(1/\delta)$.

The budgets can be selected with polynomial bit cost in
$$ b_\epsilon+b_\delta+\log m $$
using integer arithmetic. No exact transcendental evaluation is required:

• For the bounds in Section 2, replace natural-log factors by suitable larger integer ceilings of binary logarithms.
• In the high-margin case, compute

$$ H=\left\lceil\log_2\frac{k+1}{\delta}\right\rceil, \qquad J=\left\lfloor\log_2\frac1t\right\rfloor, $$
and use $n=32(1+\lceil H/J\rceil)$. Here $J\ge2$. Since $a\ge J\log2$ and $\log(3k/\delta)\le(H+2)\log2$, this budget satisfies the bound proved in Section 6 and has the same asymptotic order.

Binary-log floors and ceilings of rationals are determined by bit lengths and exact shifted-integer comparisons.

For the exact binary minimum, let
$$ H=\left\lceil\log_2\frac2\delta\right\rceil, \qquad B=\left\lceil\epsilon^{-2}H\right\rceil. $$
The exponential Markov bound gives $e_B(\epsilon)\le e^{-2B\epsilon^2}<\delta$. Thus one can compute the exact binomial errors for all $n\le B$ using the binomial dynamic recurrence and return the first qualifying $n$. This uses polynomial bit time in $B,b_\epsilon,b_\delta$; a conservative schoolbook-arithmetic bound is
$$ O\!\left( B^4(b_\epsilon+b_\delta+\log(B+1))^2 \right). $$
Sampling and prediction then use the streaming bounds above.

9. Boundary behavior and veto

At the maximum feasible margin, the formula specializes, for $k\ge2$, to
$$ N^*(m,k,\epsilon_{\max},\delta) = \Theta\!\left( 1+\frac{\log((k+1)/\delta)} {\log((m-1)/(k-1))} \right). $$
This explains why the small-margin expression cannot simply be extrapolated to every parameter range. For plurality at its feasibility boundary, exactly one sample suffices.

For veto, $k=m-1$ and $m\ge3$, the two branches combine to give
$$ N^*(m,m-1,\epsilon,\delta) = \Theta\!\left( \frac1{m\epsilon^2}\log\frac m\delta \right) $$
throughout the entire feasible range
$$ 0<\epsilon\le\frac1{2(m-1)}. $$
Indeed, in the large-margin branch, $\epsilon$ is within universal factors of $1/m$, and $-\log(1-2\epsilon)$ is within universal factors of $\epsilon$.

⟨structured verdict parsed — rendered above⟩

The output proves the claimed minimax rates, with an exact characterization for the binary case. I found no false step, blocking gap, or necessary expositional repair. The running-time claims correctly distinguish access to samples from access to the hidden society representation.

• Scope and interpretation of the claim.

The definition of $N^*$ uses a deterministic worst-case sample cap, permits internal randomness, and permits early stopping. This matches the stated prediction problem. Padding a stopped execution with unused independent samples is valid for the lower bounds.

For $m\ge3$, the output establishes the minimum sample complexity up to universal constant factors, rather than an exact integer minimum. Its use of $\Theta$ makes this distinction explicit. For $m=2$, it supplies an exact integer characterization.

The lower-bound societies have finite support with positive rational masses. The task does not impose a fixed upper bound on $\tau$ or $L$, so their support sizes and encoding lengths do not invalidate the constructions.

• Lemma 1: the exact continuous margin.

The total-variation inequality is applicable because $A_w-A_c$ takes values in $[-1,1]$. Whenever a different candidate wins under $\nu$, that candidate’s score is at least $w$’s score, including when the outcome changes through a tie. Thus the lower bound applies under the prescribed priority order.

For the upper bound, $a-b=d$ implies that the source class contains enough mass to transfer $d/2+\eta$ for sufficiently small positive $\eta$. A ranking approving $c$ and rejecting $w$ exists for every $1\le k<m$. The transfer changes the score difference by exactly twice the transferred mass, making $c$ strictly outscore $w$.

The zero-gap case is also handled: mixing with such a ranking makes the tied rival strictly outscore $w$ at arbitrarily small total variation. The use of an infimum therefore resolves the possible distinction between attaining a tie and changing the winner.

Consequently,
$$ \mathrm{MOV}_\infty(\mu)=\frac12\min_{c\ne w}(s_w-s_c) $$
is justified, and the promise implies a unique population winner.

• Feasibility and zero samples.

Summing the score-gap inequalities and using $\sum_c s_c=k$ and $s_w\le1$ gives the stated necessary upper limit on $\epsilon$.

The proposed construction attains that limit: its winner has score $1$, while every rival has score $(k-1)/(m-1)$. Its masses are positive rationals, including the deterministic case $k=1$.

The construction is available with every candidate as winner. Hence a zero-sample algorithm cannot succeed uniformly with probability greater than $1/2$. This validates both the positive lower bound on every nonempty promise class and the separately stated vacuous convention for an empty class.

• Section 2: general upper bounds.

The Bernoulli concentration argument is valid throughout its stated range. The exponential remainder inequalities hold for $0\le\lambda\le1/2$. The convexity bound involving $p$ is valid, and the condition $nt^2\ge2\log2$ ensures that the denominator used in Markov’s inequality has the stated lower bound.

Summing the resulting candidate bounds uses $\sum_c s_c=k$, so it introduces $k$, rather than $m$, into the logarithm. Strict deviations below $\epsilon$ preserve every winner–rival gap. The chosen sample budget satisfies the concentration argument’s side condition.

In the rejection argument, $q_w\le\beta$ follows because the winner minimizes rejection probability. The optimized exponential bound correctly handles both $b>0$ and the limiting case $b=0$. The subsequent inequalities give
$$ (\sqrt a-\sqrt b)^2\ge\frac{\epsilon^2}{2\beta}. $$
The required condition $\epsilon\le\beta$ follows from the feasibility bound for all $m\ge2$.

Finally, the split at $k=m/2$ correctly converts the two explicit upper bounds into the uniform bound
$$ O\!\left(\beta\epsilon^{-2}\Lambda\right). $$

• Section 3: small-margin lower bound.

The active-set size satisfies $M\ge3$ and $M\ge k+1$. The displayed case analysis establishes $\lambda\le1/2$, so all constructed masses are positive. Normalization follows from $\mathbb E_U(I_i-u)=0$.

The inclusion covariance calculation is correct. Substitution gives the stated scores and an active winner–rival gap of exactly $2\epsilon$. The bounds $u\ge1/3$ and $2\epsilon\le1/8$ ensure that inactive candidates do not determine a smaller margin.

The relative-entropy bounds are valid. The reference distribution has positive mass on every approval set in the common support, and $P_j\ge U/2$ justifies the pairwise denominator bound. The uniform estimate $V\ge\beta/5$ holds in all three parameter cases. The constants $20$ and $80$ are consistent with the preceding calculations.

The information argument applies to randomized algorithms because their internal randomness is independent of the unknown index. Under the product of the index and prediction marginals, the equality event has probability $1/M$, regardless of the prediction marginal. The binary relative-entropy lower bound therefore applies as written.

The numerical estimate
$$ \operatorname{kl}(1/2\|1/M)\ge\frac1{64}\log M $$
holds for both stated ranges of $M$.

For the confidence lower bound, the selected event has probabilities at least $1-\delta$ and at most $\delta$ under the two societies. The relative-entropy comparison and the constant $\frac14$ are valid for $\delta\le1/4$. For larger $\delta$, the bounded confidence logarithm is absorbed by $\log(k+1)$.

These arguments establish the complete first branch with universal constants.

• Lemma 2: the boundary family.

The intersection upper bound correctly counts each rival’s survival probability as $h^n$.

The deterministic completion of approval sets provides a common ranking representation across the family. Thus observing the complete rankings does not invalidate the posterior calculation: each compatible winner index has the same likelihood.

The posterior is uniform on the intersection, giving Bayes error $\mathbb E[X/(1+X)]$. The joint-approval probability $h_2$, its comparison with $h^2$, and the second-moment estimate are correct. The stated Cauchy–Schwarz application yields
$$ \mathbb E\frac{X}{1+X}\ge\frac{z}{z+2}. $$

The conversion from this bound to the claimed rate handles the potentially delicate regime $\delta$ approaching $1/2$. The separate treatment of $k=2,3$ is valid, and the logarithmic comparison for $k\ge4$ holds already at $k=4$. The confidence argument covers $\delta\le1/4$, with the remaining range absorbed as claimed.

• Section 5: large-margin lower bounds.

For $k\ge2$, feasibility ensures that the selected integer $M$ lies between $k+1$ and $m$. The boundary family then has margin at least $\epsilon$, including against inactive candidates.

The ceiling estimate for $a_M$ is correct. The displayed algebraic identity verifies
$$ (m-k)(k-1)\ge m-2. $$
Together with the large-margin assumption, this establishes $a_M\le25a$. Applying Lemma 2 therefore gives the required lower bound without a parameter-dependent implicit constant.

For $k=1$, the two societies have the asserted margin. Their affinity is $\sqrt{1-g^2}$, and the total-variation comparison and product-affinity calculation give the stated testing lower bound. The inequality $b\le a$ has the correct direction. The separate treatments of small $\delta$, larger $\delta$, and $g=1$ cover the entire allowed range.

• Section 6: large-margin upper bound.

For $\epsilon\le3/8$, the estimates on $a$ and $\beta$ correctly imply
$$ \frac{\beta}{\epsilon^2}\le\frac{128}{a}. $$
Thus the general upper bound has the required order.

For $\epsilon>3/8$, the score-gap promise implies $s_w\ge1-t$ and $s_c\le t$ for every rival. The winner-tail bound is valid. The rival-tail argument correctly uses convexity to retain a factor proportional to the rival’s approval probability, allowing summation through $\sum_c s_c=k$.

The derivative calculation proving $H(t)\ge a/16$ is correct, as is the endpoint comparison at $t=1/4$. The chosen budget controls the failure probability and satisfies the additional Markov-bound condition.

The endpoint $\epsilon=1/2$ is correctly isolated: feasibility forces $k=1$, and the promised winner appears first in every sample.

• Section 7: exact binary characterization.

For the two endpoint societies, the likelihood-ratio decision is majority with fair randomization on an observed tie. Its errors under the endpoints are equal, so its average error supplies a worst-case lower bound for every algorithm.

The coupling argument establishes the required monotonicity over each side of the promise class. Thus the same rule attains that lower bound uniformly, proving the stated exact minimum.

Randomizing a prediction when the sample counts tie is permitted by the task. It does not alter the fixed priority order defining the population winner, which is unique under the promise. The deterministic endpoint case is also handled correctly.

• Section 8: computation and representation.

The streaming time and memory bounds account for reading complete rankings and maintaining counters. Excluding the sampling oracle’s implementation is appropriate because the algorithm receives samples and does not receive the hidden support.

The additional lengths $b_\epsilon$ and $b_\delta$ are correctly distinguished from $L$. Exact rational parameters can have long encodings without large $\epsilon^{-1}$ or $\log(1/\delta)$, so this qualification is necessary for complete bit-complexity accounting.

The integer-log replacements preserve the upper bounds. In the high-margin case, $J\ge2$, and the proposed integer budget dominates the sufficient budget from Section 6.

For the binary case, the stated exponential bound guarantees termination by $B$. Exact binomial recurrence calculations have polynomial bit cost in the listed quantities; the conservative arithmetic bound is consistent with that computation.

• Section 9 and the cited context.

The maximum-margin specialization follows from the large-margin branch. The veto specialization is valid throughout the feasible range, including its endpoint.

The contextual attribution is accurate: the paper states the earlier upper bound, and the author’s page states the restriction on the discrete lower-bound proof. Neither external result is needed to complete the output’s direct arguments. [Primary source](https://arxiv.org/pdf/1502.04354v3), [author’s erratum](https://asiaccs2026.cse.iitkgp.ac.in/~palash/).

No corrective feedback is required. The write-up settles the distributional sample-complexity question to the precision it claims and supplies polynomial-time prediction algorithms with explicit encoding qualifications.

⟨structured verdict parsed — rendered above⟩