Answer: For $\alpha=0$, the problem is $\mathrm{NP}$-complete, even with $\tau=O(m^2)$. For $\alpha=1$, it is polynomial-time solvable in $m,\tau,L$ by a maximum-flow computation.
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCopelandα-manipulation, α ∈{0, 1}, is NP-complete, even for the case of two manipulators. Before we proceed with the proof, let us briefly dis- cuss the proof of a similar theorem of Faliszewski, Hemas- paandra, and Schnoor [13], which shows that Copelandα- manipulation is NP-complete for all rational α’s in (0, 1) − {0.5}, even in the case of two manipulators.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), target \(p\in C\), \(\alpha\in\{0,1\}\), a rational base mass distribution \(\mu\) over strict rankings of \(C\) with total mass \(1-\kappa\), and rational controllable mass \(\kappa>0\), decide whether there is a distribution \(q\) over rankings with total mass \(\kappa\) such that \(p\) is a Copeland\(_\alpha\) winner under the combined masses \(\mu+q\). For each pair \(a,b\in C\), define \(M(a,b)=\sum_r(\mu_r+q_r)(\mathbf{1}[a\succ_r b]-\mathbf{1}[b\succ_r a])\); the score of \(a\) is the number of \(b\) with \(M(a,b)>0\), plus \(\alpha\) times the number with \(M(a,b)=0\).
Let \(C\) be a nonempty candidate set, \(m=|C|\), \(p\in C\), and \(\alpha\in\{0,1\}\). Types are strict total rankings of \(C\); write \(\mathcal R(C)\) for their set.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number \(m!\) of possible rankings.
The input consists of a nonnegative base mass distribution \(\mu\) and a binary rational \(0<\kappa\leq1\), with \(\sum_r\mu_r=1-\kappa\); unlisted types have zero mass. Let \(L\) be the total input bit length, and state running times in \(m,\tau,L\).
A manipulation is any nonnegative rational mass distribution \(q\) on \(\mathcal R(C)\) satisfying \(\sum_r q_r=\kappa\), without a prescribed support or denominator bound.
For distinct \(a,b\in C\), set \(M(a,b)=\sum_{r\in\mathcal R(C)}(\mu_r+q_r)(\mathbf1[a\succ_r b]-\mathbf1[b\succ_r a])\). Use Copeland\(_\alpha\): a head-to-head victory earns one point, a tie earns \(\alpha\), and a loss earns zero. Every candidate with maximal score is a winner, with no further tie-breaking.
For each fixed \(\alpha\in\{0,1\}\), is deciding whether some such \(q\) makes \(p\) a winner solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Discrete unweighted coalitional manipulation is NP-complete for each \(\alpha\in\{0,1\}\), even with exactly two manipulators ([source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2010/pdf/01%20Full%20Papers/07_02_FP_0051.pdf)).
No complexity classification for this exact mass-distribution problem was located in the literature search.
The two parameters have different complexity:
The main new ingredient is a realization lemma: although an arbitrary orientation of the adjustable contests need not be realizable, every outdegree vector obtainable by orienting those contests is realizable by a rational ranking distribution. This suffices for Copeland$_1$, because opponent ties can be replaced by strict outcomes without increasing either participant’s score.
For distinct candidates $a,b$, define the base margin
$$
B(a,b)=\sum_r\mu_r\bigl(\mathbf 1[a\succ_r b]-\mathbf 1[b\succ_r a]\bigr).
$$
Lemma 1. For either $\alpha\in\{0,1\}$, if a successful manipulation exists, one exists in which every manipulating ranking puts $p$ first.
Proof. Move $p$ to the first position in every manipulating ranking, preserving the relative order of all other candidates. Comparisons between opponents are unchanged, and every margin involving $p$ weakly increases in $p$’s favor.
For both permitted parameters, this cannot decrease $p$’s points or increase an opponent’s points. Hence success is preserved. The resulting masses remain nonnegative rational numbers summing to $\kappa$. $\square$
Write $A=C\setminus\{p\}$ and $n=|A|$. After this normalization,
$$
M(p,a)=B(p,a)+\kappa
$$
for every $a\in A$, independently of the remaining manipulation choices.
A normalized manipulation is therefore $\kappa$ times a rational probability distribution on rankings of $A$.
Let $G=(V,E)$ be a finite simple undirected graph. For each ordered adjacent pair $a,b$, prescribe a rational threshold satisfying
$$
0<t_{ab}<1,\qquad t_{ba}=1-t_{ab}.
$$
For a probability distribution on strict rankings of $V$, write
$$
x_{ab}=\Pr(a\succ b).
$$
When $x_{ab}\ne t_{ab}$, orient $\{a,b\}$ from $a$ to $b$ exactly when $x_{ab}>t_{ab}$.
Lemma 2. Suppose an integer vector $d=(d_a)_{a\in V}$ is the outdegree vector of some orientation of $G$. Then there is a rational probability distribution, assigning positive probability to every ranking of $V$, whose threshold comparisons are all strict and have outdegree vector $d$.
Define
$$
R_{ab}=\frac{t_{ab}}{1-t_{ab}},
\qquad R_{ba}=R_{ab}^{-1}.
$$
Among all orientations with outdegree vector $d$, choose an orientation $\sigma$ minimizing
$$
P(\sigma)=\prod_{a\to b\text{ in }\sigma}R_{ab}.
$$
Such a minimum exists because the set of eligible orientations is finite and nonempty.
For every directed simple cycle
$$
a_1\to a_2\to\cdots\to a_\ell\to a_1
$$
of $\sigma$, we have
$$
\prod_{i=1}^{\ell}R_{a_i a_{i+1}}\leq 1,
\qquad a_{\ell+1}=a_1.
$$
Indeed, reversing that cycle preserves every vertex’s outdegree. Its effect on the objective is
$$
\frac{P(\text{reversed orientation})}{P(\sigma)}
=
\left(\prod_{i=1}^{\ell}R_{a_i a_{i+1}}\right)^{-2}.
$$
A cycle product greater than $1$ would therefore contradict minimality.
Construct a directed graph $K$ by replacing each arc $a\to b$ of $\sigma$ with an arc $b\to a$ of multiplicative weight $R_{ab}$. Add a new vertex $s$, with an arc of weight $1$ from $s$ to every vertex.
Every directed simple cycle of $K$ has weight product at most $1$: traversing its edges in reverse order gives a directed cycle of $\sigma$ with the same product. Every closed walk likewise has product at most $1$, by decomposition into simple cycles.
For $a\in V$, let $\lambda_a$ be the maximum product of arc weights along a simple directed path from $s$ to $a$. These maxima exist, are positive, and are rational.
Removing a closed subwalk of product at most $1$ cannot decrease a walk’s product. Consequently, $\lambda_a$ also bounds the product of every directed walk from $s$ to $a$.
For an arc $a\to b$ of $\sigma$, append the arc $b\to a$ to a maximizing path to $b$. This gives
$$
\lambda_a\geq \lambda_b R_{ab}.
$$
Take independent exponential random variables $T_a$, with respective rates $\lambda_a$, and rank candidates by increasing $T_a$.
Their pairwise probabilities are
$$
x_{ab}
=
\Pr(T_a<T_b)
=
\int_0^\infty \lambda_a e^{-\lambda_a t}e^{-\lambda_b t}\,dt
=
\frac{\lambda_a}{\lambda_a+\lambda_b}.
$$
Thus, for every arc $a\to b$ of $\sigma$,
$$
x_{ab}\geq
\frac{R_{ab}}{1+R_{ab}}
=t_{ab}.
$$
This distribution assigns positive rational probability to every ranking. Specifically, for a ranking $r=(r_1,\ldots,r_{|V|})$, its probability is
$$
\rho_r
=
\prod_{j=1}^{|V|}
\frac{\lambda_{r_j}}
{\sum_{k=j}^{|V|}\lambda_{r_k}}.
$$
To verify the formula directly, integrate the joint exponential density over the region
$$
0<T_{r_1}<\cdots<T_{r_{|V|}},
$$
using the successive time differences as integration variables. Each factor in the displayed product results from one integral. Since every $\lambda_a$ is positive rational, so is $\rho_r$.
If $E$ is empty, the constructed distribution already proves the lemma. Otherwise, put
$$
\rho_{\min}=\min_r\rho_r>0,
\qquad
\varepsilon=\frac{\rho_{\min}}{2(|E|+1)}.
$$
For each arc $a\to b$ of $\sigma$, choose two rankings: one beginning with $a,b$, and the other beginning with $b,a$, with all remaining candidates in the same order. Transfer probability $\varepsilon$ from the second ranking to the first.
These two rankings differ only on the comparison between $a$ and $b$. Consequently, this transfer increases $x_{ab}$ by $\varepsilon$ and changes no other pairwise probability.
Across all transfers, any ranking loses at most $|E|\varepsilon<\rho_{\min}/2$. Every ranking therefore retains positive probability. All probabilities remain rational and their sum remains $1$.
Every arc $a\to b$ of $\sigma$ now satisfies
$$
x_{ab}>t_{ab}.
$$
The threshold orientation is exactly $\sigma$, whose outdegree vector is $d$. This proves Lemma 2. $\square$
After putting $p$ first, its score is fixed:
$$
S=
\left|\left\{a\in A:B(p,a)+\kappa\geq0\right\}\right|.
$$
An opponent $a$ receives from its contest against $p$ the fixed contribution
$$
c_a=
\begin{cases}
1,&B(p,a)+\kappa\leq0,\\
0,&B(p,a)+\kappa>0.
\end{cases}
$$
Partition the opponent pairs into:
$$ F=\left\{\{a,b\}\subseteq A:|B(a,b)|<\kappa\right\}. $$
For a fixed pair, its strict orientation is the sign of $B(a,b)$. When equality holds, a manipulation can create a tie but cannot reverse that sign.
Let $w_a$ be the number of fixed opponent contests whose strict orientation favors $a$. Define
$$
u_a=S-c_a-w_a.
$$
Proposition 3. A successful manipulation exists for $\alpha=1$ if and only if the graph $(A,F)$ has an orientation satisfying
$$
\operatorname{outdeg}_F(a)\leq u_a
\qquad\text{for every }a\in A.
$$
Suppose a successful manipulation exists, and normalize it using Lemma 1.
Replace every opponent tie by a strict orientation at the level of the contest outcomes. On a fixed pair, choose the orientation favored by its base margin; on an adjustable pair, either orientation may be chosen.
Under Copeland$_1$, a tie contributes $(1,1)$ to its participants, whereas a strict contest contributes either $(1,0)$ or $(0,1)$. Thus these replacements cannot increase any opponent’s score. They do not change $p$’s score.
After replacement, opponent $a$ has score
$$
c_a+w_a+\operatorname{outdeg}_F(a).
$$
Success therefore implies the stated upper bound.
Suppose a suitable orientation of $(A,F)$ exists, with outdegree vector $d$.
For each adjustable ordered pair, set
$$
t_{ab}=\frac{1-B(a,b)/\kappa}{2}.
$$
The definition of $F$ ensures
$$
0<t_{ab}<1,\qquad t_{ba}=1-t_{ab}.
$$
Apply Lemma 2. It supplies a full-support rational ranking distribution on $A$, with strict threshold outcomes and outdegree vector $d$. Multiply its probabilities by $\kappa$ and put $p$ first in every ranking.
For an adjustable pair,
$$
M(a,b)
=
B(a,b)+\kappa(2x_{ab}-1)
=
2\kappa(x_{ab}-t_{ab}).
$$
Hence its actual contest orientation is precisely its threshold orientation.
Every fixed pair also has the required strict outcome. For example, if $B(a,b)\geq\kappa$, then
$$
M(a,b)=B(a,b)-\kappa+2\kappa x_{ab}>0,
$$
because full support gives $x_{ab}>0$. The negative case follows by antisymmetry.
Thus opponent $a$ has score
$$
c_a+w_a+d_a\leq S,
$$
so $p$ is a winner. This proves Proposition 3. $\square$
Reject immediately if any $u_a<0$. Otherwise, build a flow network with:
An integral flow of value $|F|$ assigns each adjustable contest’s single point to one endpoint, respecting all score bounds. Conversely, any eligible orientation supplies such a flow. Integer capacities ensure that a maximum integral flow can be found by augmenting paths.
The network has $O(m^2)$ vertices and arcs. At most $|F|=O(m^2)$ augmentations are needed, each found in $O(m^2)$ time.
Base margins can be computed exactly using a common denominator whose bit length is $O(L)$. Using elementary integer arithmetic gives, conservatively, the total bit-operation bound
$$
O\!\left((\tau+1)m^2L^2+m^4\log(m+1)\right).
$$
The algorithm performs rational margin comparisons and an integer maximum-flow computation. The multiplicative optimization in Lemma 2 is used only to prove that the flow criterion is sufficient.
Proposition 4. Both variants belong to $\mathrm{NP}$. Every positive instance has a certificate using at most
$$
D+1,\qquad D=\binom{m-1}{2},
$$
manipulating rankings, with each mass having bit length
$$
O\!\left(L+m^2\log(m+1)\right).
$$
Proof. Normalize a successful manipulation. Its opponent-margin vector lies in the real convex hull of the pairwise vectors of opponent rankings. Carathéodory’s theorem in dimension $D$ gives a representation using $s\leq D+1$ rankings.
This use of a real convex hull does not assert that irrational points are rationally achievable. We next obtain rational coefficients with bounded encoding length.
Fix those rankings and the successful sign of each opponent margin. Let their masses be $w_1,\ldots,w_s$, and introduce a slack variable $\delta$. Impose
$$
w_i\geq0,\qquad
\sum_{i=1}^s w_i=\kappa,\qquad
0\leq\delta\leq1.
$$
For each prescribed positive margin require it to be at least $\delta$; for each negative margin require it to be at most $-\delta$; for each tie require equality to zero. Maximize $\delta$.
The representation just selected permits positive slack: choose it below the minimum absolute value of the finitely many strict margins. If there are no strict margins, $\delta=1$ is feasible.
The feasible polyhedron is bounded. An optimum therefore occurs at a vertex, and its optimal slack is positive. Its defining constraints have coefficients in $\{-1,0,1\}$ and right-hand sides with a common denominator of $O(L)$ bits.
A vertex is determined by a nonsingular square system of size at most $D+2$. Hadamard’s determinant bound and Cramer’s rule give coordinate bit length
$$
O\!\left(L+(D+2)\log(D+2)\right).
$$
The resulting rational masses preserve all prescribed signs and ties, and hence preserve success.
A verifier checks the rankings, masses, total mass, margins, and scores by exact rational arithmetic in polynomial time in $m,\tau,L$. $\square$
Define the linear ordering polytope
$$
P_{\mathrm{LO}}(n)=
\operatorname{conv}\left\{
\bigl(\mathbf 1[i\succ_r j]\bigr)_{i<j}
:r\text{ is a strict ranking of }[n]
\right\}.
$$
Exact membership for binary rational points in this polytope is $\mathrm{NP}$-hard under polynomial-time many-one reductions. Here is the precise connection to known results.
Membership in the correlation polytope
$$
Q(h)=\operatorname{conv}
\left\{(v_iv_j)_{i\leq j}:v\in\{0,1\}^h\right\}
$$
is $\mathrm{NP}$-complete. [Pitowsky, *Correlation polytopes: Their geometry and complexity*](https://link.springer.com/article/10.1007/BF01594946).
Maksimenko’s theorem identifies $Q(h)$ with a face of $P_{\mathrm{LO}}(2h)$. Set $a_i=2i-1$, $b_i=2i$. The affine map is
$$
z_{a_i,b_i}=x_{ii},
$$
and, for $i<j$,
$$
z_{b_i,a_j}=0,\qquad
z_{b_i,b_j}=x_{jj}-x_{ij},
$$
$$
z_{a_i,b_j}=x_{ii}+x_{jj}-x_{ij},
\qquad
z_{a_i,a_j}=x_{ii}-x_{ij}.
$$
Its image lies in the affine space defining that face:
$$
z_{b_i,a_j}=0,
$$
$$
z_{a_i,b_i}+z_{b_i,b_j}-z_{a_i,b_j}=0,
$$
$$
z_{a_i,a_j}+z_{a_j,b_j}-z_{a_i,b_j}=0.
$$
The inverse recovers
$$
x_{ii}=z_{a_i,b_i},
\qquad
x_{ij}=z_{a_j,b_j}-z_{b_i,b_j}.
$$
Thus membership of the image in the linear ordering polytope is equivalent to membership of $x$ in $Q(h)$; all transformations have polynomial encoding length. [Maksimenko, Theorem 1](https://arxiv.org/html/1704.06170v1).
If an image coordinate lies outside $[0,1]$, the source instance is negative and can be replaced by a fixed negative membership instance. For example, the three coordinates
$$
z_{12}=z_{23}=1,\qquad z_{13}=0
$$
cannot arise from a ranking distribution: the first two probabilities force $1\succ2\succ3$ almost surely.
Consequently, membership remains $\mathrm{NP}$-hard for inputs
$$
z\in[0,1]^{\binom n2},
\qquad n\geq2.
$$
Lemma 5. Suppose rational antisymmetric margins $b(a,b)$ satisfy
$$
S_b=\sum_{\{a,b\}}|b(a,b)|\leq1-\kappa.
$$
A base distribution of mass $1-\kappa$ realizing them can be constructed with at most
$$
2\binom m2+2
$$
ranking types, in polynomial time in their encoding length and $m$.
Proof. For a desired positive margin $b(a,b)=t$, list the remaining candidates as $c_1,\ldots,c_{m-2}$. Give mass $t/2$ to each ranking
$$
a\succ b\succ c_1\succ\cdots\succ c_{m-2},
$$
$$
c_{m-2}\succ\cdots\succ c_1\succ a\succ b.
$$
They agree on the target pair and disagree on every other pair. Their combined contribution is therefore margin $t$ on that pair, zero elsewhere, and total mass $t$. For a negative margin, interchange $a$ and $b$.
Combining these constructions uses total mass $S_b$. Assign half the residual mass to any ranking and half to its reverse; their margins cancel. Aggregating identical rankings and omitting zero masses gives the stated support bound. $\square$
Take an instance
$$
z\in[0,1]^{\binom n2}
$$
of linear ordering polytope membership.
Create candidates
$$
\{p\}\cup A\cup E,
\qquad
A=\{a_1,\ldots,a_n\},
\qquad
E=\{e_1,\ldots,e_n\}.
$$
Thus $m=2n+1$. Set
$$
N=\binom m2,\qquad
\kappa=\frac{1}{4N+1}.
$$
Prescribe these base margins:
$$ B(a_i,a_j)=\kappa(1-2z_{ij}). $$
Every absolute prescribed margin is at most $2\kappa$. Hence
$$
S_b\leq2\kappa N
=
\frac{2N}{4N+1}
<
\frac{4N}{4N+1}
=
1-\kappa.
$$
Lemma 5 constructs a valid explicit base society with $\tau=O(m^2)$. Its input length and construction time are polynomial in the source encoding length.
A manipulation of mass $\kappa$ changes any margin by at most $\kappa$. All contests outside $A$ therefore retain their prescribed strict outcomes.
Under Copeland$_0$:
Thus
$$
p\text{ is a winner}
\quad\Longleftrightarrow\quad
\text{every contest within }A\text{ ties}.
$$
A strict contest within $A$ gives its winner score at least $n+1$. Conversely, if every such contest ties, no candidate exceeds $n$.
For any manipulation $q$, define
$$
x_{ij}
=
\frac{1}{\kappa}
\sum_r q_r\,\mathbf 1[a_i\succ_r a_j].
$$
Restricting the manipulating rankings to $A$ shows that
$$
x\in P_{\mathrm{LO}}(n).
$$
Moreover,
$$
M(a_i,a_j)
=
\kappa(1-2z_{ij})+\kappa(2x_{ij}-1)
=
2\kappa(x_{ij}-z_{ij}).
$$
Every original contest ties exactly when $x=z$. Hence any successful manipulation proves that $z$ belongs to the polytope.
Conversely, suppose $z\in P_{\mathrm{LO}}(n)$. It has a rational convex representation by ranking vertices. To justify rationality, select an affinely independent representation: its coefficients are the unique solution of a full-column-rank linear system with integer coefficients and rational right-hand side, so they are rational.
Multiply those coefficients by $\kappa$ and extend the rankings to all candidates. The resulting manipulation ties every original contest and makes $p$ a winner.
This proves a polynomial-time many-one reduction. Proposition 4 then establishes $\mathrm{NP}$-completeness for $\alpha=0$.
For $\alpha=1$, the exact decision algorithm runs in
$$
O\!\left((\tau+1)m^2L^2+m^4\log(m+1)\right)
$$
bit operations using the elementary implementations described above.
For $\alpha=0$, the problem is $\mathrm{NP}$-complete, with polynomial-size certificates. An exact general algorithm is obtained by enumerating the $3^{\binom{m-1}{2}}$ opponent sign patterns and testing each by a slack-variable linear program over the $(m-1)!$ opponent rankings. Its running time is
$$
2^{O(m^2)}\operatorname{poly}(m,\tau,L).
$$
The distinction is substantive: Copeland$_0$ can force exact pairwise probabilities through ties, whereas Copeland$_1$ permits reduction to strict contests and their outdegree bounds.
⟨structured verdict parsed — rendered above⟩
The claimed classification is correct in substance: the argument establishes $\mathrm{NP}$-completeness for $\alpha=0$ and polynomial-time solvability for $\alpha=1$. I found no major mathematical error. Two minor clarifications would make the write-up fully explicit.
1. Normalization: Lemma 1
Moving $p$ first preserves all comparisons between opponents and weakly increases every margin in $p$’s favor.
For both permitted values of $\alpha$, increasing such a margin cannot decrease $p$’s contribution or increase the opponent’s contribution. This includes transitions through a tie. Rationality, nonnegativity, and total manipulating mass are preserved.
Consequently, the displayed formula
$$
M(p,a)=B(p,a)+\kappa
$$
and the reduction to distributions on rankings of $A$ are valid.
2. Threshold realization: Lemma 2
All substantive steps check out.
The lemma realizes an orientation with the required outdegree vector, which is exactly what Proposition 3 needs. It does not incorrectly assert realization of every specified orientation.
The construction also accommodates isolated vertices and an empty edge set. Its potentially large support is permissible under the task and is not used as an algorithmic output.
3. Polynomial algorithm for $\alpha=1$: Proposition 3
The score formulas correctly handle ties against $p$. In particular, when
$$
B(p,a)+\kappa=0,
$$
both candidates receive one point.
The partition into adjustable and fixed pairs is correct:
The necessity argument is sound. Replacing an opponent tie by either strict outcome changes contributions from $(1,1)$ to $(1,0)$ or $(0,1)$, so no opponent’s score increases. This is an argument about outcome vectors; it does not assume the replaced orientation is immediately realizable.
For sufficiency, Lemma 2 supplies the required adjustable outdegrees. The margin identity
$$
M(a,b)=2\kappa(x_{ab}-t_{ab})
$$
is correct. Full support ensures that fixed contests are strict even at the boundary $|B(a,b)|=\kappa$. Therefore the final opponent scores satisfy the required bounds.
The maximum-flow formulation correctly assigns each adjustable contest’s point to its winning endpoint. Integer capacities justify integral augmentations. There are at most $|F|$ augmentations, and the claimed network size and flow running time are valid.
The rational-arithmetic bound is conservative but consistent: a common denominator can have $O(L)$ bits, and exact margin computations and comparisons fit the displayed bound. The realization lemma’s multiplicative optimization is correctly excluded from the decision algorithm.
4. Polynomial certificates: Proposition 4
The certificate argument is sound after one normalization clarification.
Carathéodory’s theorem applies to a point in the convex hull of opponent-ranking comparison vectors in dimension $D$, yielding at most $D+1$ rankings. The subsequent slack program correctly preserves positive margins, negative margins, and exact ties.
Positive slack exists for a successful sign pattern: there are finitely many strict margins, and their minimum absolute value is positive. When there are no strict margins, the stated choice of slack is feasible.
The feasible set is nonempty and bounded. An optimum at a vertex therefore exists. The coefficient restrictions, common-denominator bound, and system size support the stated coordinate encoding bound through Hadamard’s bound and Cramer’s rule. Exact verification of the resulting certificate is polynomial.
Minor issue 1 — specify the vector used for Carathéodory.
The phrase “Its opponent-margin vector” does not specify whether it means total election margins, manipulating margins, or manipulating margins divided by $\kappa$. The transition to masses summing to $\kappa$ requires the last interpretation. Minimum clarification: explicitly identify the normalized manipulating comparison vector to which Carathéodory’s theorem is applied. This is an expositional issue, not a missing mathematical ingredient.
5. Polytope-membership hardness source
The cited correlation-polytope membership result supports the hardness premise. Pitowsky’s publisher abstract states the membership problem is $\mathrm{NP}$-complete; the full-coordinate formulation is also identified in the research literature. [Pitowsky](https://link.springer.com/article/10.1007/BF01594946), [Krause et al., Proposition 1.1 and Remark 1.2](https://optimization-online.org/wp-content/uploads/2017/08/6168.pdf).
The affine map, face equations, and inverse in the output agree with Maksimenko’s theorem and its proof. The coordinates use the same ordering convention. The source establishes an affine equivalence with the face, so the asserted membership equivalence follows; it is not merely an equivalence with a projection. [Maksimenko, Theorem 1 and its proof](https://arxiv.org/html/1704.06170v1).
The map has polynomial encoding length. Rejecting images with a coordinate outside $[0,1]$ is justified, and the supplied fixed negative instance is valid: its first two coordinates force a transitive comparison contradicted by the third.
6. Base-margin realization: Lemma 5
The two rankings agree on the target pair and disagree on every other pair, including comparisons between remaining candidates. Their combined target margin and total mass are both $t$.
Superposition therefore realizes the prescribed margins using total mass $S_b$. A ranking and its reverse cancel every margin, so the residual-mass construction is valid. Aggregation and removal of zero masses preserve the support bound and the required support-list representation.
The degenerate cases of fewer than two candidates require no pair gadgets and are covered by the residual construction.
7. Election reduction for $\alpha=0$
The construction specifies every candidate pair. The chosen $\kappa$ is positive, rational, and at most $1$. The bound
$$
S_b\leq 2\kappa N<1-\kappa
$$
is correct, so Lemma 5 produces a valid base society of the required total mass with $\tau=O(m^2)$.
A manipulating mass of $\kappa$ changes any margin by at most $\kappa$. Hence every prescribed margin of magnitude $2\kappa$ retains its strict outcome.
The score accounting is correct:
Thus a strict original contest prevents $p$ from winning, while ties in all original contests make $p$ a winner.
Restricting manipulating rankings to $A$ yields a point of the linear ordering polytope. The displayed margin calculation correctly forces that point to equal $z$.
Conversely, the rationality argument for an affinely independent convex representation is valid, provided the linear system includes the normalization equation for the coefficients, as is implicit in “convex representation.” Extending those rankings to all candidates cannot alter their comparisons within $A$ or the fixed outside outcomes.
The reduction is therefore a valid polynomial-time many-one reduction. Together with Proposition 4, it establishes the claimed $\mathrm{NP}$-completeness.
8. Final exponential-time algorithm and boundary cases
The enumeration and explicit linear-program sizes are consistent with
$$
2^{O(m^2)}\operatorname{poly}(m,\tau,L).
$$
The factorial number of ranking variables is absorbed by this bound.
Minor issue 2 — state the enumeration’s acceptance rule.
Section 6 says to test every sign pattern but leaves the success and strict-feasibility tests implicit. Minimum clarification: specify that only patterns making $p$ a winner qualify, and that strict signs require a positive optimal slack rather than merely feasibility with zero slack. These conditions already appear in the preceding arguments; making them explicit requires no new mathematics.
For $m=1$, the opponent set is empty and $p$ is automatically a winner; the flow criterion gives the same answer. For $\kappa=1$, the base distribution is empty and the arguments remain applicable. No denominator restriction or prescribed manipulation support has been silently imposed.
The two classifications concern different fixed values of $\alpha$, not different input encodings. Accordingly, the JSON records “hardness” for the established $\alpha=0$ result; the polynomial result for $\alpha=1$ is also accepted.
⟨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.