Answer: Polynomial-time solvable for every fixed \(Y\in\{\mathrm{cup},\mathrm{Copeland},\mathrm{maximin},\mathrm{Bucklin}\}\) with \(m=3\).
Proposition 13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing a manipulation of plurality + Y where Y ∈{cup, Copeland, maximin, Bucklin}, is NP-complete with weighted votes and 3 candidates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For three candidates \(a,b,c\), choose \(Y\in\{\text{cup},\text{Copeland},\text{maximin},\text{Bucklin}\}\). Given rational nonmanipulator masses \(\nu_{w,r}\) by weight \(w\) and ranking \(r\), and rational manipulator mass \(\kappa_w\) by weight, does there exist an allocation \(x_{w,r}\geq 0\) with \(\sum_r x_{w,r}=\kappa_w\) for every \(w\), such that \(c\) wins under \(\text{plurality}+Y\)? Evaluate weighted tallies using effective mass \(w(\nu_{w,r}+x_{w,r})\); use the paper’s tie-breaking in favor of \(c\), and include the agenda as input when \(Y\) is cup.
Let \(C=\{a,b,c\}\), \(m=3\), and fix \(Y\in\{\mathrm{cup},\mathrm{Copeland},\mathrm{maximin},\mathrm{Bucklin}\}\). Rankings \(r\) are strict total orders on \(C\), and weights \(w\) are positive binary integers.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Types are tagged nonmanipulator types \((w,r)\), with masses \(\nu_{w,r}\), or manipulator types \(w\), with masses \(\kappa_w\); omitted masses are zero. Thus \(\tau\) is the support size, not the number of possible types.
Masses are nonnegative and need not sum to \(1\); require \(W=\sum_{w,r}w\nu_{w,r}+\sum_w w\kappa_w>0\). Let \(L\) be the total binary input length; measure running times in \(m,\tau,L\).
Manipulators may allocate real masses \(x_{w,r}\geq0\) among all rankings, subject to \(\sum_r x_{w,r}=\kappa_w\) for every weight. Evaluate every tally using effective mass \(w(\nu_{w,r}+x_{w,r})\).
Use standard plurality and maximin. Copeland counts strict pairwise-majority victories only, assigning zero points for a tied contest. Simplified Bucklin minimizes the first rank depth at which a candidate's cumulative approval mass is strictly greater than \(W/2\), with no further comparison of approval totals.
For cup, the input supplies a binary agenda whose leaves contain each candidate exactly once. The input also supplies one strict tie priority with \(c\) first; use it for tied rule scores, cup contests, and runoffs.
The combination \(\mathrm{plurality}+Y\) selects each base rule's single winner on the same completed society. If they coincide, that candidate wins; otherwise their pairwise-majority runoff on the same society determines the winner.
For each fixed \(Y\in\{\mathrm{cup},\mathrm{Copeland},\mathrm{maximin},\mathrm{Bucklin}\}\), is deciding whether some feasible mass allocation makes \(c\) win under \(\mathrm{plurality}+Y\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Discrete weighted coalitional manipulation for each of these four combinations is \(\mathrm{NP}\)-complete with three candidates and favorable tie-breaking. [Source](https://cgi.cse.unsw.edu.au/~tw/nwxecai12.pdf)
No result settling this exact divisible-mass problem was located in the literature search.
For every fixed \(Y\in\{\mathrm{cup},\mathrm{Copeland},\mathrm{maximin},\mathrm{Bucklin}\}\), the divisible-mass manipulation problem for \(\mathrm{plurality}+Y\) is in \(\mathrm{P}\).
The proof gives an exact algorithm in the binary input model, including all strict inequalities and ties. Throughout, the number of candidates is fixed at \(m=3\).
Let \(\mathcal R\) be the set of six strict rankings of \(C\). Define the nonmanipulator effective mass of ranking \(r\), and the total manipulator effective mass, by
\(n_r=\sum_w w\nu_{w,r},\qquad K=\sum_w w\kappa_w.\)
For an allocation \(x\), define
\(y_r=\sum_w wx_{w,r}.\)
Every feasible allocation satisfies
\(y_r\geq 0\quad(r\in\mathcal R),\qquad \sum_{r\in\mathcal R}y_r=K.\)
The converse is essential.
Lemma 1. Every vector \(y\) satisfying these constraints is induced by a feasible manipulator allocation.
Proof. If \(K>0\), set, for every manipulator weight type \(w\),
\(x_{w,r}=\kappa_w\,\dfrac{y_r}{K}.\)
These masses are nonnegative, and
\(\sum_r x_{w,r}=\kappa_w\,\dfrac{\sum_r y_r}{K}=\kappa_w.\)
Moreover,
\(\sum_w wx_{w,r}=\dfrac{y_r}{K}\sum_w w\kappa_w=y_r.\)
If \(K=0\), positivity of the weights and nonnegativity of the masses imply that every \(\kappa_w=0\). The simplex constraints then force every \(y_r=0\), realized by the zero allocation. This proves the lemma. \(\square\)
Consequently, the feasible completed profiles are exactly those with effective ranking masses
\(s_r(y)=n_r+y_r,\qquad y\in\Delta_K,\)
where
\(\Delta_K=\{y\in\mathbb R_{\geq 0}^{6}:\sum_r y_r=K\}.\)
Their total effective mass is the fixed rational number
\(W=\sum_r n_r+K>0.\)
Thus the number of manipulation variables is six, independently of the support size and the numerical weights.
Write \(\operatorname{pos}_r(i)\) for candidate \(i\)'s position in ranking \(r\). Define the plurality, pairwise, and cumulative approval tallies by
\(P_i(y)=\sum_{r:\operatorname{pos}_r(i)=1}s_r(y),\)
\(T_{ij}(y)=\sum_{r:i\text{ precedes }j\text{ in }r}s_r(y)\qquad(i\neq j),\)
\(B_{i,k}(y)=\sum_{r:\operatorname{pos}_r(i)\leq k}s_r(y).\)
All these functions are affine with rational coefficients. Strict rankings give
\(T_{ij}(y)+T_{ji}(y)=W,\qquad B_{i,3}(y)=W.\)
We will use the signs of finitely many affine functions. A sign records whether its value is negative, zero, or positive; recording zero separately preserves the specified tie-breaking.
For each unordered candidate pair, include one plurality difference and one pairwise margin:
\(P_i-P_j,\qquad M_{ij}=T_{ij}-T_{ji}.\)
There are three functions of each kind, hence six altogether.
The plurality differences determine the plurality winner, including score ties. The pairwise margins determine every pairwise winner, using the supplied priority when a margin is zero. Therefore they also determine any runoff.
For cup, these pairwise winners determine the winner recursively along the supplied agenda.
For Copeland, they determine every candidate’s score
\(\operatorname{Cop}_i(y)=|\{j\neq i:M_{ij}(y)>0\}|.\)
A zero margin contributes no victory to either candidate. The supplied priority resolves equal Copeland scores.
Thus the six common comparisons suffice for both rules.
The maximin score is
\(\mu_i(y)=\min_{j\neq i}T_{ij}(y).\)
There are six directed pairwise tallies. Add all fifteen differences between distinct entries of this list.
Their signs determine the entire weak ordering of the six tallies. In particular, they identify a minimum tally for each candidate and determine all comparisons between the resulting minimum values. Hence they determine the maximin winner, including ties.
The total number of comparisons is at most \(6+15=21\).
Add the six threshold functions
\(H_{i,k}(y)=2B_{i,k}(y)-W,\qquad i\in C,\quad k\in\{1,2\}.\)
Candidate \(i\)'s Bucklin depth is exactly
\(d_i(y)= \begin{cases} 1,&H_{i,1}(y)>0,\\ 2,&H_{i,1}(y)\leq 0\text{ and }H_{i,2}(y)>0,\\ 3,&H_{i,1}(y)\leq 0\text{ and }H_{i,2}(y)\leq 0. \end{cases}\)
Indeed, these conditions test the required strict threshold at depths one and two. At depth three it is always reached, because \(B_{i,3}=W>W/2\).
Thus the threshold signs determine all depths. Minimizing the depth and applying the supplied priority determines the simplified Bucklin winner, without comparing approval totals.
The total number of comparisons is at most \(6+6=12\).
For the chosen rule, let \(f_1,\ldots,f_H\) be its comparison functions.
| Rule \(Y\) | Bound on \(H\) |
|---|---:|
| \(\mathrm{cup}\) | \(6\) |
| \(\mathrm{Copeland}\) | \(6\) |
| \(\mathrm{maximin}\) | \(21\) |
| \(\mathrm{Bucklin}\) | \(12\) |
Lemma 2. On any nonempty subset of \(\Delta_K\) where every \(f_\ell\) has a fixed sign, the winner of \(\mathrm{plurality}+Y\) is constant.
Proof. The preceding arguments show that the signs determine both base winners. If those winners coincide, the combination selects that candidate. Otherwise, their pairwise margin and the supplied priority determine the runoff winner. Both are already determined by the same signs. \(\square\)
Consider a proposed pattern \(\sigma\in\{-1,0,1\}^{H}\). Its realization requires
\(y\in\Delta_K,\qquad f_\ell(y)>0\text{ if }\sigma_\ell=1,\quad f_\ell(y)=0\text{ if }\sigma_\ell=0,\quad f_\ell(y)<0\text{ if }\sigma_\ell=-1.\)
Strict inequalities must remain strict. To test them exactly, introduce a variable \(\delta\) and impose
\(y\in\Delta_K,\qquad 0\leq\delta\leq 1,\)
together with
\(f_\ell(y)\geq\delta\quad\text{if }\sigma_\ell=1,\)
\(f_\ell(y)=0\quad\text{if }\sigma_\ell=0,\)
\(f_\ell(y)\leq-\delta\quad\text{if }\sigma_\ell=-1.\)
Call this closed rational polytope \(Q_\sigma\).
Lemma 3. The sign pattern is realizable if and only if \(Q_\sigma\) contains a point with \(\delta>0\).
Proof. Such a point immediately satisfies every requested strict sign.
Conversely, suppose \(y\) realizes the pattern. If the pattern contains any nonzero signs, the finite set
\(\{|f_\ell(y)|:\sigma_\ell\neq 0\}\)
consists of positive numbers. Choose \(\delta\) to be the smaller of one and its minimum. Then \(\delta>0\), and all constraints defining \(Q_\sigma\) hold. If every sign is zero, choose \(\delta=1\). \(\square\)
Because \(0\leq y_r\leq K\) and \(0\leq\delta\leq 1\), the polytope is bounded. If it is nonempty, it is compact, so the maximum of \(\delta\) is attained. Therefore the exact test is whether that maximum is strictly positive.
For completeness, we can solve these optimization problems by elementary vertex enumeration rather than relying on numerical linear programming.
Each \(Q_\sigma\) has seven variables and at most \(H+9\) constraint rows: six nonnegativity constraints, the total-mass equality, two bounds on \(\delta\), and \(H\) sign constraints.
Two facts justify enumerating seven-row subsystems, even when the polytope has lower dimension.
First, every nonempty compact polytope has a vertex maximizing \(\delta\). Start with the nonempty compact set of maximizers of \(\delta\), and successively maximize each coordinate over the remaining set. The final set is a singleton, since all coordinates have been fixed. Its point is a vertex of the original polytope: in any nontrivial convex decomposition, both endpoints must first maximize \(\delta\), then each successive coordinate, and hence must equal that point.
Second, at a vertex the equality normals and active inequality normals span the whole seven-dimensional space. Otherwise, choose a nonzero vector orthogonal to all those normals. Moving a sufficiently small positive or negative distance in that direction preserves all equalities and active inequalities. It also preserves every inactive inequality, because each has positive slack and there are only finitely many. The vertex would then be the midpoint of two distinct feasible points, a contradiction.
It follows that every vertex is the unique solution of seven linearly independent constraint rows, with selected inequalities treated as equalities. We can therefore:
If \(Q_\sigma\) is nonempty and its optimum is positive, the maximizing vertex proved above will be found. Conversely, every retained solution with positive \(\delta\) realizes the pattern by Lemma 3.
This procedure uses rational arithmetic only; it does not impose an arbitrary positive tolerance.
Computing the six numbers \(n_r\) and the number \(K\) requires only a scan of the \(\tau\) supported types and exact rational arithmetic. Their binary lengths are polynomial in \(L\): products of input denominators provide common denominators whose binary lengths are bounded by the sum of the input denominator lengths, and the weighted numerators and their sums likewise have polynomial length.
Every comparison function consequently has coefficients of polynomial binary length. Each enumerated equation system has fixed size seven. Exact elimination, constraint verification, and comparison of \(\delta\) with zero therefore take polynomial time in \(L\).
Since \(H\leq 21\), both the number \(3^H\) of sign patterns and the number of seven-row selections per pattern are constants independent of \(\tau\), \(L\), and the numerical values of the weights. Thus the total running time is polynomial in the stipulated input parameters with \(m=3\).
The algorithm is:
Soundness. An accepted pattern has a realizing vector \(y\in\Delta_K\). Lemma 1 lifts it to a feasible allocation. Lemma 2 ensures that this allocation makes \(c\) win.
Completeness. Any successful allocation induces a vector \(y\in\Delta_K\) and one of the enumerated sign patterns. Lemma 3 ensures that the feasibility test accepts that pattern. Its combination winner is \(c\), so the algorithm answers yes.
This proves polynomial-time solvability for all four choices of \(Y\).
The decisive use of divisibility is the lifting formula in Lemma 1. The indivisible manipulation model in [*Combining Voting Rules Together*](https://cgi.cse.unsw.edu.au/~tw/nwxecai12.pdf) does not permit this splitting, so its hardness results do not contradict the conclusion here.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly: for each of the four fixed choices of \(Y\), deciding whether a feasible divisible-mass allocation makes \(c\) win is in \(\mathrm{P}\) when \(m=3\). I found no major or minor mathematical issues.
Every feasible allocation induces nonnegative effective masses \(y_r\) with total \(K\). Conversely, for \(K>0\), the stated formula \(x_{w,r}=\kappa_w y_r/K\) satisfies each weight type’s allocation constraint and reproduces the prescribed effective ranking masses.
The case \(K=0\) is handled correctly: positive weights and nonnegative masses force all manipulator masses to vanish, and the simplex contains only the zero vector. Consequently, aggregation loses no feasible completed profile. It relies on precisely the divisibility allowed by the task.
The plurality, directed pairwise, and cumulative approval tallies use the required effective masses. They are affine functions of the six manipulation variables. Strict rankings justify \(T_{ij}+T_{ji}=W\), and complete rankings justify \(B_{i,3}=W\).
The three plurality differences determine all plurality score comparisons. The three pairwise margins determine all pairwise-majority outcomes, including tied contests through the supplied priority. They therefore suffice for every possible runoff. Choosing one orientation for each unordered pair loses no information: the opposite margin has the opposite sign.
The comparison counts \(6\), \(6\), \(21\), and \(12\) are correct.
The listed signs determine both single base-rule winners. If those winners differ, they also determine the required runoff. Thus Lemma 2 accounts for the entire combination rule, including every specified tie.
A feasible point with \(\delta>0\) satisfies every requested strict sign. Conversely, a realization with any nonzero signs has a positive minimum absolute value among those finitely many comparisons, so the stated choice of \(\delta\) works.
The all-zero pattern is handled explicitly by choosing \(\delta=1\). This remains valid when \(K=0\). The upper bound \(\delta\leq1\) does not exclude any realizable pattern.
The polytope is closed and bounded: nonnegative coordinates summing to \(K\) satisfy \(y_r\leq K\). Hence a nonempty polytope attains its maximum \(\delta\).
The constraint count is \(H+9\): six nonnegativity rows, one total-mass equality, two bounds on \(\delta\), and \(H\) sign rows.
Both geometric facts needed for enumeration are justified in the output:
Therefore every relevant maximizing vertex is captured by some seven-row subsystem of full rank. Checking every original constraint rejects extraneous subsystem solutions. Accepting exactly when a retained point has \(\delta>0\) is sound and complete.
Aggregation has polynomial bit complexity. A product of input denominators has bit length bounded by their total bit length; multiplying by binary weights and summing the weighted numerators also preserves polynomial bit length.
All subsequent systems have seven variables, a constant number of rows, and rational coefficients of polynomial bit length. Exact elimination and constraint checking therefore take polynomial time.
Since \(H\leq21\), both sign-pattern enumeration and row-subsystem enumeration have constant size with respect to the input. These constants can be very large, but that does not invalidate polynomial-time membership. The conclusion is appropriately restricted to the stipulated \(m=3\).
Every accepted pattern yields a feasible allocation through Lemma 1 and a winning completion through Lemma 2. Every successful allocation supplies an enumerated pattern accepted by the exact feasibility procedure. Thus the algorithm decides precisely the requested existence question for all four rules.
The discrete hardness comparison is contextual; the continuous conclusion follows from the self-contained argument and does not depend on that citation.
No repair or 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.