Answer: —
Proposition 3.4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe function Q∗ F is a decisiveness index on SG. Explicitly, Q∗ F (G) = n X k=0 f(n, k)|Wk| where f and F are linked as in (1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of ballot types \(\mathcal T\), a rational population vector \(\mu\in\Delta(\mathcal T)\), a positional scoring rule with the paper’s tie-breaking and manipulation assumptions, and the induced region \(\mathcal W\subseteq\prod_t[0,\mu_t]\) of manipulation-winning coalition masses, compute \(\theta=\inf\{u\in[0,1]:u\mu\in\mathcal W\}\). This is the limiting fraction of the population that must be queried, with \(1-\theta\) giving the continuous limit of the query-based measure.
There are \(m\geq2\) candidates. A society is given by its support: a list \(\mathcal T\) of \(\tau\) strict complete rankings with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings. The input also includes a rational positional score vector \(1=s_1\geq\cdots\geq s_m=0\); \(L\) is the total input bit length.
Scores are aggregated by mass, and the outcome lottery is uniform over all candidates attaining the maximum score. Let \(p\) be the sincere outcome lottery.
A manipulating subcoalition has real masses \(c_t\in[0,\mu_t]\) with \(\sum_t c_t>0\). Each participating type may divide its mass arbitrarily among any strict complete reported rankings, including its sincere ranking; all remaining mass votes sincerely.
Its resulting lottery \(p'\) must satisfy, for every \(t\) with \(c_t>0\) and every \(k\in\{1,\ldots,m\}\), \(\sum_{a\in\operatorname{Top}_k(t)}p'(a)\geq\sum_{a\in\operatorname{Top}_k(t)}p(a)\), with a strict inequality for at least one \(k\) for each such \(t\).
Define \(\mathcal W\subseteq\prod_{t\in\mathcal T}[0,\mu_t]\) by declaring \(x\in\mathcal W\) exactly when some manipulating subcoalition satisfies \(c_t\leq x_t\) for every \(t\). Define \(\theta=\inf\{u\in[0,1]:u\mu\in\mathcal W\}\), taking \(\theta=1\) when this set is empty; the associated continuous query measure is \(1-\theta\).
Can \(\theta\) be computed exactly in time polynomial in \(m,\tau,L\), or is this computation NP-hard?
For finite monotone simple games, the rescaled query index satisfies \(\mathbb E[F(n,Q)]=\sum_{k=0}^{n}\frac{F(n,k)-F(n,k+1)}{\binom nk}|W_k|\): \(Q\) is the first winning query count, or \(n+1\) if none exists, \(W_k\) comprises winning coalitions of size \(k\), and \(F(n,\cdot)\) decreases from \(F(n,0)=1\) to \(F(n,n+1)=0\). This identity asserts no computational complexity bound. [Source](https://arxiv.org/pdf/1202.1882v2)
Asymptotic results under impartial culture approximate minimum manipulating coalition size, a different quantity from this proportional-query threshold. No result settling this exact threshold was located. [Source](https://arxiv.org/pdf/math/0702752)
The unrestricted complexity question remains unresolved in this write-up. I prove three additional results:
The main new ingredient is a perturbation that replaces a manipulation of a unique sincere winner, at any budget below $1$, by a nearby manipulation with a single final winner.
Let $\mathcal A$ be the candidate set. For each type $t$, let $r_t(a)$ denote the position of candidate $a$ in its sincere ranking. Define sincere scores by
$$
A_a=\sum_{t\in\mathcal T}\mu_t s_{r_t(a)}.
$$
Let
$$
H=\max_{a\in\mathcal A}A_a,
\qquad
\mathcal B=\{a:A_a=H\},
\qquad
b=|\mathcal B|.
$$
Thus the sincere lottery is uniform on $\mathcal B$.
A manipulation has *budget at most $u$* when its participating masses satisfy $c_t\leq u\mu_t$ for every type. This is exactly the condition used in the definition of $\theta$.
Fix a nonempty set $W\neq\mathcal B$ and write $w=|W|$. Define
$$
E_W=
\left\{
t:
b\,|W\cap\operatorname{Top}_k(t)|
\geq
w\,|\mathcal B\cap\operatorname{Top}_k(t)|
\text{ for every }k
\right\}.
$$
These inequalities express stochastic dominance of the uniform lottery on $W$ over the uniform lottery on $\mathcal B$.
Every type in $E_W$ also has at least one strict inequality. Indeed, equality at every prefix would, by subtracting consecutive equalities, imply equality of the probability assigned to every candidate. The two uniform lotteries would then have the same support, contradicting $W\neq\mathcal B$.
Consequently, a manipulation producing exactly $W$ may involve precisely types from $E_W$, subject to the score constraints.
Put
$$
C=\sum_t c_t.
$$
Introduce variables $Y_{aj}$ for the participating mass reporting candidate $a$ in position $j$. Their constraints are
$$
Y_{aj}\geq0,
\qquad
\sum_{j=1}^mY_{aj}=C\quad(a\in\mathcal A),
\qquad
\sum_{a\in\mathcal A}Y_{aj}=C\quad(1\leq j\leq m).
$$
These constraints characterize exactly the aggregate reports allowed by arbitrary splitting.
Necessity follows because every reported ranking uses every candidate and every position once. For sufficiency, suppose $C>0$. Consider the bipartite graph of positive entries of $Y$. If $I$ is a set of candidate rows and $N(I)$ its neighboring position columns, then
$$
|I|C
=
\sum_{a\in I}\sum_jY_{aj}
\leq
\sum_{j\in N(I)}\sum_aY_{aj}
=
|N(I)|C.
$$
Thus Hall’s condition holds, and the graph has a perfect matching.
Subtract the smallest entry on that matching from every matched entry. The residual matrix remains nonnegative, with equal row and column sums, and at least one positive entry disappears. Repeating this operation terminates after at most $m^2$ steps and gives
$$
Y=\sum_\ell\alpha_\ell P_\ell,
\qquad
\alpha_\ell>0,
\qquad
\sum_\ell\alpha_\ell=C,
$$
where each $P_\ell$ is the permutation matrix of a strict complete ranking.
Each participating type can report ranking $P_\ell$ on fraction $\alpha_\ell/C$ of its participating mass. Summing these reports realizes $Y$. If $C=0$, the constraints force $Y=0$.
The resulting candidate scores are therefore
$$
q_a
=
A_a-\sum_t c_t s_{r_t(a)}
+\sum_{j=1}^m s_jY_{aj}.
$$
Let $P_W$ be the following closed linear program, with objective to minimize $u$:
$$
0\leq u\leq1,
\qquad
0\leq c_t\leq u\mu_t,
\qquad
c_t=0\quad(t\notin E_W),
$$
together with the aggregate-report constraints and
$$
0\leq M\leq1,
\qquad
q_a=M\quad(a\in W),
\qquad
q_a\leq M\quad(a\notin W).
$$
To test whether a genuine manipulation produces exactly $W$, add a variable $0\leq\varepsilon\leq1$, impose
$$
C\geq\varepsilon,
\qquad
M-q_a\geq\varepsilon\quad(a\notin W),
$$
and maximize $\varepsilon$.
Call $W$ *admissible* if this program is feasible and its optimum is positive. This is equivalent to the existence of a genuine manipulation producing $W$: positive $\varepsilon$ supplies positive participating mass and all required strict score gaps; conversely, a genuine manipulation supplies a positive minimum of these finitely many quantities.
For admissible $W$, let
$$
\alpha_W=\min\{u:(u,c,Y,M)\in P_W\}.
$$
Then $\alpha_W$ is the infimum of budgets of genuine manipulations producing $W$.
To prove this assertion, let $z_0$ minimize $u$ in $P_W$, and let $z_1$ be a genuine strict-feasibility witness. For $0<\lambda\leq1$, the point
$$
z_\lambda=(1-\lambda)z_0+\lambda z_1
$$
satisfies the closed constraints, has positive participating mass, and has every exclusion gap positive. Its budget tends to $\alpha_W$ as $\lambda$ tends to zero. Conversely, every genuine manipulation producing $W$ is feasible in $P_W$.
It follows that
$$
\theta
=
\min\left(
\{1\}\cup
\{\alpha_W:W\neq\mathcal B,\ W\text{ admissible}\}
\right).
$$
Each program has $O(m^2+\tau)$ variables and constraints, with rational coefficients of polynomial encoding length. All feasible regions are bounded: $C\leq1$, $Y_{aj}\leq C$, and the remaining variables are explicitly bounded.
I use the standard rational linear programming theorem: feasibility and exact optimization over a nonempty bounded rational polyhedron can be performed in time polynomial in the encoded program size. The rationality, size, and boundedness hypotheses have all been verified here. See [Khachiyan’s polynomial-time linear programming theorem](https://www.mathnet.ru/eng/dan42319).
In particular, enumerating all $W$ gives an exact algorithm using $O(2^m)$ polynomial-size linear programs. Below, smaller families of winner sets suffice in additional cases.
Assume throughout this section that
$$
\mathcal B=\{b_0\}.
$$
Thus
$$
A_{b_0}>A_a\quad(a\neq b_0).
$$
First observe a necessary preference condition. If a participating type $t$ accepts the uniform lottery on $W$, then the dominance inequality at the prefix ending at $b_0$ gives
$$
\frac{|W\cap\operatorname{Top}_{r_t(b_0)}(t)|}{|W|}
\geq1.
$$
Hence every candidate in $W\setminus\{b_0\}$ is ranked above $b_0$ by every participant. Moreover, $W\setminus\{b_0\}$ is nonempty, since otherwise the outcome would not change.
Lemma. Suppose the sincere winner is unique and a manipulation produces $W$ at budget $u<1$. For every $\eta>0$, there is a manipulation at budget less than $\min\{1,u+\eta\}$ whose outcome is a singleton $\{a\}$, where $a\neq b_0$.
If $W$ is already a singleton, the assertion follows by retaining the manipulation. The proof below handles nonsingleton $W$.
When $m=2$, no manipulation exists under a unique sincere winner.
Indeed, write $a$ for the other candidate. Every participant would have to rank $a$ above $b_0$, so sincerely contributes score $1$ to $a$ and score $0$ to $b_0$. Changing its report cannot increase $a$’s score or decrease $b_0$’s score. Thus
$$
q_a\leq A_a<A_{b_0}\leq q_{b_0},
$$
which prevents $a$ from being a winner.
It remains to prove the lemma for $m\geq3$.
Take a manipulation at budget $u<1$. Let its masses be $c_t$, let $C=\sum_t c_t>0$, and define the withdrawn sincere contribution
$$
S_z=\sum_t c_t s_{r_t(z)}
\quad(z\in\mathcal A).
$$
Let $R_z$ be its aggregate reported contribution. Then
$$
q_z=A_z-S_z+R_z,
\qquad
0\leq R_z\leq C.
$$
Choose
$$
a\in W\setminus\{b_0\}
$$
minimizing $S_a$ over $W\setminus\{b_0\}$. Therefore
$$
S_a\leq S_z
\quad
(z\in W\setminus\{a,b_0\}).
$$
Every original participant ranks $a$ above $b_0$, so every such participant strictly prefers the singleton outcome $\{a\}$.
Define
$$
\beta=
\min\left\{
\frac{s_2}{2},
\frac{A_{b_0}-A_a}{2C}
\right\},
\qquad
\rho=
\frac{\sum_{j=1}^m s_j-1-\beta}{m-2}.
$$
We construct a report distribution with average scores
$$
v_a=1,
\qquad
v_{b_0}=\beta,
\qquad
v_z=\rho\quad(z\notin\{a,b_0\}).
$$
If $s_2=0$, put $a$ first, $b_0$ last, and distribute the other candidates uniformly over the remaining positions. This realizes the desired averages, with $\beta=\rho=0$.
If $s_2>0$, mix the following two distributions:
Within each distribution, assign the other candidates uniformly to the remaining positions. Give the second distribution probability $\beta/s_2$. Since $0\leq\beta\leq s_2/2$, this is a valid mixture. The average score of $b_0$ is $\beta$, and symmetry and conservation of total score give average $\rho$ to each remaining candidate.
Crucially,
$$
\rho<1.
$$
For $s_2=0$, this was already established. Otherwise $\beta>0$, and
$$
\sum_{j=1}^m s_j\leq m-1
$$
because $s_m=0$ and all other entries are at most $1$. Consequently,
$$
\rho\leq1-\frac{\beta}{m-2}<1.
$$
This small positive value of $\beta$ handles veto as well as score vectors whose total score is strictly below $m-1$.
For each original participant, add mass $\delta c_t$ using the new report distribution, where $\delta>0$ will be sufficiently small. The new participating mass of type $t$ is $(1+\delta)c_t$, so its budget is at most $(1+\delta)u$.
The resulting score is
$$
q_z^{(\delta)}=q_z+\delta D_z,
\qquad
D_z=Cv_z-S_z.
$$
For $z\in W\setminus\{a,b_0\}$, the original scores tie, and
$$
D_a-D_z
=
C(1-\rho)+S_z-S_a
>
0.
$$
Thus $a$ strictly outranks every such $z$ after the perturbation.
If $b_0\in W$, its original score also ties with $a$. The equality
$$
A_a-S_a+R_a
=
A_{b_0}-S_{b_0}+R_{b_0}
$$
implies
$$
C-S_a+S_{b_0}
=
A_{b_0}-A_a+C-R_a+R_{b_0}
\geq A_{b_0}-A_a.
$$
Therefore
$$
D_a-D_{b_0}
=
C-S_a+S_{b_0}-C\beta
\geq
\frac{A_{b_0}-A_a}{2}
>
0.
$$
So $a$ also strictly outranks $b_0$.
Finally, every candidate outside $W$ originally has score strictly below $q_a$. Since there are finitely many candidates and scores depend continuously on $\delta$, these strict gaps remain positive for all sufficiently small $\delta>0$.
Choose such a $\delta$ also satisfying
$$
(1+\delta)u<1,
\qquad
\delta u<\eta.
$$
This is possible because $0<u<1$. Candidate $a$ is then the unique winner at budget less than $\min\{1,u+\eta\}$.
The participants remain exactly the original participating types, and each strictly prefers $\{a\}$ to $\{b_0\}$. This proves the lemma.
Theorem. If the sincere winner is unique, $\theta$ can be computed exactly in time polynomial in $m,\tau,L$, for an arbitrary rational positional score vector.
Proof. For each $a\neq b_0$, apply the fixed-set formulation to $W=\{a\}$. Its eligible types are exactly
$$
E_{\{a\}}=\{t:r_t(a)<r_t(b_0)\}.
$$
Test admissibility and, when admissible, compute $\alpha_{\{a\}}$. Define
$$
\widehat\theta
=
\min\left(
\{1\}\cup
\{\alpha_{\{a\}}:a\neq b_0,\ \{a\}\text{ admissible}\}
\right).
$$
Singleton manipulations are particular manipulations, so
$$
\theta\leq\widehat\theta.
$$
If $\theta<1$, there are manipulation budgets $u$ arbitrarily close to $\theta$ with $u<1$. By the perturbation lemma, for every such $u$ there are singleton manipulation budgets arbitrarily close to $u$ from above. Hence
$$
\widehat\theta\leq u.
$$
Taking manipulation budgets tending to $\theta$ gives $\widehat\theta\leq\theta$.
If $\theta=1$, the inequalities $\theta\leq\widehat\theta\leq1$ give equality directly. Thus in every case
$$
\theta=\widehat\theta.
$$
There are $m-1$ proposed singleton sets, each requiring at most two polynomial-size rational linear programs. The running time is polynomial in $m,\tau,L$. $\square$
The use of an infimum matters here. The perturbation adds participating mass, so the lemma applies to budgets below $1$. It does not assert that every manipulation at budget exactly $1$ can be replaced by a singleton manipulation. The definition’s default value $\theta=1$ makes this endpoint unnecessary for computing the threshold.
Assume now that $b\geq2$. For each type $t$, let $h_t$ be its highest-ranked candidate in $\mathcal B$. Define
$$
\kappa=\max\{j:s_j=1\},
$$
the size of the initial plateau of maximal positional scores.
Proposition. If some type $t$ satisfies
$$
s_{r_t(h_t)}<1,
$$
then $\theta=0$.
Proof. The type’s first candidate lies outside $\mathcal B$: otherwise it would be $h_t$ and would receive score $1$.
On an arbitrarily small positive mass of this type, swap $h_t$ with its first candidate. The score of $h_t$ increases by
$$
c_t\bigl(1-s_{r_t(h_t)}\bigr)>0.
$$
The swapped outsider’s score decreases; all other candidate scores remain unchanged. Thus $h_t$ becomes the unique winner.
Because $h_t$ is this type’s favorite sincere winner and $b\geq2$, its singleton lottery strictly stochastically dominates the uniform lottery on $\mathcal B$. Arbitrarily small proportional budgets suffice. $\square$
Proposition. Suppose
$$
s_{r_t(h_t)}=1
\quad\text{for every type }t.
$$
Every genuine manipulation has a final winner set $W$ satisfying
$$
|W|\leq b\kappa.
$$
Proof. Take any participating type $t$. Its prefix ending at $h_t$ contains exactly one sincere winner. Stochastic dominance therefore requires
$$
\frac{|W\cap\operatorname{Top}_{r_t(h_t)}(t)|}{|W|}
\geq\frac1b.
$$
Consequently,
$$
|W|
\leq
b\,|W\cap\operatorname{Top}_{r_t(h_t)}(t)|
\leq
b\,r_t(h_t)
\leq
b\kappa.
$$
The last inequality follows from $s_{r_t(h_t)}=1$. $\square$
Combining these propositions with the fixed-set formulation gives an exact algorithm:
Its running time is
$$
O\left(
\left(
\sum_{j=1}^{\min\{m,b\kappa\}}\binom mj
\right)
\operatorname{poly}(m,\tau,L)
\right).
$$
In particular, exact computation is polynomial-time for fixed $b$ and $\kappa$. If $s_1>s_2$, then $\kappa=1$, so it is polynomial-time for every fixed number of sincere winners.
Assume
$$
\mathcal B=\{a_0,b_0\},
\qquad
s_1>s_2.
$$
For type $t$, let $h_t$ and $\ell_t$ be respectively its higher- and lower-ranked members of $\mathcal B$.
Theorem. The exact threshold is
$$
\theta=
\begin{cases}
0,
&
\text{if some }t\text{ has }
s_{r_t(h_t)}<1
\text{ or }
s_{r_t(\ell_t)}>0,
\\
1,
&
\text{otherwise}.
\end{cases}
$$
In the second case, no manipulation exists.
Proof.
If $s_{r_t(h_t)}<1$ for some type, Section 4.1 proves $\theta=0$.
Suppose instead that $s_{r_t(\ell_t)}>0$ for some type. On an arbitrarily small positive mass, move $\ell_t$ to last position, preserving the order of all other candidates. Its score strictly decreases, while the score of $h_t$ remains unchanged. Every outsider initially has score strictly below $H$, so for sufficiently small mass all outsiders remain below $H$. Hence $h_t$ becomes the unique winner. This type strictly prefers $\{h_t\}$ to the uniform lottery on the two sincere winners, proving $\theta=0$.
It remains to consider the case
$$
s_{r_t(h_t)}=1,
\qquad
s_{r_t(\ell_t)}=0
\quad\text{for every }t.
$$
Because $s_1>s_2$, every type’s sincere first candidate is $h_t\in\mathcal B$.
Suppose a manipulation produces $W$, with $w=|W|$. For every participant, dominance at its first prefix requires
$$
\frac{\mathbf 1_{\{h_t\in W\}}}{w}\geq\frac12.
$$
Thus
$$
h_t\in W,
\qquad
w\leq2.
$$
Strict improvement requires $W\neq\mathcal B$. Since $W$ contains a participant’s first candidate from $\mathcal B$ and has at most two members, it must contain exactly one sincere winner, say $a$, and exclude the other, say $d$.
Every participant then sincerely places $a$ first and gives $d$ score $0$. Its reports cannot increase its contribution to $a$ above its sincere contribution, and cannot decrease its contribution to $d$ below its sincere contribution. Therefore
$$
q_a\leq A_a=H,
\qquad
q_d\geq A_d=H.
$$
This contradicts the requirement that $a$ be a winner while $d$ is strictly below the winning score.
No manipulation exists, so $\theta=1$. $\square$
The criterion requires only the rankings and their positional scores, and is polynomial-time computable.
The unrestricted problem still requires either a polynomial-time algorithm or a valid NP-hardness reduction.
The new results eliminate the unique-sincere-winner case as a source of hardness. They also give polynomial algorithms when both the number of sincere winners and the maximal-score plateau size are fixed. For a strict top score and exactly two sincere winners, they give the stronger explicit classification above.
What remains unresolved is the optimization over final winner sets in unrestricted tied sincere outcomes. No argument here proves that this remaining optimization is polynomial-time, and no hardness reduction is established.
⟨structured verdict parsed — rendered above⟩
The output establishes the three stated special-case results, but does not resolve the unrestricted question in USER_TASK. I found no mathematical error or substantive proof gap in Sections 1–5. The prover’s own description of its contribution as partial is accurate.
The sole major issue relative to the assignment is incomplete coverage: neither a polynomial-time algorithm nor an NP-hardness proof is supplied for unrestricted tied sincere outcomes.
The definition of $E_W$ correctly expresses stochastic dominance. The two lotteries assign prefix probabilities
$$
\frac{|W\cap\operatorname{Top}_k(t)|}{w}
\quad\text{and}\quad
\frac{|\mathcal B\cap\operatorname{Top}_k(t)|}{b},
$$
and multiplying by the positive quantity $bw$ gives exactly the stated inequalities.
The strict-improvement argument also holds. Equality at every prefix implies, by consecutive subtraction, equality of each candidate’s probability. Uniform lotteries with different nonempty supports cannot have identical probability vectors. Thus, for $W\neq\mathcal B$, every eligible type has a strict prefix improvement.
Accordingly, restricting participating types to $E_W$ correctly enforces the participation requirement.
The row and column constraints on $Y$ are necessary: every ranking assigns each candidate one position and fills each position once.
The sufficiency argument is valid. For $C>0$, the displayed calculation verifies Hall’s condition for every set of candidate rows. The graph has equally many candidate and position vertices, so Hall’s theorem supplies the required perfect matching.
Subtracting the minimum matched entry:
No new positive entry appears. Hence the procedure terminates after at most $m^2$ iterations. The resulting coefficients sum to $C$, as follows from any row sum.
Giving each participating type the same ranking mixture realizes the aggregate matrix without imposing any restriction absent from the task. Arbitrary splitting is explicitly allowed. The case $C=0$ is correctly handled separately.
The score expression
$$
q_a=A_a-\sum_t c_t s_{r_t(a)}+\sum_j s_jY_{aj}
$$
therefore correctly represents all permitted reporting strategies.
The auxiliary optimization correctly distinguishes an actual final winner set from a larger tie allowed by the closed constraints.
A positive $\varepsilon$ guarantees both $C>0$ and strict exclusion of every candidate outside $W$. Conversely, a genuine manipulation has positive participating mass and positive exclusion gaps, so a positive common $\varepsilon$ exists.
This also works when $W=\mathcal A$: there are no exclusion constraints, but the condition $C\geq\varepsilon$ still enforces positive participation.
The interpolation argument is sound. Both endpoints satisfy the closed linear constraints. Interpolation with a strict witness gives positive mass and positive exclusion gaps for every positive interpolation parameter. The budget converges to $\alpha_W$.
Thus $\alpha_W$ is indeed the infimum of genuine manipulation budgets for admissible $W$, even when the minimizing closed solution itself is not a manipulation.
The formula for $\theta$ correctly incorporates the default value $1$ and excludes the unchanged lottery on $\mathcal B$.
The LPs have polynomially many variables and constraints. Their coefficients have polynomial encoding length: sincere scores are sums of products of input rationals, and eligibility uses integer prefix counts.
Boundedness is correctly established. In particular, the budget constraints imply $C\leq1$, and the matrix constraints imply $Y_{aj}\leq C$. The remaining optimization variables are explicitly bounded.
The stated rational linear programming theorem applies to these programs, including programs with equality constraints or lower-dimensional feasible regions. The cited [Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time linear programming.
Assessment: The exact formulation and exponential enumeration algorithm are correct.
With sincere outcome $\{b_0\}$, the prefix ending at $b_0$ has sincere probability $1$. Dominance requires the entire final lottery to lie within that prefix. Consequently, every final winner other than $b_0$ must be ranked above $b_0$ by every participant.
Strict improvement excludes $W=\{b_0\}$. Thus the candidate selection from $W\setminus\{b_0\}$ is legitimate.
The normalization forces the score vector to be $(1,0)$. Every possible participant ranks the other candidate first, so changing reports cannot increase that candidate’s score or decrease $b_0$’s score.
The displayed inequalities prevent both a replacement winner and a tie involving the other candidate. The impossibility claim is correct.
For $m\geq3$, the quantities defining $\beta$ and $\rho$ are well-defined because $C>0$ and $m-2>0$.
When $s_2=0$, all scores after first position are zero, so the proposed distribution realizes $\beta=\rho=0$.
When $s_2>0$, the mixture probability $\beta/s_2$ lies in $[0,1/2]$. The two constituent distributions produce the stated average score for $b_0$. Symmetry and conservation of positional score produce the stated average for every remaining candidate.
The strict inequality $\rho<1$ is correctly justified. In this case $\beta>0$, and
$$
\sum_j s_j\leq m-1
$$
uses exactly the hypotheses $s_j\leq1$ and $s_m=0$.
For another final winner $z\neq a,b_0$, the minimizing choice of $S_a$ gives $S_z-S_a\geq0$. Hence
$$
D_a-D_z=C(1-\rho)+S_z-S_a>0.
$$
When $b_0\in W$, rearranging the original score tie gives the stated identity. The estimate uses the valid bounds $R_a\leq C$ and $R_{b_0}\geq0$. Together with
$$
C\beta\leq\frac{A_{b_0}-A_a}{2},
$$
it proves the claimed positive derivative gap.
Candidates outside $W$ have strictly positive original exclusion gaps. Since there are finitely many candidates and each perturbed score is affine in $\delta$, all these gaps persist for sufficiently small positive $\delta$.
A genuine manipulation cannot have budget $u=0$, since all $\mu_t$ are positive and $C>0$. Therefore the use of $0<u<1$ is justified.
The selected $\delta$ ensures both the requested budget bound and enough remaining sincere mass:
$$
(1+\delta)c_t\leq(1+\delta)u\mu_t<\mu_t.
$$
All participating types strictly prefer the new singleton outcome because they rank $a$ above $b_0$. Thus the perturbation satisfies the task’s per-type improvement condition.
Assessment: The perturbation lemma is correct, including score plateaus, outside candidates, and the budget endpoint restriction.
The singleton eligibility characterization is correct.
The inequality $\theta\leq\widehat\theta$ follows because singleton manipulations are permitted manipulations. For $\theta<1$, manipulation budgets approaching $\theta$ can be chosen below $1$, where the perturbation lemma applies. Singleton budgets can then approach each such budget arbitrarily closely from above, establishing the reverse inequality.
For $\theta=1$, the default value in the definition of $\widehat\theta$ gives equality without requiring a perturbation at budget exactly $1$.
Only $m-1$ singleton sets are tested, with polynomial-size LPs.
Assessment: The polynomial-time theorem for a unique sincere winner is established.
If $s_{r_t(h_t)}<1$, the type’s first candidate is outside $\mathcal B$. Swapping it with $h_t$ increases only $h_t$ among the sincere winners; the swapped outsider decreases and all other scores remain unchanged.
Thus $h_t$ becomes the unique winner. Since it is the type’s highest-ranked sincere winner, its singleton lottery strictly dominates the original lottery when $b\geq2$.
Positive $\mu_t$ permits arbitrarily small positive proportional budgets.
Assessment: The proposition proving $\theta=0$ is correct.
If the zero-threshold condition fails, then $r_t(h_t)\leq\kappa$ for every type. For any participant, the prefix ending at $h_t$ contains exactly one sincere winner. The dominance inequality therefore gives precisely the displayed bound
$$
|W|\leq b\kappa.
$$
A genuine manipulation has at least one participant, so the argument always applies.
Enumerating the resulting bounded-size winner sets, while retaining the fixed-set formulation’s exclusion of $W=\mathcal B$, yields the stated running time. It is polynomial when both $b$ and $\kappa$ are fixed. Under $s_1>s_2$, one has $\kappa=1$.
Assessment: Both the support bound and the restricted polynomial-time claims are established.
The first zero-threshold condition correctly invokes Section 4.1.
For the second condition, moving $\ell_t$ to last position strictly reduces its score because its sincere positional score is positive. Candidate $h_t$ precedes $\ell_t$, so its position and score remain unchanged. Outsiders remain below $H$ for sufficiently small participating mass. Thus the claimed improving singleton outcome follows.
In the remaining case, every type places $h_t$ first and assigns score zero to $\ell_t$. Dominance at the first prefix forces every participant’s first candidate into $W$ and gives $|W|\leq2$.
Because $W\neq\mathcal B$, the final set must contain exactly one sincere winner. Every participant therefore sincerely puts that included winner first and assigns the excluded sincere winner zero score.
The bounds
$$
q_a\leq H,\qquad q_d\geq H
$$
are valid and contradict the strict exclusion of $d$ when $a$ is a winner.
Assessment: The explicit criterion and the assertion that no manipulation exists in its second branch are established.
Major issue relative to USER_TASK: the unrestricted complexity classification remains unproved.
The special-case results do not establish polynomial-time computation when tied sincere outcomes have unrestricted $b\kappa$. The enumeration bound can then be exponential. No hardness reduction is supplied.
This is an acknowledged limitation, not a false intermediate claim. The output is useful partial progress and internally consistent.
To complete the assignment, the prover must supply either a polynomial-time exact algorithm covering unrestricted tied sincere outcomes or a valid NP-hardness proof under the stated participation and reporting model. No repair to Sections 1–5 is needed based on this audit; completing the target requires additional mathematics.
⟨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.