Answer: —
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a λ-query single-winner voting rule that achieves a distortion of O(λ·(min{n, m})1/λ) and runs in poly(n, m) time. More precisely, if a β-approximately stable committee ex- ists for a given instance, the distortion guarantee is β · 1/λ · (min{n, m})1/λ. We provide the proof and the algorithm in the full ver- sion and discuss the main differences compared to one-sided matching below.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates C, finite observable cohorts T with rational masses summing to one, a ranking for each cohort, a constant query budget lambda, and a promise that each cohort has one hidden utility vector consistent with its ranking, design or decide the existence of an adaptive deterministic policy making at most lambda value queries per cohort and outputting a candidate whose worst-case mass-weighted welfare distortion is at most D.
Let \(C\) be a nonempty set of \(m\) candidates. A society is given by its support: the list of \(\tau\) observable cohort types with positive binary rational masses \(p_t\), summing to \(1\), and a total ranking \(\sigma_t\) for each. Here \(\tau\) is the support size, not the number of possible rankings; distinct cohorts may share a ranking.
Each cohort has one fixed hidden utility vector \(u_t:C\to\mathbb R_{\ge0}\), shared by its entire mass, with \(u_t(\sigma_t(1))\ge\cdots\ge u_t(\sigma_t(m))\). Utilities have no normalization; utility ties are resolved by the supplied ranking.
A query \(Q(t,c)\) reveals exactly \(u_t(c)\). A deterministic policy chooses queries and its final candidate using the observable input and all previous answers, making at most \(\lambda\) queries to each cohort on every feasible history, where \(\lambda\ge1\) is a fixed integer. Cohorts cannot be split into independently queried subcohorts.
Define \(W_u(c)=\sum_t p_tu_t(c)\). Given a binary rational \(D\ge1\), a policy has distortion at most \(D\) if, for every consistent hidden profile \(u\), its output \(c_P(u)\) satisfies \(\max_{c\in C}W_u(c)\le D W_u(c_P(u))\); this also covers profiles with zero welfare. Let \(L\) be the total bit length of the observable input.
Is deciding whether such a policy exists solvable in time \(\operatorname{poly}(m,\tau,L)\) for each fixed \(\lambda\), or is it NP-hard for some fixed \(\lambda\)?
For a finite society of \(n\) agents, a deterministic polynomial-time rule achieves distortion \(O(\lambda(\min\{n,m\})^{1/\lambda})\) using at most \(\lambda\) value queries per agent. [Ebadian–Shah](https://www.cs.toronto.edu/~nisarg/papers/value-queries.pdf)
No result settling this exact cohort-policy existence problem was located.
Theorem. For $\lambda=1$, the cohort-policy existence problem is $\mathrm{coNP}$-complete under polynomial-time many-one reductions. Hardness holds even when each top candidate is the top of at most two cohorts.
This substantially narrows the complexity question: a polynomial-time algorithm for every fixed $\lambda$ would imply $\mathrm{P}=\mathrm{NP}$. It also establishes $\mathrm{NP}$-hardness under polynomial-time Turing reductions already for $\lambda=1$.
I use the customary many-one interpretation of the requested $\mathrm{NP}$-hardness. Under that interpretation, the original question remains partially unresolved: the proof below does not establish $\mathrm{NP}$-hardness for some fixed $\lambda\ge2$.
Set
$$
v_t(c)=p_tu_t(c).
$$
Since $p_t>0$, this transformation is a bijection between admissible original utility vectors and arbitrary nonnegative vectors $v_t$ respecting the same rankings. Moreover,
$$
W_u(c)=\sum_t v_t(c).
$$
A query answer in either representation determines the answer in the other by multiplication or division by $p_t$. Thus the transformation preserves policies, query budgets, and distortion.
Throughout the proof, utilities refer to $v_t$, and welfare is their sum. In particular, policy existence is independent of the positive cohort masses.
Write $h_t=\sigma_t(1)$.
Lemma 1. At any feasible terminal history of a finite-distortion policy, an unqueried value $v_t(h_t)$ forces the output to be $h_t$.
Proof. Suppose the output is $c\ne h_t$. Starting from any profile producing this history, increase only $v_t(h_t)$. Ranking consistency is preserved, and every queried value remains unchanged.
Determinism therefore preserves the entire history and output. The welfare of $c$ remains fixed, while that of $h_t$ becomes arbitrarily large, contradicting finite distortion. $\square$
Lemma 2. A one-query-per-cohort distortion-$D$ policy exists if and only if one exists that queries every cohort’s top candidate and then chooses its output.
Proof. Let $P$ be any successful one-query policy. The replacement policy queries all tops, obtaining
$$
a_t=v_t(h_t).
$$
It then simulates $P$, answering every simulated query to cohort $t$ with $a_t$. This transcript is feasible: the flat vectors $v_t(d)=a_t$ for all $d$ produce it.
Let $c$ be the simulated output. If the simulation queried a non-top candidate in cohort $t$, its top was unqueried because the budget is one. Lemma 1 implies $c=h_t$.
Now fix any actual profile $v$ with the recorded top answers. Construct $v'$ by replacing each cohort queried at a non-top candidate during the simulation by its flat vector of value $a_t$. Retain all other cohorts.
Every simulated query receives the same answer on $v'$, so $P$ outputs $c$. Every modified cohort has $c=h_t$; consequently, its utility for $c$ is unchanged, while its utility for every rival weakly increases. Hence
$$
W_{v'}(c)=W_v(c),
\qquad
W_{v'}(d)\ge W_v(d)\quad(d\in C).
$$
The guarantee of $P$ gives
$$
W_v(d)\le W_{v'}(d)\le D W_{v'}(c)=D W_v(c).
$$
Thus the replacement succeeds for every completion of its top answers. $\square$
If all cohorts have a common top, that candidate is pointwise optimal. Henceforth assume there are at least two distinct tops. Put
$$
H=\{h_1,\ldots,h_k\},
\qquad
r=D-1.
$$
For a vector $a$ of top answers, define
$$
A_c(a)=\sum_{t:h_t=c}a_t,
\qquad
F_c(a)=\max_{d\ne c}\sum_{t:d\succ_t c}a_t,
$$
where $d\succ_t c$ means that $d$ precedes $c$ in cohort $t$’s ranking.
Lemma 3. Candidate $c$ is safe for every completion of the top answers $a$ precisely when
$$
F_c(a)\le rA_c(a).
$$
Proof. Fix a rival $d\ne c$. We maximize each cohort’s contribution
$$
v_t(d)-Dv_t(c)
$$
subject to its ranking and top answer.
$$
v_t(d)-Dv_t(c)\le(1-D)v_t(c)\le0.
$$
The maximum zero is attained by assigning zero to every non-top candidate.
These cases exhaust all possibilities. Cohorts are independent, so their maxima can be attained simultaneously for this fixed rival. Therefore
$$
\max_{v:\,v_t(h_t)=a_t}
\bigl(W_v(d)-DW_v(c)\bigr)
=
\sum_{t:d\succ_t c}a_t-rA_c(a).
$$
Requiring this expression to be nonpositive for every rival proves the lemma. $\square$
For $a\ne0$, no candidate outside $H$ is safe: its $A_c(a)$ is zero, while some positive-answer cohort’s top precedes it, making $F_c(a)>0$. If $a=0$, all utilities are zero.
Combining the lemmas gives
$$
\text{A one-query policy exists}
\iff
\forall a\in\mathbb R_{\ge0}^{\tau}\setminus\{0\},
\ \exists c\in H:\ F_c(a)\le rA_c(a).
$$
Failure means that one answer vector satisfies
$$
F_c(a)>rA_c(a)\qquad(c\in H).
$$
At a failing vector, choose a witnessing rival $d_c\ne c$ for each $c\in H$. Then
$$
\sum_{t:d_c\succ_t c}a_t-r\sum_{t:h_t=c}a_t>0
\qquad(c\in H).
$$
Because these are finitely many strict homogeneous inequalities, a common positive scaling makes all their left sides at least one. Thus failure is equivalent to feasibility, for some chosen rivals, of
$$
a_t\ge0,
\qquad
\sum_{t:d_c\succ_t c}a_t-r\sum_{t:h_t=c}a_t\ge1
\qquad(c\in H).
$$
Write $D=P/Q$, with positive integers $P\ge Q$. Clearing denominators gives
$$
Q\sum_{t:d_c\succ_t c}a_t
-
(P-Q)\sum_{t:h_t=c}a_t
\ge Q.
$$
We verify that feasibility supplies a polynomial-size rational certificate.
Let $\mathcal P$ be this feasible polyhedron. Minimize $\sum_t a_t$ over $\mathcal P$. Given any feasible point $a^0$, the portion satisfying
$$
\sum_t a_t\le\sum_t a_t^0
$$
is nonempty and compact, because all coordinates are nonnegative. Thus a minimum exists. The minimizing face is also nonempty and compact, so it has an extreme point; successive minimization of the coordinates supplies one. Such a point is extreme in $\mathcal P$, since any convex decomposition in $\mathcal P$ must have both endpoints attain the same minimum objective.
At an extreme point, the active constraint normals span $\mathbb R^\tau$. Otherwise, a nonzero vector orthogonal to all active normals would allow sufficiently small perturbations in both directions while preserving every constraint, contradicting extremality.
Choose $\tau$ independent active constraints. Their coefficients and right-hand sides are integers of magnitude at most $P$. Cramer’s rule and Hadamard’s determinant bound show that each coordinate has numerator and denominator of magnitude at most
$$
(\sqrt{\tau}\,P)^\tau.
$$
Consequently, the rational vector has polynomial encoding length. A certificate consists of this vector and the chosen rivals. Its inequalities can be checked in polynomial time.
Therefore the one-query existence problem belongs to $\mathrm{coNP}$.
The next lemma is the key new structural result: spreading positive top answers among several cohorts with the same top cannot create a failure that requires such spreading.
For a finite nonnegative square matrix $M$, let $\rho(M)$ denote its spectral radius. We use these standard facts:
$$
\rho(M)=\lim_{\ell\to\infty}\|M^\ell\|^{1/\ell}
$$
for any matrix norm.
Two consequences will be useful. If $0\le N\le M$ entrywise, then $N^\ell\le M^\ell$; applying Gelfand’s formula with the maximum-row-sum norm gives
$$
\rho(N)\le\rho(M).
$$
Also, if $y\ge0$, $y\ne0$, and $M^{\mathsf T}y\ge sy$ for $s\ge0$, then
$$
(M^{\mathsf T})^\ell y\ge s^\ell y.
$$
Taking norms and applying Gelfand’s formula yields $\rho(M)\ge s$.
All matrices below are finite, square, and nonnegative, as these applications require.
For every top candidate $h_j$, choose a cohort $t_j$ whose top is $h_j$. For every $h_i$, choose a rival $d_i\ne h_i$. Define
$$
B_{ij}=
\begin{cases}
1,&d_i\succ_{t_j}h_i,\\
0,&\text{otherwise}.
\end{cases}
$$
Since $h_i$ is the top of cohort $t_i$, every diagonal entry is zero.
Lemma 4. A one-query policy fails to exist if and only if some such choices satisfy
$$
\rho(B)>r.
$$
Proof: failure implies a matrix witness.
Let $a$ be a failing top-answer vector, and choose witnessing rivals $d_i$. Put
$$
x_j=A_{h_j}(a).
$$
Within each top group, choose probabilities $q_j(t)$ satisfying
$$
a_t=x_jq_j(t).
$$
When $x_j>0$, take $q_j(t)=a_t/x_j$. When $x_j=0$, choose any probability distribution on that nonempty group.
Define the matrix
$$
M_{ij}=\sum_{t:h_t=h_j}q_j(t)\,\mathbf 1[d_i\succ_t h_i].
$$
The witnessing inequalities say exactly
$$
Mx>rx
$$
componentwise.
To obtain a strictly positive vector, take $w=x+\varepsilon\mathbf 1$ for sufficiently small $\varepsilon>0$. Every coordinate of $Mx-rx$ is strictly positive, so continuity ensures
$$
Mw>rw.
$$
Hence
$$
s=\min_i\frac{(Mw)_i}{w_i}>r.
$$
Let $y\ge0$, $y\ne0$, be a left Perron vector of $M$. Since $w>0$, we have $y^{\mathsf T}w>0$, and
$$
\rho(M)y^{\mathsf T}w
=
y^{\mathsf T}Mw
\ge
s\,y^{\mathsf T}w.
$$
Thus $\rho(M)>r$.
For each group $j$, select $t_j$ maximizing
$$
\sum_i y_i\mathbf 1[d_i\succ_t h_i]
$$
over cohorts with top $h_j$. The resulting binary matrix $B$ satisfies
$$
B^{\mathsf T}y\ge M^{\mathsf T}y=\rho(M)y.
$$
The matrix consequence proved above gives
$$
\rho(B)\ge\rho(M)>r.
$$
Proof: a matrix witness implies failure.
Suppose $\rho(B)>r$, and take a nonzero nonnegative right Perron vector $z$:
$$
Bz=\rho(B)z.
$$
Give selected cohort $t_j$ top answer $z_j$, and give every unselected cohort top answer zero. These answers are feasible, for example using flat utility vectors.
For each $i$ with $z_i>0$,
$$
F_{h_i}(a)\ge(Bz)_i=\rho(B)z_i>rz_i=rA_{h_i}(a).
$$
If $z_i=0$, choose $j$ with $z_j>0$. Necessarily $j\ne i$. The rival $h_j$ precedes $h_i$ in cohort $t_j$, so
$$
F_{h_i}(a)\ge z_j>0=rA_{h_i}(a).
$$
Thus every top candidate fails its safety inequality. The characterization in Section 2 rules out a successful policy. $\square$
In particular, every failure has a witness with at most one positive top answer per top-candidate group.
Let $J$ be the $k$-by-$k$ all-ones matrix, and put
$$
K=J-I.
$$
Thus $K$ has every off-diagonal entry equal to one, and $\rho(K)=k-1$.
Lemma 5. For $k\ge3$, every binary matrix $B$ with zero diagonal satisfies
$$
\rho(B)>k-1-\frac1k
\iff
B=K.
$$
Proof. The implication from $B=K$ is immediate.
Otherwise, choose a missing off-diagonal entry $(a,b)$. Then
$$
B\le M:=K-E_{ab},
$$
where $E_{ab}$ has its only nonzero entry, equal to one, at $(a,b)$.
The directed graph of $M$ is strongly connected: the single missing arc can be replaced by a two-arc path through a third vertex. Thus $M$ is irreducible.
Let $v>0$ be its right Perron vector, let $\rho=\rho(M)$, and set $S=\sum_i v_i$. Row $b$ is unchanged, because $a\ne b$, so
$$
\rho v_b=S-v_b,
\qquad
\frac{v_b}{S}=\frac1{\rho+1}.
$$
Summing all eigenvector equations, and accounting for the single missing entry, gives
$$
\rho S=(k-1)S-v_b.
$$
Therefore
$$
\rho=k-1-\frac1{\rho+1}.
$$
In particular, $\rho<k-1$, whence
$$
\frac1{\rho+1}>\frac1k.
$$
It follows that
$$
\rho(B)\le\rho(M)<k-1-\frac1k.
$$
$\square$
Combining Lemmas 4 and 5, at the rational distortion
$$
D=k-\frac1k,
$$
failure of a one-query policy is equivalent to the existence of cohort and rival choices producing the complete matrix $K$.
We reduce unsatisfiability of a Boolean formula with at most three literals per clause to policy existence. Satisfiability for this class is $\mathrm{NP}$-complete. [Karp, “Reducibility Among Combinatorial Problems”](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
Let the formula have variables $X_1,\ldots,X_n$ and nonempty clauses $C_1,\ldots,C_s$, with $n,s\ge1$. These restrictions preserve completeness: a fresh variable and a tautological clause can ensure nonemptiness without changing satisfiability.
Introduce distinct candidates:
Let $R_i$ be the ordered list of literal-occurrence candidates for clause $C_i$, and define the block
$$
B_i=(R_i,c_i).
$$
Parenthesized lists below are rankings from highest to lowest; inserting a block means inserting all its entries.
There are two cohorts with top $v_j$, one for each Boolean value $\beta\in\{0,1\}$; one cohort with top $c_i$ for each clause; and one cohort with each top $b_1,b_2$. Thus
$$
k=n+s+2,
\qquad
\tau=2n+s+2.
$$
We set $\lambda=1$ and
$$
D=k-\frac1k.
$$
They are
$$
(b_1,B_1,B_2,\ldots,B_s,q,b_2,z,v_1,\ldots,v_n)
$$
and
$$
(b_2,B_s,B_{s-1},\ldots,B_1,q,b_1,z,v_1,\ldots,v_n).
$$
For variable $X_j$ and value $\beta$, partition $R_i$ into two ordered lists:
The corresponding ranking is
$$
\begin{aligned}
(&v_j,q,b_1,b_2,\\
&G_1(j,\beta),c_1,N_1(j,\beta),\ldots,
G_s(j,\beta),c_s,N_s(j,\beta),\\
&z,v_1,\ldots,v_{j-1},v_{j+1},\ldots,v_n).
\end{aligned}
$$
The cohort with top $c_i$ has ranking
$$
(c_i,q,b_1,b_2,R_i,
B_1,\ldots,B_{i-1},B_{i+1},\ldots,B_s,
z,v_1,\ldots,v_n).
$$
Each displayed ranking contains every candidate exactly once.
Choose any positive, polynomially encoded masses summing to one. For example, with $b=\lceil\log_2\tau\rceil$, give the first $\tau-1$ cohorts mass $2^{-b}$ and the final cohort mass
$$
1-(\tau-1)2^{-b}>0.
$$
These are dyadic rationals.
There are at most $k+3s+2$ candidates. All rankings, masses, and $D$ have polynomial total encoding length, and the construction is computable in polynomial time.
For each clause candidate $c_i$,
$$
\{d:d\succ_{\sigma_{b_1}}c_i\}
\cap
\{d:d\succ_{\sigma_{b_2}}c_i\}
=
R_i.
$$
Indeed, its own literal-occurrence candidates precede it in both rankings. Every other block precedes its block in one ranking and follows it in the other. Candidate $b_1$ follows all clause blocks in the second ranking, and $b_2$ does so in the first. The candidates $q,z$ and all variable candidates follow every clause block in both.
Consequently, if selected cohorts and challengers produce $K$, the challenger for clause candidate $c_i$ must belong to $R_i$.
Suppose $\beta_1,\ldots,\beta_n$ satisfies the formula. Select the variable cohort corresponding to $\beta_j$ for each $j$, and the unique cohort for every other top.
Choose challengers as follows:
We check every kind of row.
For a variable row $v_j$, candidate $z$ precedes $v_j$ in every other selected cohort: it precedes all variable candidates in the clause and $b_1,b_2$ rankings, and all variable candidates other than the top in every variable ranking.
For a clause row $c_i$, its selected true literal occurrence precedes $c_i$:
For row $b_1$, candidate $q$ precedes $b_1$ in the $b_2$ ranking and every variable and clause ranking. The symmetric statement holds for row $b_2$.
Thus every off-diagonal entry is one. Diagonal entries are zero because each selected cohort ranks its own top first. Hence the matrix is $K$.
By Lemmas 4 and 5, no successful one-query policy exists.
Conversely, suppose selected cohorts and challengers produce $K$. The selected variable cohorts specify values $\beta_1,\ldots,\beta_n$.
For each clause candidate $c_i$, Section 6.2 forces its challenger to be one of its own literal-occurrence candidates. Suppose this occurrence involves variable $X_j$.
Since the matrix is $K$, this occurrence precedes $c_i$ in the selected cohort with top $v_j$. By construction, occurrences involving $X_j$ precede $c_i$ in that ranking precisely when their literal is true under $\beta_j$.
Thus every clause has a true literal. The selected assignment satisfies the formula.
The preceding arguments establish
$$
\text{Formula satisfiable}
\iff
\text{Some cohort and rival choices produce }K.
$$
Using Lemmas 4 and 5 at $D=k-1/k$ gives
$$
\text{Formula unsatisfiable}
\iff
\text{A one-query distortion-}D\text{ policy exists}.
$$
This is a polynomial-time many-one reduction from a $\mathrm{coNP}$-complete problem to policy existence. Together with Section 3, it proves $\mathrm{coNP}$-completeness.
Each top candidate belongs to at most two cohorts, as asserted.
The one-query problem is now classified as $\mathrm{coNP}$-complete. Therefore polynomial-time solvability for every fixed query budget would imply $\mathrm{P}=\mathrm{NP}$.
There is also a one-query polynomial-time Turing reduction from satisfiability to policy existence: construct the instance above, ask whether a policy exists, and negate the answer.
However, this does not establish many-one $\mathrm{NP}$-hardness. Indeed, many-one $\mathrm{NP}$-hardness for the one-query problem, together with its membership in $\mathrm{coNP}$, would imply $\mathrm{NP}=\mathrm{coNP}$. Establishing the requested many-one hardness for some fixed larger budget remains open here.
⟨structured verdict parsed — rendered above⟩
The proof establishes the stated $\mathrm{coNP}$-completeness theorem for $\lambda=1$, subject to a minor indexing clarification. I found no false central step or substantive gap in the policy characterization, certificate argument, spectral characterization, or reduction.
The original task remains partially resolved under the customary polynomial-time many-one interpretation of $\mathrm{NP}$-hardness. The prover correctly acknowledges this limitation: $\mathrm{coNP}$-completeness establishes a strong complexity obstruction, but does not establish the requested many-one $\mathrm{NP}$-hardness alternative.
The substitution
$$
v_t(c)=p_tu_t(c)
$$
is valid because every $p_t$ is strictly positive. It preserves nonnegativity, ranking inequalities, and utility ties, and it is invertible separately in each cohort.
The welfare identity and correspondence between query answers are correct. An adaptive policy can translate each answer before choosing its next action, so the transformation preserves entire histories and query budgets.
The conclusion that policy existence is independent of the positive masses is justified specifically by the absence of utility normalization.
The perturbation is admissible: increasing only the top utility preserves every ranking inequality and leaves all queried coordinates unchanged.
Determinism preserves subsequent actions and the terminal output because the observed answers remain identical. If the output differs from that cohort’s top, its welfare stays fixed while the top candidate’s welfare becomes unbounded.
Thus the contradiction applies for every finite $D$, including histories whose output initially has zero welfare. The lemma is correct.
The simulated transcript is feasible: the profile consisting of flat cohort vectors produces every simulated answer.
The one-query budget is essential and is used correctly. If the simulation queries a non-top coordinate in a cohort, that cohort’s top remains unqueried, so Lemma 1 forces the simulated output to equal its top.
For an arbitrary actual completion of the recorded top answers, the modified profile reproduces the simulated transcript. In each modified cohort:
Unmodified cohorts need no further adjustment, including cohorts queried at their tops and cohorts not queried during the simulation. Consequently, the welfare comparison transfers the original guarantee to every actual completion.
Both directions of the equivalence are justified.
For each fixed rival, the three cases correctly exhaust all cohorts.
When the output candidate is the cohort’s top, its value is fixed at $a_t$, and the rival’s value is at most $a_t$. The maximum contribution is therefore
$$
-(D-1)a_t,
$$
with the stated flat-vector attainment.
When the rival precedes a non-top output candidate, the contribution is at most $a_t$. The stated prefix assignment attains it and respects the supplied ranking.
When the output candidate precedes the rival and is not the top, monotonicity and $D\ge1$ give a nonpositive contribution. Setting all non-top values to zero attains zero.
The independent cohort maxima may be attained simultaneously for each fixed rival. The proof does not require a single completion to maximize every rival’s expression simultaneously.
Thus the condition
$$
F_c(a)\le(D-1)A_c(a)
$$
is necessary and sufficient for that output to be safe for every completion.
For a nonzero answer vector, any candidate outside the set of tops has zero guaranteed welfare. A positive-answer cohort’s top supplies a rival with strictly positive contribution to its safety test. Hence such a candidate cannot be safe.
When all top answers are zero, nonnegativity and ranking consistency force every utility to be zero. All outputs satisfy the distortion condition.
The resulting universal characterization has the correct quantifier order: for each answer vector, the policy may choose a candidate that works for every completion of that vector.
There is one minor notation issue: the distinct top candidates require explicit reindexing, discussed below.
Choosing one witnessing rival for each unsafe top correctly replaces the maxima by finitely many strict inequalities.
Because the system is homogeneous and every selected left side is strictly positive, a common positive scaling makes every left side at least one. The converse is immediate.
The rational-certificate argument is sound:
After clearing denominators, the relevant matrix and right-hand-side entries have magnitude at most $P$. The determinant bound
$$
(\sqrt{\tau}\,P)^\tau
$$
applies both to denominators and to the Cramer numerators. Its logarithm is polynomial in the input parameters.
The rivals and rational answer vector therefore form a polynomial-size certificate, and exact rational verification takes polynomial time. The membership claim is established.
The stated Perron–Frobenius conclusions apply to finite nonnegative square matrices. Strict positivity is invoked only when irreducibility has been established.
The entrywise monotonicity consequence correctly follows by using the maximum-row-sum norm in Gelfand’s formula.
The implication from
$$
M^{\mathsf T}y\ge sy
$$
to $\rho(M)\ge s$ also follows from the stated iterated inequality and a compatible norm. The required assumptions $y\ge0$, $y\ne0$, and $s\ge0$ are satisfied in its subsequent application.
No unverified theorem hypothesis breaks the argument.
The within-group probability distributions are well-defined. When a group has zero total answer, the arbitrary distribution does not affect the identity $a_t=x_jq_j(t)$.
The witnessing inequalities give strict inequality in every coordinate of $Mx-rx$, including coordinates where $x_i=0$. Hence the small perturbation to a strictly positive vector preserves the strict inequalities.
Pairing that vector with a nonzero nonnegative left Perron vector establishes $\rho(M)>r$.
Selecting one cohort per group to maximize the left-vector weighted column score correctly gives
$$
B^{\mathsf T}y\ge\rho(M)y.
$$
The preceding matrix consequence then establishes $\rho(B)>r$.
This direction is rigorous and does not assume irreducibility.
For positive Perron-vector coordinates, the selected rivals give the required strict safety violations directly.
The zero-coordinate case is handled correctly and is essential. A nonzero Perron vector has some positive coordinate; its selected cohort’s top precedes every other candidate in that cohort. This supplies a rival with positive welfare contribution for any zero-answer top.
Thus every top fails its safety test even when the matrix is reducible or its Perron vector has zero coordinates. No positivity assumption is missing.
A binary zero-diagonal matrix distinct from $K$ has a missing off-diagonal entry and is entrywise bounded by the stated matrix $M$.
For $k\ge3$, the missing directed edge can be replaced by a path through a third vertex, so irreducibility is established before invoking a positive Perron vector.
Both eigenvector calculations are correct:
They yield
$$
\rho=k-1-\frac1{\rho+1}.
$$
Since $v_b>0$, this implies $\rho<k-1$, and consequently the claimed strict gap follows.
The reduction uses $k=n+s+2\ge4$, so the lemma’s domain restriction is satisfied.
The invoked source problem, satisfiability with at most three literals per clause, is among the complete problems in the cited [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). The nonempty source restrictions are routine and do not affect the reduction’s substance.
Every displayed ranking contains each candidate exactly once. In particular, the variable rankings partition each occurrence list, and the clause rankings omit their own block after listing their own top and occurrences separately.
The counts are correct:
$$
k=n+s+2,\qquad \tau=2n+s+2.
$$
The candidate bound follows from the maximum of three occurrences per clause.
The masses are positive dyadic rationals, sum to one, and have polynomial encoding length. The distortion parameter is rational, has polynomial encoding length, and satisfies $D\ge1$.
The construction respects the fixed cohort model and does not split cohorts.
The prefix intersection in the two fixed rankings is exactly $R_i$:
Since those two cohorts must be selected, a complete matrix forces each clause challenger into its own occurrence list. The argument is correct.
For a satisfying assignment, the proposed challengers produce every off-diagonal entry:
Diagonal entries vanish because each selected cohort ranks its own top first.
Conversely, a complete matrix forces each clause challenger to be an own-clause occurrence. Its comparison in the selected cohort of the occurrence’s variable certifies that the corresponding literal is true.
Thus the equivalence between satisfiability and existence of the complete matrix is proved. Combining it with the spectral characterization gives the correct reduction direction:
$$
\text{unsatisfiable formula}
\iff
\text{successful one-query policy exists}.
$$
The $\mathrm{coNP}$-hardness and the restriction to at most two cohorts per top follow.
The final complexity distinctions are accurate.
A polynomial-time algorithm for the one-query existence problem would yield a polynomial-time satisfiability algorithm by constructing the instance and complementing its answer. Thus polynomial-time solvability for every fixed budget would imply $\mathrm{P}=\mathrm{NP}$.
That complementing procedure is a Turing reduction. It is not a many-one reduction from satisfiability to policy existence.
The observation that many-one $\mathrm{NP}$-hardness together with membership in $\mathrm{coNP}$ would imply $\mathrm{NP}=\mathrm{coNP}$ is also correct.
Accordingly, the prover’s explicit partial-resolution claim is justified.
The established one-query theorem is genuine progress. Its verification does not depend on a missing structural lemma or an unproved spectral assertion.
⟨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.