Answer: —
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any m ≥t > k, with probability at least 1 −δ, Algorithm 2 returns a committee that satisfies α-EJR and α-OAS after querying no more than 578Hk m −k t −k αk2 (1 −α)k + 1 3 log 4mk4 δ voters. For any fixed δ > 0, if α = 1, this leads to a query complexity of O mk6 log k log m , and if α < 1, this leads to a query complextiy of O mk3 log k log m .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates C, committee size k, query limit t, accuracy parameters alpha and delta, and a hidden society distribution mu over approval types A subset of C, adaptively choose query sets Q of size at most t, observe independent samples A intersect Q from mu, and output a k-member committee satisfying alpha-EJR with probability at least 1-delta while minimizing the worst-case number of samples.
Let \(C\) contain \(m\) candidates, with integers \(1\le k<t\le m\), binary rationals \(0<\alpha\le1\) and \(0<\delta<1\), and a binary-encoded sample budget \(B\ge0\).
A society is represented by its support: the list of its \(\tau\) approval types \(A\subseteq C\) with positive binary-rational masses \(\mu(A)\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible approval types; empty approval sets are allowed.
The society description is hidden from the querying strategy. Public parameters \(\tau\) and \(L\) specify the support size and an upper bound on its description length; assume this class of societies is nonempty.
Each query chooses \(Q\subseteq C\), with \(|Q|\le t\), and observes only \(A\cap Q\) for a fresh independent draw \(A\sim\mu\). Queries and the final committee may be randomized and depend on previous responses.
A group consists of real submasses \(0\le g_A\le\mu(A)\). A committee \(W\subseteq C\), with \(|W|=k\), satisfies \(\alpha\)-EJR if, for every integer \(1\le\ell\le k\) and every group with \(\sum_A g_A\ge\ell/(\alpha k)\) and \(\left|\bigcap_{A:g_A>0}A\right|\ge\ell\), some type with \(g_A>0\) satisfies \(|A\cap W|\ge\ell\).
Let \(N^*\) be the smallest sample cap for which one strategy, knowing only the public parameters, outputs an \(\alpha\)-EJR committee with probability at least \(1-\delta\) for every admissible hidden society. The cap applies to every execution, including unsuccessful executions.
Is deciding whether \(N^*\le B\) solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,k,t,\log(B+1)\) and the bit lengths of \(\alpha,\delta\).
For finite electorates, an adaptive algorithm achieves \(\alpha\)-EJR using \(O\!\left(\left\lceil(m-k)/(t-k)\right\rceil k^6\log(k+1)\log(mk/\delta)\right)\) samples; its noisy-query model explicitly includes population-distribution sampling. [Verified bound and model](https://daniel-halpern.com/files/representation-journal.pdf).
For complete sampled ballots, population JR requires \(\Omega(k^3)\) samples on some instances. These bounds do not determine the complexity of deciding the exact minimum sample cap. [Verified lower bound](https://arxiv.org/html/2606.10446v1).
The general polynomial-time-versus-NP-hardness classification remains unresolved. I establish several additional structural results and an exact polynomial-time solution for a nontrivial regime with arbitrary support size:
Write $b_\alpha,b_\delta$ for the bit lengths of $\alpha,\delta$.
As in the notes, I use an explicit encoding in which approval sets have $m$-bit incidence vectors and rational masses have a fixed canonical binary numerator–denominator encoding. In particular, changing approval sets while retaining the number of types and the mass vector does not change the description length. The structural results for individual societies do not depend on this convention; the public-class symmetry and admissibility arguments use it.
Put $s=\alpha k$. For a committee $W$, an integer $\ell$, and an $\ell$-element set $S$, define
$$
M_\mu(S,W,\ell)
=
\sum_{\substack{A\supseteq S\\ |A\cap W|<\ell}}\mu(A).
$$
Lemma 1. A committee $W$ violates $\alpha$-EJR if and only if, for some $1\le\ell\le k$ and some $\ell$-element set $S$,
$$
M_\mu(S,W,\ell)\ge\frac{\ell}{s}.
$$
Proof. Suppose a group witnesses a violation. Its mass is positive, so its participating types form a nonempty collection. Choose an $\ell$-element subset $S$ of their common intersection. Every participating type contains $S$ and approves fewer than $\ell$ members of $W$. Since $g_A\le\mu(A)$,
$$
M_\mu(S,W,\ell)\ge\sum_A g_A\ge\frac{\ell}{s}.
$$
Conversely, suppose the displayed inequality holds. Assign full mass to every type counted in $M_\mu(S,W,\ell)$ and zero mass elsewhere. The positive threshold ensures that some type participates. This group has sufficient mass, its common intersection contains $S$, and none of its participating types approves $\ell$ elected candidates. It therefore witnesses a violation. $\square$
This gives an exact verification algorithm in
$$
2^m\operatorname{poly}(m,\tau,L,k,b_\alpha)
$$
bit operations.
If $s<1$, every threshold exceeds the society’s total mass. Hence every committee is valid and $N^*=0$. Below, assume $s\ge1$ and put
$$
r=\lfloor s\rfloor.
$$
For this section, call a set $T$, possibly smaller than $k$, valid for the prescribed thresholds if it satisfies the representation condition in the task with the thresholds $\ell/s$ and utilities $|A\cap T|$.
Theorem 2. Every society has a set $T$ with $|T|\le r$ that is valid for the prescribed thresholds. Consequently, every size-$k$ committee containing $T$ satisfies $\alpha$-EJR.
Proof. Start with all support types remaining and $T=\varnothing$. Process the integers $\ell=r,r-1,\ldots,1$ in descending order.
At level $\ell$, while there is an $\ell$-element set $S$ such that the total mass of remaining types containing $S$ is at least $\ell/s$:
Every selection removes positive mass, so there are at most $\tau$ selections.
Suppose the selected levels, with repetitions, are $\ell_1,\ldots,\ell_q$. Their removed collections of types are disjoint, and selection $i$ removes mass at least $\ell_i/s$. Therefore
$$
\frac{\ell_1+\cdots+\ell_q}{s}\le1.
$$
The numerator is an integer, giving
$$
|T|\le\ell_1+\cdots+\ell_q\le\lfloor s\rfloor=r.
$$
It remains to prove validity. Suppose, to the contrary, that a group witnesses a violation at level $\ell$ for the final set $T$. Necessarily $\ell\le r$, since otherwise $\ell/s>1$.
No participating type could have been removed at a level $j\ge\ell$. Such a removed type contains the selected $j$-element set, which remains in $T$, and would approve at least $j\ge\ell$ candidates of $T$, contradicting the alleged violation.
Thus all participating types remain after processing level $\ell$. Choose an $\ell$-element subset $S$ of their common intersection. The remaining types containing $S$ have total mass at least
$$
\sum_A g_A\ge\frac{\ell}{s}.
$$
This contradicts termination of the selection loop at level $\ell$. Hence $T$ is valid.
Finally, adding elected candidates cannot decrease any type’s utility. Every size-$k$ completion of $T$ is therefore valid. $\square$
This is an existence result; the proof does not claim that finding such a core is polynomial-time.
Let $\mathcal G_\mu$ denote the set of valid size-$k$ committees. The theorem gives
$$
|\mathcal G_\mu|
\ge
\binom{m-r}{k-r}.
$$
Indeed, a core of size $a\le r$ has $\binom{m-a}{k-a}$ completions, and this quantity decreases with $a$ because, for $a<k$,
$$
\frac{\binom{m-a-1}{k-a-1}}{\binom{m-a}{k-a}}
=
\frac{k-a}{m-a}<1.
$$
Let $\mathcal H$ be the admissible public class, and let $V_0$ be the optimal worst-case success probability using no queries.
Proposition 3. Under the stated encoding convention,
$$
V_0
=
\min_{\mu\in\mathcal H}
\frac{|\mathcal G_\mu|}{\binom{m}{k}}.
$$
Thus a uniformly random size-$k$ committee is optimal without samples.
Proof. Uniform selection succeeds on society $\mu$ with probability $|\mathcal G_\mu|/\binom{m}{k}$.
For the reverse inequality, fix any output distribution over committees and any admissible society $\mu$. Every candidate permutation of $\mu$ remains admissible. Average the strategy’s success probability over a uniformly random permutation. For every fixed output committee, its inverse image is uniform among all size-$k$ committees. The average success probability is therefore
$$
\frac{|\mathcal G_\mu|}{\binom{m}{k}},
$$
regardless of the strategy’s output distribution. At least one permuted society has success probability no greater than this average. Taking the minimum over $\mu$ proves the claim. $\square$
In particular, Theorem 2 gives the universal guarantee
$$
V_0\ge
\rho_r
:=
\frac{\binom{m-r}{k-r}}{\binom{m}{k}}
=
\frac{\binom{k}{r}}{\binom{m}{r}}.
$$
Consequently,
$$
\rho_r\ge1-\delta
\quad\Longrightarrow\quad
N^*=0
$$
for every admissible support size and description-length bound.
The next sections characterize equality when $s=r$ is an integer.
Assume throughout this section that
$$
s=\alpha k=r\in\{1,\ldots,k\}.
$$
A candidate is approved somewhere if its total approval mass is positive.
Lemma 4. Let $D$ be a set of
$$
|D|=k-r+1
$$
candidates containing at least one candidate approved somewhere. Then some $\alpha$-EJR committee contains $D$.
Proof. Define the harmonic numbers and weighted potential by
$$
H_0=0,\qquad
H_j=\sum_{i=1}^j\frac1i,\qquad
F_\mu(W)=\sum_A\mu(A)H_{|A\cap W|}.
$$
Choose a size-$k$ committee $W\supseteq D$ maximizing $F_\mu$ among all such committees. A maximizer exists because the feasible collection is finite.
Suppose $W$ violates $\alpha$-EJR at level $\ell$. A witnessing group has a common candidate $z\notin W$: otherwise its common intersection would supply $\ell$ elected candidates to every participating type.
Write
$$
a=F_\mu(W\cup\{z\})-F_\mu(W).
$$
For every participating type, $|A\cap W|<\ell$, and adding $z$ contributes at least $1/\ell$. Hence
$$
a
\ge
\sum_A\frac{g_A}{|A\cap W|+1}
\ge
\frac{\sum_Ag_A}{\ell}
\ge\frac1r.
$$
For $y\in W$, define the swap gain and removal loss
$$
d_y
=
F_\mu((W\setminus\{y\})\cup\{z\})-F_\mu(W),
$$
$$
\lambda_y
=
F_\mu(W\cup\{z\})
-
F_\mu((W\cup\{z\})\setminus\{y\}).
$$
Then
$$
d_y=a-\lambda_y,
\qquad
\lambda_y
=
\sum_{A:y\in A}
\frac{\mu(A)}{|A\cap(W\cup\{z\})|}.
$$
Thus $\lambda_y\ge0$, with strict inequality whenever $y$ is approved somewhere.
Let
$$
c=\mu\bigl(\{A:A\cap(W\cup\{z\})\ne\varnothing\}\bigr)\le1.
$$
A type-by-type calculation gives
$$
\sum_{y\in W}d_y=(k+1)a-c.
$$
To verify it, put $v=|A\cap W|$. If $z\in A$, the sum of the type’s swap contributions is $(k-v)/(v+1)$. If $z\notin A$ and $v>0$, it is $-1$. If neither $z$ nor any member of $W$ is approved, it is zero. These are exactly the contributions to the displayed identity.
Subtracting the gains for removals in $D$ yields
$$
\begin{aligned}
\sum_{y\in W\setminus D}d_y
&=(k+1-|D|)a-c+\sum_{y\in D}\lambda_y\\
&=ra-c+\sum_{y\in D}\lambda_y\\
&\ge\sum_{y\in D}\lambda_y\\
&>0.
\end{aligned}
$$
The last inequality follows because $D$ contains a candidate approved somewhere.
Every swap in this sum retains $D$, so maximality of $W$ requires every summand to be nonpositive. This contradicts the strict positive sum. The argument also covers $r=1$, when the sum is empty and the resulting contradiction is immediate. $\square$
For $\alpha=1$, the lemma says that every candidate approved somewhere belongs to some EJR committee.
Theorem 5. Suppose $s=\alpha k=r$ is an integer. Then
$$
|\mathcal G_\mu|=\binom{m-r}{k-r}
$$
if and only if the support consists of pairwise disjoint, nonempty approval sets whose union $T$ has size $r$, with
$$
\mu(A)=\frac{|A|}{r}
$$
for every support type.
For such a society, the valid committees are exactly the size-$k$ committees containing $T$.
Proof.
By Theorem 2, some core $T$ has size at most $r$. If its size were smaller than $r$, its completions alone would exceed $\binom{m-r}{k-r}$, by the strict inequality established in Section 2. Therefore $|T|=r$.
Every completion of $T$ is valid. Since their number already equals $|\mathcal G_\mu|$, the valid committees are exactly those containing $T$.
First, no candidate outside $T$ is approved anywhere. If such a candidate $x$ existed, choose
$$
D\subseteq C\setminus T,\qquad
|D|=k-r+1,\qquad x\in D.
$$
This is possible because $m>k$. Lemma 4 supplies a valid committee containing $D$. It cannot also contain $T$, since
$$
|D|+|T|=k+1.
$$
This contradicts the characterization of the valid committees. Thus every support type is a subset of $T$.
Fix $y\in T$, and choose a $(k-r+1)$-element set $D\subseteq C\setminus T$. The committee
$$
W_y=(T\setminus\{y\})\cup D
$$
does not contain $T$, so it is invalid.
By Lemma 1, some level $\ell$ and some $\ell$-element set $S$ satisfy
$$
\sum_{\substack{A\supseteq S\\|A\cap W_y|<\ell}}\mu(A)
\ge\frac{\ell}{r}.
$$
Every counted type is contained in $T$ and has $|A|\ge\ell$. Moreover,
$$
|A\cap W_y|=|A|-\mathbf 1_{\{y\in A\}}<\ell.
$$
These inequalities force $y\in A$ and $|A|=\ell$. Since $A\supseteq S$ and $|S|=\ell$, necessarily $A=S$. Thus a single support type containing $y$ satisfies
$$
\mu(A)\ge\frac{|A|}{r}.
$$
Let $\mathcal F$ be the collection of nonempty support types satisfying this inequality. The preceding argument shows that their union is $T$. Consequently,
$$
1
\ge
\sum_{A\in\mathcal F}\mu(A)
\ge
\frac1r\sum_{A\in\mathcal F}|A|
\ge
\frac{|T|}{r}
=1.
$$
Every inequality is an equality. It follows that:
This proves necessity.
Suppose the support has the stated form. A type $A$ of size $a$ has mass $a/r$. Taking its entire mass gives an eligible group at level $\ell=a$. Since this group contains only type $A$, any valid committee must contain all of $A$.
Therefore every valid committee contains the union $T$.
Conversely, a committee containing $T$ contains every support approval set. For any eligible group at level $\ell$, every participating type contains the group’s $\ell$ common candidates and therefore approves at least $\ell$ elected candidates. Such a committee is valid.
The valid committees are precisely the completions of $T$, numbering $\binom{m-r}{k-r}$. $\square$
A useful special case is the following.
Corollary 6. A society has exactly one $\alpha$-EJR committee if and only if $\alpha=1$ and its support consists of disjoint nonempty approval sets partitioning $k$ candidates, each having mass $|A|/k$.
Proof. If $\alpha<1$, then $r\le k-1$, and Theorem 2 supplies at least
$$
\binom{m-r}{k-r}>1
$$
valid committees. For $\alpha=1$, apply Theorem 5 with $r=k$. $\square$
In particular, a society with a unique valid committee necessarily has $\tau\le k$.
Theorem 5 reduces admissibility of an extremal society to a small integer optimization problem.
Let $h(m,\tau)$ be the fixed description cost of the headers and $\tau$ incidence vectors. Let $c_r(a)$ be the encoded mass cost of the reduced rational $a/r$, for $1\le a\le r$. These costs are computable in polynomial time in $\log(r+1)$ under the stated encoding.
An extremal society with $\tau$ types exists within length $L$ exactly when there are positive integers
$$
a_1+\cdots+a_\tau=r
$$
such that
$$
h(m,\tau)+\sum_{i=1}^{\tau}c_r(a_i)\le L.
$$
The approval sets can then be chosen as disjoint blocks of these sizes.
Define
$$
D(0,0)=0,
$$
with all other initially impossible states having value $+\infty$, and use the recurrence
$$
D(i,j)
=
\min_{1\le a\le j}
\bigl(D(i-1,j-a)+c_r(a)\bigr).
$$
Then admissibility is equivalent to
$$
h(m,\tau)+D(\tau,r)\le L.
$$
If $\tau>r$, it is impossible immediately.
There are at most $(\tau+1)(r+1)$ states and at most $r$ transitions per state. Thus this test uses
$$
O(\tau r^2)
$$
transitions and polynomial bit cost per transition. Including rational comparisons and binomial computations, its running time is
$$
\operatorname{poly}
\bigl(m,\tau,L,k,b_\alpha,b_\delta,\log(B+1)\bigr).
$$
When $s=r$ is an integer:
$$ V_0=\rho_r. $$
$$ V_0\ge \frac{\binom{m-r}{k-r}+1}{\binom{m}{k}}. $$
Thus sharpness of the universal zero-sample bound is polynomial-time decidable. In the sharp case, the decision for $B=0$ is exactly the rational comparison $\rho_r\ge1-\delta$.
For nonintegral $s$, the same disjoint-block construction, with masses $a_i/r$, still attains $\rho_r$ whenever admissible: each block of size $a_i$ has mass at least $a_i/s$ and therefore forces inclusion of the entire block. The necessity direction above is proved only for integral $s$.
This regime admits additional exact results.
Let
$$
I_\mu=\bigcap_{A:\mu(A)>0}A,
\qquad
U_\mu=\bigcup_{A:\mu(A)>0}A.
$$
Lemma 7. When $\alpha k=1$:
$$ W\cap U_\mu\ne\varnothing. $$
Proof. Levels $\ell\ge2$ have thresholds exceeding one and impose no requirement. At level one, a group must have mass at least one. Since $g_A\le\mu(A)$ and the masses sum to one, necessarily $g_A=\mu(A)$ for every support type.
Thus the only potentially eligible group is the entire society. It is cohesive precisely when $I_\mu\ne\varnothing$. Its representation condition requires at least one support type to approve an elected candidate, which is equivalent to $W\cap U_\mu\ne\varnothing$. $\square$
Notice that representation here depends on hitting the union, once the common intersection is nonempty.
Theorem 8. Suppose $\alpha k=1$. If
$$
\tau>2^{m-1},
$$
then $V_0=1$. Otherwise, put
$$
u=1+\lceil\log_2\tau\rceil.
$$
Then
$$
V_0
=
1-\frac{\binom{m-u}{k}}{\binom{m}{k}},
$$
where a binomial coefficient is zero when its lower argument exceeds its nonnegative upper argument.
Proof. If $I_\mu\ne\varnothing$, choose $x\in I_\mu$. Every support type contains $x$. If the union has size $v$, there are at most $2^{v-1}$ distinct subsets of the union containing $x$. Therefore
$$
\tau\le2^{v-1},
\qquad
v\ge1+\lceil\log_2\tau\rceil=u.
$$
If $\tau>2^{m-1}$, a nonempty common intersection is impossible, so Lemma 7 makes every committee valid.
Otherwise, for a society with nonempty common intersection and union size $v$, Lemma 7 gives
$$
|\mathcal G_\mu|
=
\binom{m}{k}-\binom{m-v}{k}.
$$
This is minimized when $v$ is as small as possible, namely $u$.
Such a society is admissible under the encoding convention. Choose a $u$-element universe containing $x$, and choose $\tau$ distinct subsets containing $x$. They can be chosen to have union equal to that universe. Indeed, for $u\ge2$,
$$
\tau>2^{u-2},
$$
so a collection of $\tau$ such subsets cannot omit any of the other $u-1$ candidates; omitting one would leave only $2^{u-2}$ possibilities. For $u=1$, necessarily $\tau=1$, and choose the singleton.
Take the mass vector from any admissible society, whose existence is assumed, and assign it to these new approval types. The mass validity and total description length are preserved.
This constructs an admissible society attaining the minimum count. Proposition 3 proves the formula. $\square$
In particular, every committee is valid for every admissible society whenever
$$
\tau>2^{m-k-1}.
$$
This follows from the formula when $\tau\le2^{m-1}$, because then $u>m-k$, and from the first case otherwise.
The formula is computable in
$$
O(m^3)+
\operatorname{poly}
\bigl(\tau,L,k,b_\alpha,b_\delta,\log(B+1)\bigr)
$$
bit operations, using a Pascal table for the binomial coefficients.
Proposition 9. When $\alpha k=1$, every capped adaptive strategy can be replaced, without reducing its success probability on any society, by a strategy that chooses all queries before receiving responses.
Proof. Whenever a response contains an approved candidate, output a committee containing that candidate. By Lemma 7, this committee is valid for every possible underlying society.
Replacing the original strategy’s behavior after its first nonempty response by this rule cannot decrease success.
Fix the strategy’s internal randomness. Along the hypothetical sequence in which every response is empty, its queries form a fixed list
$$
Q_1,\ldots,Q_B,
$$
after padding with empty queries if necessary, and its final output is a fixed committee $W$.
Choose this list and $W$ in advance. If any actual response is nonempty, output a committee containing an observed approved candidate; otherwise output $W$. Up to the first nonempty response, this reproduces the modified adaptive strategy. After that response, it succeeds. Averaging over internal randomness proves the claim. $\square$
For a fixed plan $(Q_1,\ldots,Q_B,W)$ and a society with $I_\mu\ne\varnothing$, its failure probability is exactly
$$
\mathbf 1_{\{W\cap U_\mu=\varnothing\}}
\prod_{j=1}^{B}
\left(
\sum_{A:A\cap Q_j=\varnothing}\mu(A)
\right).
$$
The product is justified by fresh independent population draws. For societies with $I_\mu=\varnothing$, failure probability is zero.
This formula reduces the remaining optimization to distributions over fixed query plans, but does not establish a polynomial-time algorithm for that optimization.
Put
$$
J=\left\lceil\frac{m-k}{t}\right\rceil.
$$
Proposition 10. When $\alpha k=1$, a deterministic strategy using at most $J$ samples always succeeds.
Proof. Partition $m-k$ candidates into $J$ disjoint query sets of size at most $t$. If any response is nonempty, elect an observed approved candidate and complete the committee arbitrarily.
If every response is empty, output the $k$ unqueried candidates.
If $I_\mu=\varnothing$, every output is valid. Otherwise, every common candidate belongs to every drawn approval set, so an empty response proves that none of those common candidates belongs to its query set. After all empty responses, the nonempty set $I_\mu$ lies among the $k$ unqueried candidates. The output therefore intersects $U_\mu$ and is valid by Lemma 7. $\square$
When $t\ge m-k$, this cap is one. Combining it with Theorem 8 gives the exact answer:
$$
N^*
=
\begin{cases}
0,&V_0\ge1-\delta,\\
1,&V_0<1-\delta.
\end{cases}
$$
Thus, for arbitrary $\tau$ and $L$, deciding $N^*\le B$ is polynomial-time solvable whenever $\alpha k=1$ and $t\ge m-k$. Its running time is polynomial in
$$
m,\tau,L,k,t,\log(B+1),b_\alpha,b_\delta.
$$
For example, with $m=6$, $k=2$, $\alpha=1/2$, $\tau=3$, and $t=4$, Theorem 8 gives
$$
V_0
=
1-\frac{\binom32}{\binom62}
=
\frac45.
$$
Hence $N^*=0$ when $\delta\ge1/5$, and $N^*=1$ when $\delta<1/5$.
The fixed-plan characterization also gives an exact algorithm for all parameters with $\alpha k=1$.
If $B\ge J$, answer yes. Otherwise, $B<J\le m$. Enumerate all admissible descriptions of length at most $L$ and all fixed plans. There are fewer than $2^{L+1}$ descriptions and at most
$$
2^{m(B+1)}
$$
plans, since there are at most $2^m$ legal query sets and at most $2^m$ committees.
Introduce one nonnegative variable per plan, require their sum to be one, and for each admissible society require the weighted sum of the failure probabilities above to be at most $\delta$.
Proposition 9 proves equivalence between feasibility of this program and $N^*\le B$. All coefficients are rational, with bit lengths polynomial in $BL$. The standard exact rational linear-program feasibility theorem applies: an explicitly represented rational system is decidable in time polynomial in its complete binary encoding length.
The resulting running time is
$$
2^{O(L+m(B+1))}
\operatorname{poly}
\bigl(m,\tau,L,k,t,B,b_\alpha,b_\delta,\log(B+1)\bigr).
$$
Since this branch has $B<J$, it is bounded in the requested parameters by
$$
2^{O(L+mJ)}
\operatorname{poly}
\bigl(m,\tau,L,k,t,b_\alpha,b_\delta,\log(B+1)\bigr).
$$
This is an upper bound, not a hardness result.
For completeness, the following restates and proves the one-support result with the conditional-probability domain repaired.
Assume $\tau=1$. The sole approval type $A$ has mass one. Directly from the definition, validity is equivalent to
$$
|A\cap W|\ge\min(r,|A|),
\qquad r=\lfloor\alpha k\rfloor.
$$
Indeed, an eligible group exists at level $\ell$ precisely when $\ell\le|A|$ and $\ell\le\alpha k$.
The case $r=0$ is vacuous. Suppose $r\ge1$, and define
$$
b=\min(Bt,m),\qquad u=m-b,
$$
$$
\mathcal A
=
\{a\in\mathbb Z:0\le a\le r,\ a\le b,\ r-a\le u\}.
$$
Theorem 11. The optimal worst-case success probability is
$$
V_B
=
\frac1{\binom mr}
\sum_{a\in\mathcal A}
\binom ba
\binom{\min(k-a,u)}{r-a}.
$$
Therefore
$$
N^*\le B
\quad\Longleftrightarrow\quad
V_B\ge1-\delta.
$$
Proof of the upper bound. Choose $A$ uniformly among the $r$-element approval sets, all of which are admissible under the encoding convention.
Responses are deterministic membership information. Repeated tests can be replaced by fresh candidate tests while retaining the original information, and unused query capacity can be filled. Thus, for an upper bound, allow the strategy to test exactly $b$ distinct candidates.
Conditional on any positive-probability history, the untested approvals are uniform among the untested candidates. Adaptive choices do not disturb this property: each new candidate is chosen using only previously revealed memberships. Consequently, the number $a$ of tested approvals has distribution
$$
\Pr(a)
=
\frac{\binom ba\binom u{r-a}}{\binom mr},
\qquad a\in\mathcal A.
$$
For an approval set of size $r$, success requires including all approvals. After observing $a$, the committee must include those $a$ known approvals and can select at most $\min(k-a,u)$ untested candidates. Its conditional success probability is therefore at most
$$
\frac{\binom{\min(k-a,u)}{r-a}}{\binom u{r-a}},
\qquad a\in\mathcal A.
$$
Every denominator here is positive by the definition of $\mathcal A$. Impossible observations are omitted entirely.
Averaging gives $V_B$. This bounds the worst-case success of every strategy by its average success under the chosen prior.
Proof of attainment. Choose a uniform random ordering of the candidates and query its first $b$ positions in batches of at most $t$.
If at least $k$ approvals are observed, output $k$ of them. Otherwise, include all observed approvals, fill the remaining places with the earliest unqueried candidates, and, if needed, use observed disapproved candidates to complete the committee.
For every $r$-element approval set, the preceding hypergeometric calculation gives success probability exactly $V_B$.
Fix an ordering. Adding an unqueried approval cannot decrease the number of elected approvals. Adding a queried approval also cannot decrease it: below $k$ observed approvals, it adds one known elected approval and shortens the unqueried filler prefix by at most one; at or above $k$, the elected approval count is already $k$.
Thus, for $|A|\ge r$, choose an $r$-element subset $T\subseteq A$. Success on $T$ implies success on $A$ for every ordering.
If $|A|<r$, choose an $r$-element superset $T\supseteq A$. Success on $T$ includes all of $T$. Every queried member of $A$ is elected when running on $A$. If $T$ has unqueried members, its observed approval count is below $k$, and the filler prefix used on $A$ is at least as long as the one used on $T$. Hence every unqueried member of $A$ is also elected. If all of $T$ was queried, this last assertion is vacuous.
Therefore success on $T$ implies success on $A$ in this case as well. Every approval set consequently has success probability at least $V_B$, proving attainment. $\square$
A Pascal table computes all needed binomial coefficients in $O(m^3)$ bit operations. Computing $b$ requires binary multiplication and comparison, rather than iterating $B$ times. The decision is polynomial in
$$
m,L,k,t,\log(B+1),b_\alpha,b_\delta.
$$
The missing general result is still either a polynomial-time algorithm for the public-parameter decision problem or a valid hardness reduction whose output contains only those public parameters.
In particular, hardness of finding or verifying committees for an explicitly supplied society does not supply such a reduction: the society is hidden and universally quantified here.
The supplied [sampling upper bound](https://daniel-halpern.com/files/representation-journal.pdf) and [population sampling lower bound](https://arxiv.org/html/2606.10446v1) concern information requirements. The results above resolve additional exact regimes and constrain possible extremal societies, but do not classify the full decision problem.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial special-case results, but it does not resolve the general decision problem in USER_TASK. Its explicit claim of partial progress is accurate. I found no false mathematical step in the structural results or exact formulas. The principal remaining issue is the missing general complexity classification; a secondary issue is the dependence of several results on an encoding convention that the task does not specify.
The prover explicitly assumes fixed-length incidence vectors for approval sets and a canonical numerator–denominator encoding for masses.
This assumption is essential to several arguments: candidate permutations and replacement of approval sets must preserve admissibility under the description-length bound $L$. The task specifies binary-rational masses but does not explicitly prescribe the approval-set encoding.
Minor issue. The public-class conclusions are conditional on the stated encoding convention. This is a natural, explicitly stated completion of an underspecified aspect of the task, but the conclusions should retain that qualification. To make the description-length tests fully reproducible, the prover should specify the header and rational encoding used to define $h(m,\tau)$ and $c_r(a)$.
The results concerning an individual society do not require this convention.
Both implications are correct.
A violating group has positive total mass, so its participating support is nonempty. Selecting an $\ell$-element subset of its common intersection produces the required $S$. Every participating type is included in the defining sum for $M_\mu(S,W,\ell)$.
Conversely, assigning full mass to the counted types gives a legitimate group. The positive threshold ensures nonempty participation, and every participating type contains $S$ and approves fewer than $\ell$ committee members.
The verification bound is valid: there are at most $2^m$ candidate subsets to examine, and the necessary rational additions and comparisons have polynomial bit complexity in the stated parameters.
The conclusion for $s=\alpha k<1$ is also correct: every eligibility threshold exceeds total mass $1$.
The construction and proof are sound.
$$
\sum_i\ell_i\le s.
$$
Integrality gives the asserted bound by $\lfloor s\rfloor$.
The completion count and its strict decrease with core size are correct. Strictness uses $m>k$, which follows from $k<t\le m$.
This establishes existence, not a polynomial-time core-finding algorithm, as the prover correctly notes.
The permutation averaging argument is correct under the encoding convention.
For any fixed committee, its inverse image under a uniform candidate permutation is uniform over all size-$k$ committees. Averaging therefore gives the valid-committee fraction independently of the strategy’s output distribution. At least one admissible permuted society attains success no greater than this average.
The minimum exists because descriptions of bounded length form a finite class. The resulting guarantee using $\rho_r$ is valid.
The potential argument is correct, including its strict inequality.
A violating group supplies a common candidate $z\notin W$. Otherwise its common intersection would already provide every participating type with at least $\ell$ elected approvals.
Adding $z$ gives
$$
a\ge\frac{1}{r}.
$$
The removal-loss formula is correct, and its denominator is positive whenever the corresponding type approves the removed candidate.
The critical identity
$$
\sum_{y\in W}d_y=(k+1)a-c
$$
checks out type by type:
Subtracting contributions indexed by $D$ leaves a strictly positive sum because $D$ contains a positively approved candidate. Every remaining swap preserves $D$, contradicting maximality.
The case $r=1$ is covered: the sum over $W\setminus D$ is empty, and the displayed positive lower bound yields a contradiction directly.
The extremal characterization is correct.
Equality in the completion bound forces a core $T$ of size exactly $r$ and forces every valid committee to contain it. Lemma 4 then excludes approval of any candidate outside $T$.
For the committee $W_y$, the inequalities
$$
|A|\ge\ell,\qquad
|A|-\mathbf 1_{\{y\in A\}}<\ell
$$
indeed force $y\in A$ and $|A|=\ell$. Since $A\supseteq S$ and both have size $\ell$, only the single type $A=S$ can be counted.
The subsequent chain of inequalities has equal endpoints. Equality forces all mass onto the specified types, exact masses $|A|/r$, and pairwise disjointness.
The sufficiency argument correctly uses level $\ell=|A|$ to force inclusion of each entire block. These levels lie within the permitted range because $|A|\le r\le k$.
Corollary 6 follows, including the assertion $\tau\le k$.
Under the stated additive encoding convention, the dynamic program correctly tests whether an extremal society fits within $L$.
The positive block sizes must sum to $r$, and every such composition can be realized by disjoint candidate blocks. The recurrence enforces these constraints, and its transition count is $O(\tau r^2)$.
The conclusions about $V_0$ are correct:
The nonintegral construction also works: block mass $a_i/r$ is at least $a_i/s$, so the block forces its inclusion. The prover appropriately does not claim necessity in that case.
Lemma 7 is correct. A group of mass at least $1$ must use every support type at full mass. Cohesion therefore depends on the common intersection, while representation depends on hitting the union.
The counting argument in Theorem 8 is sound. A support with nonempty common intersection and union size $v$ has at most $2^{v-1}$ distinct types.
The construction attaining the minimum union size is also valid. For $u\ge2$, having
$$
\tau>2^{u-2}
$$
prevents omission of any candidate other than the prescribed common candidate. The case $u=1$ is explicitly handled.
Admissibility of the construction depends on the encoding qualification identified above.
The replacement of adaptive queries by a predetermined list is correct.
After any nonempty response, a committee containing an observed approved candidate is valid. Before the first nonempty response, the strategy follows its all-empty history, which determines a fixed query list after internal randomness is fixed.
The resulting failure formula correctly uses independence of fresh population draws. “Adaptivity is unnecessary” here concerns query selection; the final committee may still depend on responses, as the proof specifies.
The deterministic cap
$$
J=\left\lceil\frac{m-k}{t}\right\rceil
$$
is valid. Along the all-empty history, every common candidate must be among the unqueried candidates. Thus the final committee succeeds whenever cohesion is possible.
For $t\ge m-k$, combining this cap with the exact zero-sample value establishes the asserted formula for $N^*$ and the polynomial decision procedure. The numerical example gives $V_0=4/5$ correctly.
The finite linear program correctly characterizes the decision problem in this regime.
There are finitely many admissible descriptions and fixed plans; the failure coefficients are rational. Their bit lengths are polynomially bounded using the description length and number of draws. The stated exact rational linear-program feasibility theorem applies to this explicitly represented finite system.
The enumeration and running-time bounds are valid. The branch restriction $B<J$ removes dependence polynomial in the numerical value of an arbitrarily large binary budget.
The validity condition
$$
|A\cap W|\ge\min(r,|A|)
$$
follows directly from the eligibility thresholds.
The upper-bound argument is correct. Under a uniform prior on size-$r$ approval sets, testing distinct candidates preserves conditional uniformity of untested approvals. Allowing exactly $b$ distinct tests can only strengthen the strategy for this upper bound.
The hypergeometric probabilities and conditional success bound are correct. The set $\mathcal A$ ensures all conditional denominators are positive, including boundary cases with no untested candidates.
The attainment argument is also sound:
The formula handles $B=0$ and complete observation. The case $r=0$ is separately declared vacuous. Binary computation of $b$ and polynomial-size binomial arithmetic justify the stated polynomial decision time.
Major incompleteness relative to USER_TASK. No general polynomial-time algorithm or NP-hardness reduction is supplied. The structural results, sharpness test, and exact special cases do not decide the problem for arbitrary public parameters.
The prover explicitly acknowledges this limitation, so this is not an erroneous claim of a complete solution. The minimum additional work required is precisely the missing general algorithm with its correctness and running-time proof, or a valid hardness reduction to the public-parameter decision problem.
⟨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.