Answer: In \(\mathrm{P}\) for every fixed rational \(\alpha\in[0,1]\), with \(m=3\); an exact algorithm uses \(O(\tau)\) arithmetic operations and \(O(\tau L^2)\) bit operations.
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet α be a rational number such that 0 ≤α < 1. Then Copelandα-weighted-manipulation is NP- complete when considering elections with exactly 3 candi- dates. For α = 1 the same problem is in P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix \(C=\{p,a,b\}\) and rational \(\alpha\in[0,1]\). An instance gives rational masses \(\nu_{r,w}\) of fixed voters by ranking \(r\) and weight \(w\), and masses \(\lambda_w\) of controllable voters by weight, with total mass \(1\). Choose \(x_{w,\pi}\ge 0\) for each weight \(w\) and ranking \(\pi\in S_3\), with \(\sum_{\pi\in S_3}x_{w,\pi}=\lambda_w\). Is there an allocation \(x\) for which \(p\) is a Copeland\(_\alpha\) winner, using weighted pairwise margins from the fixed and allocated masses?
Fix \(C=\{p,a,b\}\), with \(m=3\), and a rational constant \(\alpha\in[0,1]\). Rankings are strict linear orders; \(S_3\) denotes their set. Weights \(w\) are nonnegative integers encoded in binary.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Fixed types \((r,w)\) have masses \(\nu_{r,w}\); controllable types \(w\) have masses \(\lambda_w\). Here \(\tau\) counts these listed types, not possible rankings or weights, and \(\sum_{r,w}\nu_{r,w}+\sum_w\lambda_w=1\).
An allocation consists of real masses \(x_{w,\pi}\geq0\), with \(\sum_{\pi\in S_3}x_{w,\pi}=\lambda_w\) for every controllable weight. Controllable mass may be split freely among rankings, retaining its weight.
For distinct candidates \(c,d\), define \(\sigma_r(c,d)=1\) if \(r\) ranks \(c\) above \(d\), and \(-1\) otherwise. The pairwise margin is \(M(c,d)=\sum_{r,w}w\nu_{r,w}\sigma_r(c,d)+\sum_{w,\pi}wx_{w,\pi}\sigma_\pi(c,d)\).
Under \(\mathrm{Copeland}_\alpha\), a candidate receives one point for each positive margin, \(\alpha\) points for each zero margin, and zero for each negative margin. All candidates of maximum score are winners; no tie-breaking is applied. The decision problem asks whether some allocation makes \(p\) a winner, possibly tied.
For each fixed rational \(\alpha\in[0,1]\), is this continuous manipulation problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m=3\), \(\tau\), and the total input bit length \(L\).
Discrete weighted manipulation with exactly three candidates and this winner convention is \(\mathrm{NP}\)-complete for every fixed rational \(0\leq\alpha<1\), and in \(\mathrm{P}\) for \(\alpha=1\). [Source](https://www.ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0293.pdf)
No result settling this exact divisible-mass formulation was located in the literature search.
For every fixed rational \(\alpha\in[0,1]\), the continuous manipulation problem with \(m=3\) is in \(\mathrm{P}\).
An exact algorithm uses \(O(\tau)\) arithmetic operations and \(O(\tau L^2)\) bit operations with schoolbook integer arithmetic. Whenever manipulation is possible, there is a rational allocation using only the rankings \(p>a>b\) and \(p>b>a\).
Define the score contribution of a margin by
\(f_\alpha(t)=1\) if \(t>0\), \(f_\alpha(t)=\alpha\) if \(t=0\), and \(f_\alpha(t)=0\) if \(t<0\).
Because \(0\leq\alpha\leq1\), this function is nondecreasing.
Take any allocation. In every controllable ranking, move \(p\) to first place while preserving the relative order of \(a\) and \(b\). Transfer each allocated mass to the resulting ranking, retaining its weight. This preserves the mass constraint for every controllable type.
For \(c\in\{a,b\}\), the transformation changes each controllable contribution to the margin \(M(p,c)\) from either sign to the positive sign. Nonnegative weights therefore imply
\(M'(p,c)\geq M(p,c)\).
Consequently, \(p\)’s score does not decrease. Candidate \(c\)’s contribution from its contest against \(p\), namely \(f_\alpha(-M(p,c))\), does not increase. The margin between \(a\) and \(b\) is unchanged, so neither rival’s total score increases.
Thus, if \(p\) was a winner, it remains a winner after this transformation. Conversely, an allocation putting \(p\) first is an allowed allocation. Hence it suffices to consider the two rankings \(p>a>b\) and \(p>b>a\).
Let the fixed contributions be
\(F_{cd}=\sum_{r,w}w\nu_{r,w}\sigma_r(c,d)\),
and let the total controllable weighted mass be
\(W=\sum_w w\lambda_w\).
Once all controllable mass ranks \(p\) first, the two margins involving \(p\) are fixed:
\(A=M(p,a)=F_{pa}+W,\qquad B=M(p,b)=F_{pb}+W.\)
Write \(D=F_{ab}\). If \(y_w\) is the mass of controllable type \(w\) assigned to \(p>a>b\), then the remaining mass \(\lambda_w-y_w\) is assigned to \(p>b>a\). Therefore
\(q=M(a,b)=D+\sum_w w(2y_w-\lambda_w),\qquad 0\leq y_w\leq\lambda_w.\)
Since \(w\geq0\), every such margin lies in
\(I=[D-W,D+W].\)
Every point of this interval is attainable. If \(W>0\) and \(q\in I\), set
\(\theta=\dfrac{q-D+W}{2W}.\)
The interval condition gives \(0\leq\theta\leq1\). Assign, for every controllable type,
\(x_{w,p>a>b}=\theta\lambda_w,\qquad x_{w,p>b>a}=(1-\theta)\lambda_w.\)
These masses are nonnegative and sum to \(\lambda_w\). Their margin between \(a\) and \(b\) is
\(D+(2\theta-1)W=q.\)
If \(W=0\), the interval is the singleton \(\{D\}\), and assigning every controllable type to \(p>a>b\) realizes it. This also handles controllable types of weight zero.
Thus \(I\) is exactly the attainable set of margins between \(a\) and \(b\).
Define
\(P=f_\alpha(A)+f_\alpha(B),\qquad u=f_\alpha(-A),\qquad v=f_\alpha(-B).\)
For an attainable margin \(q\), the three scores are
\(\operatorname{score}(p)=P,\qquad \operatorname{score}(a)=u+f_\alpha(q),\qquad \operatorname{score}(b)=v+f_\alpha(-q).\)
Let \(\ell=D-W\) and \(h=D+W\). The algorithm accepts precisely when at least one row of the following table has all its conditions satisfied.
| Sign of the remaining margin | Attainability condition | Conditions for \(p\) to be a winner |
|---|---|---|
| \(q<0\) | \(\ell<0\) | \(P\geq u\) and \(P\geq v+1\) |
| \(q=0\) | \(\ell\leq0\leq h\) | \(P\geq u+\alpha\) and \(P\geq v+\alpha\) |
| \(q>0\) | \(h>0\) | \(P\geq u+1\) and \(P\geq v\) |
The attainability conditions follow directly from the closed interval \(I\). For example, a negative margin exists exactly when its lower endpoint is negative. The score conditions follow by substituting the corresponding values of \(f_\alpha(q)\) and \(f_\alpha(-q)\).
Correctness. If a row passes, choose \(q=\ell\), \(q=0\), or \(q=h\), respectively. Section 2 constructs an allocation realizing that margin, and the row’s score inequalities make \(p\) a winner.
Conversely, any successful allocation can be transformed as in Section 1. Its remaining margin lies in \(I\) and has exactly one of the three signs. Its attainability and winning inequalities therefore satisfy the corresponding row.
This proves both directions of the decision rule, including all pairwise ties and ties for maximum score.
For \(m=3\), each listed fixed type contributes to three margins, and each listed controllable type contributes to \(W\). Computing \(F_{pa},F_{pb},F_{ab},W\) takes \(O(\tau)\) arithmetic operations. The subsequent three-case test takes \(O(1)\) operations.
To establish a bit bound, write each listed mass as \(n_i/d_i\), with \(d_i>0\), and form the common denominator
\(Q=\prod_i d_i.\)
Its bit length is \(O(L)\), since the sum of the encoded denominator lengths is at most \(L\). Compute all four aggregates as integers scaled by \(Q\), using contributions of the form
\(w_i n_i(Q/d_i).\)
These integers and their partial sums have \(O(L)\) bits. Indeed, the masses are nonnegative and sum to one, so every partial weighted sum has magnitude at most the largest listed weight; after scaling, its magnitude is at most \(Q\) times that weight. Signed fixed-margin sums satisfy the same bound.
There are \(O(\tau)\) integer multiplications, exact divisions, and additions. Schoolbook arithmetic therefore gives the explicit bound
\(T(m=3,\tau,L)=O(\tau L^2)\)
bit operations. Comparisons of scores take constant time because \(\alpha\) is fixed. The algorithm processes only the listed support; it does not enumerate weights up to their numerical values.
For an accepted row, the selected margin \(q\) is rational. When \(W>0\), the construction’s \(\theta\) and each allocated mass have \(O(L)\)-bit rational representations. Thus successful real allocations can always be replaced by rational allocations of polynomial total encoding length.
The cited discrete classification appears in [Theorem 4.1 of *Copeland Voting: Ties Matter*](https://www.ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0293.pdf). It does not extend to the divisible formulation: here the common fractional split \(\theta\) realizes every margin in \([D-W,D+W]\), including an exact zero whenever the interval contains it.
The continuous problem is therefore polynomial-time solvable for every fixed rational \(\alpha\in[0,1]\), with no unresolved cases.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. For every fixed rational \(\alpha\in[0,1]\), its algorithm decides continuous manipulation with \(m=3\) in polynomial time. The stated bounds of \(O(\tau)\) arithmetic operations and \(O(\tau L^2)\) bit operations are justified. No major or minor issues were found.
The function \(f_\alpha\) is nondecreasing precisely because \(0\leq\alpha\leq1\). This includes both endpoints.
Moving \(p\) to first place while preserving the relative order of \(a\) and \(b\) produces a strict ranking. Transferring mass within each controllable weight preserves nonnegativity, total mass, and weight.
For each rival \(c\), every affected contribution to \(M(p,c)\) either remains unchanged or changes from \(-wx\) to \(wx\). Nonnegative weights and allocated masses therefore justify \(M'(p,c)\geq M(p,c)\).
The score comparison is valid:
Consequently, an existing winner remains a winner, including when the original victory was tied. The converse follows because the restricted rankings are permitted allocations. Thus the reduction preserves existence of a successful allocation in both directions.
Finding: Correct and complete.
The formulas for \(A\) and \(B\) correctly account for all controllable mass placing \(p\) first.
For the remaining margin, the expression
\(q=D+\sum_w w(2y_w-\lambda_w)\)
correctly gives opposite signs to the two available rankings. Since \(0\leq y_w\leq\lambda_w\) and \(w\geq0\), the asserted interval bound follows.
The construction establishing attainability is valid for every real \(q\) in the interval. When \(W>0\), the interval inequalities ensure that the stated \(\theta\) lies in \([0,1]\). The assignments preserve every controllable type’s mass, and substitution gives exactly the requested margin.
The separate treatment of \(W=0\) avoids division by zero. Because all terms \(w\lambda_w\) are nonnegative, controllable contributions then vanish, so the attainable interval is indeed the singleton \(\{D\}\). The argument also covers absent controllable types and controllable types of weight zero.
Finding: Correct and complete.
The three score formulas follow directly from the definition of Copeland scoring and antisymmetry of the margins.
Each table row is correct:
The attainability tests correctly distinguish strict signs from zero. In particular, \(\ell=0\) does not permit a negative margin, and \(h=0\) does not permit a positive margin. The zero case correctly requires both endpoint inequalities.
For sufficiency, the selected endpoint or zero belongs to the interval and has the required sign whenever its row passes. Section 2 supplies the corresponding allocation.
For necessity, Section 1 transforms any successful allocation into the restricted form. Its remaining margin belongs to the interval and satisfies exactly one sign case. Its winning scores therefore satisfy that row’s inequalities.
All winning comparisons are weak inequalities, as required by the task’s convention that tied maximum scores count as victories.
Finding: Correct and complete, including pairwise ties and ties between winners.
With \(m=3\), each listed type requires only a constant number of contributions. Therefore aggregate computation uses \(O(\tau)\) arithmetic operations, followed by a constant number of decision operations.
The common denominator construction has the claimed size: the bit length of \(Q=\prod_i d_i\) is bounded by the sum of the denominator bit lengths, hence is \(O(L)\).
The scaled contributions, aggregate integers, and intermediate products have \(O(L)\) bits. The normalization of the masses and nonnegativity of weights justify the bound on partial weighted sums. For signed fixed-margin sums, the corresponding absolute-value bound also holds.
Forming \(Q\), computing the exact quotients \(Q/d_i\), and accumulating the scaled contributions require \(O(\tau)\) integer operations. Schoolbook multiplication and division on operands of \(O(L)\) bits support the stated \(O(\tau L^2)\) total bound.
The score comparisons take constant time after the margin signs are known: for fixed \(\alpha\), each score belongs to a fixed finite set of constants. This claim does not treat comparisons of the input-dependent margins as constant-time bit operations.
The algorithm depends on the listed support, with no enumeration over numerically possible weights.
Finding: The stated running times are justified for \(m=3\).
The selected \(q\) is an endpoint or zero, so it is rational with \(O(L)\)-bit representation. For \(W>0\), the displayed expression for \(\theta\) uses rational quantities of that size and preserves an \(O(L)\)-bit representation. Multiplying by each listed mass preserves the same asymptotic bound.
There are at most two nonzero allocation entries per controllable type. Thus the total witness encoding length is polynomial. When \(W=0\), the specified allocation uses the input masses directly.
Finding: The rational-witness claim is justified.
The ancillary discrete classification matches Theorem 4.1: it concerns exactly three candidates, making the designated candidate one of the winners, NP-completeness for fixed rational \(0\leq\alpha<1\), and membership in P for \(\alpha=1\). [*Copeland Voting: Ties Matter*, Theorem 4.1](https://www.ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0293.pdf)
The continuous proof does not rely on that theorem. Its interval construction explicitly uses divisible allocations, so the cited discrete hardness is not being applied to a formulation outside its hypotheses.
Finding: The citation is accurate, and the continuous classification is independently established.
No repair or additional clarification is required. The output establishes the requested classification for every permitted fixed \(\alpha\), with the requested dependence on \(\tau\) and \(L\).
⟨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.