Answer: \(\mathrm{NP}\)-complete for both the unique-winner and nonunique-winner models, for every fixed rational \(0\leq\alpha<1\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe constructive control problems by adding or deleting votes for Copelandα for every 0 ≤α < 1 are NP-complete when restricted to elections with single-peaked width 2, for both unique-winner model and nonunique-winner model.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(0\leq\alpha<1\), given candidates \(C\), target \(p\), a valid supplied single-peaked partition \(P\) of width at most \(2\), and binary-rational registered and eligible masses \(\rho_r,\sigma_r\) for supported rankings \(r\), with total mass \(1\), is there a choice of \(x_r\in[0,\sigma_r]\) with \(\sum_r x_r\leq\beta\) such that \(p\) wins after adding the selected mass? For the resulting mass \(w_r=\rho_r+x_r\), pairwise support is \(M(a,b)=\sum_{r:a\succ_r b}w_r\), and \(\mathrm{Copeland}_\alpha(a)=|\{b:M(a,b)>M(b,a)\}|+\alpha|\{b:M(a,b)=M(b,a)\}|\); the input specifies unique-winner or nonunique-winner.
Fix a rational \(\alpha\) with \(0\leq\alpha<1\). Candidates form a nonempty set \(C\), with \(m=|C|\) and target \(p\in C\); types are strict linear rankings of \(C\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here the list is the union of registered and eligible supports: each ranking \(r\) has nonnegative binary-rational masses \(\rho_r,\sigma_r\), with \(\rho_r+\sigma_r>0\) and \(\sum_r(\rho_r+\sigma_r)=1\). Thus \(\tau\) is the support size, not the number of possible rankings.
The input supplies an ordered partition \(P=(C_1,\ldots,C_q)\) into nonempty blocks of size at most \(2\). Every block is contiguous in every supported ranking, and contracting each block to one alternative gives rankings single-peaked on the supplied axis \(C_1,\ldots,C_q\).
Given a nonnegative binary-rational budget \(\beta\), eligible mass may be divided: choose real \(x_r\in[0,\sigma_r]\) with \(\sum_r x_r\leq\beta\), leaving registered mass fixed and setting \(w_r=\rho_r+x_r\).
Define \(M(a,b)=\sum_{r:a\succ_r b}w_r\) and \(s_\alpha(a)=|\{b\in C\setminus\{a\}:M(a,b)>M(b,a)\}|+\alpha|\{b\in C\setminus\{a\}:M(a,b)=M(b,a)\}|\).
The input selects the unique-winner condition \(s_\alpha(p)>s_\alpha(a)\) for every \(a\neq p\), or the nonunique-winner condition \(s_\alpha(p)\geq s_\alpha(a)\) for every \(a\neq p\); no tie-breaking is applied. Let \(L\) be the total binary input length, including the budget.
For each fixed \(\alpha\), is deciding whether such an addition makes \(p\) win in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it NP-hard, for each of the two winner models?
Discrete constructive control by adding votes under \(\mathrm{Copeland}_\alpha\) is NP-complete at single-peaked width \(2\), for both winner models. [Yang–Guo](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p629.pdf)
Fractional Copeland profiles and unrestricted vote addition have been studied in an analysis of influence likelihoods. [Xia](https://minbiaohan.github.io/LSA/papers/LSA-2022_paper_3.pdf) No complexity classification for exactly the bounded eligible-mass problem above was located.
For every fixed rational \(\alpha\) with \(0\leq\alpha<1\), the decision problem is \(\mathrm{NP}\)-complete for both the unique-winner and nonunique-winner models.
The key is an integrality gadget: adding any positive mass of a certain type gives one block an additional strict pairwise win. That block then prevents \(p\) from winning unless its internal contest is tied; the tie equation forces the added mass to equal its full capacity.
For distinct candidates \(a,b\), write their pairwise margin as
\(\Delta_{ab}(x)=M(a,b)-M(b,a)\).
This is an affine function of the addition variables, with rational coefficients of polynomial encoding length.
Suppose a real feasible addition makes \(p\) win. Fix the resulting sign of every pairwise margin. Consider the following rational linear program, with variables \(x_r\) and \(\varepsilon\):
Maximize \(\varepsilon\). The original addition gives a feasible point with \(\varepsilon>0\): take the minimum of \(1\) and the finitely many nonzero absolute margins. If every margin is zero, take \(\varepsilon=1\).
The feasible polytope is compact, so the positive optimum is attained at a vertex. After clearing denominators, its defining coefficients have polynomial bit length. Cramer’s rule and the determinant bound imply that every coordinate of this vertex has polynomial bit length. Thus there is a polynomial-size rational addition preserving all pairwise outcomes.
A verifier checks its capacities, budget, pairwise margins, and Copeland scores using exact rational arithmetic. This establishes membership in \(\mathrm{NP}\) for both models.
We reduce from Exact Cover by 3-Sets, the \(\mathrm{NP}\)-complete source problem also used by [Yang–Guo](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p629.pdf).
Let the universe be \(U=\{u_1,\ldots,u_k\}\), where \(k=3t\), and let the available triples be \(S_1,\ldots,S_n\). We may restrict to \(t,n\geq1\).
Initially describe masses without normalization; normalization follows below.
Introduce the following blocks:
Supply the block axis
\(\bigl(H_n,\ldots,H_1,A,V_1,\ldots,V_n,E_1,\ldots,E_k,B,Z,G_{n+1},G_n,\ldots,G_1\bigr)\).
Call the consecutive blocks from \(A\) through \(Z\) the *middle blocks*.
Define a left ranking of blocks by
\(T_{\mathrm L}: A\succ H_1\succ V_1\succ H_2\succ V_2\succ\cdots\succ H_n\succ V_n\succ E_1\succ\cdots\succ E_k\succ B\succ Z\succ G_{n+1}\succ\cdots\succ G_1.\)
For each \(j\), let \(T_j\) be obtained from \(T_{\mathrm L}\) by swapping the adjacent blocks \(H_j,V_j\).
Define the right ranking by
\(T_{\mathrm R}: Z\succ B\succ E_k\succ\cdots\succ E_1\succ G_{n+1}\succ V_n\succ G_n\succ V_{n-1}\succ G_{n-1}\succ\cdots\succ V_1\succ G_1\succ A\succ H_1\succ\cdots\succ H_n.\)
These are strict rankings of the blocks. Expand each block contiguously, using the internal orders specified next.
There are two registered types, each of mass \(1\):
Both rank \(v_j^-\succ v_j^+\) in every variable block and \(e_i^-\succ e_i^+\) in every element block.
For each \(j\), introduce an eligible type of capacity \(1\), with contracted ranking \(T_j\). Its internal orders are:
Finally introduce one eligible type of capacity \(t\), with contracted ranking \(T_{\mathrm R}\), ranking the \(+\) candidate first in every variable and element block.
In the unique-winner construction, every type ranks \(p\succ p'\).
The unnormalized budget is \(2t\).
The total registered-plus-eligible mass is \(D=2+n+t\). Divide every mass, capacity, and the budget by \(D\).
This gives exactly the normalization required in the question. All numbers have polynomial binary encoding length. There are \(n+3\) supported types and \(O(n+t)\) candidates, so the construction has polynomial size.
Multiplying every final mass by \(D>0\) preserves all pairwise outcomes. We therefore analyze the unnormalized masses.
Every block has size at most \(2\), and expansion makes every block contiguous in every supported ranking.
For a strict block ranking with a specified peak, single-peakedness follows when the blocks on each side of the peak occur in order of increasing distance from it: the ranking may interleave the two sides, but must preserve each side’s order.
For \(T_{\mathrm L}\), the peak is \(A\). Its left-side subsequence is \(H_1,\ldots,H_n\), and its right-side subsequence is
\(V_1,\ldots,V_n,E_1,\ldots,E_k,B,Z,G_{n+1},\ldots,G_1\).
Both have the required order. Swapping \(H_j,V_j\) interchanges blocks from opposite sides of \(A\), preserving each side’s subsequence. Thus every \(T_j\) is also single-peaked with peak \(A\).
For \(T_{\mathrm R}\), the peak is \(Z\). Its left-side subsequence is
\(B,E_k,\ldots,E_1,V_n,\ldots,V_1,A,H_1,\ldots,H_n\),
and its right-side subsequence is \(G_{n+1},\ldots,G_1\). Again both have the required order.
Hence the supplied partition satisfies every promise in the task.
Let \(z_j\in[0,1]\) be the mass added from eligible type \(T_j\), and let \(y\in[0,t]\) be the added mass of the right eligible type. Put \(S=\sum_{j=1}^n z_j\).
The total mass of types with peak \(A\) is \(1+S\); the total mass of types with peak \(Z\) is \(1+y\).
If \(S>y\), more than half the final mass ranks \(a\) first. Consequently \(a\) strictly defeats every other candidate. Its score is \(m-1\), whereas each other candidate loses to \(a\) and has score at most \(m-2\). Thus \(p\) cannot win.
If \(y>S\), the same argument makes \(z\) the unique winner.
Therefore every successful addition satisfies
\(y=S.\)
Under this equality, the left and right masses are equal. Every left type orders the middle blocks as
\(A\succ V_1\succ\cdots\succ V_n\succ E_1\succ\cdots\succ E_k\succ B\succ Z\),
while every right type orders them in reverse. Thus candidates in distinct middle blocks always tie.
Assume \(y=S\). For a middle block \(Q\), let \(d(Q)\) count the outside candidates that a candidate in \(Q\) strictly defeats. Contiguity makes this count independent of the candidate chosen in \(Q\).
Every right type ranks every middle block above every \(H_j\). Since the right mass is half the total, a middle block strictly defeats \(h_j\) precisely when some positive-mass left type ranks that block above \(H_j\); otherwise they tie.
Likewise, every left type ranks every middle block above every \(G_j\). The two right types have the same contracted ranking, and the registered right type has positive mass. Hence a middle block strictly defeats \(g_j\) precisely when \(T_{\mathrm R}\) ranks that block above \(G_j\).
The resulting counts are:
| Middle block \(Q\) | Strict wins against the \(H\) candidates | Strict wins against the \(G\) candidates | \(d(Q)\) |
|---|---|---|---|
| \(A\) | \(n\) | \(0\) | \(n\) |
| \(V_j\) | \(n-j+\mathbf 1_{\{z_j>0\}}\) | \(j\) | \(n+\mathbf 1_{\{z_j>0\}}\) |
| \(E_i\) | \(0\) | \(n+1\) | \(n+1\) |
| \(B\) | \(0\) | \(n+1\) | \(n+1\) |
| \(Z\) | \(0\) | \(n+1\) | \(n+1\) |
Here \(\mathbf 1_{\{z_j>0\}}\) equals \(1\) when \(z_j>0\), and \(0\) otherwise.
To verify the only variable-dependent entry, \(T_{\mathrm L}\) ranks \(V_j\) above exactly \(H_{j+1},\ldots,H_n\). Among all eligible left rankings, only \(T_j\) changes a comparison involving \(V_j\) and an \(H\) block: it places \(V_j\) above \(H_j\). This produces one additional strict win exactly when \(z_j>0\).
All remaining comparisons of a middle candidate with outside candidates are ties, rather than losses.
Define the common baseline \(K=\alpha(m-1)\).
A singleton middle block with external count \(d\) has score
\(K+(1-\alpha)d.\)
For a two-candidate middle block with external count \(d\):
Indeed, the decisive internal winner scores \(1\) internally, defeats \(d\) outside candidates, and ties its remaining \(m-2-d\) opponents. Its score is
\(1+d+\alpha(m-2-d)=K+(1-\alpha)(d+1).\)
The internal loser scores exactly \(1\) less than the internal winner.
The two registered masses contribute \(-2\) to the margin of \(v_j^+\) against \(v_j^-\). Eligible left types contribute \(2z_j-S\), and the right eligible type contributes \(y\). Therefore, using \(y=S\),
\(\Delta(v_j^+,v_j^-)=-2+2z_j-S+y=2(z_j-1).\)
Thus \(V_j\) is internally tied exactly when \(z_j=1\). It is decisive whenever \(0\leq z_j<1\).
Let \(c_i=\sum_{j:u_i\in S_j}z_j\). The same calculation gives
\(\Delta(e_i^+,e_i^-)=-2+2c_i-S+y=2(c_i-1).\)
Thus \(E_i\) is internally tied exactly when \(c_i=1\).
For the nonunique-winner construction, \(B\) is a singleton, so
\(s_\alpha(p)=K+(1-\alpha)(n+1).\)
For the unique-winner construction, \(p\) strictly defeats \(p'\), so
\(s_\alpha(p)=K+(1-\alpha)(n+2).\)
Since \(\alpha<1\), we have \(1-\alpha>0\).
Suppose \(0<z_j<1\). Then \(V_j\) has external count \(n+1\) and a decisive internal contest. Its internal winner has score
\(K+(1-\alpha)(n+2).\)
This exceeds \(p\)’s score in the nonunique-winner construction and equals \(p\)’s score in the unique-winner construction. Both outcomes prevent the requested kind of victory.
Consequently, every successful addition satisfies
\(z_j\in\{0,1\}\qquad\text{for every }j.\)
Next, every element block has external count \(n+1\). If \(c_i\neq1\), its internal contest is decisive, and its internal winner again has score \(K+(1-\alpha)(n+2)\). Hence every successful addition also satisfies
\(\sum_{j:u_i\in S_j}z_j=1\qquad\text{for every }i.\)
These equations, together with integrality, say that the triples with \(z_j=1\) cover every element exactly once. Summing the equations over the \(3t\) elements gives
\(3\sum_{j=1}^n z_j=3t,\)
because each triple contains three elements. Thus exactly \(t\) triples are selected, forming an exact cover.
This proves that a successful addition implies a yes-instance of Exact Cover by 3-Sets.
Conversely, suppose an exact cover exists. Set \(z_j=1\) for its triples and \(z_j=0\) for all other triples, and set \(y=t\).
Then \(S=y=t\). All capacities are respected, and the added mass is \(S+y=2t\), exactly the budget.
Every element block is internally tied. A selected variable block is internally tied and has external count \(n+1\). An unselected variable block is decisive and has external count \(n\). Consequently, every candidate in a variable or element block has score at most
\(K+(1-\alpha)(n+1).\)
The singleton endpoints \(A,Z\) have scores \(K+(1-\alpha)n\) and \(K+(1-\alpha)(n+1)\), respectively.
It remains to check the outside candidates:
For any candidate with \(w\) strict wins and \(\ell\) strict losses, its score is
\(K+(1-\alpha)w-\alpha\ell.\)
Thus every outside candidate has score at most \(K+(1-\alpha)n\), which is strictly below \(p\)’s score in both constructions.
In the nonunique-winner construction, all opponents therefore have score at most \(p\)’s score. In the unique-winner construction, all candidates outside \(B\) have strictly smaller scores than \(p\); its twin \(p'\) scores exactly \(1\) less than \(p\).
Hence the exact cover produces the required victory in each model.
The construction is a polynomial-time reduction satisfying the supplied width-two partition, contiguous blocks, explicit support representation, bounded divisible eligible masses, and normalization. It works for every fixed rational \(0\leq\alpha<1\).
Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness for both winner models.
⟨structured verdict parsed — rendered above⟩
The reduction is correct in substance and establishes \(\mathrm{NP}\)-completeness for both winner models, for every fixed rational \(\alpha\) satisfying \(0\leq\alpha<1\). I found no false step or substantive gap. There is one minor omission: the certificate-size argument invokes a determinant bound without stating it precisely.
Each pairwise margin is an affine rational function of the addition variables. Its coefficients and constant term have polynomial encoding length: summing the input rationals does not require more than polynomially many bits.
Fixing the signs of all margins also fixes every Copeland score and hence preserves either winner condition. The proposed linear program correctly represents that sign pattern using equalities for ties and a common positive separation variable for strict comparisons.
A successful real addition supplies a feasible point with positive \(\varepsilon\). There are finitely many margins, so the minimum of their nonzero absolute values is positive. If there are no nonzero margins, the stated choice \(\varepsilon=1\) works. This also covers the case \(m=1\), where there are no pairwise comparisons.
All variables are bounded, and the constraints are closed. Thus the feasible region is a nonempty compact rational polytope. A linear objective has an optimal vertex, and its optimum here is positive. Consequently, the vertex preserves every prescribed sign.
The application of rational vertex bounds is valid: the dimension is \(\tau+1\), the number of constraints is polynomial, and clearing denominators gives coefficients of polynomial bit length. Lower-dimensional feasible regions do not invalidate the vertex argument.
Minor issue: “Cramer’s rule and the determinant bound” does not state the quantitative bound being invoked. Under the requested standard of precise theorem statements, this justification should be made explicit. The omission is routine and does not require new mathematics.
Minimum clarification: State the determinant bit-length bound used, explain that a vertex is determined by a full-rank selection of tight constraints, and apply the bound to dimension \(\tau+1\) and the coefficient bit length after clearing denominators.
Exact rational verification of capacities, budget, margins, and scores is polynomial-time. Since \(\alpha\) is fixed and rational, its use in score comparisons causes no additional certificate problem.
The source is standard Exact Cover by 3-Sets: an explicitly given universe of size \(3t\) and a collection of three-element subsets. The cited [Yang–Guo paper](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p629.pdf) states this source problem and uses it for its hardness reductions.
Restricting to \(t,n\geq1\) excludes only trivial source cases and does not affect hardness.
Every candidate belongs to exactly one supplied block. The two constructions differ only in whether the target block contains the twin \(p'\). Every block has size at most two.
The registered and eligible rankings specify complete strict orders. The eligible left types are distinct because their contracted rankings perform different swaps. The registered and eligible right types are distinct because their internal orders differ. Thus the asserted support size \(n+3\) is correct.
The total unnormalized registered-plus-eligible mass is
\[
\]
\(D=2+n+t\).
Dividing all masses, capacities, and the budget by this positive number produces exactly the required normalization. Every supported type retains positive total supplied mass.
The number of candidates, number of supported rankings, and binary lengths of all constructed rationals are polynomial in the explicit source input size. Scaling by \(D\) preserves the signs and zeros of every pairwise margin, so the subsequent unnormalized analysis is valid.
Expanding blocks contiguously directly satisfies the contiguity requirement.
For \(T_{\mathrm L}\), the blocks on the left of peak \(A\) occur in the required nearest-to-farthest order, as do the blocks on its right. Each swap forming \(T_j\) exchanges adjacent blocks on opposite sides of \(A\); it changes neither side’s subsequence and leaves \(A\) first.
For \(T_{\mathrm R}\), the stated left-side and right-side subsequences likewise match the supplied axis outward from \(Z\).
The criterion used is appropriate for strict single-peaked rankings: each side must preserve its outward order, while the two sides may interleave. All supported contracted rankings satisfy it.
Every left type ranks the singleton candidate \(a\) first, and every right type ranks the singleton candidate \(z\) first.
If \(S>y\), the mass ranking \(a\) first exceeds half the final mass. Therefore \(a\) strictly defeats every opponent and has score \(m-1\). Every other candidate loses to \(a\) and has score at most \(m-2\), since each remaining comparison contributes at most one. This excludes \(p\) in both winner models.
The argument for \(y>S\) is identical with candidate \(z\). Hence success necessarily implies \(S=y\).
Under this equality, the left and right masses are equal. Their orders on the middle blocks are exact reversals, so every comparison between distinct middle blocks ties. Internal block orders do not affect these comparisons.
Against any \(H\) candidate, the entire right half supports the middle candidate. A strict win therefore occurs exactly when some positive left mass also supports it; otherwise the comparison ties.
Against any \(G\) candidate, the entire left half supports the middle candidate. Both right types have the same contracted ranking, and the registered right type has positive mass. Thus strictness depends exactly on the stated comparison in \(T_{\mathrm R}\).
The table checks out:
The adjacent swap defining \(T_j\) changes precisely the relevant \(H_j,V_j\) comparison. No middle candidate loses to an outside candidate.
With \(K=\alpha(m-1)\), a singleton middle candidate having \(d\) external wins has score \(K+(1-\alpha)d\).
In a two-candidate middle block, an internal tie gives the same expression. A decisive internal winner has score
\(1+d+\alpha(m-2-d)=K+(1-\alpha)(d+1)\).
The internal loser has identical external outcomes and loses the internal comparison, so its score is exactly one smaller.
The variable-margin contributions are correctly counted:
\(\Delta(v_j^+,v_j^-)=-2+2z_j-S+y=2(z_j-1)\).
Since \(0\leq z_j\leq1\), this contest ties exactly at full capacity.
The element calculation is also correct:
\(\Delta(e_i^+,e_i^-)=-2+2c_i-S+y=2(c_i-1)\).
It ties exactly when \(c_i=1\), including the possibility that \(c_i>1\) otherwise makes the opposite internal candidate win.
The target scores follow from the external count \(n+1\). In the unique-winner construction, all types rank \(p\) above \(p'\), and the registered mass is positive, so their internal comparison is strictly decisive.
If \(0<z_j<1\), the variable block combines external count \(n+1\) with a decisive internal contest. Its winner’s score exceeds the nonunique-model target score and equals the unique-model target score. Both prevent the required victory.
Hence every successful addition has \(z_j\in\{0,1\}\).
Likewise, any \(c_i\neq1\) gives an element-block winner with the same blocking score. Thus success forces every coverage equation \(c_i=1\).
These equations and integrality state exactly that the selected triples cover every element once. Summing the equations counts each selected triple three times, giving \(3S=3t\), hence \(S=t\). The selected triples therefore form an exact cover.
Selecting its \(t\) left types at full capacity and setting \(y=t\) respects every capacity and uses precisely budget \(2t\).
All element blocks and selected variable blocks tie internally. Unselected variable blocks are decisive but have one fewer external win. The resulting upper bound on all variable and element candidates is therefore the stated \(K+(1-\alpha)(n+1)\). The endpoint scores also agree with the table.
The outside-candidate check is sufficient:
The general formula \(K+(1-\alpha)w-\alpha\ell\) correctly accounts for wins, losses, and ties. Since \(\alpha\geq0\), the asserted outside score bound follows.
In the nonunique model, no opponent exceeds \(p\). In the unique model, all candidates outside the target block score strictly less than \(p\), while \(p'\) scores exactly one less.
Every required strict score separation uses \(1-\alpha>0\), which holds throughout the stated range, including \(\alpha=0\). The proof makes no unsupported extension to \(\alpha=1\).
The reduction directly handles divisible eligible masses; it does not merely transfer hardness from the discrete problem. Both directions of the reduction are established, and the rational-certificate argument supplies membership in \(\mathrm{NP}\).
⟨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.