Answer: The problem is in \(\mathrm P\) for every fixed rational \(\alpha\in[0,1)\), with running time \(O((\tau+1)m^2L^2)\) in bit operations.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe weighted manipulation problem for Copelandα is polynomial-time solvable in single-peaked elections, for every 0 ≤α < 1. PROOF. We first give the proof for the unique-winner model with three candidates. To this end, we derive a polynomial-time algorithm. First observe that ranking the distinguished candidate p in the top is always the optimal choice.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a known left-to-right order \(L\), a target \(p\), a fixed rational \(\alpha\in[0,1)\), a rational mass distribution over nonmanipulator rankings that are single-peaked with respect to \(L\), and a strategic bloc of mass \(\beta\), does there exist an allocation of that bloc among \(L\)-single-peaked rankings that makes \(p\) a Copeland\(_\alpha\) co-winner?
Given a nonempty candidate set \(C\) of size \(m\), a known axis \(A\), a target \(p\in C\), and a fixed rational \(\alpha\in[0,1)\), all rankings are strict complete orders single-peaked with respect to \(A\).
A society is given by its support: the list of its \(\tau\) ranking types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible rankings. The nonmanipulator masses \(w_1,\ldots,w_\tau\) sum to \(1\); an additional strategic bloc has binary-rational mass \(\beta\geq0\).
Let \(\mathcal R_A\) be all rankings single-peaked with respect to \(A\). An allocation assigns nonnegative real masses \(x_r\) to \(r\in\mathcal R_A\), with \(\sum_{r\in\mathcal R_A}x_r=\beta\); it may use types absent from the input support.
For distinct candidates \(a,b\), define \(N(a,b)=\sum_{i:a\succ_i b}w_i+\sum_{r:a\succ_r b}x_r\). Apply Copeland\(_\alpha\) using these pairwise masses, with exact equality giving a pairwise tie. Success means that \(p\) has maximum score, allowing other winners and also allowing \(p\) to be the unique winner; there is no tie-breaking.
For every fixed rational \(\alpha\in[0,1)\), is deciding whether such an allocation exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\).
Discrete weighted manipulation with strict complete single-peaked rankings on a supplied axis is polynomial-time solvable for every \(\alpha\in[0,1)\), in both winner models. [Yang (2015)](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p77.pdf)
No result settling exactly the divisible-mass problem above was located in the literature search.
For every fixed rational \(\alpha\in[0,1)\), the problem is in \(\mathrm P\).
More strongly, a successful allocation exists if and only if allocating the entire strategic mass to one of two explicit rankings succeeds. This gives an algorithm using \(O((\tau+1)m^2)\) arithmetic operations and, conservatively, \(O((\tau+1)m^2L^2)\) bit operations.
Write the axis as \(c_1<_A\cdots<_A c_m\), with \(p=c_k\). The two rankings are
\(r_L:\quad p\succ c_{k-1}\succ\cdots\succ c_1\succ c_{k+1}\succ\cdots\succ c_m,\)
\(r_R:\quad p\succ c_{k+1}\succ\cdots\succ c_m\succ c_{k-1}\succ\cdots\succ c_1.\)
Empty blocks are omitted. Both rankings are strict, complete, and single-peaked on \(A\).
The proof has two parts: transferring a known discrete normalization result to real allocations, and showing that a successful allocation normalized in this way can be replaced by one of these two rankings.
For distinct candidates \(a,b\), define the pairwise margin
\(M(a,b)=N(a,b)-N(b,a).\)
Suppose that a successful real allocation \(x\) exists, and let \(S=\{r:x_r>0\}\). The set \(S\) is finite because there are finitely many complete rankings.
Consider variables \(z_r\) for \(r\in S\). Impose the following linear equations:
Here \(M_z\) includes the fixed nonmanipulator contribution. All coefficients and right-hand sides are rational, and \(x|_S\) satisfies the equations.
Gaussian elimination therefore expresses their solution set as
\(z=z^{(0)}+\sum_{j=1}^{d}t_jv^{(j)},\)
where \(z^{(0)}\) and all \(v^{(j)}\) have rational coordinates. Approximating the real parameters representing \(x|_S\) by rational parameters gives rational solutions arbitrarily close to \(x|_S\).
Choose such a solution sufficiently close that every coordinate remains positive and every originally nonzero pairwise margin retains its sign. This is possible because there are finitely many positive coordinates and finitely many nonzero margins. Set all coordinates outside \(S\) to zero.
The resulting rational allocation has exactly the original pairwise outcomes, including every exact tie. Consequently, every Copeland score is unchanged, and \(p\) remains a winner.
We use this established discrete normalization fact:
In an unweighted manipulation instance with strict complete rankings single-peaked on a supplied axis, if \(p\) can be a Copeland\(_\alpha\) winner, then a successful manipulation exists in which every manipulator ranks \(p\) first.
This is [Yang (2015), Lemma 5](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p77.pdf), specialized to single-peaked width one. Each partition block is then a singleton, so putting the block containing \(p\) first means putting \(p\) first. The paper explicitly states that its results apply to the nonunique-winner model.
To verify its applicability here, take the rational successful allocation from Section 1. Choose a positive integer \(Q\) clearing the denominators of all nonmanipulator and strategic masses. Replace each ranking of mass \(w\) by \(Qw\) unweighted voters.
This produces a finite unweighted instance on the same supplied axis. Every ranking remains strict, complete, and single-peaked. Scaling multiplies all pairwise margins by \(Q\), preserving wins, losses, ties, and Copeland winners.
Apply the discrete normalization fact to this instance. Divide the resulting strategic voter counts by \(Q\). We obtain a successful allocation of total mass \(\beta\) in which every strategic ranking has peak \(p\).
The expansion is only an existence argument; the algorithm below never performs it.
Consider any profile of total mass \(T>0\), and put \(H=T/2\). Define the contribution of the contest against \(b\) to \(a\)'s score by
\(F(a,b)=1\) if \(N(a,b)>H\), \(F(a,b)=\alpha\) if \(N(a,b)=H\), and \(F(a,b)=0\) if \(N(a,b)<H\).
Thus \(\operatorname{score}(a)=\sum_{b\ne a}F(a,b)\). Because \(0\leq\alpha<1\), \(F(a,b)\) is a nondecreasing function of \(N(a,b)\).
We repeatedly use the following consequence of single-peakedness: for axis positions \(a<_A b<_A c\),
\(c\succ a\ \Longrightarrow\ b\succ a,\qquad a\succ c\ \Longrightarrow\ b\succ c.\)
Indeed, either failed implication would put the middle candidate below both endpoints, contradicting single-peakedness.
Let \(U\) be the total mass whose peaks lie strictly left of \(p\), and \(V\) the total mass whose peaks lie strictly right of \(p\).
Suppose \(U>H\), and let \(a\) be the immediate axis neighbor left of \(p\). Every voter with a peak left of \(p\) prefers \(a\) to \(p\) and to every candidate right of \(p\). Hence \(a\) strictly beats all these candidates.
For every candidate \(c<_A a\), single-peakedness gives
\(p\succ c\ \Longrightarrow\ a\succ c,\)
so \(N(a,c)\geq N(p,c)\), and therefore \(F(a,c)\geq F(p,c)\).
For every \(c>_A p\), we have \(F(a,c)=1\geq F(p,c)\). There is no candidate between \(a\) and \(p\). Finally, \(F(a,p)=1\) and \(F(p,a)=0\). Thus
\(\operatorname{score}(a)-\operatorname{score}(p)=1+\sum_{c\notin\{a,p\}}\bigl(F(a,c)-F(p,c)\bigr)\geq1.\)
Consequently, \(p\) is not a winner. The proof for \(V>H\) is symmetric.
The mass with peaks at or right of \(p\) is \(T-U>H\). All those voters prefer \(p\) to every candidate left of \(p\). Therefore \(p\) strictly beats every such candidate.
Fix \(a<_A p\). For every other candidate \(c<_A p\), \(F(p,c)=1\geq F(a,c)\). For every \(c>_A p\), single-peakedness gives
\(a\succ c\ \Longrightarrow\ p\succ c,\)
and hence \(F(p,c)\geq F(a,c)\). The mutual contest contributes \(1\) to \(p\) and \(0\) to \(a\). Therefore
\(\operatorname{score}(p)-\operatorname{score}(a)\geq1.\)
Symmetrically, if \(V<H\), then \(p\) strictly outscores every candidate right of \(p\).
Assume \(\beta>0\), and take a successful allocation in which every strategic ranking has peak \(p\), as provided by Section 2.
Let \(Z\) be the total mass with peak \(p\). Then
\(T=1+\beta=U+V+Z,\qquad Z\geq\beta>0.\)
The values \(U,V,Z\) do not depend on how strategic rankings interleave the two sides of \(p\).
Claim 1 implies \(U\leq H\) and \(V\leq H\). Since \(Z>0\), these two inequalities cannot both be equalities.
There are exactly three cases.
Claim 2 and its symmetric version show that \(p\) strictly outscores every other candidate in every profile having these peak masses. In particular, both unanimous allocations, to \(r_L\) and to \(r_R\), succeed.
Replace the entire strategic allocation by mass \(\beta\) on \(r_L\).
Every strategic ranking before and after replacement puts \(p\) first. Thus all pairwise contests involving \(p\), and \(p\)'s score, remain unchanged.
A ranking with peak \(p\) necessarily orders each side from nearest to farthest. Consequently, comparisons within either side also remain unchanged.
For a left candidate \(a\) and a right candidate \(b\), the replacement ranks \(a\) above \(b\) throughout the strategic bloc. Therefore
\(N_{\mathrm{new}}(b,a)\leq N_{\mathrm{old}}(b,a).\)
All other contests of \(b\) remain unchanged, so every right candidate's score weakly decreases. Since the original allocation succeeded, no right candidate overtakes \(p\).
Left candidates may gain score, but the new profile still has \(U<H\). Claim 2 therefore guarantees that \(p\) strictly outscores every left candidate.
Thus the unanimous allocation to \(r_L\) succeeds.
The symmetric argument shows that the unanimous allocation to \(r_R\) succeeds.
These cases prove the claimed reduction to two rankings. If \(\beta=0\), both proposed allocations simply reproduce the original society, so the equivalence remains valid. If \(m=1\), success is automatic.
Compute the nonmanipulator pairwise margins. For each of \(r_L,r_R\), add the pairwise contribution of strategic mass \(\beta\), compute every Copeland score, and test whether \(p\) has maximum score. Return “yes” exactly when at least one test succeeds.
The preceding proof establishes both directions of correctness: every accepted test supplies a valid allocation, and every successful allocation implies that one of the tests succeeds.
For exact arithmetic, let \(D\) be the product of the input denominators of \(w_1,\ldots,w_\tau,\beta\). Then \(D\), every scaled mass, and every scaled pairwise margin have \(O(L)\) bits. Pairwise ties are tested by exact integer equality.
Write the fixed rational parameter as \(\alpha=a_0/b_0\). Compare scores using the integers
\(b_0\cdot(\text{number of wins})+a_0\cdot(\text{number of ties}).\)
Precomputing ranking positions and accumulating pairwise margins requires \(O(\tau m^2)\) arithmetic operations. Testing the two strategic rankings requires another \(O(m^2)\). Including denominator conversion, the total is \(O((\tau+1)m^2)\) arithmetic operations on integers of \(O(L)\) bits.
Using elementary integer arithmetic gives the conservative bit bound \(O((\tau+1)m^2L^2)\). The algorithm depends on the supplied support size \(\tau\); it never enumerates all single-peaked rankings or expands binary masses into individual voters.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. The argument establishes the reduction to two unanimous allocations and the stated polynomial running time. I found no major or minor mathematical issues.
Both \(r_L\) and \(r_R\) rank \(p\) first and order the candidates on each side of \(p\) from nearest to farthest along the axis. Their ordering of the two sides is therefore compatible with single-peakedness.
Omitting empty blocks correctly handles targets at either endpoint. When \(m=1\), both rankings consist solely of \(p\).
Section 1 is correct.
Setting the remaining coordinates to zero therefore preserves feasibility, total strategic mass, and every pairwise outcome. Copeland scores depend only on those outcomes, so success is preserved.
This is an existence argument; no bound on the rationalized allocation’s denominator or support size is required for the proposed algorithm.
The citation is accurate. Yang’s Lemma 5 asserts the top-block normalization used here. The paper’s problem definition requires manipulative votes to respect the supplied single-peaked partition, and its Section 2 remark explicitly includes the nonunique-winner model. See [Yang (2015), Lemma 5 and Section 2](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p77.pdf).
The specialization and scaling argument satisfy the relevant hypotheses:
The possible size of the expanded election does not compromise the running-time claim: the algorithm never constructs it.
The definition of \(F\) is correct because strict complete rankings imply \(N(a,b)+N(b,a)=T\). Thus the comparison with \(H=T/2\) exactly distinguishes wins, ties, and losses.
For the specified range \(0\leq\alpha<1\), the successive values \(0,\alpha,1\) are nondecreasing. Every inference from a pairwise-mass inequality to an \(F\)-inequality is therefore valid, including when \(\alpha=0\).
The two stated implications of single-peakedness are also correct. Failure of either implication would place the middle candidate below both endpoints.
Claim 1 is valid. If \(U>H\), a candidate left of \(p\) exists, so the immediate left neighbor \(a\) is defined. Every voter with a peak left of \(p\) prefers \(a\) to \(p\) and to every candidate right of \(p\); these contests are therefore strict wins for \(a\).
For candidates left of \(a\), the stated preference implication gives \(N(a,c)\geq N(p,c)\). The immediate-neighbor choice leaves no unexamined candidates between \(a\) and \(p\). The displayed score-difference identity correctly includes the mutual contest as \(1-0=1\), and all other summands are nonnegative. Hence \(a\) strictly outscores \(p\). The right-side argument is symmetric.
Claim 2 is valid. If \(U<H\), the mass with peaks at or right of \(p\) exceeds \(H\), and all that mass prefers \(p\) to every left candidate. Thus \(p\) strictly beats each such candidate.
For comparison with a fixed left candidate \(a\), all other left-side contests contribute at least as much to \(p\), and the stated implication handles every right-side contest. The mutual contest contributes an advantage of one. These comparisons exhaust the candidate set and establish the claimed strict score advantage.
Neither claim assumes integral or rational masses.
Section 4 correctly treats the normalized allocation when \(\beta>0\).
The identities \(T=U+V+Z\) and \(Z\geq\beta>0\) are valid. Normalized strategic votes all have peak \(p\), so changing their interleavings leaves \(U,V,Z\) unchanged.
Claim 1 forces \(U,V\leq H\). Both cannot equal \(H\), since that would force \(Z=0\). The three listed cases are therefore exhaustive.
The argument allows exact pairwise ties and co-winners throughout. It establishes precisely the winner condition requested in the task.
The separate treatments of \(\beta=0\) and \(m=1\) are sufficient. Both directions of the two-ranking equivalence follow.
The algorithm tests two feasible allocations, so an affirmative answer always supplies a valid witness. The preceding equivalence establishes completeness.
The arithmetic and bit bounds are justified:
Elementary arithmetic on these integers supports the conservative bound \(O((\tau+1)m^2L^2)\) bit operations.
The complexity depends on the input support size \(\tau\), and neither the algorithm nor its running-time bound enumerates all admissible ranking types.
No additional mathematical clarification is needed.
⟨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.